Participatory budgeting algorithm


A participatory budgeting algorithm is an algorithm for implementing participatory budgeting.
The inputs to a PB algorithm are: a list of possible projects that require funding, the total available budget for funding the projects, and the preferences of voters over the project. The output of a PB algorithm is a partition of budget among the projects - determining how much money to allocate to each project.
A PB algorithm can treat the projects as either divisible or indivisible:
An important consideration in designing a PB algorithm is what input format to use for preference elicitation - how each voter should express his/her preferences over the projects. Several input formats used in practice are:
These input formats are problematic for indivisible PB, since they ignore the different costs of the projects. Some newer input formats, which do consider the costs, are:
The various input formats can be compared based in terms of implicit utilitarian voting - how much each input-format is useful in maximizing the sum of utilities. From this perspective, threshold approval voting is superior to knapsack voting, ranking-by-value and ranking-by-value-for-money: it minimizes the distortion from the maximum sum-of-utilities both theoretically and empirically.
After the system receives the citizens' inputs, it should compute a budget. There are various criteria by which a budget can be evaluated.

Knapsack budgeting

The budgeting method most common in practice is a greedy solution to a variant of the knapsack problem: the projects are ordered by decreasing order of the number of votes they received, and selected one-by-one until the budget is full. Alternatively, if the number of projects is sufficiently small, the knapsack problem may be solved exactly, by selecting a subset of projects that maximizes the total happiness of the citizens. The disadvantage of this method, often called individually-best knapsack budgeting, is that it may be unfair towards minorities: if 51% of the population support 10 projects and 49% support 10 other projects, and the money suffices only for 10 projects, then knapsack budgeting will choose the 10 projects supported by the 51%, and ignore the 49% altogether.
Two alternatives to individually-best knapsack are:
Unfortunately, for general utility domains, both these rules are NP-hard to compute. However, diverse-knapsack is polynomially-solvable in specific preference domains, or when the number of voters is small.

Majority budgeting

One such criterion is the Condorcet criterion: the selected budget should be at least as good as any other proposed budget, according to a majority of the voters. There exists a polynomial-time algorithm for finding such a budget. The algorithm uses Schwartz sets.

Proportional budgeting

Another set of criteria is related to proportional representation. These criteria generalize the justified representation criteria from multi-winner voting. The idea of these criteria is that, if there is a sufficiently large group of voters who all agree on a specific project, then this project should receive a sufficiently large part of the budget.
The expressions below formalize this intuition for the case of indivisible PB and approval voting, i.e.:
Below, L denotes the budget limit.
Unfortunately, Strong BJR budgets may not exist. For example, suppose there are two projects with cost 2, the budget-limit is 3, and there are two voters each of whom desires a single project. Then, each voter is a group of size 1 > 2/3, so BJR requires that the project of each voter is funded, but the sum of costs of both projects is 4>3. Therefore, weaker variants of these criteria have been suggested:
Fortunately, Weak BPJR budgets always exist and can be found by a super-polynomial algorithm. Finding a weak-BPJR budget is NP-hard, but finding a weak-BJR budget can be done by a polynomial greedy algorithm.
Another criterion, Weak Local BPJR, is weaker than weak BPJR but stronger than weak BJR; it can be found by a polynomial-time algorithm based on Phragmen's sequential rule.
Each of these criteria has a weaker variant where, instead of the external budget-limit L, the denominator is W, which is the actual amount used for funding. Since usually W<L, the W-variants are easier to satisfy than their L-variants.

Core budgeting

For the case of divisible PB and utility voting, a compelling budgeting method is one based on the core of the underlying game. A budget is considered "in the core" if no subset of k voters can take their share of the budget and fund a subset of the projects such that the utility of each voter in the subset strictly increases. There are efficient algorithms for calculating the core budget for some natural classes of utility functions.

Donor coordination

The donor coordination problem is a variant of divisible PB in which the budget is donated by the voters themselves. A coordination algorithm can improve the efficiency of the distribution of funds. For example, suppose three projects are considered: theater, chess club, and basketball field. There are two donors: Alice and Bob, each of whom wants to contribute 3000. Alice prefers indoor activities, while Bob prefers competitive activities.
Since the donations are voluntary, it is important that the coordination algorithm ensures that each voter weakly gains from participating in the algorithm, i.e., the amount contributed to projects he approves of is weakly higher when he participates than when he does not. This requirement may be incompatible with efficient budget allocation when the voters' utilities are general linear functions.
However, it is attainable when the voters' utilities are linear and binary, i.e., in the approval voting model:
Several rules have been analyzed in this setting. They are exemplified below for a setting with 4 charities and 5 donors who contribute 1 each, and whose beloved sets are ac, ad, bc, bd, a.