Research map / Learning theory and algorithms / Fairness
Proportionally Fair Matching via Randomized Rounding
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.
Relaxes proportionally fair (balanced) bipartite matching to a probabilistic δ-ProbablyFair notion, giving a 1/2-approximate LP-based randomized rounding (OCRS + Freedman concentration) and near-exact fairness for the α=0 case.
Problem
Proportional fair matching: find a maximum-weight matching in an edge-colored graph where each color's share of matched edges lies in [α,β]; exact version is NP-hard to approximate even on unweighted paths, so exact fairness is infeasible at good approximation.
Approach
Round an LP relaxation of the fairness-constrained matching polytope using an online contention resolution scheme (per-vertex proposals with 1/2-selectable attenuation), and analyze color counts with a Doob martingale and Freedman's inequality to get δ-multiplicative fairness violations with high probability; for α=0, an LP perturbation (β replaced by (1-ε)β) yields exact β-fairness with high prob
Key results
- Algorithm returns a matching with expected weight at least 1/2 OPT that is δ-ProbablyFair with failure probability 4exp(-δ^2 sum x_e /28) per color.
- For α=0, the algorithm satisfies the β-fairness constraint exactly with probability at least 1-2exp(-ε^2 β sum x_e/28) and expected weight at least (1/2)(1-ε)OPT.
- Azuma-Hoeffding fails here because worst-case one-step changes sum to Θ(n); Freedman's inequality with variance bound 12M_0 gives the needed concentration.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use OCRS randomized rounding of the fair LP solution | Bipartite proportional fair matching · Bipartite proportional fair matching (0 < α ≤ β ≤ 1) | expected weight / OPT: \frac{1}{2}\mathrm{OPT} | Helped |
| Use OCRS randomized rounding of the fair LP solution | Bipartite proportional fair matching · Bipartite proportional fair matching (0 < α ≤ β ≤ 1) | probability of δ-probably-fair output: 1-4\exp\left( \frac{-\delta^2\sum_{e\in E_c}x_e}{28}\right) | Helped |
| Replace β with (1-ε)β in the LP (ablation) | OCRS Rounding Algorithm · Bipartite proportional fair matching (α = 0) | probability of satisfying β-fairness exactly: 1-2\exp \Big(- \frac{\epsilon^2\beta \sum_{e\in E}x_e}{28} \Big) | Helped |
| Replace β with (1-ε)β in the LP (ablation) | OCRS Rounding Algorithm · Bipartite proportional fair matching (α = 0) | expected weight / OPT: \frac{1}{2}(1-\epsilon)\mathrm{OPT} | Hurt |
Surprising findings
- Azuma-Hoeffding concentration is insufficient for this problem since worst-case martingale steps sum to Θ(n), motivating a variance-based analysis.
Limitations
- Guarantees hold only for bipartite graphs; general graphs left as future work.
- Exact β-fairness for α=0 requires β·sum x_e ≥ C; small instances need brute force with runtime exponential in ℓ in the worst case.
- Approximation factor 1/2 is below the 1-1/e target achievable with random-order CRS, which the analysis does not yet support.
Experimental setup
Metrics: approximation ratio fairness violation probability
Baselines: GKPS dependent rounding prior (alpha,beta)-balanced matching algorithm with 1/(4l) approximation
Builds on: contention resolution schemes Freedman's inequality GKPS dependent rounding
Closest papers by meaning
- Fairness and Efficiency in Online Class Matching (NeurIPS 2024 · similarity 0.87)
- Proportional Fairness in Clustering: A Social Choice Perspective (NeurIPS 2024 · similarity 0.86)
- Individual Fairness in Graph Decomposition (ICML 2024 · similarity 0.86)
- Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS (ICML 2024 · similarity 0.85)
- Balanced and Fair Partitioning of Friends (AAAI 2025 · similarity 0.85)
- Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time (ICML 2025 · 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.