Learning-Augmented Online Bipartite Fractional Matching¶

Conference: NeurIPS 2025 arXiv: 2505.19252 Code: None Area: Other Keywords: online bipartite matching, learning-augmented algorithms, competitive ratio, robustness-consistency trade-off, fractional matching

TL;DR¶

This paper proposes two learning-augmented algorithms (LAB and PAW) for online bipartite fractional matching. Given a potentially inaccurate advice matching, both algorithms Pareto-dominate the naïve CoinFlip strategy across the entire robustness spectrum for the first time.

Background & Motivation¶

Online bipartite matching is a fundamental problem in online optimization, with broad applications in online advertising, resource allocation, and ride-hailing platforms. In the classical setting, offline vertices are known in advance while online vertices arrive sequentially, and the algorithm must make irrevocable matching decisions without knowledge of future arrivals.

Limitations of Prior Work: Traditional adversarial models assume no structural information and measure worst-case performance, which tends to be overly pessimistic. Stochastic models assume known arrival distributions, but distribution estimation may be inaccurate. Learning-augmented algorithms offer a middle ground—leveraging predictions of unknown quality to improve performance—and are evaluated via robustness (worst-case guarantee independent of prediction quality) and consistency (performance when predictions are accurate).

Key Challenge: The classical CoinFlip strategy (randomly deciding whether to follow the advice) serves as a natural baseline, yet prior work (Mahdian et al. 2007, Spaeh & Ene 2023) only improves upon CoinFlip over a partial robustness range and fails to dominate it across the entire spectrum.

Goal: Whether a learning-augmented algorithm exists that Pareto-dominates CoinFlip across the entire robustness range. This paper answers affirmatively.

Method¶

Overall Architecture¶

Two algorithms are proposed: 1. LearningAugmentedBalance (LAB): Designed for the vertex-weighted setting; built on the classical Balance algorithm with an advice-aware penalty function. 2. PushAndWaterfill (PAW): Designed for the unweighted setting; built on the Waterfilling algorithm, pushing fractional values along advice edges up to a threshold \(\lambda\) at each iteration.

Both algorithms are governed by a trade-off parameter \(\lambda \in [0,1]\) controlling the degree of trust placed in the advice: \(\lambda=0\) reduces to classical Balance (no advice), and \(\lambda=1\) follows the advice completely.

Key Designs¶

Advice-Aware Penalty Function \(f(A,X)\): The core innovation of LAB lies in a two-dimensional penalty function depending on the advised allocation \(A\) and the algorithmic allocation \(X\). It is constructed from \(f_0(z) = \min\{e^{z+\lambda-1}, 1\}\) and \(f_1(z)\) defined via the Lambert \(W\) function. When \(A > X\) (under-allocation), \(f_1\) is applied; when \(A \leq X\) (allocation exceeds the advice), the maximum of \(f_0(X-A)\) and \(f_1(X)\) is taken. This design assigns lower penalties to vertices recommended by the advice (encouraging compliance) while maintaining penalties for excessive allocation (ensuring robustness).
Robustness-Consistency Guarantee of LAB: Via primal-dual analysis, the performance guarantees of LAB are established as:
Robustness: \(r(\lambda) = 1 - e^{\lambda-1} - (e^{\lambda-1} - \lambda)\ln(1-\lambda e^{1-\lambda}) - \lambda(1-\lambda)\)
Consistency: \(c(\lambda) = 1 + \lambda - e^{\lambda-1}\)

At \(\lambda=0\): \(r = 1-1/e\) (classical Balance guarantee), \(c = 1-1/e\); at \(\lambda=1\): \(r = 0\), \(c = 1\).

PushAndWaterfill (PAW): To address the setting where LAB cannot surpass CoinFlip in the unweighted case (since any maximal matching is automatically \(1/2\)-robust), PAW first pushes the fractional value along advice edges up to the threshold \(\lambda\) at each iteration before performing Waterfilling. Its guarantees are:
Robustness: \(r(\lambda) = 1 - (1-\lambda+\lambda^2/2)e^{\lambda-1}\)
Consistency: \(c(\lambda) = 1 - (1-\lambda)e^{\lambda-1}\)
Impossibility Results: By constructing two adaptive adversaries (one targeting robustness and one targeting consistency) and solving a factor-revealing LP, an upper bound on the achievable robustness-consistency trade-off for learning-augmented algorithms in the unweighted setting is established.

