TL;DR
This paper introduces the first non-trivial consistency–robustness tradeoffs for multi-stage online bipartite allocation augmented with machine-learned predictions. By utilizing stage-wise convex programming with a dynamic, history-dependent safety reserve, the proposed algorithms smoothly balance worst-case robustness with prediction exploitation, outperforming standard baselines across both finite-stage and classical online settings.
What Problem Does This Paper Address?
Online bipartite matching and allocation are foundational problems in computer science with massive real-world applications, including ad placement (like Google AdWords), ride-hailing, and resource allocation. In the classical online setting, supply vertices (e.g., ad slots) are known in advance, but demand vertices (e.g., user queries) arrive one by one, forcing the algorithm to make irrevocable allocation decisions under total uncertainty about the future.
Recently, researchers have turned to the learning-augmented framework, which leverages potentially inaccurate machine learning predictions to guide these online decisions. The goal is to design algorithms that achieve two competing guarantees:
- Consistency ($C$): A high performance ratio when the predictions are perfectly accurate.
- Robustness ($R$): A worst-case performance ratio even if the predictions are completely wrong.
While tight consistency–robustness tradeoffs were previously established for simple two-stage settings, finding non-trivial tradeoffs for an arbitrary number of stages ($k \ge 3$) or for the classical online setting with an unknown horizon remained an open challenge. This paper fills that gap.
Methods
The authors propose a stage-wise greedy marginal-value algorithm implemented via convex programming. In each non-final stage, assigning a load to a supply vertex is credited not with its full weight, but with a penalized marginal value.
The core innovation lies in how these penalties are calibrated using a dynamic reserve account. A mathematical "safety curve" dictates exactly how much dual protection a supply vertex must retain based on its current accumulated load and the number of remaining stages.
- For non-predicted vertices: The algorithm charges a penalty just high enough to buy local robustness protection against adversarial future arrivals.
- For predicted vertices: The algorithm aggressively spends its accumulated reserve to follow the prediction and make the edge attractive, stopping precisely when it hits the safety curve.
To analyze the performance, the authors use a dual-fitting framework based on the Karush-Kuhn-Tucker (KKT) optimality conditions. Furthermore, to handle complex scenarios where predictions recommend fractional allocations (rather than simple one-to-one matchings), they introduce a virtual advertiser construction that splits resources into stage-indexed virtual copies, restoring the clean structural properties needed for multi-stage matching.
Datasets
Not discussed in the paper. This work is purely theoretical and focuses on proving mathematical performance guarantees rather than evaluating on empirical datasets.
Key Insights and Ideas
- The Safety Curve Invariant: Instead of using static penalties, the algorithm maintains a vertex-specific, history-dependent safety target based on the polynomial $g_m(z) = (1 - \frac{1-z}{m})^m$. This elegantly bridges the gap between multi-stage hedging and real-time prediction tracking.
- Stationary Limit for Online Matching: By taking the limit as the number of stages approaches infinity ($k \to \infty$), the safety curve converges to an exponential function: $g_\infty(z) = \exp(z-1)$. This provides a horizon-independent penalty framework perfectly suited for the classical online setting where the total number of demands is unknown.
- Virtualization of Fractional Advice: Splitting resources into stage-indexed virtual copies allows the multi-stage matching framework to seamlessly generalize to complex fractional AdWords settings without losing structural guarantees.
Key Results
- Multi-Stage Allocation: For any $k$-stage vertex-weighted fractional matching problem, the algorithm achieves a consistency of $C_k(R) = k(1-R)^{1/k} + R - (k-1)$ for a given robustness $R$. This successfully recovers the optimal two-stage tradeoff when $k=2$ and matches the optimal prediction-free competitive ratio $R_k = 1 - (1-1/k)^k$ when predictions are ignored.
- Classical Online Setting: In the standard online setting (unknown horizon), the algorithm achieves a consistency ratio of $C_\infty(R) = 1 + R + \ln(1-R)$, strictly improving upon the previous state-of-the-art tradeoff.
- Dominating the Baseline: As shown in Figure 1, these curves strictly dominate the naive randomized "coin-flip" baseline, which simply interpolates randomly between a purely robust and a purely consistent algorithm.
Limitations and Future Work
- Optimality Gap for $k \ge 3$: While the two-stage tradeoff ($k=2$) is proven to be tight, there remains a mathematical gap between the proposed curve $C_k(R)$ and the known upper bounds for three or more stages. Closing this gap is a major open question.
- Static vs. Adaptive Predictions: The model assumes an "output prediction" that is fixed globally at the start, meaning later recommendations are not re-computed or adapted based on the algorithm's real-time residual capacities.
- Fractional vs. Integral Matching: The proposed algorithms operate in the fractional domain. Extending these exact tradeoffs to integral online matching remains difficult, as standard lossless online rounding techniques do not easily apply to these specific stage-wise convex programs.
Summary updated