Research map / Learning theory and algorithms / Fairness
The Price of Opportunity Fairness in Matroid Allocation Problems
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.
Characterizes the price of opportunity fairness (PoF) for matroid allocation problems via polymatroids and proves worst-case, parametric, semi-random (random coloring) and random-graph bounds on the welfare loss.
Problem
Quantifying the social welfare loss (price of fairness) when allocating resources under matroid constraints subject to opportunity fairness, where each group's allocation is proportional to its isolated maximum feasible allocation.
Approach
Shows that the feasible per-group allocation set of a colored matroid is a polymatroid, which yields a closed-form combinatorial characterization of PoF; uses this to derive tight adversarial bounds (C-1), parametric bounds via an independence index, and semi-random bounds under random group coloring (PoF tends to 1 when max group probability is at most 1/(C-1)).
Key results
- Adversarial worst-case PoF is C-1 for any C-colored matroid, tight; any 2-colored matroid has PoF = 1.
- With random coloring, PoF converges in probability to 1 whenever the maximum group probability is at most 1/(C-1).
- For random Erdos-Renyi graphic and transversal matroids with constant or extreme edge probability, PoF converges to 1 w.h.p.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Impose opportunity fairness on fractional allocations | C-colored matroids with adversarial group assignments and feasibility constraints · C-colored matroid, adversarial | PoF: PoF(M) ≤ C-1 | Hurt |
| Impose opportunity fairness on fractional allocations | 2-colored matroids · 2-colored matroid | PoF: PoF(M)=1 | No clear effect |
| Impose opportunity fairness when all groups have equal rank and ρ ∈ [1/C, 1/(C-1)] | C-colored matroids · Equal-rank groups; low independence index | PoF: PoF(M) = 1 | No clear effect |
| Randomly assign group labels with maximum group probability at most 1/(C-1) | Large matroid allocation problems · Random coloring, max_c p_c ≤ 1/(C-1) | PoF: PoF(M_n) converges in probability towards 1 | No clear effect |
| Use a random graphic matroid with edge probabilities outside the critical regime | Opportunity-fair allocation on Erdős–Rényi random graphs · G_{n,q}(p), q ≤ 1/(ωn) or q ≥ ω/n | PoF: PoF(G_{n,q}(p)) converges to 1 | No clear effect |
| Use a random bipartite graph with edge probabilities outside the specified intermediate regime | Opportunity-fair allocation on random bipartite matching · B_{n,β,q}(p), q ≤ 1/(ωn^{3/2}) or q ≥ ωlog(n)/n | PoF: PoF(B_{n,β,q}(p)) converges to 1 | No clear effect |
| Relax exact opportunity fairness to γ-opportunity fairness | C-colored matroids · C-colored matroid | PoF upper bound: PoF_γ(M) ≤ γ · (C-1) | Mixed |
Surprising findings
- Even when all agents are treated identically (random coloring), PoF can exceed 1; when max group probability exceeds 1/2 the worst-case PoF is at least C-2.
- The price of proportional fairness can be unbounded when irrelevant agents are added, whereas opportunity fairness remains bounded.
Experimental setup
Metrics: price of fairness
Baselines: proportional fairness equitability
Builds on: Price of Fairness Kalai-Smorodinsky fairness Equality of Opportunity matroid theory
Closest papers by meaning
- On Fair Division under Heterogeneous Matroid Constraints (AAAI 2021 · similarity 0.90)
- Truthful and Fair Mechanisms for Matroid-Rank Valuations (AAAI 2022 · similarity 0.89)
- Maximin Fairness with Mixed Divisible and Indivisible Goods (AAAI 2021 · similarity 0.89)
- Constrained Fair and Efficient Allocations (AAAI 2025 · similarity 0.89)
- Fair and Welfare-Efficient Constrained Multi-Matchings under Uncertainty (NeurIPS 2024 · similarity 0.88)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 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.