# Maxmin Participatory Budgeting

arXiv: https://arxiv.org/abs/2204.13923 · HTML: https://mlsanity.com/paper/2204.13923/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 34 references that are in the map.
- First posted on arXiv 29 Apr 2022.

## Builds on (most cited first, 9 of 9)

- [Proportional Participatory Budgeting with Additive Utilities](https://mlsanity.com/paper/2008.13276/) (2020)
- [Participatory Budgeting: Models and Approaches](https://mlsanity.com/paper/2003.00606/) (2020)
- [Fair mixing: the case of dichotomous preferences](https://mlsanity.com/paper/1712.02542/) (2017)
- [Knapsack Voting for Participatory Budgeting](https://mlsanity.com/paper/2009.06856/) (2020)
- [Proportionally Representative Participatory Budgeting: Axioms and Algorithms](https://mlsanity.com/paper/1711.08226/) (2017)
- [Proportionally Representative Participatory Budgeting with Ordinal Preferences](https://mlsanity.com/paper/1911.00864/) (2019)
- [A Framework for Approval-based Budgeting Methods](https://mlsanity.com/paper/1809.04382/) (2018)
- [Pabulib: A Participatory Budgeting Library](https://mlsanity.com/paper/2012.06539/) (2020)
- [What Should We Optimize in Participatory Budgeting? An Experimental Study](https://mlsanity.com/paper/2111.07308/) (2021)

## Built on by (most cited first, 2 of 2)

- [Combinatorial Civic Crowdfunding with Budgeted Agents: Welfare Optimality at Equilibrium and Optimal Deviation](https://mlsanity.com/paper/2211.13941/) (2022)
- [Participatory Budgeting With Multiple Degrees of Projects And Ranged Approval Votes](https://mlsanity.com/paper/2305.10972/) (2023)

## Abstract (arXiv)

Participatory Budgeting (PB) is a popular voting method by which a limited budget is divided among a set of projects, based on the preferences of voters over the projects. PB is broadly categorised as divisible PB (if the projects are fractionally implementable) and indivisible PB (if the projects are atomic). Egalitarianism, an important objective in PB, has not received much attention in the context of indivisible PB. This paper addresses this gap through a detailed study of a natural egalitarian rule, Maxmin Participatory Budgeting (MPB), in the context of indivisible PB. Our study is in two parts: (1) computational (2) axiomatic. In the first part, we prove that MPB is computationally hard and give pseudo-polynomial time and polynomial-time algorithms when parameterized by certain well-motivated parameters. We propose an algorithm that achieves for MPB, additive approximation guarantees for restricted spaces of instances and empirically show that our algorithm in fact gives exact optimal solutions on real-world PB datasets. We also establish an upper bound on the approximation ratio achievable for MPB by the family of exhaustive strategy-proof PB algorithms. In the second part, we undertake an axiomatic study of the MPB rule by generalizing known axioms in the literature. Our study leads to the proposal of a new axiom, maximal coverage, which captures fairness aspects. We prove that MPB satisfies maximal coverage.