Research map / Learning theory and algorithms / Fairness
Project-Fair and Truthful Mechanisms for Budget Aggregation
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.
Introduces project fairness (l_inf distance to the mean) for truthful budget aggregation and proposes the Ladder moving phantom mechanism, which achieves essentially optimal overfunding/underfunding bounds and new l1 approximation guarantees for 3 to 6 projects.
Problem
Truthful budget aggregation where strategic voters split a divisible resource among projects; the mean is a fair baseline but not strategyproof, so the goal is a strategyproof mechanism whose output is close to the mean for every project.
Approach
Defines project fairness as the worst-case per-project deviation from the mean and proposes the Ladder mechanism, a simple moving phantom system f_k(t)=max(t-k/n,0) that moves phantoms upward uniformly, giving tight over- and underfunding bounds and an l1 approximation via a combinatorial proof.
Key results
- Ladder mechanism underfunds by at most 1/2 - 1/(2m) and overfunds by at most 1/4 (essentially tight for moving phantom mechanisms).
- Ladder mechanism is 2/3-approximate in l1 distance for m=3, matching the known lower bound and closing the gap left by the Piecewise Uniform mechanism's 2/3 + 10^-5 bound.
- First non-trivial l1 guarantees for m=4,5,6: 1, 3/2, and 5/3 respectively.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Ladder mechanism instead of the Piecewise Uniform mechanism | Budget aggregation with 3 projects · Budget aggregation, m=3 | worst-case ℓ1 distance to mean (upper bound): 2/3+ \epsilon -> 2/3 | Helped |
| Use the Ladder mechanism for 4 projects | Budget aggregation · Budget aggregation, m=4 | worst-case ℓ1 distance to mean (upper bound): 2 -> 1 | Helped |
| Use the Ladder mechanism for 5 projects | Budget aggregation · Budget aggregation, m=5 | worst-case ℓ1 distance to mean (upper bound): 2 -> 3/2 | Helped |
| Use the Ladder mechanism for 6 projects | Budget aggregation · Budget aggregation, m=6 | worst-case ℓ1 distance to mean (upper bound): 2 -> 5/3 | Helped |
Surprising findings
- Proportional moving phantom mechanisms can be shown to never overfund by more than 1/4, while underfunding by up to nearly 1/2 is unavoidable for moving phantom mechanisms.
Limitations
- Results are restricted to moving phantom mechanisms; whether non-moving-phantom strategyproof mechanisms can do better is open.
- Gap of O(1/n) between upper and lower overfunding bounds for odd n.
- The l1 approximation bounds are non-trivial only for m up to 6, since the approach gives bounds above the trivial 2 for larger m.
Experimental setup
Metrics: l_infinity distance to mean (project fairness: overfunding a l1 distance to mean (approximation factor)
Baselines: Piecewise Uniform mechanism Independent Markets mechanism utilitarian social welfare mechanism
Builds on: moving phantom mechanisms Piecewise Uniform mechanism Independent Markets mechanism generalized median mechanisms
Closest papers by meaning
- Truthful Aggregation of Budget Proposals with Proportionality Guarantees (AAAI 2022 · similarity 0.94)
- Price of Fairness in Budget Division and Probabilistic Social Choice (AAAI 2020 · similarity 0.88)
- Fair Lotteries for Participatory Budgeting (AAAI 2024 · similarity 0.88)
- The Distortion of Public-Spirited Participatory Budgeting (AAAI 2025 · similarity 0.86)
- A Unified Framework for Uniform-Price Resource Allocation Mechanisms (NeurIPS 2026 · similarity 0.86)
- Reachability of Fair Allocations via Sequential Exchanges (AAAI 2024 · similarity 0.85)
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.