Problem in social choice
Combinatorial participatory budgeting, also called indivisible participatory budgeting or budgeted social choice, 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, fractional social choice, or budget-proposal aggregation.
PB rules have other applications besides proper budgeting. For example:
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, which is NP-hard in theory but can be solved easily in practice. There are also greedy algorithms that attain a constant-factor approximation of the maximum welfare.
There are many possible utility functions for a given rated ballot:
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:
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.
Phragmen's rule.
This method Phragmen's rules for committee elections. Los, Christoff and Grossi describe it for approval ballots as a continuous process:
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.
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 extends the single transferable vote to participatory budgeting.
Aziz and Lee present a rule called the expanding approvals rule that uses the . 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 that 51% of the population live in the north and 49% live in the south, and that every possible budget . 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. Voting on budgets by simple majority rule will result in the 10 projects in the north being selected, with no projects 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:
Based on these definitions, many fairness notions have been defined; see Rey and Maly for a taxonomy of the various fairness notions. Below, the chosen budget-allocation (the set of projects chosen to be funded) is denote by "X".
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.Sec.5, fn.5
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.Sec.4 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)":
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 formula_1. The total number of voters removed is at most "n"; hence, the total cost of projects added is at most formula_4.
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 means 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:
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).5.1.1.2
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:
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 PetersThm.2 prove