Loss & Training¶

This work is theory-driven and involves no loss functions in the conventional sense. The core analytical tool is the primal-dual method: dual variables \((\alpha, \beta)\) are maintained such that the dual objective equals the algorithm's gain; approximate dual feasibility (corresponding to robustness) and a lower bound with respect to the advice value (corresponding to consistency) are then proved separately.

Key Experimental Results¶

Main Results¶

Experiments on synthetic graphs and real-world data validate the performance of LAB and PAW.

Setting	Algorithm	Performance
Vertex-weighted	LAB	Pareto-dominates CoinFlip over the entire range \(r \in [0, 1-1/e]\)
Unweighted	PAW	Pareto-dominates CoinFlip over the entire range \(r \in [1/2, 1-1/e]\)
AdWords (small bids)	LAB extension	Significantly improves upon Mahdian et al. (2007)

Ablation Study¶

Experimental Setting	Key Observation	Remarks
Small noise parameter \(\gamma\)	Competitive ratio approaches 1	Full compliance under perfect advice
Large noise parameter \(\gamma\)	LAB/PAW degrades to Balance	Automatic fallback under low-quality advice
\(\lambda\) parameter sweep	Smooth robustness-consistency trade-off	Validates theoretically predicted trade-off curve

Key Findings¶

The competitive ratios of LAB and PAW start at 1 under perfect advice and degrade smoothly as noise increases.
When noise is sufficiently large, the advice-free Balance algorithm outperforms LAB/PAW, as expected.
LAB extends seamlessly to the AdWords problem under the small-bids assumption.
The derived upper bounds indicate that PAW is near-optimal in the unweighted setting.

Highlights & Insights¶

First comprehensive dominance over CoinFlip: All prior learning-augmented online matching algorithms only improved upon CoinFlip over a partial range; this paper is the first to achieve Pareto dominance across the full range.
Carefully crafted advice-aware penalty function: The construction of \(f(A,X)\) is grounded in a deep understanding of primal-dual analysis; the use of the Lambert \(W\) function, though appearing complex, carries natural mathematical motivation.
Complementary algorithms: LAB handles the weighted setting, while PAW resolves the analytical difficulties that LAB encounters in the unweighted setting.
Strong theory-experiment alignment: Experimental results precisely corroborate theoretical predictions.

Limitations & Future Work¶

LAB and PAW apply only to fractional matching; extension to integral matching requires additional rounding techniques.
A gap remains between the upper bounds and the algorithmic guarantees, leaving the optimal trade-off curve not yet fully characterized.
Advice is provided in the form of a matching; more general advice formats (e.g., predictions of arrival distributions) are worth exploring.
Experiments are conducted at a relatively small scale; validation in large-scale real-world application scenarios warrants further investigation.

This paper builds on the learning-augmented algorithms framework (Lykouris & Vassilvitskii 2021), whose central idea is to leverage imperfect machine-learned predictions to improve worst-case guarantees for online decision-making. This framework has achieved success across numerous online optimization problems, including caching/paging, ski rental, and covering problems. The technical contribution of this work lies in designing an advice-aware penalty function that enables primal-dual analysis to simultaneously handle both robustness and consistency.

Rating¶

Novelty: ⭐⭐⭐⭐ First to achieve full-range dominance over CoinFlip, though the core technique remains rooted in the classical primal-dual framework.
Experimental Thoroughness: ⭐⭐⭐ Experiments primarily serve to validate the theory and are limited in scale.
Writing Quality: ⭐⭐⭐⭐⭐ Well-organized presentation, rigorous mathematical proofs, and intuitive illustrations.
Value: ⭐⭐⭐⭐ Resolves an open problem in the field and makes a significant theoretical contribution to learning-augmented online optimization.