Online bipartite allocation balances prediction accuracy and robustness
Consistency-Robustness Tradeoffs for Online Bipartite Allocation with Multiple Stages
Data Structures and Algorithms
Summary
This work looks at how to match resources to demands that arrive in several steps, even when the predictions about the demands might be wrong. The authors found formulas to balance using these predictions and guarding against bad surprises for any number of steps. They also offer improved methods for cases where demands keep coming one-by-one without a fixed total number. Their approach uses mathematical programs that carefully reserve some resource capacity to handle uncertainty while benefiting from predictions.
What this means in practice
- •For online ad platform engineers: Improve allocation algorithms for sequential ad requests that use predictive models but remain effective despite prediction errors.
- •For cloud resource schedulers: Manage multiple-stage resource assignments under uncertain demand predictions while balancing efficiency and safety.
Authors
Alexander Lindermayr, Nicole Megow, Lauren Paul
Abstract
We study learning-augmented online bipartite allocation with multiple stages. In the $k$-stage vertex-weighted fractional bipartite matching problem, demand vertices arrive in $k$ stages, and the algorithm receives possibly inaccurate predictions of the allocation in each stage. While tight consistency-robustness tradeoffs were known for the two-stage case, no nontrivial tradeoff was known for an arbitrary number of stages. Our main result is the first consistency-robustness tradeoff for $k$-stage vertex-weighted fractional bipartite matching with predictions, for every $k\ge2$. Let $R_k=1-(1-1/k)^k$. For every $R\in[0,R_k]$, our algorithm is $R$-robust and $C_k(R)$-consistent, where $C_k(R)=k(1-R)^{1/k}+R-(k-1)$. This simultaneously recovers the known tight two-stage tradeoff and the optimal prediction-free $k$-stage competitive guarantee $R_k = C_k(R_k)$, while strictly dominating the natural randomized coin-flip baseline between these endpoints. We also present an algorithm for the classical online setting, where demands arrive one by one and the number of demands is unknown in advance. It has a consistency ratio of at least $C_\infty(R)=1+R+\ln(1-R)$ for a given robustness $R\in[0,1-1/e]$, improving the best previously known tradeoff for this problem. Finally, we extend the framework to fractional AdWords and fractional predictions. Our algorithms are based on stage-wise convex programs with carefully calibrated vertex-dependent penalties. The penalties maintain a dynamic safety reserve for each supply vertex, balancing protection against adversarial future arrivals with the ability to exploit the predicted allocation.