Research map / Learning theory and algorithms / Fairness
Fair and Welfare-Efficient Constrained Multi-Matchings under Uncertainty
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 fair, welfare-efficient constrained multi-matching (reviewer assignment) under uncertainty in valuations, deriving tractable robust (uncertainty-set) and CVaR (stochastic) optimization methods for utilitarian and group egalitarian welfare.
Problem
Allocating constrained resources (e.g., reviewers to papers) to maximize welfare while maintaining group fairness when agent valuations are unknown and must be estimated with uncertainty.
Approach
Uses robust optimization over ML-derived uncertainty sets (linear, single/multiple ellipsoidal) and CVaR over estimated distributions to optimize utilitarian and group egalitarian welfare; derives dual reformulations yielding LPs, iterated QPs, and sampling-based LPs instead of costly adversarial subgradient methods.
Key results
- On AAMAS 2015 binarized bids, non-robust allocations have 0 robust welfare while the robust-USW allocation attains 1.00 normalized robust USW and the robust-GESW allocation 1.00 normalized robust GESW.
- Iterated QP converges much faster than adversarial projected subgradient ascent on AAMAS 2015 and 2016; the adversarial method fails to converge in 1,000 iterations for robust GESW on all datasets.
- Under increasing Gaussian noise, the CVaR_0.01 of baseline USW and GESW allocations drops relative to CVaR-optimized allocations, with GESW declining more sharply than USW.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Optimize robust USW or robust GESW instead of using a non-robust allocation | Reviewer assignment · AAMAS 2015, binarized bids | Robust USW: 0 ± 0 -> 1.00 ± 0 | Helped |
| Optimize robust USW or robust GESW instead of using a non-robust allocation | Reviewer assignment · AAMAS 2016, binarized bids | Robust USW: 0 ± 0 -> 1.00 ± 0 | Helped |
| Optimize robust USW or robust GESW instead of using a non-robust allocation | Reviewer assignment · AAMAS 2021, binarized bids | Robust USW: 0 ± 0 -> 1.00 ± 0 | Helped |
| Optimize CVaR rather than the central-estimate objective | Reviewer assignment · AAMAS 2015, binarized bids | CVaR USW: 1.00 ± 0 -> 1.00 ± 0 | No clear effect |
| Optimize CVaR rather than the central-estimate objective | Reviewer assignment · AAMAS 2016, binarized bids | CVaR USW: 1.00 ± 0 -> 0.99 ± 0 | No clear effect |
| Increase modeled noise and optimize CVaR instead of naïve USW or GESW | Reviewer assignment · Gaussian AAMAS datasets | CVaR welfare | Helped |
Surprising findings
- The USW-optimal allocation has very high GESW on the real AAMAS data, so the USW and GESW tradeoff is small in that setting.
- Non-robust allocations score zero robust welfare, showing that robustness must be targeted explicitly.
Limitations
- CVaR approach requires solving LPs with many samples, which is computationally expensive.
- Egalitarian robust problem under general uncertainty sets lacks efficient reduction and relies on generic adversarial subgradient ascent.
- Individual egalitarian welfare is not considered; under uncertainty it is zero when items are proportional to agents.
Experimental setup
Datasets: AAMAS 2015 bids AAMAS 2016 bids AAMAS 2021 bids
Benchmarks: AAMAS 2015 reviewer bids AAMAS 2016 reviewer bids AAMAS 2021 reviewer bids
Metrics: utilitarian social welfare group egalitarian social welfare CVaR of USW CVaR of GESW robust USW robust GESW
Baselines: adversarial projected subgradient ascent expected welfare maximization (USW/GESW central estimate)
Builds on: Gaussian process matrix factorization adversarial projected subgradient ascent
Closest papers by meaning
- The Price of Opportunity Fairness in Matroid Allocation Problems (NeurIPS 2025 · similarity 0.88)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.88)
- Stable Matching with Ties: Approximation Ratios and Learning (NeurIPS 2025 · similarity 0.87)
- Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning (NeurIPS 2024 · similarity 0.87)
- 1/2-Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations (AAAI 2024 · similarity 0.87)
- Multidimensional Bayesian Utility Maximization: Tight Approximations to Welfare (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.