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;
^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, ISBN9781643684369