Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model

AI summary

Overview

Research area: Theoretical computer science, specifically online algorithms and learning-augmented algorithm design, with a machine learning framing (arXiv:2511.23388v1 [cs.LG], 28 Nov 2025, by Kunanon Burathep, Thomas Erlebach, and William K. Moses Jr. of Durham University, UK).

Technical level: Advanced. The paper is a purely theoretical worst-case/expected competitive-ratio analysis; it assumes familiarity with online bipartite matching, the random arrival order model, and learning-augmented notions of consistency, robustness, and smoothness.

Scope: The paper generalizes the sampling-based learning-augmented matching algorithm of Choo et al. (ICML 2024, pp. 8762–8781) so that it no longer requires the optimal matching to have size n, achieving (1−o(1))-consistency and (β−o(1))-robustness whenever the predicted matching size is at least αn for a constant 0 < α ≤ 1. An extended abstract of the paper appears in the proceedings of the 51st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2026).

What This Paper Is About

The paper studies online unweighted bipartite matching with n offline vertices (known in advance) and n online vertices that arrive in a uniformly random order. Each arriving online vertex must be permanently matched to an available neighbor or left unmatched, and the goal is to maximize the number of matches.

In the learning-augmented setting, the algorithm receives untrusted predictions describing the types (neighborhoods) of the online vertices — that is, a predicted count ĉ(t) for each type t. The aim is to be near-optimal when the predictions are accurate and to fall back gracefully to the best prediction-free guarantee when they are wrong.

Key Contributions

1. Removal of the perfect-matching assumption. The authors show that the analysis of Choo et al. implicitly assumes the optimal matching size equals n (n* = n), an assumption underlying their Theorem 4.1 and Lemmas 4.3 and 4.4. This paper removes that assumption entirely and analyzes arbitrary optimal matching sizes.

2. A weaker condition on the predicted matching size. The new algorithm Test-and-Match+ only requires the predicted matching size n̂ to satisfy n̂ ≥ αn for an arbitrary constant 0 < α ≤ 1, rather than the condition n̂ ≥ βn with β = 0.696 required by Choo et al. This yields (1−o(1))-consistency over a strictly larger set of inputs, including cases where αn ≤ n* < βn.

3. New consistency, robustness, and smoothness guarantees. The algorithm achieves (1−o(1))-consistency and (β−o(1))-robustness, and the competitive ratio degrades smoothly with prediction error at rate 1 − 2L₁(p,q)/(2α + L₁(p,q)) − o(1), where L₁(p,q) is the L₁-distance between the true and predicted type distributions.

4. A refined probabilistic analysis and adjusted failure parameters. The paper introduces new lemmas bounding the expected number of optimal matches remaining after the sampling phase (Lemma 5) and the expected total number of matches (Corollary 6), and it replaces the failure probability δ > 1/poly(r̂) of Choo et al. with δ > 1/poly(n+1) so that the failure probability is o(1) even when the number of predicted types r̂ is a small constant.

Main Findings

• Main theorem (Theorem 2): Let α ∈ (0,1] be a constant and let ε ∈ (0, α(1−β)/(1+β)] be another constant. For any instance with predicted matching size n̂ ≥ αn, if the prediction error satisfies L₁(p,q) ≤ (2n̂/n)·((1−β)/(1+β)) − 2ε, then Test-and-Match+ achieves competitive ratio at least 1 − 2L₁(p,q)/(2α + L₁(p,q)) − o(1) (and at least β − o(1)). Otherwise the algorithm achieves competitive ratio at least β − o(1).

• Perfect predictions give near-optimal performance: When predictions are accurate (L₁ = 0), the smoothness bound reduces to 1 − o(1), i.e., (1−o(1))-consistency.

• Robustness for small predicted matchings: If the predicted matching size n̂ is less than αn, the algorithm runs the baseline immediately, guaranteeing competitive ratio at least β, which ensures robustness.

• Baseline constant: Throughout, β denotes the best-known competitive ratio for online bipartite matching in the random arrival order model without predictions, currently β = 0.696 (Mahdian and Yan).

• Mimic guarantee (Lemma 3): If Mimic is run for the entire input sequence, the number of matches obtained is at least n̂ − (n/2)L₁(p,q).

• Upper bound on the optimum (Lemma 4): The optimal matching size satisfies n* ≤ n̂ + (n/2)L₁(p,q).

• Remaining optimal matches (Lemma 5): With δ′ = 1/(log log log n) and sample size k = s₁+s₂ below the sample size limit, the number of matches made by the optimal matching among the remaining n − k′ ≥ n − k arrivals is at least ((n−k)/n − o(1))·n* with probability 1 − o(1).

• Improved threshold: The threshold on the estimated L₁-distance for continuing with Mimic is τ − ε with τ = (2n̂/n)·(1−β)/(1+β), compared to 2(n̂/n − β) − ε used by Choo et al. This makes the threshold useful when n* < n.

• Probability of oversampling: If the sample size s₁+s₂ exceeds s_{n,ε,δ′}·(1 + √log(n+1)), which happens with probability δ_poi = O(1/poly(n+1)), the algorithm runs the baseline from the beginning.

• No empirical evaluation is reported. The paper presents theoretical proofs only; no experiments, datasets, or benchmarks are included.

