Research map / Learning theory and algorithms / Submodular and game algorithms
Beyond the Half Approximation: Fair and Efficient Online Class Matching
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.
Introduces threshold-based EFTT (divisible) and Hybrid Ranking (indivisible) algorithms for online class matching that trade off class envy-freeness against utilitarian welfare via a parameter gamma, beating the 1/2-USW barrier, plus an improved price-of-fairness upper bound.
Problem
Online bipartite class matching where agents are partitioned into classes and items arrive adversarially; prior constant-CEF algorithms only achieve 1/2 utilitarian social welfare, and it was open whether fairness forces this loss.
Approach
Equalize allocations across classes (equal filling) until each class's agents reach fractional load threshold gamma, then switch to water-filling/RANKING for efficiency; analyze both CEF and USW simultaneously via a primal-dual certificate with a threshold-dependent potential g, plus a two-phase adversarial instance for an upper bound on price of fairness.
Key results
- EFTT is (1-e^{-gamma})-CEF and (1-e^{gamma-1}/(gamma+1))-USW for divisible matching; gamma=0.7915 gives 0.5468-USW and 0.5468-CEF.
- Hybrid Ranking gives gamma/2-CEF and the same USW guarantee for indivisible matching, beating 1/2-USW for gamma>0.
- Upper bound: no randomized non-wasteful alpha-CEF divisible algorithm exceeds (1+alpha-e^{alpha-1})/(1+alpha)-USW, improving the prior 1/(1+alpha) bound that was vacuous for alpha<0.58.
Surprising findings
- The prior 1/(1+alpha) price-of-fairness upper bound is vacuous (exceeds 1-1/e) for alpha <= 0.58.
Limitations
- Indivisible CEF guarantee gamma/2 is weaker than the divisible guarantee and the gap to the upper bound is not closed.
- Upper bound is only shown for divisible matching and for non-wasteful algorithms; the paper's bounds do not fully match the algorithms.
- Results are for unweighted adversarial arrivals; weighted preferences and random-order models left open.
Experimental setup
Metrics: CEF approximation ratio USW competitive ratio
Baselines: RANKING water-filling Random (Hajiaghayi et al.) Hosseini et al. deterministic algorithms
Builds on: RANKING water-filling Hosseini et al. online class matching online correlated selection Hajiaghayi et al. Random algorithm
Closest papers by meaning
- Fairness and Efficiency in Online Class Matching (NeurIPS 2024 · similarity 0.96)
- Online Fair Division Meets Reordering Buffers (NeurIPS 2026 · similarity 0.89)
- Promoting Fairness Among Dynamic Agents in Online-Matching Markets under Known Stationary Arrival Distributions (NeurIPS 2024 · similarity 0.89)
- Online Multi-Class Selection with Group Fairness Guarantee (NeurIPS 2025 · similarity 0.88)
- Learning-Augmented Online Bipartite Fractional Matching (NeurIPS 2025 · similarity 0.88)
- On Hierarchies of Fairness Notions in Cake Cutting: From Proportionality to Super Envy-Freeness (NeurIPS 2025 · similarity 0.86)
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.