Research map / Learning theory and algorithms / Submodular and game algorithms
Price of Fairness in Budget Division and Probabilistic Social Choice
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 CUT instead of NASH | NASH · Mallow's, m=10, average | normalized utilitarian welfare: 0.91 -> 0.97 | Helped |
| use CUT instead of NASH | NASH · Euclidean, m=10, average | normalized utilitarian welfare: 0.86 -> 0.92 | Helped |
| use CUT instead of PV | PV · Mallow's, m=50, average | normalized utilitarian welfare: 0.78 -> 0.98 | Helped |
| use NASH instead of PV | PV · Mallow's, m=50, average | normalized utilitarian welfare: 0.78 -> 0.92 | Helped |
| use NASH instead of EGAL or ES | ES · Impartial Culture, m=10, average | normalized utilitarian welfare: 0.97 -> 0.97 | No clear effect |
| use CUT instead of ES (coordination) | ES · Mallow's, m=50, worst | normalized utilitarian welfare: 0.64 -> 0.95 | Helped |
| use f(x)=sqrt(x) interpolating rule instead of NASH (log) | NASH · worst-case efficiency guarantee (theory) | worst-case guarantee | Helped |
| impose IFS on any rule | utilitarian rule · worst-case welfare (theory) | worst-case guarantee: <= 2/sqrt(m) of optimum | Hurt |
| impose stronger fairness (core or AFS) instead of only IFS | IFS rules · worst-case welfare (theory) | worst-case guarantee | No clear effect |
| use egalitarian rule | EGAL · worst-case welfare (theory) | worst-case guarantee: 1/m | Hurt |
| different preference models (Euclidean, IC, Mallow's) | all rules · price of fairness | normalized utilitarian welfare | No clear effect |
Closest papers by meaning
- Project-Fair and Truthful Mechanisms for Budget Aggregation (AAAI 2024 · similarity 0.88)
- Reducing Leximin Fairness to Utilitarian Optimization (AAAI 2025 · similarity 0.88)
- Fair Division with Social Impact (AAAI 2025 · similarity 0.87)
- The (Exact) Price of Cardinality for Indivisible Goods: A Parametric Perspective (AAAI 2025 · similarity 0.87)
- On Optimal Tradeoffs between EFX and Nash Welfare (AAAI 2024 · similarity 0.87)
- Fair Lotteries for Participatory Budgeting (AAAI 2024 · 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.