Maxmin Participatory Budgeting
This work addresses fairness in participatory budgeting for indivisible projects, offering computational and axiomatic insights, though it is incremental as it builds on existing PB frameworks.
The paper tackles the lack of egalitarian focus in indivisible participatory budgeting by studying the Maxmin Participatory Budgeting rule, proving computational hardness and providing algorithms with pseudo-polynomial time and polynomial-time parameterized solutions, along with empirical exact optimal results on real-world datasets and an axiomatic analysis introducing a new fairness axiom.
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.