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

arXiv: https://arxiv.org/abs/2206.11397 · HTML: https://mlsanity.com/paper/2206.11397/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jun 2022.

## Built on by (most cited first, 19 of 19)

- [Online bipartite matching with imperfect advice](https://mlsanity.com/paper/2405.09784/) (2024)
- [Learning-Augmented Online Bipartite Fractional Matching](https://mlsanity.com/paper/2505.19252/) (2025)
- [Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints](https://mlsanity.com/paper/2301.12863/) (2023)
- [Online Ad Allocation with Predictions](https://mlsanity.com/paper/2302.01827/) (2023)
- [Non-clairvoyant Scheduling with Partial Predictions](https://mlsanity.com/paper/2405.01013/) (2024)
- [Learning for Edge-Weighted Online Bipartite Matching with Robustness Guarantees](https://mlsanity.com/paper/2306.00172/) (2023)
- [Learning-Augmented Online Packet Scheduling with Deadlines](https://mlsanity.com/paper/2305.07164/) (2023)
- [Best of Many in Both Worlds: Online Resource Allocation with Predictions under Unknown Arrival Model](https://mlsanity.com/paper/2402.13530/) (2024)
- [On Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rental](https://mlsanity.com/paper/2312.02547/) (2023)
- [Efficiently Solving Discounted MDPs with Predictions on Transition Matrices](https://mlsanity.com/paper/2502.15345/) (2025)
- [Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model](https://mlsanity.com/paper/2511.23388/) (2025)
- [Constrained Online Two-stage Stochastic Optimization: Algorithm with (and without) Predictions](https://mlsanity.com/paper/2401.01077/) (2024)
- [Learning-Augmented Competitive Algorithms for Spatiotemporal Online Allocation with Deadline Constraints](https://mlsanity.com/paper/2408.07831/) (2024)
- [Hierarchical Optimization via LLM-Guided Objective Evolution for Mobility-on-Demand Systems](https://mlsanity.com/paper/2510.10644/) (2025)
- [Parsimonious Learning-Augmented Online Metric Matching](https://mlsanity.com/paper/2605.26886/) (2026)
- [Online Uniform Sampling: Randomized Learning-Augmented Approximation Algorithms with Application to Digital Health](https://mlsanity.com/paper/2402.01995/) (2024)
- [A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives](https://mlsanity.com/paper/2406.03574/) (2024)
- [Online Algorithms with Unreliable Guidance](https://mlsanity.com/paper/2602.20706/) (2026)
- [The Secretary Problem with a Stochastic Precursor](https://mlsanity.com/paper/2605.22653/) (2026)

## Abstract (arXiv)

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.