Research map / Learning theory and algorithms / Fairness
Fair Lotteries for 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.
Initiates lotteries over discrete participatory budgeting outcomes, introducing a BB1 implementation via dependent rounding and studying best-of-both-worlds ex-ante/ex-post fairness (IFS, UFS, GFS vs JR, EJR, FJR).
Problem
Participatory budgeting with heterogeneous project costs: fractional outcomes cannot always be implemented by integral lotteries with equal spend, and existing deterministic PB rules give no ex-ante representation guarantees to individual voters.
Approach
Defines BB1 (budget balanced up to one project) and shows any feasible fractional PB outcome can be implemented by a lottery whose outcomes all satisfy BB1 via a cost-weighted dependent rounding; then defines ex-ante fair share hierarchies (IFS, UFS, Strong UFS, GFS) and gives best-of-both-worlds algorithms (GCR-based exponential-time, MES-based polynomial-time) plus impossibilities.
Key results
- Shows any feasible fractional PB outcome can be implemented by a polynomial-time lottery whose integral outcomes all satisfy BB1 with probability 1.
- Proves ex-ante GFS and ex-post JR are incompatible in PB with binary utilities; also ex-ante IFS and ex-post JR incompatible in unit-cost general PB.
- Gives an exponential-time algorithm for ex-ante Strong UFS + ex-post FJR + BB1 and a polynomial-time algorithm for ex-ante Strong UFS + ex-post EJR + BB1 (binary utilities).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use cost-preserving dependent rounding to implement a feasible fractional outcome | PB lottery implementation · PB with heterogeneous costs | ex-post budget balance | Helped |
| Combine GCR with fractional budget allocation and dependent rounding | PB with binary utilities · PB with binary utilities | fairness guarantees | Helped |
| Use MES with remaining-budget allocation and dependent rounding | PB with binary utilities · PB with binary utilities | fairness guarantees | Helped |
| Average voters' optimal fractional outcomes | Fractional Random Dictator · PB | ex-ante GFS | Helped |
| Use MES with remaining-budget allocation and dependent rounding | BW-MES-PB · PB with cost utilities | fairness guarantees | Helped |
| Require ex-post JR together with ex-ante GFS | PB with binary utilities · PB with binary utilities | compatibility | Hurt |
| Require ex-post JR together with ex-ante IFS | General PB with unit costs and cardinal utilities · Unit-cost PB | compatibility | Hurt |
| Require ex-post BFx for every supported outcome | Lottery implementation of fractional PB outcomes · PB with heterogeneous costs | implementability | Hurt |
Surprising findings
- Ex-ante Strong UFS cannot be combined with ex-post BFx-type lotteries for all fractional outcomes, unlike committee voting.
- Ex-ante GFS is incompatible with ex-post JR in PB with binary utilities, a separation from approval-based committee voting where GFS is compatible with EJR.
Limitations
- Best-of-both-worlds results for binary utilities hold for some pairs only; GFS incompatible with JR and IFS incompatible with JR in general settings.
- Exponential-time algorithm for the strongest FJR result.
- Results focus on fairness; efficiency not addressed.
Experimental setup
Baselines: Greedy Cohesive Rule (GCR) Method of Equal Shares (MES) Random Dictator
Builds on: dependent randomized rounding Greedy Cohesive Rule Method of Equal Shares fair share axioms for approval-based committee voting
Closest papers by meaning
- Project-Fair and Truthful Mechanisms for Budget Aggregation (AAAI 2024 · similarity 0.88)
- The Distortion of Public-Spirited Participatory Budgeting (AAAI 2025 · similarity 0.86)
- Strategic Cost Selection in Participatory Budgeting (NeurIPS 2025 · similarity 0.85)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.83)
- Promoting External and Internal Equities Under Ex-Ante/Ex-Post Metrics in Online Resource Allocation (ICML 2024 · similarity 0.83)
- Smooth Partial Lotteries for Stable Randomized Selection (NeurIPS 2026 · similarity 0.83)
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.