Research map / Bandits and online learning / Online convex optimization and games
Online bipartite matching with imperfect advice
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that no adversarial-arrival learning-augmented matching algorithm can be both 1-consistent and strictly better than 1/2-robust, and gives TestAndMatch, a 1-consistent, (beta-o(1))-robust algorithm for random-order online bipartite matching that uses type-count histogram advice and L1 distribution testing.
Problem
Online unweighted bipartite matching with predictions: whether advice can give 1-consistency while retaining the best advice-free competitive ratio as robustness, under adversarial and random-order arrivals.
Approach
Use a histogram over online-vertex types as advice; test its L1 distance to the realized type distribution with a sublinear number of arrivals via a distribution-testing L1 estimator; mimic the advice matching if it passes, otherwise fall back to a black-box advice-free baseline (e.g., RANKING).
Key results
- Impossibility: no learning-augmented algorithm under adversarial arrivals can be both 1-consistent and strictly more than 1/2-robust.
- TestAndMatch is 1-consistent and (beta - o(1))-robust under random-order arrivals, with beta = 0.696 when RANKING is the baseline.
- Proof-of-concept experiments with n=2000 show the attained competitive ratio degrades less than 0.1 below the baseline under corrupted advice.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use TestAndMatch with perfect type-count advice instead of the advice-free baseline | Online bipartite matching · Random Order, perfect advice | competitive ratio: $\beta$ to 1 | Helped |
| use TestAndMatch with arbitrary-quality advice and its baseline fallback | Online bipartite matching · Random Order, arbitrary advice | competitive ratio: $\beta \cdot (1 - o(1))$ | Helped |
| use learning-augmented advice while requiring 1-consistency | Online bipartite matching · Adversarial arrival, arbitrary advice | competitive ratio: strictly more than $1/2$ is unattainable | Hurt |
| disable sigma remapping (ablation) | TestAndMatch · Synthetic hard known-IID instances, random order | competitive ratio | Hurt |
| disable bucketing (ablation) | TestAndMatch · Synthetic hard known-IID instances, random order | competitive ratio | Hurt |
| disable patching (ablation) | TestAndMatch · Synthetic hard known-IID instances, random order | competitive ratio | Hurt |
Surprising findings
- Hardness holds even against randomized algorithms and extends to any alpha in [0,1/2]: (1-alpha)-consistent algorithms cannot be strictly better than (1/2+alpha)-robust.
- The advice-based L1 distance can be large (e.g., 4 in an example) even when advice yields a perfect matching, motivating type remapping.
Limitations
- Robustness is beta(1-o(1)) rather than exactly beta, and the o(1) term is not removed.
- The L1 quality metric is sensitive to noise such as random edge additions or removals.
- Only an empirical L1 estimator is implemented as proof of concept, not the optimal sublinear tester, and the sample complexity may be large relative to n.
Experimental setup
Datasets: synthetic hard known-IID instances generated following the construction of a prior hard instance
Benchmarks: synthetic online bipartite matching instances with n=2000
Metrics: competitive ratio
Baselines: RANKING LOMAR Greedy
Builds on: RANKING learning-augmented algorithms Poissonization tolerant identity testing
Closest papers by meaning
- Learning-Augmented Online Bipartite Fractional Matching (NeurIPS 2025 · similarity 0.91)
- Online Matching with Stochastic Rewards: Provable Better Bound via Adversarial Reinforcement Learning (ICML 2024 · similarity 0.88)
- Fairness and Efficiency in Online Class Matching (NeurIPS 2024 · similarity 0.86)
- DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models (ICML 2025 · similarity 0.86)
- Active Ranking and Matchmaking, with Perfect Matchings (ICML 2024 · similarity 0.85)
- MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation (ICML 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.