Research map / Learning theory and algorithms / Submodular and game algorithms
Strategic Cost Selection in 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.
Studies a game where project proposers strategically choose costs (payoff = reported cost minus delivery cost) under approval-based PB rules, characterizing when pure Nash equilibria exist for AV-over, Phragmén, and MES variants, and runs experiments on real Pabulib elections.
Problem
Strategic cost selection by project proposers in approval-based participatory budgeting: whether pure Nash equilibria exist when proposers set project prices above delivery costs, given fixed and known votes.
Approach
Defines PB cost games where projects are players choosing costs to maximize their cost above delivery cost subject to being funded; proves existence/non-existence of NE across rules (AV, AV-over, Phragmén, MES with cost or approval utilities), ballot types (plurality, party-list, unrestricted), delivery costs, and tie-breaking orders, and gives a polynomial-time NE algorithm for MES with cost util
Key results
- MES with cost utilities always admits a pure Nash equilibrium regardless of tie-breaking, computable in polynomial time, even with arbitrary delivery costs.
- AV-over, Phragmén, and MES with approval utilities can fail to have equilibria for some tie-breaking orders; e.g., Phragmén has a six-project, six-voter party-list instance with zero delivery costs and no NE for any tie-breaking order.
- Experiments on Pabulib elections: after 10,000 iterations of best-response-style dynamics, winning and losing margins drop drastically for most rules (e.g., AV-over winning margin in Bemowo falls from 150 to 1 thousand PLN/EUR).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Run the strategic cost-selection dynamics for 10000 iterations | PB election projects under GreedyAV, AV over Cost, Phragmén, MES with approval utilities, or MES with cost utilities · Real-life PB elections | winning and losing margins | Helped |
| Use GreedyAV rather than proportional PB rules | Strategic cost-selection dynamics · Real-life PB elections | winning margin after 10000 iterations | Mixed |
Surprising findings
- Under plurality ballots with AV-over the equilibrium costs of selected projects can be arbitrarily far below the total budget.
- Basic AV has equilibria where the most-approved project requests the full budget, showing proposers of popular projects overstate costs.
Limitations
- Set of projects is fixed and votes are common knowledge.
- Project costs do not affect approvals.
- Several cases (e.g., Phragmén party-list with arbitrary delivery costs) remain conjectures.
Experimental setup
Datasets: Pabulib
Metrics: winning margin losing margin
Baselines: AV AV-over Phragmén MES with approval utilities
Builds on: Method of Equal Shares Phragmén rule AV-over (approval-to-cost greedy)
Closest papers by meaning
- Participatory Budgeting Designs for the Real World (AAAI 2023 · similarity 0.86)
- Fair Lotteries for Participatory Budgeting (AAAI 2024 · similarity 0.85)
- The Distortion of Public-Spirited Participatory Budgeting (AAAI 2025 · similarity 0.85)
- Project-Fair and Truthful Mechanisms for Budget Aggregation (AAAI 2024 · similarity 0.83)
- Competition among Pairwise Lottery Contests (AAAI 2024 · similarity 0.83)
- Equilibria of the Colonel Blotto Games with Costs (AAAI 2025 · similarity 0.82)
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.