Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model

Billy Jin, Will Ma

TL;DR

This paper provides the first tight theoretical characterization of the tradeoff between trusting potentially inaccurate "advice" (consistency) and hedging against worst-case scenarios (robustness) in two-stage online bipartite matching. The authors introduce a novel algorithm using advice-dependent penalty functions that achieves a Pareto-optimal performance curve, significantly outperforming standard randomized baselines in both theory and real-world ride-sharing simulations.

What Problem Does This Paper Address?

In many real-world scenarios—like ride-hailing platforms matching drivers to riders or e-commerce warehouses placing inventory—decisions must be made under significant uncertainty. Traditionally, researchers have tackled this using two extremes:

  1. Stochastic Optimization: Assumes we know the exact probability distribution of future demand. This works great if the model is perfect but fails if the data is biased or shifted.
  2. Adversarial (Robust) Optimization: Assumes the worst possible future. While safe, this is often overly pessimistic and leads to mediocre performance in typical cases.

The authors address the middle ground using the Algorithms with Predictions (ALPS) framework. They focus on a "two-stage" model where demand arrives in two batches. The goal is to use "advice" (like a machine learning prediction of future demand) to improve performance without becoming dangerously vulnerable if that advice is completely wrong.

Methods

The paper defines two key metrics:

  • Consistency ($C$): How well the algorithm performs if the advice is perfectly accurate.
  • Robustness ($R$): The worst-case performance guarantee, even if the advice is maliciously misleading.

For the vertex-weighted matching and Adwords (budgeted allocation) problems, the authors propose a sophisticated algorithm based on advice-dependent penalty functions.

In standard robust matching, you penalize using a resource (like a driver) based on how much it has already been used. The "aha!" moment here is to adjust these penalties based on the advice:

  • If the advice suggests matching a specific node, the algorithm applies a lower penalty to encourage following the prediction.
  • If the advice ignores a node, the algorithm applies a higher penalty to save that resource for a potentially different future.

By tuning a parameter $R$, the algorithm can smoothly transition from "blindly follow advice" to "ignore advice and be robust."

Datasets

The authors validated their theoretical findings using two approaches:

  1. Synthetic Simulations: A model mimicking inventory placement where the algorithm must decide which warehouses to fill before seeing the second stage of demand.
  2. Chicago Ride-Sharing Dataset (2022): Real-world trip data from the City of Chicago. They constructed matching instances by treating ride requests at one time as the first stage and requests 15 minutes later as the second stage, using various methods to generate "advice" (e.g., perturbing the optimal hindsight solution).

Key Insights and Ideas

  • Non-Linear Tradeoffs: For vertex-weighted matching, the optimal tradeoff isn't a simple straight line (which you'd get by just flipping a coin between two strategies). Instead, it follows a specific concave curve defined by the equation $\sqrt{1-R} + \sqrt{1-C} = 1$.
  • ALPS as Regularization: The framework can be viewed as a principled way to "regularize" data-driven decisions. It prevents a model from "overfitting" to a specific predicted future, ensuring it remains balanced enough to handle unexpected demand shifts.
  • Tightness Matters: The authors don't just provide a tradeoff; they prove their curve is the absolute best possible (Pareto-efficient) for this model. As shown in Figure 2, their two-stage specific analysis yields much stronger guarantees than applying general multi-stage results from prior literature.
Comparison of the authors' tight tradeoff curve against various baselines. The solid blue line represents their optimal result for vertex-weighted matching.

Key Results

  • Theoretical Optimality: The paper characterizes the tight $(R, C)$ tradeoff for four settings:
  • Vertex-weighted/Adwords: $\sqrt{1-R} + \sqrt{1-C} = 1$ (for $R \in [0, 3/4]$).
  • Unweighted: $R + C = 3/2$.
  • Edge-weighted: A linear segment between $(0, 1)$ and $(1/2, 1/2)$.
  • Empirical Gains: In ride-sharing simulations, the algorithm with intermediate $R$ values (e.g., $R=0.6$) achieved the best balance. It captured the "upside" of good predictions while avoiding the heavy "downside" of pure prediction-following when data was noisy or shifted.
  • Superiority over Baselines: Figure 2 illustrates that the proposed method significantly outperforms the classic "Mahdian et al. '12" approach in the two-stage setting, especially in the high-consistency regime.
Comparison with the guarantees of Mahdian et al. (2012), showing the authors' curve (blue) is strictly better.

Limitations and Future Work

  • Parameter Selection: While the paper defines the existence of the optimal tradeoff, it doesn't provide a method for automatically choosing the "best" $R$ for a given real-world dataset. This remains an open area for data-driven tuning.
  • Integral Adwords: The tight results for the Adwords problem apply to the fractional version. Characterizing the optimal tradeoff for the integral version (where you can't split a budget) is noted as a challenging open question.
  • Beyond Two Stages: The current tight analysis is specific to the two-stage batch model. Extending these Pareto-efficiency results to fully sequential online matching is a promising future direction.

Summary updated

Abstract

Two-stage bipartite matching is a fundamental problem of optimization under uncertainty introduced by Feng, Niazadeh, and Saberi (2021), who study it under the stochastic and adversarial paradigms of uncertainty. We propose a method to interpolate between these paradigms, using the Algorithms with Predictions (ALPS) framework. To elaborate, given some form of information (e.g. a distributional prediction) about the uncertainty, we consider the optimal decision assuming that information is correct to be some "advice", whose accuracy is unknown. In the ALPS framework, we define Consistency to be an algorithm's performance relative to the advice, and Robustness to be an algorithm's performance relative to the hindsight-optimal decision. We characterize the tight tradeoff between Consistency and Robustness for four settings of two-stage matching: unweighted, vertex-weighted, edge-weighted, and fractional budgeted allocation. Additionally, we show our algorithm achieves state-of-the-art performance in both synthetic and real-data simulations.
BibTeX
@inproceedings{jin2022online,
  author = {Billy Jin and Will Ma},
  title = {{Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=GeT7TSy1_hL},
}
Figure