Research map / Bandits and online learning / Online convex optimization and games
Online Budgeted Matching with General Bids
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.
Removes the fractional-last-match assumption from online budgeted matching with general bids, proposing a meta algorithm MetaAd with provable competitive ratios parameterized by the max bid-budget ratio, plus a learning-augmented variant LOBM.
Problem
Online budgeted matching (OBM) with general (non-small, indivisible) bids and no fractional-last-match assumption; prior algorithms either need small bids or FLM, and no deterministic competitive algorithm was known.
Approach
A meta algorithm scores each offline node by its bid times a discounting function of its normalized remaining budget, with a dual construction that sets alpha_u=1 for nodes that hit budget insufficiency; this yields competitive ratios as a function of kappa, and the analysis gives a deterministic upper bound of 1-kappa.
Key results
- Proves a deterministic upper bound of 1-kappa on the competitive ratio for OBM with general bids without FLM.
- On MovieLens, MetaAd achieves worst-case normalized reward 0.8524 vs 0.8429 for PrimalDual and 0.7941 for Greedy; LOBM-0.8 reaches 0.8538 worst-case with 0.9372 average.
- MetaAd with exponential discounting achieves a non-zero competitive ratio for every kappa in [0,1) and recovers 1-1/e as kappa goes to 0.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MetaAd instead of Greedy or PrimalDual | Online movie matching · MovieLens | worst-case normalized reward: 0.7941, 0.8429 -> 0.8524 | Helped |
| Use MetaAd instead of Greedy or PrimalDual | Online movie matching · MovieLens | average normalized reward: 0.9329, 0.9340 -> 0.9344 | Mixed |
| Add the competitive guarantee to ML-based scoring (LOBM-0.8) | Online movie matching · MovieLens | worst-case normalized reward: 0.7903 -> 0.8538 | Helped |
| Increase LOBM slackness parameter from 0.5 to 0.8 (ablation) | LOBM · MovieLens | worst-case normalized reward: 0.8324 -> 0.8538 | Helped |
| Increase LOBM slackness parameter from 0.5 to 0.8 (ablation) | LOBM · MovieLens | average normalized reward: 0.9371 -> 0.9372 | Mixed |
| Increase LOBM slackness parameter from 0.3 to 0.8 (ablation) | LOBM · MovieLens | worst-case normalized reward: 0.8113 -> 0.8538 | Helped |
| Increase LOBM slackness parameter from 0.3 to 0.8 (ablation) | LOBM · MovieLens | average normalized reward: 0.9343 -> 0.9372 | Helped |
Surprising findings
- Without FLM, no deterministic algorithm can achieve a non-zero competitive ratio when kappa=1.
- For large kappa, the optimal discounting reduces to a greedy algorithm (phi=1).
Limitations
- Choice of the optimal discounting function phi remains open.
- Competitive ratios without FLM are small for large kappa (e.g., upper bound 1-kappa is attained only in limit).
- Fairness concern: nodes with larger budgets may be favored due to smaller bid-to-budget ratios.
Experimental setup
Datasets: MovieLens
Benchmarks: MovieLens online movie matching online VM placement simulations
Metrics: worst-case normalized reward average normalized reward competitive ratio
Baselines: Greedy PrimalDual ML BJN2007
Builds on: primal-dual online matching (Adwords) BJN2007 fractional-last-match algorithm Greedy under FLM
Closest papers by meaning
- Learning-Augmented Online Bipartite Fractional Matching (NeurIPS 2025 · similarity 0.86)
- Online Resource Allocation With General Constraints (NeurIPS 2026 · similarity 0.85)
- Learning-Augmented Online Bidding in Stochastic Settings (NeurIPS 2025 · similarity 0.84)
- Promoting Fairness Among Dynamic Agents in Online-Matching Markets under Known Stationary Arrival Distributions (NeurIPS 2024 · similarity 0.84)
- Beyond the Half Approximation: Fair and Efficient Online Class Matching (NeurIPS 2026 · similarity 0.83)
- Maximizing the Success Probability of Policy Allocations in Online Systems (AAAI 2024 · similarity 0.83)
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.