Maxmin Participatory Budgeting: A Novel Way for Empowered Citizens to Select Public Projects
Participatory Budgeting (PB) is a popular voting method for dividing a budget among a set of projects, based on the voters’ preferences over the projects. PB is broadly categorised as divisible PB (fractionally implementable projects) and indivisible PB (atomic projects). Egalitarianism, an important objective in PB, has not received much attention in the indivisible PB context. This study addresses this gap through a detailed study of a natural egalitarian rule, Maxmin Participatory Budgeting (MPB), in the context of indivisible PB. We show the superiority of MPB to two popular existing methods namely Social welfare Maximizing (SW) and Proportionality. Our study is in two parts: computational and axiomatic. In the first, 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 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. We propose a new axiom, maximal coverage, which captures fairness aspects. We prove that MPB satisfies maximal coverage.
Gogulapati Sreedurga, Mayank Ratan Bhardwaj, Yadati Narahari: Maxmin Participatory Budgeting. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-2022). pp. 489-495.