Research map / Learning theory and algorithms / Submodular and game algorithms
Class Fairness in Online Matching
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adaptive class priorities, moving a class to the queue's end after it receives an item | Match-and-Shift · Indivisible online matching | class envy-freeness up to one item approximation: \sfrac{1}{2} approximation; tight upper bound \sfrac{1}{2} | Helped |
| Use adaptive class priorities, moving a class to the queue's end after it receives an item | Match-and-Shift · Indivisible online matching | class maximin share approximation: \sfrac{1}{2} approximation; no deterministic algorithm achieves more than \sfrac{1}{2} | Helped |
| Use adaptive class priorities, moving a class to the queue's end after it receives an item | Match-and-Shift · Indivisible online matching | utilitarian social welfare approximation: \sfrac{1}{2} approximation; no deterministic algorithm achieves more than \sfrac{1}{2} | Helped |
| Split each arriving item equally among eligible classes, then water-fill within each class | Equal-Filling · Divisible online matching | class envy-freeness approximation: 1-\sfrac{1}{e}; the algorithm does not achieve more than 1-\sfrac{1}{e} | Helped |
| Split each arriving item equally among eligible classes, then water-fill within each class | Equal-Filling · Divisible online matching | class proportionality approximation: 1-\sfrac{1}{e}; upper bound 1-\sfrac{1}{e} | Helped |
| Split each arriving item equally among eligible classes, then water-fill within each class | Equal-Filling · Divisible online matching | utilitarian social welfare approximation: \sfrac{1}{2} | Helped |
| Apply online correlated selection to round a guiding divisible matching into an indivisible matching | Equal-Filling-OCS · Indivisible online matching | class proportionality approximation: \sfrac{1}{2} -> 0.593 | Helped |
| Apply online correlated selection to round a guiding divisible matching into an indivisible matching | Equal-Filling-OCS · Indivisible online matching | utilitarian social welfare approximation: \sfrac{1}{2} | Helped |
| Use independent randomized rounding instead of online correlated selection (ablation) | Equal-Filling-OCS · Indivisible online matching | class proportionality approximation: 0.593 -> \sfrac{1}{2} | Hurt |
| Use deterministic class-level assignment (ablation) | Randomized class-proportionality algorithms · Indivisible online matching | class proportionality approximation: at best \sfrac{1}{2} | Hurt |
| Use deterministic within-class assignment (ablation) | Randomized class-proportionality algorithms · Indivisible online matching | class proportionality approximation: at best \sfrac{1}{2} | Hurt |
| Use Ranking without accounting for class sizes (ablation) | Ranking · Indivisible online matching | class proportionality: one item: first class gets probability \frac{1}{n+1} | Hurt |
Closest papers by meaning
- Fairness and Efficiency in Online Class Matching (NeurIPS 2024 · similarity 0.97)
- Beyond the Half Approximation: Fair and Efficient Online Class Matching (NeurIPS 2026 · similarity 0.95)
- 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.87)
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.