Research map / Learning theory and algorithms / Fairness
Online Multi-Class Selection with Group Fairness Guarantee
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.
Studies online multi-class selection with group fairness (quantity-based and beta-proportional fairness) for multi-labeled agents, proposing lossless online rounding, optimal set-aside algorithms, and a learning-augmented variant.
Problem
Online allocation of indivisible resources to sequentially arriving multi-labeled agents under group fairness constraints (quantity-based and utility-based), where prior work only handles fractional allocation and single-labeled agents.
Approach
A lossless online rounding scheme (inspired by online correlated k-rental rounding) converts any optimal fractional set-aside solution into an integral allocation without expected loss; relax-and-round with pairwise-class threshold functions handles multi-labeled agents, and a consistency-robustness linear combination adds untrusted advice.
Key results
- The randomized R-SetAside-GFQ algorithm attains the same competitive ratio as the optimal fractional algorithm, and recovers the tight 1+ln(theta) bound in the single-class case, which is the first randomized algorithm to do so per the authors.
- The beta-PF relaxation achieves alpha(b)-competitive and beta(b)-PF guarantees, with the rounding step preserving these bounds exactly.
- LinLA is (1+epsilon)-consistent proportional fair and ((1+epsilon)(beta-1)/epsilon)-robust proportional fair, with experiments showing predictions improve empirical fairness when advice quality is high.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use β-PF instead of quantity-based fairness | Online Multi-Class Selection on Google Cluster Data · Google Cluster Data | empirical fairness | Helped |
| use quantity-based fairness instead of β-PF | Online Multi-Class Selection on Google Cluster Data · Google Cluster Data | total utility | Helped |
| add predictions with ξ = 0 and ε = 1.25 | LinLA · Google Cluster Data, ξ = 0 | empirical competitive ratio | Helped |
| use randomized rather than deterministic set-aside | GFQ algorithms · Google Cluster Data | empirical competitive ratio | Helped |
| increase reliance on predictions | β-PF-LA · Google Cluster Data, varying adversarial probability ξ | empirical β-PF guarantee | Mixed |
Surprising findings
- In the single-labeled case, a relaxation-based randomized rounding closes the gap so the integral algorithm matches the fractional optimum, outperforming the deterministic DSAG especially at small inventory sizes.
- The prior method of Tan et al. extended to multi-labeled arrivals guarantees only a weaker beta-PF bound, unlike the proposed algorithm.
Limitations
- Analysis is restricted to adversarial arrivals with bounded valuations; stochastic or random-order settings are left open.
- Experiments are limited to a single simulated setup built from Google Cluster Data with random valuations.
- Learning-augmented fairness with K-competitive efficiency loss when predictions are perfect in single-class settings.
Experimental setup
Datasets: Google Cluster Data
Benchmarks: Google Cluster Data (simulated OMCS instances)
Metrics: competitive ratio beta-proportional fairness utility per class resource allocation per class
Baselines: DSAG (deterministic set-aside) Dynamic threshold algorithm (no fairness) Prior group-fair online allocation method (Tan et al.)
Builds on: online correlated selection online correlated k-rental scheme Fairness in online fractional allocation (Tan et al.) k-search threshold algorithms
Closest papers by meaning
- Fairness and Efficiency in Online Class Matching (NeurIPS 2024 · similarity 0.89)
- Beyond the Half Approximation: Fair and Efficient Online Class Matching (NeurIPS 2026 · similarity 0.88)
- Class Fairness in Online Matching (AAAI 2023 · similarity 0.88)
- Selective Omniprediction and Fair Abstention (NeurIPS 2025 · similarity 0.86)
- Monotone Individual Fairness (ICML 2024 · similarity 0.85)
- Promoting Fairness Among Dynamic Agents in Online-Matching Markets under Known Stationary Arrival Distributions (NeurIPS 2024 · similarity 0.84)
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.