Methodology in Plain English

The approach follows the sample-then-decide template of Choo et al., with several modifications.

1. Sample a prefix. The algorithm draws an expected number of samples s_{n,ε,δ′} = Θ((n+1) log(1/δ′) / (ε² log(n+1))) online vertices, where actual sample size s₁+s₂ is drawn from Poisson distributions with parameter ½·s_{n,ε,δ′}. Sampling is done with replacement.

2. Estimate the prediction error. Using the algorithm of Theorem 1 (from Choo et al., based on results by Jiao et al.), the algorithm computes an estimate L̂₁(p,q) of the L₁-distance between the predicted type distribution q = ĉ/n and the true type distribution p = c*/n, with |L̂₁(p,q) − L₁(p,q)| ≤ ε holding with probability at least 1 − δ′. The algorithm uses domain size n+1 rather than r̂+1, combining the r̂ predicted types, one dummy type for all unpredicted types, and n − r̂ arbitrary other types.

3. Decide whether to trust the predictions. If the estimated error is below the threshold τ − ε, the algorithm continues with Mimic, which matches each arriving vertex according to a precomputed maximum matching M̂ of the predicted graph Ĝ, leaving it unmatched if no unused matching edge exists for its type. Otherwise, it switches to Baseline — the best known prediction-free algorithm for the random arrival order model, with competitive ratio β = 0.696 — for the remaining input, disregarding edges to offline vertices already matched during sampling.

4. Prove guarantees. The analysis bounds the matches from Mimic (Lemma 3), the true optimum in terms of the prediction error (Lemma 4), the optimal matches remaining after sampling (Lemma 5), the expected total matches (Corollary 6), and the failure probability of the sampling and estimation steps. These are combined in Section 2.4 to prove Theorem 2. A key technical difficulty, absent when n* = n, is bounding how many optimal matches are still possible after the sampling phase has passed.

Why This Matters

Impact on research. The paper corrects a hidden limitation in prior learning-augmented matching work: the earlier analysis only established its consistency guarantee under the implicit assumption that every online vertex can be matched. By supporting arbitrary optimal matching sizes, it widens the class of instances for which near-optimal performance with accurate predictions is provable, and it provides a smoothness curve that continuously interpolates between consistency and robustness as the prediction error grows.

Real-world applications (as identified in the paper's introduction):

• Online advertising, where ad slots (offline vertices) must be assigned to arriving user impressions (online vertices) without knowing future arrivals.
• Ride-sharing platforms, matching drivers and incoming ride requests.
• Resource allocation more broadly, where a fixed set of resources is committed to requests that appear over time.

Industry relevance. Systems that already use learned predictions — for example, a model that forecasts the composition of incoming demand — can wrap a matching policy with this sampling test. If the forecast looks reliable, the system follows it; if not, it reverts to a proven prediction-free algorithm, so that bad predictions cannot degrade performance below the baseline guarantee.

Future Directions

• Tightening the smoothness bound. The paper establishes 1 − 2L₁(p,q)/(2α + L₁(p,q)) − o(1) but does not claim it is optimal; determining matching lower bounds on the achievable competitive ratio as a function of prediction error is a natural open question.

• Extending beyond unweighted matching. The paper addresses the unweighted setting with 2n possible types; generalizing to weighted matching or to offline vertices with capacities (as studied by Li et al.) is a logical next step.

• Relaxing the αn requirement further. The algorithm still requires n̂ ≥ αn for a constant α > 0; understanding what happens as α shrinks toward zero, or whether the αn condition can be replaced by a relative-error condition, is unresolved.

• Empirical validation. Since the paper reports no experiments, evaluating Test-and-Match+ on real matching workloads and comparing sampling overhead against achieved match quality remains open.

Target Audience

Researchers and graduate students in theoretical computer science working on online algorithms, competitive analysis, and learning-augmented algorithm design will benefit most, particularly those familiar with prior work on online bipartite matching in the random arrival order model (Karp et al., Goel and Mehta, Karande et al., Mahdian and Yan) and with the learning-augmented matching line of work by Choo et al., Aamand et al., Feng et al., Jin and Ma, Antoniadis et al., and Li et al. Practitioners building prediction-driven matching systems may find the sample-then-decide structure useful conceptually, but the paper contains no implementation or empirical guidance.

Authors’ abstract

We study the online unweighted bipartite matching problem in the random arrival order model, with $n$ offline and $n$ online vertices, in the learning-augmented setting: The algorithm is provided with untrusted predictions of the types (neighborhoods) of the online vertices. We build upon the work of Choo et al. (ICML 2024, pp. 8762-8781) who proposed an approach that uses a prefix of the arrival sequence as a sample to determine whether the predictions are close to the true arrival sequence and then either follows the predictions or uses a known baseline algorithm that ignores the predictions and is $β$-competitive. Their analysis is limited to the case that the optimal matching has size $n$, i.e., every online vertex can be matched. We generalize their approach and analysis by removing any assumptions on the size of the optimal matching while only requiring that the size of the predicted matching is at least $αn$ for any constant $0 &lt; α\le 1$. Our learning-augmented algorithm achieves $(1-o(1))$-consistency and $(β-o(1))$-robustness. Additionally, we show that the competitive ratio degrades smoothly between consistency and robustness with increasing prediction error.