Research map / Learning theory and algorithms / Submodular and game algorithms

Fairness and Efficiency in Online Class Matching

NeurIPS 2024 · Learning theory and algorithms › Submodular and game algorithms · approach: Fair division of indivisible goods · 1 citations (OpenAlex)

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.

Gives a randomized non-wasteful algorithm for online class fair matching of indivisible items that simultaneously achieves 1/2 CEF, CPROP, and USW, and proves upper bounds on CEF (0.761 randomized indivisible, 0.677 deterministic divisible) and a price-of-fairness trade-off.

Problem

Online class fair matching: items arrive online and must be matched irrevocably to agents partitioned into classes; the goal is class envy-freeness (CEF) together with non-wastefulness or utilitarian social welfare (USW), with randomized algorithms for indivisible items.

Approach

A simple randomized algorithm (Random) picks uniformly among classes that have an unsaturated agent liking the arriving item, then picks a uniform unsaturated agent within that class; analysis uses dummy-item augmentation with subadditive optimistic valuations to show 1/2-CEF while remaining non-wasteful, and a worst-case instance links CEF loss to a USW price of fairness.

Key results

• The Random algorithm is non-wasteful and achieves 1/2-CEF, 1/2-CPROP, and 1/2-USW simultaneously in expectation for indivisible matching.
• No non-wasteful randomized algorithm can achieve alpha-CEF for alpha > (e^2-1)/(e^2+1) ≈ 0.761 on indivisible instances.
• No deterministic non-wasteful divisible algorithm can achieve beta-CEF for beta > 0.677; the price of fairness bound gives USW ≤ 1/(1+alpha)+eps.

Measured effects reported in the paper

Surprising findings

• A non-wasteful CEF matching is not guaranteed to maximize class Nash social welfare, though CNSW maximizers are CEF1.

Limitations

• Gap between 1/2 achievable CEF and 0.761 upper bound remains open.
• The CPROP guarantee (1/2) is weaker than the 0.593 achieved by Equal-Filling-OCS, which does not extend to CEF analysis.
• Price-of-fairness bound is an impossibility result and is not shown to be tight.

Experimental setup

Metrics: class envy-freeness approximation class proportionality approximation utilitarian social welfare approximation non-wastefulness

Baselines: Ranking Equal-Filling-OCS

Builds on: Ranking algorithm (Karp et al.) Equal-Filling-OCS online class fair matching (prior work) EF1 / CEF1 notions from fair division

Closest papers by meaning

• Beyond the Half Approximation: Fair and Efficient Online Class Matching (NeurIPS 2026 · similarity 0.96)
• Online Fair Division Meets Reordering Buffers (NeurIPS 2026 · similarity 0.90)
• Online Multi-Class Selection with Group Fairness Guarantee (NeurIPS 2025 · similarity 0.89)
• Promoting Fairness Among Dynamic Agents in Online-Matching Markets under Known Stationary Arrival Distributions (NeurIPS 2024 · similarity 0.88)
• Learning-Augmented Online Bipartite Fractional Matching (NeurIPS 2025 · similarity 0.87)
• Proportionally Fair Matching via Randomized Rounding (AAAI 2025 · similarity 0.87)