Combinatorial participatory budgeting

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 also called portioning ^{[4] [5]} or fractional social choice.

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.

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. ^[7] 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. ^{[2] [8]} 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-basedsatisfaction assumes that an agent's utility equals the total cost of his approved projects that are funded.
• Decreasing-normalized-satisfaction (DNS) functions ^[8] 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 ^[7] study greedy algorithms for cardinality-based, cost-based and Chamberlin-Courant utilities, as resolute (single-valued) rules. Baumeister, Boes and Seeger ^[9] complement their work by studying irresolute (multi-valued) rules, and introduce hybrid greedy rules.

Sreedurga, Bhardwaj and Narahari ^[10] 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 ^[11] 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 ^[12] 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. ^{[13] [14]} 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. ^[12] 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. ^[6] 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. ^[15]

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 ^[15] 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. ^[16] It was adapted to PB by Aziz, Lee and Talmon (though they call it 'Phragmen's rule'). ^[17] 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. ^[6]

• 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 ^[18] 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 ^[19] 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 ^[20] 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 that 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^{[ clarification needed ]}, such as knapsack budgeting, will choose the 10 projects in the north, and no projects in the south, which is unfair to the southerners. ^[12]

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. ^[6]

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 ${\displaystyle |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 ${\displaystyle \sum _{x\in P}\min _{i\in N}u_{i}(x)}$. ^{[2] : Sec.5} 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, many fairness notions have been defined; see Rey and Maly ^[2] 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. ^{[2] : 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 onemember 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. ^{[6] : 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):

• 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 ${\displaystyle |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 ${\displaystyle 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 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:

• 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. ^[21]

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). ^{[2] : 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:

• 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 ^{[6] : Thm.2} 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 ^[22] 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. ^[22]

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 ${\displaystyle \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 ^[17] ).

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. ^[21]

Analogously to EJR-x, one can define PJR-x, which means PJR up to any project. Brill, Forster, Lackner, Maly and Peters ^[22] 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 ^[17] 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. ^[17]

Ordinal JR conditions

Aziz and Lee ^[20] extend the justified-representation notions to weak-ordinal ballots, which contain approval ballots as a special case. They extend the notion of a cohesive group to a solid coalition, and define two incomparable proportionality notions: Comparative Proportionality for Solid Coalitions (CPSC) and Inclusion Proportionality for Solid Coalitions (IPSC). CPSC may not always exist, but IPSC always exists and can be found in polynomial time. Equal Shares satisfies PSC - a weaker notion than both IPSC and CPSC. ^[6]

Core fairness

One way to assess 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 ${\displaystyle |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 onemember 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. ^[23]

However, for indivisible PB, the weak core might be empty even with unit costs. For example: ^[6] 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 utility values (e.g. 2, 1, 0).

With only 2 utility values (i.e., approval ballots), it is an open question whether a weak-core allocation always exists, with or without unit costs; both with cardinality-satisfaction and cost-satisfaction. ^[6]

Some approximations to the core can be attained: Equal Shares attains a multiplicative approximation of ${\displaystyle 4\log(2{\frac {u_{\max }}{u_{\min }}})}$. ^[6] Munagala, Shen, Wang and Wang ^[24] 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 ^{[25] [26]} consider a different notion of approximation called entitlement-approximation; they prove that a 32-approximate core by this notion always exists.

Priceability

Priceability means that ^[6] it is possible to assign a fixed budget to each voter, and split each voter's budget among candidates he approves, such that each elected candidate is 'bought' by the candidates who approve him, and no unelected candidate can be bought by the remaining money of the voters who approve him. MES can be viewed as an implementation of Lindahl equilibrium in the discrete model, with the assumption that the customers sharing an item must pay the same price for the item. ^[27] The definition is the same for cardinal ballots as for approval ballots.

A priceable allocation is computed by the rules of Equal Shares (for cardinal ballots), ^[6] Sequential Phragmen (for approval ballots), ^[15] and Maximin Support (for approval ballots). ^[22]

With approval ballots, priceability implies PJR-x for cost-based satisfaction. Moreover, a slightly stronger priceability notion implies PJR-x simultaneously for all DNS satisfaction functions. This stronger notion is satisfied by Equal Shares with cardinality satisfaction, Sequential Phragmen, and Maximin Support. ^[22]

Laminar fairness

Laminar fairness ^{[28] [15]} is a condition on instances of a specific structure, called laminar instances. A special case of a laminar instance is an instance in which the population is partitioned into two or more disjoint groups, such that each group supports a disjoint set of projects. Equal Shares and Sequential Phragmen are laminar-proportional with unit costs, ^[28] but not with general costs. ^[15]

Fair Share

Maly, Rey, Endriss and Lackner ^{[29] [30]} defined a new fairness notion for PB with approval ballots, that depends only on equality of resources, and not on a particular satisfaction function. The idea was first presented by Ronald Dworkin. ^{[31] [32]} They explain the rationale behind this new notion as follows: "we do not aim for a fair distribution of satisfaction, but instead we strive to invest the same effort into satisfying each voter. The advantage is that the amount of resources spent is a quantity we can measure objectively." They define the share of an agent i from the set P of funded projects as: ${\displaystyle {\text{share}}(P,i):=\sum _{x\in P\cap A_{i}}{\frac {{\text{cost}}(x)}{|\{j:x\in A_{j}\}|}}}$. Intuitively, this quantity represents the amount of resources that society put into satisfying i. For each funded project x, the cost of x contributes equally to all agents who approve x. As an example, suppose the budget is 8, there are three projects x,y,z with costs 6,2,2, four agents with approval ballots xy, xy, y, z.

• If {x,y} is selected, then the share of voters 1,2 is 6/3+2/2=3; the share of voter 3 is 6/3=2; and the share of voter 4 is 0.
• If {x,z} is selected, then the share of voters 1,2,3 is 6/3=2, and the share of voter 4 is 2/1=2, so all voters got the same share.

A budget-allocation satisfies fair share (FS) if the share of each agent is at least min(B/n, share(A_i,i)). Obviously, a fair-share allocation may not exist, for example, when there are two agents each of whom wants a different project, but the budget suffices for only one project. Moreover, even fair-share up-to one project (FS-1) allocation might not exist. For example, suppose B=5, there are 3 projects of cost 3, and the approval ballots are xy, yz, zx. The fair share is 5/3. But in any feasible allocation, at most one project is funded, so there is an agent with no approved funded project. For this agent, even adding one project would increase his share to 3/2=1.5, which is less than 5/3. Checking whether a FS or an FS-1 allocation exists is NP-hard. On practical instances from pabulib, it is possible to give each agent between 45% and 75% of their fair share; MES rules give a larger fraction than sequential Phragmen.

A weaker relaxation, called local fair-share (Local-FS), requires that, for every unfunded project y, there exsits at least one agent i who approves y and has share(X+y, i) > B/n. Local-FS can be satisfied by a variant of the Method of Equal Shares in which the contribution of each agent to funding a project x is proportional to share({x},i), rather than to u_i(x).

Another relaxation is the Extended Justified Share (EJS): it means that, for any group of agents N who can afford a set of projects P, such that every member in N approves all elements of P, there is at least one member i in N for whom share(X,i) ≥ share(P,i). It looks similar to EJR, but they are independent: there are instances in which some allocations are EJS and not EJR, while other allocations are EJR and not EJS. An EJS allocation always exists and can be found by the exponential-time Greedy Cohesive Rule, in time ${\displaystyle O(n\cdot 2^{m})}$; finding an EJS allocation is NP-hard. But the above variant of MES satisfies EJS up-to one project (EJS-1). It is open whether EJS up-to any project (EJS-x) can be satisfied in polynomial time.

District fairness

District fairness is a fairness notion that focuses on the pre-specified districts in a city. Each district i deserves a budget B_i (a part of the entire city budget), which is usually proportional to the population size in the district. In many cities, there is a separate PB process in each district. It may be more efficient to do a single city-wide PB process, but it is important to do so in a way that does not harm the districts. Thus, a city-wide budget-allocation is district fair if it gives each district i at least the welfare it could get by an optimal allocation of B_i.

Hershkowitz, Kahng, Peters and Procaccia ^[33] study the problem of welfare maximization subject to district fairness. They show that finding an optimal deterministic allocation is NP-hard, but finding an optimal randomized allocation that is district-fair in expectation can be done efficiently. Moreover, if it is allowed to overspend (by up to 65%), it is possible to find an allocation that maximizes social welfare and guarantees district-fairness up-to one project.

Monotonicity properties

It is natural to expect that, when some parameters of the PB instance change, the outcome of a PB rule would change in a predictable way. In particular:

• Discount monotonicity says that, if a rule selects project x, and x becomes cheaper, and all other data does not change, the rule would still select x.
• Limit monotonicity (inspired by resource monotonicity and house monotonicity) says that, if a rule selects project x, and the total budget increases, then the rule would still select x.
• Merging monotonicity says that, if a rule selects a set X of projects, and all these projects merge into a single project y (such that cost(y)=cost(X), and every agent approves y iff he approves all projects in X), then the rule selects y.
• Splitting monotonicity says that, if a rule selects a project x, and this project splits into a set of projects Y (such that cost(Y)=cost(x), and every agent approves x iff he approves all projects in Y), then the rule selects at least one project from Y.

Monotonicity properties have been studied for welfare-maximization rules and for their greedy variants. ^{[7] [9] [34]}

Strategic properties

A PB rule is called strategyproof if no voter can increase his utility by reporting false preferences. With unit costs, the rule that maximizes the utilitarian welfare (choosing the B projects with the largest number of approvals) is strategyproof. This is not necessarily true with general costs. Goel, Krishnaswamy, Sakshuwong and Aitamurto ^[35] define an approximation to strategyproof, strategyproof up-to one project, which means that no voter can increase his utility by more than the satisfaction from adding one project. They prove that, with approval ballots and cost-satisfaction, the greedy algorithm, that selects projects by the number of approvals, is strategyproof up-to one project. The result does not hold for cardinality-satisfaction.

The utilitarian rule is not proportional even with unit costs and approval ballots. Indeed, even in committee voting, there is a fundamental tradeoff between strategyproofness and proportionality; see multiwinner approval voting#strategy.

Constraints on the allocation

Often, there are constraints that forbid some subsets of projects from being the outcome of PB. For example:

• some projects are incompatible and cannot be funded together;
• some projects depend on other projects.

Rey, Endriss and de Haan ^[36] develop a general framework to handle any constraints that can be described by propositional logic, by encoding PB instances as judgement aggregation. ^[37] Their framework allows dependency constraints as well as category constraints, with possibly overlapping categories.

Fain, Munagala and Shah ^[38] study a generalization of PB: allocating indivisible public goods, with possible constraints on the allocation. They consider matroid constraints, matching constraints, and packing constraints (which correspond to budget constraints).

Jain, Sornat, Talmon and Zehavi ^[39] assume that projects are partitioned into disjoint categories, and there is a budget limit on each category, in addition to the general budget limit. They study the computational complexity of maximizing the social welfare subject to these constraints. In general the problem is hard, but efficient algorithms are given for settings with few categories.

Patel, Khan and Louis ^[40] also assume that projects are partitioned into disjoint categories, with both upper and lower quotas on each category. They present approximation algorithms using dynamic programming.

Chen, Lackner and Maly ^[41] assume that projects belong to possibly-overlapping categories, with upper and lower quotas on each category.

Motamed, Soeteman, Rey and Endriss ^[42] show how to handle categorical constraints by reduction to PB with multiple resources.

Extensions

Recently, several extensions of the basic PB model have been studied.

The shortlisting stage

Rey, Endriss and de Haan ^[43] consider an important stage that occurs, in real-life PB implementations, before the voting stage: choosing a short list of projects that will be presented to the voters. They model this shortlisting stage as a multiwinner voting process in which there is no limit on the total size or cost of the outcome. They analyze several rules that can be used in this stage, to guarantee diversity of the selected projects. They also analyze possible strategic manipulations in the shortlisting stage.

Repeated PB

Lackner, Maly and Rey ^[44] note that, in reality, PB is not a one-time process, but rather a repeating process, that occurs annually. They extend some fairness notions from perpetual voting to PB. In particular, they assume that voters are partitioned into types, and try to achieve fairness to types over time.

Non-additive utilities

Jain, Sornat and Talmon ^[45] assume that the projects may be substitute goods or complementary goods, and therefore the utility an agent receives from a set of projects is not necessarily the sum of utilities of each project. They analyze the computational complexity of welfare maximization in this extended setting. In this work, the interaction structure between the projects is fixed and identical for all voters; Jain, Talmon and Bulteau ^[46] extend the model further by allowing voters to specify individual interaction structures.

Non-fixed costs

Lu and Boutilier ^[3] consider a model of budgeted social choice, which is very similar to PB. In their setting, the cost of each project is the sum of a fixed cost, and a variable cost that increases with the number of agents "assigned" to the project. Motamed, Soeteman, Rey and Endriss ^[42] consider multi-dimensional costs, e.g. costs in terms of money, time, and other resources. They extend some fairness properties and strategic properties to this setting, and consider the computational complexity of welfare maximization.

Uncertain costs

Baumeister, Boes and Laussmann ^[47] assume that costs are uncertain: each cost has a probability distribution, and its actual cost is revealed only when it is completed. To reduce risk, it is possible to implement projects one after the other, so that if the first project costs too much, some later projects can be removed. But might cause some projects to be implemented very late. They show that it is impossible to both maintain a low risk of over-spending, and guarantee that all projects complete in their due time. They adapt the fairness criteria, as well as the Method of Equal Shares, to this setting.

Different degrees of funding

Projects that can be funded in different degrees. ^[1] For example, a new building for youth activities could have 1, 2 or 3 floors; it can be small or large; it can be built from wood or stone; etc. This can be seen as a middle-ground between indivisible PB (which allows only two levels) and divisible PB (which allows continuously many levels). Formally, each project j can be implemented in any degree between 0 and t_j, where 0 means "not implemented at all" and tj is the maximum possible implementation. Each degree of implementation has a cost. The ballots are ranged-approval ballots, that is: each voter gives, for each project, a minimum and a maximum amount of money that should be put into this project.

Sreedurga ^[48] considers utilitarian welfare maximization in this setting. He considers four satisfaction functions:

• Cardinality-based satisfaction assumes that a voter's utility equals the number of projects that are funded between his minimum degree and maximum degree.
• Cost-basedsatisfaction assumes that an agent's utility equals the total cost of projects that are funded between his minimum degree and maximum degree.
• Capped-cost-based satisfaction assumes that an agent's utility equals the total cost of projects that are funded above his minimum degree, where if the funding is higher than his maximum degree, the utility is capped to the maximum degree.
• Distance disutility assumes that an agent has a negative utility, which is - for each project - minus the distance between the actual funding to that project and the agent's approval range for that project.

For cardinality-satisfaction, maximizing the utilitarian welfare can be done in polynomial time by dynamic programming. For the other satisfaction functions, welfare maximization is NP-hard, but can be computed in pseudo-polynomial time or approximated by an FPTAS, and also fixed-parameter tractable for some natural parameters.

Additionally, Sreedurga defines several monotonicity and consistency axioms for this setting. He shows that each welfare-maximization rule satisfies some of these axioms, but no rule satisfies all of them.

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.
• Fractional social choice - can be used to model divisible PB, in which any partition of the available budget among the projects is feasible.
• Donor coordination - an extension of the PB model in which some or all of the money comes from the voters, rather than the government.
• Crowdfunding

External links

• Pabulib - an online collection of real-world participatory budgeting instances.
• Javascript demo of various combinatorial PB rules, in pref.tools website.

Open-source platforms for participatory budgeting

• PBStanford
• Decidim
• AdhocracyPlus

References

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. Rey, Simon; Maly, Jan (2023). "The (Computational) Social Choice Take on Indivisible Participatory Budgeting". arXiv: 2303.00621 [cs.GT].
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 .
7. Talmon, Nimrod; Faliszewski, Piotr (2019-07-17). "A Framework for Approval-Based Budgeting Methods". Proceedings of the AAAI Conference on Artificial Intelligence. 33 (1): 2181–2188. arXiv: 1809.04382 . doi: 10.1609/aaai.v33i01.33012181 . ISSN   2374-3468. S2CID   52195436.
8. Brill, Markus; Forster, Stefan; Lackner, Martin; Maly, Jan; Peters, Jannik (2023). "Proportionality in Approval-Based Participatory Budgeting". arXiv: 2302.03672 [cs.GT].
9. Baumeister, Dorothea; Boes, Linus; Seeger, Tessa (2020-05-13). "Irresolute Approval-based Budgeting". Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems. AAMAS '20. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems: 1774–1776. ISBN   978-1-4503-7518-4.
10. Sreedurga, Gogulapati; Mayank Ratan Bhardwaj; Narahari, Y. (2022). "Maxmin Participatory Budgeting". arXiv: 2204.13923 [cs.GT].
11. Laruelle, Annick (2021-01-16). "Voting to select projects in participatory budgeting". European Journal of Operational Research. 288 (2): 598–604. doi:10.1016/j.ejor.2020.05.063. ISSN   0377-2217. S2CID   219970753.
12. Fluschnik, Till; Skowron, Piotr; Triphaus, Mervin; Wilker, Kai (2019-07-17). "Fair Knapsack". Proceedings of the AAAI Conference on Artificial Intelligence. 33: 1941–1948. doi: 10.1609/aaai.v33i01.33011941 . ISSN   2374-3468.
13. Ashish Goel; Anilesh K. Krishnaswamy; Sukolsak Sakshuwong; Tanja Aitamurto (2016). "Knapsack Voting: Voting mechanisms for Participatory Budgeting" (PDF). S2CID   9240674. Archived from the original (PDF) on 2019-03-05.{{cite journal}}: Cite journal requires |journal= (help)
14. Benadè, Gerdus; Nath, Swaprava; Procaccia, Ariel D.; Shah, Nisarg (2021-05-01). "Preference Elicitation for Participatory Budgeting". Management Science. 67 (5): 2813–2827. doi:10.1287/mnsc.2020.3666. ISSN   0025-1909. S2CID   10710371.
15. Los, Maaike; Christoff, Zoé; Grossi, Davide (2022). "Proportional Budget Allocations: Towards a Systematization". arXiv: 2203.12324 [cs.GT].
16. Sánchez-Fernández, Luis; Fernández-García, Norberto; Fisteus, Jesús A.; Brill, Markus (2022-04-29). "The maximin support method: an extension of the D'Hondt method to approval-based multiwinner elections". Mathematical Programming. 203 (1–2): 107–134. arXiv: 1609.05370 . doi: 10.1007/s10107-022-01805-8 . ISSN   1436-4646.
17. Haris Aziz, Barton E. Lee and Nimrod Talmon (2017). "Proportionally Representative Participatory Budgeting: Axioms and Algorithms" (PDF). Proc. of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2018). arXiv: 1711.08226 . Bibcode:2017arXiv171108226A.
18. Shapiro, Ehud; Talmon, Nimrod (2017-09-18). "A Participatory Democratic Budgeting Algorithm". arXiv: 1709.05839 [cs.GT].
19. Skowron, Piotr; Slinko, Arkadii; Szufa, Stanisław; Talmon, Nimrod (2020). "Participatory Budgeting with Cumulative Votes". arXiv: 2009.02690 [cs.MA].
20. Aziz, Haris; Lee, Barton E. (2021-05-18). "Proportionally Representative Participatory Budgeting with Ordinal Preferences". Proceedings of the AAAI Conference on Artificial Intelligence. 35 (6): 5110–5118. arXiv: 1911.00864 . doi: 10.1609/aaai.v35i6.16646 . ISSN   2374-3468. S2CID   207837615.
21. Aziz, Haris; Brill, Markus; Conitzer, Vincent; Elkind, Edith; Freeman, Rupert; Walsh, Toby (2017-02-01). "Justified representation in approval-based committee voting". Social Choice and Welfare. 48 (2): 461–485. arXiv: 1407.8269 . doi:10.1007/s00355-016-1019-3. ISSN   1432-217X. S2CID   8564247.
22. Brill, Markus; Forster, Stefan; Lackner, Martin; Maly, Jan; Peters, Jannik (2023). "Proportionality in Approval-Based Participatory Budgeting". arXiv: 2302.03672 [cs.GT].
23. Fain, Brandon; Goel, Ashish; Munagala, Kamesh (2016). "The Core of the Participatory Budgeting Problem". In Cai, Yang; Vetta, Adrian (eds.). Web and Internet Economics. Lecture Notes in Computer Science. Vol. 10123. Springer Berlin Heidelberg. pp. 384–399. arXiv: 1610.03474 . doi:10.1007/978-3-662-54110-4_27. ISBN   9783662541104. S2CID   13443635.. Note that what they call "core" is often called the "weak core".
24. Munagala, Kamesh; Shen, Yiheng; Wang, Kangning; Wang, Zhiyi (January 2022). Naor, Joseph (Seffi); Buchbinder, Niv (eds.). Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Philadelphia, PA: Society for Industrial and Applied Mathematics. arXiv: 2110.12499 . doi:10.1137/1.9781611977073.89. ISBN   978-1-61197-707-3. S2CID   239768887.
25. Jiang, Zhihao; Munagala, Kamesh; Wang, Kangning (2020-06-22). "Approximately stable committee selection". Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. STOC 2020. New York, NY, USA: Association for Computing Machinery. pp. 463–472. doi:10.1145/3357713.3384238. ISBN   978-1-4503-6979-4. S2CID   204960804.
26. Munagala, Kamesh; Shen, Yiheng; Wang, Kangning (2022). "Auditing for Core Stability in Participatory Budgeting". In Hansen, Kristoffer Arnsfelt; Liu, Tracy Xiao; Malekian, Azarakhsh (eds.). Web and Internet Economics. Lecture Notes in Computer Science. Vol. 13778. Cham: Springer International Publishing. pp. 292–310. arXiv: 2209.14468 . doi:10.1007/978-3-031-22832-2_17. ISBN   978-3-031-22832-2.
27. Peters, Dominik; Pierczynski, Grzegorz; Shah, Nisarg; Skowron, Piotr (2021). "Market-Based Explanations of Collective Decisions". Proceedings of the AAAI Conference on Artificial Intelligence. AAAI'21. 35 (6): 5656–5663. doi: 10.1609/aaai.v35i6.16710 . S2CID   222132258.
28. Peters, Dominik; Skowron, Piotr (2020-07-13). "Proportionality and the Limits of Welfarism". Proceedings of the 21st ACM Conference on Economics and Computation. EC '20. New York, NY, USA: Association for Computing Machinery. pp. 793–794. arXiv: 1911.11747 . doi:10.1145/3391403.3399465. ISBN   978-1-4503-7975-5. S2CID   208291203.
29. Lackner, Martin; Maly, Jan; Rey, Simon (2021-05-03). "Fairness in Long-Term Participatory Budgeting". Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems. AAMAS '21. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems: 1566–1568. ISBN   978-1-4503-8307-3.
30. Maly, Jan; Rey, Simon; Endriss, Ulle; Lackner, Martin (2023-05-30). "Fairness in Participatory Budgeting via Equality of Resources". Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems. AAMAS '23. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems: 2031–2039. arXiv: 2205.07517 . ISBN   978-1-4503-9432-1.
31. Dworkin, Ronald (1981). "What is Equality? Part 1: Equality of Welfare". Philosophy & Public Affairs. 10 (3): 185–246. ISSN   0048-3915. JSTOR   2264894.
32. Dworkin, Ronald (2001), "What is Equality? Part 2: Equality of Resources", The Notion of Equality, Routledge, pp. 143–205, doi:10.4324/9781315199795-7, ISBN   978-1-315-19979-5 , retrieved 2023-10-24
33. Hershkowitz, D. Ellis; Kahng, Anson; Peters, Dominik; Procaccia, Ariel D. (2021-05-18). "District-Fair Participatory Budgeting". Proceedings of the AAAI Conference on Artificial Intelligence. 35 (6): 5464–5471. arXiv: 2102.06115 . doi: 10.1609/aaai.v35i6.16688 . ISSN   2374-3468. S2CID   221713786.
34. Rey, Simon; Endriss, Ulle; Haan, Ronald de (2020-07-09). "Designing Participatory Budgeting Mechanisms Grounded in Judgment Aggregation". Proceedings of the Seventeenth International Conference on Principles of Knowledge Representation and Reasoning. Vol. 17. pp. 692–702. doi:10.24963/kr.2020/71. ISBN   978-0-9992411-7-2. ISSN   2334-1033. S2CID   221335357.
35. Goel, Ashish; Krishnaswamy, Anilesh K.; Sakshuwong, Sukolsak; Aitamurto, Tanja (2019-07-29). "Knapsack Voting for Participatory Budgeting". ACM Transactions on Economics and Computation. 7 (2): 8:1–8:27. arXiv: 2009.06856 . doi: 10.1145/3340230 . ISSN   2167-8375. S2CID   37262721.
36. Rey, Simon; Endriss, Ulle; de Haan, Ronald (2023-07-07). "A general framework for participatory budgeting with additional constraints". Social Choice and Welfare. doi: 10.1007/s00355-023-01462-6 . ISSN   1432-217X. S2CID   259551973.
37. Endriss, Ulle (2016-01-21). Judgment Aggregation (Report).
38. Fain, Brandon; Munagala, Kamesh; Shah, Nisarg (2018-06-11). "Fair Allocation of Indivisible Public Goods". Proceedings of the 2018 ACM Conference on Economics and Computation. EC '18. New York, NY, USA: Association for Computing Machinery. pp. 575–592. doi:10.1145/3219166.3219174. ISBN   978-1-4503-5829-3. S2CID   3331859.
39. Jain, Pallavi; Sornat, Krzysztof; Talmon, Nimrod; Zehavi, Meirav (2021-01-01). Zhou, Zhi-Hua (ed.). "Participatory Budgeting with Project Groups: 30th International Joint Conference on Artificial Intelligence, IJCAI 2021". Proceedings of the 30th International Joint Conference on Artificial Intelligence, IJCAI 2021. IJCAI International Joint Conference on Artificial Intelligence: 276–282.
40. Patel, Deval; Khan, Arindam; Louis, Anand (2020). "Group Fairness for Knapsack Problems". arXiv: 2006.07832 [cs.DS].
41. Chen, Jiehua; Lackner, Martin; Maly, Jan (2022-06-28). "Participatory Budgeting with Donations and Diversity Constraints". Proceedings of the AAAI Conference on Artificial Intelligence. 36 (9): 9323–9330. arXiv: 2104.15075 . doi: 10.1609/aaai.v36i9.21163 . ISSN   2374-3468. S2CID   233476312.
42. Motamed, Nima; Soeteman, Arie; Rey, Simon; Endriss, Ulle (2022). "Participatory Budgeting with Multiple Resources". In Baumeister, Dorothea; Rothe, Jörg (eds.). Multi-Agent Systems. Lecture Notes in Computer Science. Vol. 13442. Cham: Springer International Publishing. pp. 330–347. doi:10.1007/978-3-031-20614-6_19. ISBN   978-3-031-20614-6. S2CID   252357719.
43. Rey, Simon; Endriss, Ulle; Ronald de Haan (2020). "Shortlisting Rules and Incentives in an End-to-End Model for Participatory Budgeting". arXiv: 2010.10309 [cs.GT].
44. Lackner, Martin; Maly, Jan; Rey, Simon (2021-05-03). "Fairness in Long-Term Participatory Budgeting". Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems. AAMAS '21. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems: 1566–1568. ISBN   978-1-4503-8307-3.
45. Jain, Pallavi; Sornat, Krzysztof; Talmon, Nimrod (2021-01-07). "Participatory budgeting with project interactions". Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. IJCAI'20. Yokohama, Yokohama, Japan: 386–392. ISBN   978-0-9992411-6-5.
46. Jain, Pallavi; Talmon, Nimrod; Bulteau, Laurent (2021-05-03). "Partition Aggregation for Participatory Budgeting". Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems. AAMAS '21. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems: 665–673. ISBN   978-1-4503-8307-3.
47. https://www.ijcai.org/proceedings/2022/0011.pdf
48. Sreedurga, Gogulapati (2023). "Participatory Budgeting with Multiple Degrees of Projects and Ranged Approval Votes". arXiv: 2305.10972 [cs.GT].