Research map / Learning theory and algorithms / Submodular and game algorithms
The Distortion of Public-Spirited Participatory Budgeting
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.
Theoretical study of distortion in public-spirited participatory budgeting, showing linear barriers for standard ballots and proposing a rank-of-predefined-bundles ballot with sublinear, logarithmic, and constant distortion protocols.
Problem
Participatory budgeting aggregates voter ballots into a budget-feasible project set; with unrestricted utilities, standard ballot formats and deterministic rules incur unbounded or large welfare distortion. The paper asks whether public-spirited voters allow low distortion in PB.
Approach
Extends the public-spirited voting model of Flanigan et al. to PB with additive values, proves linear distortion lower bounds for deterministic rules on existing ballots, and introduces a ranking-of-predefined-bundles ballot whose multi-round protocols achieve sublinear, logarithmic, and constant distortion.
Key results
- Deterministic rules on ranking ballots have distortion Θ(m/γmin) and randomized rules Θ(log m/γmin) at best; Copeland achieves O(m/γmin^2) for PB.
- Rank-of-predefined-bundles protocols achieve O(√m/γmin^2) (Copeland, HLB), O(log(m)/γmin^4) (two rounds, TCB), and O(1/γmin^4) (two rounds, EB).
- On 1244 real pabulib PB elections, the rank→rank-b(EB) ballot typically requires voters to rank far fewer than m bundles.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace individual-project rankings with high-low bundle rankings | Copeland in deterministic PB · PB | distortion: O(m/γ²_min) -> O(√m/γ²_min) | Helped |
| Use two-round tiered-cost bundle rankings after project rankings | Copeland in deterministic PB · PB | distortion: O(log(m)/γ⁴_min) | Helped |
| Use two-round exhaustive bundle rankings after project rankings | Copeland in deterministic PB · PB | distortion: O(1/γ⁴_min) | Helped |
| Use project rankings with a deterministic PB aggregation rule | Deterministic PB rules · PB | distortion: Ω(m/γmin) | Hurt |
| Use project rankings with a randomized PB aggregation rule | Randomized PB rules · PB | distortion: Ω(log(m)) | Hurt |
| Use rankings by value for money | Deterministic PB rules · PB | distortion: ∞ | Hurt |
| Use k-approval ballots with k > 1 | Deterministic PB rules · PB | distortion: ∞ | Hurt |
| Use 1-approval ballots | Deterministic PB rules · PB | distortion: Ω(m²/γmin) | Hurt |
| Use knapsack ballots | Deterministic PB rules · PB | distortion: Ω(m/γmin) | Hurt |
| Use threshold approval ballots | Deterministic PB rules · PB | distortion: Ω(m) | Hurt |
Surprising findings
- Existing PB ballot formats (value-for-money rankings, k-approval, knapsack, threshold approval) all suffer linear or worse distortion for deterministic rules under public spirit, even though single-winner rules achieve constant distortion.
- Single-winner rules applied to PB achieve optimal dependence on m for rank ballots.
Limitations
- Constant-distortion protocol requires quasipolynomially many bundles in the worst case.
- Results depend on voters being public-spirited, which is assumed and not empirically established.
- Two-round elicitation protocols add practical burden.
Experimental setup
Datasets: 1244 real PB elections from pabulib.org
Metrics: distortion number of bundles ranked per alternative
Baselines: rankings by value-for-money k-approval knapsack ballots threshold approval plurality
Builds on: Flanigan, Procaccia, and Wang (2023) public-spirited voting Benadè et al. (2021) PB distortion under unit-sum utilities Copeland rule Maximal Lottery
Closest papers by meaning
- Project-Fair and Truthful Mechanisms for Budget Aggregation (AAAI 2024 · similarity 0.86)
- Fair Lotteries for Participatory Budgeting (AAAI 2024 · similarity 0.86)
- Metric Distortion of Line-up Elections: The Right Person for the Right Job (AAAI 2025 · similarity 0.86)
- Tight Bounds on the Distortion of Randomized and Deterministic Distributed Voting (NeurIPS 2025 · similarity 0.85)
- On the Distortion of Committee Election with 1-Euclidean Preferences and Few Distance Queries (AAAI 2025 · similarity 0.85)
- Strategic Cost Selection in Participatory Budgeting (NeurIPS 2025 · 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.