Combinatorial participatory budgeting

A participatory budgeting (PB) rule is an rule used in a participatory budgeting system for aggregating the votes of individual citizens into a final budget.

The inputs to a PB rule are: a list of possible projects that require funding, the total available budget for funding the projects, and the preferences of voters over the projects. The output of a PB algorithm is a budget-allocation - a partition of the available money among the projects - determining how much money to allocate to each project.

A PB rule can treat the projects as either divisible or indivisible, and either bounded or unbounded:

• An indivisible bounded PB rule takes as an input the cost of each project. It returns a subset of the projects, such that the total cost of the selected projects does not exceed the budget. Each selected project is allocated its entire cost, while each unselected project is allocated nothing. It is suited for projects which must be entirely funded in order to operate, such as constructing a new bridge. This setting is sometimes called combinatorial PB.
• An indivisible unbounded PB rule can fund each project in two or more degrees. For example, a project of constructing a new building can have an integral degree, which represents the number of floors in the new building.
• A divisible bounded PB rule may allocate any amount of money to any project, up to a pre-specified cap (which w.l.o.g. can be assumed 1), as long as the sum of allocations equals the budget. It is suited for projects that can be funded fractionally, for example "cleaning the public toilets".
• A divisible unbounded PB rule may allocate any amount of money to any project, with no cap. In other words, its output can be any partition of the budget among the projects. It is suited for dividing money among differeng organizations, in which each additional dollar can be used effectively, such as charity donations. It can also be used for dividing state-budget among ministries, such as education vs. health. This setting is alaso called portioning.

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.

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

• 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.

Input formats

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:

• Approval voting: each voter specifies a subset of the projects that they "approve" (consider as valuable), while the others are considered unapproved. This is like a binary scoring system in which each voter can score each project as either 1 or 0.
• k-approval voting: each voter specifies a subset of their top k projects - the k projects that they consider to be the most valuable.
• Threshold approval voting: given a threshold-value t, each voter specifies the subset of all projects which they value as at least t.
• Ranked voting: each voter specifies an entire preference-relation over the projects, specifying the project that they consider the most valuable, the 2nd-most valuable, etc.
• Cardinal voting: each voter specifies a value for each project.
• Cumulative voting: each voter receives a coin, and has to specify how this coin should be partitioned among the projects.

These input formats ignore the different costs of the projects. Some newer input formats, which do consider the costs, are:

• Knapsack voting: each voter specifies a subset of the projects, such that the total cost of the projects in the subset is at most the budget (regardless of how many projects are in the subset). Thus, each voter has to solve an individual knapsack problem - finding the subset which maximizes their personal utility under the budget constraint. An advantage of knapsack voting is that, if the algorithm scores each project by the number of votes it received, and chooses projects greedily in descending order of score, then knapsack voting is a partially truthful mechanism.
• Value-for-money ranking: each voter ranks the projects, not according to their total value, but according to their value/cost ratio.

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.

A third input format, particualrly suited for divisible PB, lets users report their entire ideal budget, that is, specify exactly how much money should be given to each project (see Budget-proposal aggregation).

After the system receives the citizens' inputs, it should compute a budget. Various classes of rules have been suggested.

Welfare-maximization rules

One class of rules aims to maximize a given social welfare function. In particular, the utilitarian rule aims to find a budget-allocation that maximizes the sum of agents' utilities. With cardinal voting, finding a utilitarian budget-allocation requires solving a knapsack problem. It is NP-hard, but can be solved reasonably fast in practice. There are also greedy algorithms that attain a constant-factor approximation of the maximum welfare.

With approval voting, there is an additional complication: we have to map the agents' approvals to utilities. Such a map is known as a satisfaction function. Several satisfaction functions are known:

