Combinatorial participatory budgeting

Part of the Politics series
Direct democracy
Referendum types
Referendums by country
Referendums by issue
Referendums by method
History of direct democracy
Related
icon Politics portal


Combinatorial participatory budgeting,[1] also called indivisible participatory budgeting[2] or budgeted social choice,[3] is a problem in social choice. There are several candidate projects, each of which has a fixed costs. There is a fixed budget, that cannot cover all these projects. Each voter has different preferences regarding these projects. The goal is to find a budget-allocation - a subset of the projects, with total cost at most the budget, that will be funded. Combinatorial participatory budgeting is the most common form of participatory budgeting.

Combinatorial PB can be seen as a generalization of committee voting: committee voting is a special case of PB in which the "cost" of each candidate is 1, and the "budget" is the committee size. This assumption is often called the unit-cost assumption. The setting in which the projects are divisible (can receive any amount of money) is called portioning,[4][5] fractional social choice, or budget-proposal aggregation.

PB rules have other applications besides proper budgeting. For example:[6]

  • Selecting validators in consensus protocols, such as the blockchain;
  • Selecting web pages that should be displayed in response to user queries;
  • Locating public facilities;
  • Improving the quality of genetic algorithms.
  1. ^ Aziz, Haris; Shah, Nisarg (2021), Rudas, Tamás; Péli, Gábor (eds.), "Participatory Budgeting: Models and Approaches", Pathways Between Social Science and Computational Social Science: Theories, Methods, and Interpretations, Computational Social Sciences, Cham: Springer International Publishing, pp. 215–236, arXiv:2003.00606, doi:10.1007/978-3-030-54936-7_10, ISBN 978-3-030-54936-7, S2CID 211027484, retrieved 2023-10-15
  2. ^ Cite error: The named reference :10 was invoked but never defined (see the help page).
  3. ^ Lu, Tyler; Boutilier, Craig (2011-07-16). "Budgeted social choice: from consensus to personalized decision making". Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence - Volume Volume One. IJCAI'11. Barcelona, Catalonia, Spain: AAAI Press: 280–286. ISBN 978-1-57735-513-7.
  4. ^ Airiau, Stéphane; Aziz, Haris; Caragiannis, Ioannis; Kruger, Justin; Lang, Jérôme; Peters, Dominik (2023-01-01). "Portioning using ordinal preferences: Fairness and efficiency". Artificial Intelligence. 314: 103809. doi:10.1016/j.artint.2022.103809. ISSN 0004-3702.
  5. ^ Elkind, Edith; Suksompong, Warut; Teh, Nicholas (2023), "Settling the Score: Portioning with Cardinal Preferences", ECAI 2023, Frontiers in Artificial Intelligence and Applications, IOS Press, pp. 621–628, arXiv:2307.15586, doi:10.3233/FAIA230324, ISBN 9781643684369
  6. ^ Pierczyński, Grzegorz; Skowron, Piotr; Peters, Dominik (2021-11-09). "Proportional Participatory Budgeting with Additive Utilities". Proceedings of NeurIPS 2021. arXiv:2008.13276.