• Chamberlin-Courant satisfaction assumes that an agent's utility is 1 if at least one of his approved projects is funded, and 0 otherwise.
• Cardinality-based satisfaction assumes that an agent's utility equals the number of his approved projects that are funded.
• Cost-based satisfaction assumes that an agent's utility equals the total cost of his approved projects that are funded.
• Decreasing-normalized-satisfaction (DNS) functions are satisfaction functions that are weakly-increasing with the cost, but the increase-rate is not faster than the cost. Cardinality-satisfaction is one extreme, in which satisfaction does not change with the cost; cost-based is another extreme, in which satisfaction grows exactly like the cost. In between, there are utility functions such as the square-root of the cost, or the logarithm of the cost. Approval-based satisfaction assumes that there is a function sat that maps a set of projects to a positive number, and an agent's utility equals sat(approved-funded-projects). All previous utilities are special cases of approval-based satisfaction functions.

Talmon and Faliszewski study greedy algorithms for cardinality-based, cost-based and Chamberlin-Courant utilities, as resolute (single-valued) rules. Baumeister, Boes and Seeger complement their work by studying irresolute (multi-valued) rules, and introduce hybrid greedy rules.

Sreedurga, Bhardwaj and Narahari study the egalitarian rule, which aims to maximize the smallest utility of an agent. They prove that finding an egalitarian budget-allocation is NP-hard, but give pseudo-polynomial time and polynomial-time algorithms when some natural paramerters are fixed. They propose an algorithm that achieves an additive approximation for restricted spaces of instances, and show that it gives exact optimal solutions on real-world datasets. They also prove that the egalitarian rule satisfies a new fairness axiom, which they call maximal coverage.

Annick Laruelle studies welfare maximization under weak ordinal voting, where a scoring rule is used to translate ranking to utility. She studies a greedy approximation to the utilitarian welfare and for the Chamberlin-Courant welfare. She tests three algorithms on real data from the PB in Portugalete in 2018; the results show that the algorithm including project costs in the ballot performs better than the other two.

Knapsack budgeting

Fluschnik, Skowron, Triphaus and Wilker study maximization of utilitarian welfare, Chamberlin-Courant welfare, and Nash welfare, assuming cardinal utilities.

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 exhausted. 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. Since this method (called "individually-best knapsack") might be unfair to minority groups, they suggest two fairer alternatives:

• Diverse knapsack - maximizing the number of citizens for whom at least one preferred item funded (similarly to the Chamberlin-Courant rule for multiwinner voting).
• Nash-optimal knapsack - maximizing the product of the citizens' utilities.

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.

Proportional approval voting

Proportional approval voting is a rule for multiwinner voting, which was adapted to PB by Pierczynski, Peters and Skowron. It chooses a rule that maximizes the total score, which is defined by a harmonic function of the cardinality-based satisfaction. It is not very popular, since in the context of PB it does not satisfy the strong proportionality guarantees as in the context of multiwinner voting.

Sequential purchase rules

In sequential purchase rules, each candidate project should be "bought" by the voters, using some virtual currency. Several such rules are known.

Sequential Phragmen rule

The sequential phragmen rule generalizes Phragmen's rules for committee elections. Los, Christoff and Grossi describe it for approval ballots as a continuous process:

• Each voter starts with 0 virtual money, and receives money in a constant rate of 1 per second.
• At each time t, we define a not-yet-selected project x as affordable if the total money held by voters who approve x is at least the cost of x.
• At the first time in which some project is affordable, we choose one affordable project y arbitrarily. We add y to the budget, and reset the virtual money of voters who approve y (as they "used" their vitrual money to fund y).
• Voters keep earning virtual money and funding projects, until the next fundable project would bring the total cost over the total available budget; at that point, the algorithm stops.

Maximin support rule

This rule is an adaptation of the sequential Phragmen rule, which allows a redistribution of the loads in each round. It was first introduced as a multiwinner voting rule by Sanchez-Fernandez, Fernandez-Garcia, Fisteus and Brill. It was adapted to PB by Aziz, Lee and Talmon (though they call it 'Phragmen's rule'). They also present an efficient algorithm to compute it.

Method of Equal Shares

This method generalizes the Method of Equal Shares for committee elections. The generalization to PB with cardinal ballots was done by Pierczynski, Peters and Skowron.

• Each voter starts with B/n virtual money, where B is the available budget and n is the number of voters.
• A project x is called r-affordable if it is possible to cover its cost by taking money from agents such that each agent i pays min(current-money-of-i, r*u_i(x)). That is: each agent participates in funding x in proportion to u_i(x). The number r represents the "price per unit of utility" (note that the utilities are normalized to the range [0,1]).
  • In the special case of approval ballots, the utilities are 0 or 1, so a project is r-affordable if it is possible to cover its cost by taking money from agents who approve x, such that each agent i pays min(current-money-of-i, r). Agents with less than r money pay only their current balance.
• We iteratively add to the budget, an r-affordable project for the smallest possible value of r, and decrease the virtual balance of agents who support this project.
• When no more r-affordable projects can be found, for any r, the process stops.

Other rules

Shapiro and Talmon present a polynomial-time algorithm for finding a budget-allocation satisfying the Condorcet criterion: the selected budget-allocation should be at least as good as any other proposed budget, according to a majority of the voters (no proposed change to it has majority support among the votes). Their algorithm uses Schwartz sets.

Skowron, Slinko, Szufa and Talmon present a rule called Minimal Transfers over Costs, that is particularly suited for cumulative voting. It can be seen as an adaptation of Single transferable vote.

Aziz and Lee present a rule called expanding approvals rule, that is particularly suited for weak-ordinal ballots. Pierczynski, Peters and Skowron present a variant of the Method of Equal Shares for weak-ordinal ballots, and show that it is an expanding approvals rule.

Fairness considerations

An important consideration in budgeting is to be fair to both majority and minority groups. To illustrate the challenge, suppose thast 51% of the population live in the north and 49% live in the south; suppose there are 10 projects in the north and 10 projects in the south, each of them costs 1 unit, and the available budget is 10. The rules currently in use, such as knapsack budgeting, will choose the 10 projects in the north, and no project in the south, which is unfair to the southerners.

To partially address this issue, many municipalities perform a separate PB process in each district, to guarantee that each district receives a proportional representation. But this introduces other problems. For example, projects on the boundary of two districts can be voted only by one district, and thus may not be funded even if they are supported by many people from the other district. Additionally, projects without a specific location, that benefit the entire city, cannot be handled. Moreover, there are groups that are not geographic, such as: parents, or bike-riders.

The notion of fairness to groups is formally captured by extending the justified representation criteria from multiwinner voting. The idea of these criteria is that, if there is a sufficiently large group of voters who all agree on a sufficiently large group of projects, then these projects should receive a sufficiently large part of the budget. Formally, given a group N of voters and a set P of projects, we define:

• N can afford P if $|N|\cdot B/n\geq {\text{cost}}(P)$, that is: N is sufficiently large to fund the projects in P with their proportional share of the budget.
• The potential utility of N from P is $\sum _{x\in P}\min _{i\in N}u_{i}(x)$. In particular, in case of approval ballots and cardinal satisfaction, the potential utility is simply the number of projects in P approved by all members in N.

Based on these definitions, we can define several fairness properties. Below, we denote by X the chosen budget-allocation (the set of projects chosen to be funded).

Strong Extended Justified Representation

Strong Extended Justified Representation (SEJR) means that, for every group N of voters that can afford a set P of projects, the utility of every member of N from X is at least as high as the potential utility of N from P. In particular, with approval ballots and cardinal satisfaction, if N can afford P and all members in N approve P, then for each member i in N, at least |P| projects approved by i should be funded.

This property is too strong, even in the special case of approval ballots and unit-cost projects (committee elections) For example, suppose n=4 and B=2. There are three unit-cost projects {x, y, z}. The approval ballots are: {1:x, 2:y, 3:z, 4:xyz}. The group N={1,4} can afford P={x}, and their potential utility from {x} is 1; similarly, {2,4} can afford {y}, and {3,4} can afford {z}. Therefore, SEJR requires that the utility of each of the 4 agent must be at least 1. This can only be done by funding all 3 projects; but the budget is sufficient for only 2 projects. Note that this holds for any satisfaction function.

Fully Justified Representation

Fully Justified Representation (FJR) means that, for every group N of voters who can afford a set P of projects, the utility of at least one member of N from X is at least as high as the potential utility of N from P. In particular, with approval ballots and cardinal satisfaction, if N can afford P, and every member in N approves at least k elements of P, then for at least one member i in N, at least k projects approved by i should be funded.

The "at least one member" clause may make the FJR property seem weak. But note that it should hold for every group N of voters who can afford some set P of projects, so it implies fairness guarantees for many individual voters.

An FJR budget-allocation always exists. For example, in the example above, {a,b,c} satisfies FJR: in {1,2,3} and {3,4,5} and {5,6,7} all agents have utility at least 1, and in {7,8,9} voter #7 has utility at least 1. The existence proof is based on a rule called Greedy Cohesive Rule (GCR):

• Iterate over all 2ⁿ groups of voters. For each group N, search a set P of projects, such that N can afford P, and subject to this, the potential utility of N from P is maximum.
• If such a pair (N,P) is found, all projects in P are funded, all voters in N are removed, and the process repeats.
• If no pair (N,P) is found, the algorithm stops.

It is easy to see that GCR always selects a feasible budget-allocation: whenever it funds a set P of projects, it removes a set N of voters satisfying $|N|\cdot B/n\geq {\text{cost}}(P)$. The total number of voters removed is at most n; hence, the total cost of projects added is at most $n\cdot B/n=B$.

To see that GCR satisfies FJR, consider any group N who can afford a set P, and has potential utility u(N,P). Let i be the member of N who was removed first. Voter i was removed as a member in some other voter-group M, who could afford a set Q, with potential utility u(M,Q). When M was removed, N was available; so the algorithm order implies that u(M,Q) ≥ u(N,P). Since the entire Q is funded, each agent in M - including agent i - receives utility at least u(M,Q), which is at least u(N,P). So the FJR condition is satisfied for i. Note that the proof holds even for non-additive monotone utilities.

GCR runs in time exponential in n. Indeed, finding an FJR budget-allocation is NP-hard even there is a single voter. The proof is by reduction from the knapsack problem. Given a knapsack problem, define a PB instance with a single voter in which the budget is the knapsack capacity, and for each item with weight w and value v, there is a project with cost w and utility v. Let P be the optimal solution to the knapsack instance. Since cost(P)=weight(P) is at most the budget, it is affordable by the single voter. Therefore, his utility in an EJR budget-allocation should be at least value(P). Therefore, finding an FJR budget-allocation yields a solution to the knapsack instance. The same hardness exists even with approval ballots and cost-based satisfaction, by reduction from the subset sum problem.

Extended Justified Representation

Extended Justified Representation (EJR) is a property slightly weaker than FJR. It mean that the FJR condition should apply only to groups that are sufficiently "cohesive". In particular, with approval ballots, if N can afford P, and every member in N approves all elements of P, then for at least one member i in N, the satisfaction from i's approved project in X should be at least as high as the satisfaction from P. In particular:

• with cardinal-based satisfaction, this means that at least |P| projects approved by i should be funded;
• with cost-based satisfaction, this means that some projects approved by i, with total cost at least cost(P), should be funded.

Since FJR implies EJR, an EJR budget-allocation always exists. However, similar to FJR, it is NP-hard to find an EJR allocation. The NP-hardness holds even with approval ballots, for any satisfaction function that is strictly increasing with the cost. But with cardinality-based satisfaction and approval ballots, the Method of Equal Shares finds an EJR budget allocation.

Moreover, checking whether a given budget-allocation satisfies EJR is coNP-hard even with unit costs.

It is an open question, whether an EJR or an FJR budget-allocation can be found in time polynomial in n and B (that is, pseudopolynomial time).

Extended Justified Representation up to One Project

EJR up-to one project (EJR-1) means that, for every group N of voters who can afford a set P of projects, there exists at least one member i in N such that one of the following holds:

• The utility of i from X is at least the potential utility of N from P, or -
• There exists a project y in P such that, the utility of i from X+y is strictly larger than the potential utility of N from P.

With cardinal ballots, EJR-1 is weaker than EJR; with approval ballots and cardinal-satisfaction, EJR-1 is equivalent to EJR. This is because all projects' utilities are 0 or 1. Therefore, if adding a single project makes i's utility strictly larger than u(N,P), then without this single project, i's utility is at least u(N,P).

Pierczynski, Skowron and Peters prove that the Method of Equal Shares, which runs in polynomial time, always finds an EJR-1 budget allocation; hence, with approval ballots and cardinality-based satisfaction, it always finds an EJR budget allocation (even for non-unit costs).

EJR up-to any project (EJR-x) means that, for every group N of voters who can afford a set P of projects, and for every unfunded project y in P, the utility of i from X+y is strictly larger than the potential utility of N from P. Clearly, EJR implies EJR-x which implies EJR-1. Brill, Forster, Lackner, Maly and Peters prove that, for approval ballots and for any satisfaction function with decreasing normalized satisfaction (DNS), if the Method of Equal Shares is applied with that satisfaction function, the outcome is EJR-x.

However, it may not be possible to satisfy EJR-x or even EJR-1 simultaneously for different satisfaction functions: there are instances in which no budget-allocation satisfies EJR-1 simultaneously for both cost-satisfaction and cardinality-satisfaction.

Proportional justified representation

Proportional justified representation (PJR) means that, for every group N of voters who can afford a set P of projects, the group-utility of N from the budget-allocation - defined as $\sum _{x{\text{ is funded }}}\max _{i\in N}u_{i}(x)$ - is at least the potential utility of N from P. In particular, with approval ballots, if N can afford P, and every member in N approves all elements of P, then the satisfaction from the set of all funded projects that are approved by at least one member of N should be at least as high as the satisfaction from P. In particular:

• with cardinal-based satisfaction, this means that at least |P| projects from the union of approval-ses of all members in N should be funded;
• with cost-based satisfaction, this means that projects of total cost at least cost(P), from the union of approval-ses of all members in N, should be funded (PJR for approval ballots with cost-based satisfaction is equivalent to the property called BPJR-L by Aziz, Lee and Talmon).

Since EJR implies PJR, a PJR budget-allocation always exists. However, similar to EJR, it is NP-hard to find a PJR allocation even for a single voter (using the same reduction from knapsack). Moreover, checking whether a given budget-allocation satisfies PJR is coNP-hard even with unit costs and approval ballots.

Analogously to EJR-x, one can define PJR-x, which means PJR up to any project. Brill, Forster, Lackner, Maly and Peters prove that, for approval ballots, the sequential Phragmen rule, the maximin-support rule, and the method of equal shares with cardinality-satisfaction, all guarantee PJR-x simuntaleously for every DNS satisfaction function.

Local JR conditions

Aziz, Lee and Talmon present local variants of the above JR criteria, that can be satisfied in polynomial time. For each of these criteria, they also present a weaker variant where, instead of the external budget-limit B, the denominator is W, which is the actual amount used for funding. Since usually W<B, the W-variants are easier to satisfy than their B-variants.

Core fairness

One way to asses both fairness and stability of budget-allocations is to check whether any given group of voters could attain a higher utility by taking their share of the budget and dividing in a different way. This is captured by the notion of core from cooperative game theory. Formally, a budget-allocation X is in the weak core there is no group N of voters, and an alternative budget-allocation Z of $|N|\cdot B/n$, such that all members of N strictly prefer Z to X.

Core fairness is stronger than FJR, which is stronger than EJR. To see the relation between these conditions, note that, for the weak core, it is sufficient that, for each group N of voters, the utility of at least one member of N from X is at least as high as the potential utility of N from P; it is not required that N should be cohesive.

For the setting of divisible PB and cardinal ballots, a there are efficient algorithms for calculating a core budget-allocation for some natural classes of utility functions.

However, for indivisible PB, the weak core might be empty even with unit costs. For example: suppose there are 6 voters and 6 unit-cost projects, and the budget is 3. The utilities satisfy the following inequalities:

• u1(a) > u1(b) > 0; u2(b) > u2(c) > 0; u3(c) > u3(a) > 0;
• u4(d) > u4(e) > 0; u5(e) > u5(f) > 0; u6(f) > u6(d) > 0.

All other utilities are 0. Any feasible budget-allocation contains either at most one project {a,b,c} or at most one project {d,e,f}. W.l.o.g. suppose the former, and suppose that b and c are not funded. Then voters 2 and 3 can take their proportional share of the budget (which is 1) and fund project c, which will give both of them a higher utility.

Note that the above example requires only 3 utilitiy values (e.g. 2, 1, 0). With 2 utility values (i.e., approval ballots), it is an open question whether a weak-core allocation always exists, with or without unit costs.

Some approximations to the core can be attained: Equal Shares attains a multiplicative approximation of $4\log(2{\frac {u_{\max }}{u_{\min }}})$. Munagala, Shen, Wang and Wang prove that, for arbitrary monotone utilities, a 67-approximate core allocation exists can be computed in polynomial time. For additive utilities, a 9.27-approximate core allocation exists, but it is not known if it can be computed in polynomial time.

Jiang, Munagala and Wang consider a different notion of approximation called entitlement-approximation; they prove that a 32-appoximate core by this notion always exists.

Donor coordination

The donor coordination problem is a variant of divisible PB in which the budget is donated by the voters themselves (rather than fixed in advance). 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 (theater or chess), while Bob prefers competitive activities (chess or basketball).

• If they do not coordinate, then naturally Alice contributes 1500 to each indoor activity, while Bob contributes 1500 to each competitive activity. The resulting distribution is 1500, 3000, 1500. Each donor feels a happiness of 4500 from the donations to his/her preferred projects.
• In contrast, if they coordinate, they can contribute everything to the chess club, so the distribution becomes 0, 6000, 0. Now, each donor feels a happiness of 6000, so this distribution Pareto-dominates the previous one.

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:

• There are m charities; each charity can benefit from any amount of money put into it.
• There are n donors; each donor has a set of charities he/she cares about. Each donor i is willing to donate a total amount of C_i.
• The goal is to decide on a distribution of the total funds collected from all donors (the sum of the C_i) among the m charities. The utility of each agent from a given distribution is the sum of money allocated to his/her beloved charities.

Several rules have been analyzed in this setting. They are exemplified below for a setting with 4 charities (a,b,c,d) and 5 donors who contribute 1 each, and whose beloved sets are ac, ad, bc, bd, a.

• The uncoordinated rule just divides the contribution of each agent i among the charities liked by i. So the funding distribution is 2,1,1,1 and the utilities of the five agents are 3,3,2,2,2. This mechanism is implementable and individually-rational, but not efficient: the outcome is dominated, for example, by the distribution 3,2,0,0, where the utilities are 3,3,2,2,3.
• The Nash-optimal rule finds a budget-allocation maximizing the product of utilities. It is Pareto optimal, implementable and individually-rational. However, it is not Strategyproof nor resource-monotonic.
• The Constrained-utilitarian rule finds a budget-allocation maximizing the sum of utilities from the set of all implementable rules. It is implementable, individually-rational, strategyproof and resource-monotonic. However, it is not Pareto-optimal.
• There is no PB rule that satisfies all five properties, even with binary preferences.

See also

• Multiwinner voting - can be seen as a special case of participatory budgeting, in which the "cost" of each candidate is 1, and the budget is the parliament size.
• Budget-proposal aggregation - a special case of PB in which each voter submits an entire budget-proposal, and a rule aggregates all proposals to a single budget-allocation.