Budget-proposal aggregation

Budget-proposal aggregation (BPA) is a problem in social choice theory. A group has to decide on how to distribute its budget among several issues. Each group-member has a different idea about what the ideal budget-distribution should be. The problem is how to aggregate the different opinions into a single budget-distribution program.

BPA is a special case of participatory budgeting, with the following characteristics:

1. The issues are divisible and unbounded – each issue can be allocated any amount, as long as the sum of allocations equals the total budget.
2. Agents' preferences are given by single-peaked preferences over an ideal budget.

It is also a special case of fractional social choice (portioning), in which agents express their preferences by stating their ideal distribution, rather than by a ranking of the issues.

Another sense in which aggregation in budgeting has been studied is as follows. Suppose a manager asks his worker to submit a budget-proposal for a project. The worker can over-report the project cost, in order to get the slack to himself. Knowing that, the manager might reject the worker's proposal when it is too high, even though the high cost might be real. To mitigate this effect, it is possible to ask the worker for aggregate budget-proposals (for several projects at once). The experiment shows that this approach can indeed improve the efficiency of the process.

The same problem has been studied in the context of aggregating probability distributions. Suppose each citizen in society has a certain probability-distribution over candidates, representing the probability that the citizen prefers each candidate. The goal is to aggregate all distributions to a single probability-distribution, representing the probability that society should choose each candidate.

Rules for the one-dimensional case

The one-dimensional case is the special case in which there are only two issues, e.g. defense and education. In this case, distributions can be represented by a single parameter: the allocation to issue #1 (the allocation to issue #2 is simply the total budget minus the allocation to issue #1). It is natural to assume that the agents have single-peaked preferences, that is: between two options that are both larger, or both smaller, than their ideal allocation, they prefer the option that is closer to their ideal allocation.

This setting is similar to a one-dimensional facility location problem: a certain facility (e.g. a public school) has to be built on a line; each voter has an ideal spot on the line in which the facility should be built (nearest to his own house); and the problem is to aggregate the voters' preferences and decide where on the line the facility should be built.

The average rule

Main article: Average voting rule

The average voting rule is an aggregation rule that simply returns the arithmetic mean of all individual distributions. It is the unique rule that satisfies the following three axioms:

• Completeness: for every n distributions, the rule returns a distribution.
• Unanimity for losers: if an issue receives 0 in all individual distributions, then it receives 0 in the collective distribution.
• Strict and equal sensitivity to individual allocations: if one voter increases his allocation to one issue, while all other allocations remain the same, then the collective allocation to this issue strictly increases; moreover, the rate of increase is the same for all voters – it depends only on the issue.

But the average rule is not incentive-compatible, and is very easy to manipulate. For example, suppose there are two issues, the ideal distribution of Alice is (80%, 20%), and the average of the ideal distributions of the other voters is (60%, 40%). Then Alice would be better-off by reporting that her ideal distribution is (100%, 0%), since this will pull the average distribution closer to her ideal distribution.

The median rule

Main article: Median voting rule

The median voting rule for the one-dimensional case is an aggregation rule that returns the median of the ideal budgets of all citizens. It has several advanatages:

• Assuming the agents' preferences are single-peaked, the median rule is strategyproof, and even group strategyproof.
• Assuming further that each agent's utility function is minus the distance between his ideal allocation and the chosen allocation, the median rule is utilitarian – it maximizes the sum of agents' utilities. This also implies that it is Pareto efficient.

But the median rule may be considered unfair, as it ignores the minority opinion. For example, suppose the two issues are "investment in the north" vs. "investment in the south". 49% of the population live in the north and therefore their ideal distribution is (100%,0%), while 51% of the population live in the south and therefore their ideal distribution is (0%,100%), The median rule selects the distribution (0%,100%), which is unfair for the citizens living in the north.

This fairness notion is captured by proportionality (PROP), which means that, if all agents are single-minded (want either 0% or 100%), then the allocation equals the fraction of agents who want 100%. The average rule is PROP but not strategyproof; the median rule is strategyproof but not PROP.

Median with phantoms

The median rule can be generalized by adding fixed votes, that do not depend on the citizen votes. These fixed votes are called "phantoms". Forr every set of phantoms, the rule that chooses the median of the set of real votes + phantoms is strategyproof; see median voting rule for examples and characterization.

The Uniform Phantom median rule (UPM) is a special case of the median rule, with n-1 phantoms at 1/n, ..., (n-1)/n. This rule is strategyproof (like all phantom-median rules), but in addition, it is also proportional. It has several characerizations:

• UPM is the only rule satisfying continuity, anonymity, strategyproofness and proportionality among all symmetric single-peaked preferences.
• UPM is the only rule satisfying strategyproofness and proportionality among all single-peaked preferences.

Proportional fairness

Aziz, Lam, Lee and Walsh study the special case in which the preferences are single-peaked and symmetric, that is: each agent compares alternatives only by their distance from his ideal point, regardless of the direction. In particular, they assume that each agent's utility is 1 minus the distance between his ideal point and the chosen allocation. They consider several fairness axioms:

• Individual fair share (IFS) means that each agent's utility is at least 1/n (that is, the distance from his ideal point to the allocation is at most 1-1/n);
• Proportionality means that, if all agents are single-minded and want either 0% or 100%, then the allocation equals the fraction of agents who want 100%.
• Unanimity means that, if all agents agree on an allocation, then this allocation should be chosen.
• Unanimous fair share (UFS) means that, for each group of size k with exactly the same ideal point, the utility of each group member is at least k/n (this is analogous to requirements of justified representation).
  • UFS implies IFS (take k=1), unanimity (take k=n) and proportionality (take k=number of agents whose ideal point is 100%).
• Proportional fairness (PF) means that, for each group of size k with ideal points in an interval of radius r, the utility of each group member is at least k/n-r. PF implies UFS (take r=0). All implications are strict.

The following is known about existing rules:

• The median rule is strategyproof. It satisfies unanimity, but not IFS or PROP (hence not UFS or PF).
• The egalitarian rule (- selecting the midpoint between the smallest and largest ideal point) satisfies unanimity and IFS, but not PROP (hence not UFS or PF). It is also not strategyproof.
• The Nash rule (- selecting an allocation that maximizes the product of agents' utilities) satisfies PF (hence all other fairness properties), but it is not strategyproof.
• The uniform phantom median rule satisfies PF (hence all other fairness properties), and it is also strategyproof.

They prove the following characterizations:

• Every rule that satisfies IFS, unanimity, anonymity and strategyproofness is a phantom-median mechanism with n-1 phantoms between 1/n and 1-1/n.
• The only rule that satisfies PROP, unanimity and strategyproofness is the Uniform Phantom median rule. Hence, the only rule that satisfies UFS/PF and strategyproofness is UPM.

Border and Jordan prove that the only rule satisfying continuity, anonymity, proportionality and strategyproofness is UPM.

Average vs. median

Rosar compares the average rule to the median rule when the voters have diverse private information and interdependent preferences. For uniformly distributed information, the average report dominates the median report from a utilitarian perspective, when the set of admissible reports is designed optimally. For general distributions, the results still hold when there are many agents.

Rules for the multi-dimensional case

When there are more than two issues, the space of possible budget-allocations is multi-dimensional. Extending the median rule to the multi-dimensional case is challenging, since the sum of the medians might be different than the median of the sum. In other words, if we pick the median on each issue separately, we might not get a feasible distribution.

In the multi-dimensional case, aggregation rules depend on assumptions on the utility functions of the voters.

L1 utilities

A common assumption is that the utility of voter i, with ideal budget (peak) p_i, from a given budget allocation x, is minus the L1-distance between p_i and x. Under this assumption, several aggregation rules were studied.

Utilitarian rules

Lindner, Nehring and Puppe consider BPA with discrete amounts (e.g. whole dollars). They define the midpoint rule: it chooses a budget-allocation that minimizes the sum of L1-distances to the voters' peaks. In other words, it maximizes the sum of utilities – it is a utilitarian rule. They prove that the set of midpoints is convex, and that it is locally determined (one can check if a point is a midpoint only by looking at its neighbors in the simplex of allocations). Moreover, they prove that the possibility of strategic manipulation is limited: a manipulating agent cannot make the closest midpoint closer to his peak, nor make the farthest midpoint closer to his peak. As a consequence, the midpoint rule is strategyproof if all agents have symmetric single-peaked preferences.

Goel, Krishnaswamy, Saskhuwong and Aitamurto consider BPA in the context of participatory budgeting with divisible projects: they propose to replace the common voting format of approving k projects with "knapsack voting". With discrete projects, this means that each voter has to select a set of projects whose total cost is at most the available budget; with divisible projects, this means that each voter reports his ideal budget-allocation. Now, each project is partitioned into individual "dollars"; for dollar j of project i, the number of votes is the total number of agents whose ideal budget gives at least j to project i. Given the votes, the knapsack-voting rule selects the dollars with the highest amount of support (as in utilitarian approval voting). They prove that, with L1-utilities, the knapsack voting is strategyproof and utilitarian (and hence efficient).

Both utilitarian rules are not "fair" in the sense that they may ignore minorities. For example, if 60% of the voters vote for the distribution (100%,0%) whereas 40% vote for (0%,100%), then the utilitarian rules would choose (100%,0%) and give nothing to the issue important for the minority.

Moving phantoms rules

Freeman, Pennock, Peters and Vaughan suggest a class of rules called moving-phantoms rules, where there are n+1 phantoms that increase continuously until the outcome equals the total budget. They prove that all these rules are strategyproof. The proof proceeds in two steps. (1) If an agent changes his reported peak, but all the phantoms are fixed in place, then we have a median voting rule in each issue, so the outcome in each issue either stays the same or goes farther from the agent's real peak. (2) as the phantoms move, the outcome in some issues may move nearer to the agent's real peak, but the agent's gain from this is at most the agent's loss in step 1.

Note that the proof of (2) crucially relies on the assumption of L1 utilities, and does not work with other distance metrics. For example, suppose there are 3 issues and two agents with peaks at (20,60,20) and (0,50,50). One moving-phantoms rule (the "independent markets" rule below) returns (20,50,30), so agent 1's L1 disutility is 10+10+0=20 and L2 disutility is sqrt(100+100+0)=sqrt(200). If agent 1 changes his peak to (30,50,20), then the rule returns (25,50,25). Agent 1's L1 disutility is 5+10+5=20 and L2 disutility is sqrt(25+100+25)=sqrt(150). Agent 1 does not gain in L1 disutility, but does gain in L2 disutility.

Independent markets rule

A particular moving-phantoms rule is the Independent Markets rule. In addition to strategyproofness, it satisifes a property that they call proportionality: if all agents are single-minded (each agent's ideal budget allocates 100% of the budget to a single issue), then the rule allocates the budget among the issues proportionally to the number of their supporters. However, this rule is not efficient (in fact, the only efficient moving-phantom rule is the utilitarian rule). A demo of the Independent Markets rule, and several other moving-phantoms rules, is available online..

Piecewise-uniform rule

Caragiannis, Christodoulou and Protopapas extended the definition of proportionality from single-minded preference profiles to any preference profile. They define the proportional outcome as the arithmetic mean of peaks. The only mechanism which is always proportional is the average rule, which is not strategyproof. Hence, they define the L1 distance between the outcome of a rule and the average as the degree of dis-proportionality. The disproportionality of any budget-allocation is between 0 and 2. They evaluate BPA mechanisms by their worst-case disproportionality. In BPA with two issues, they show that UPM has worst-case disproportionality 1/2. With 3 issues, the independent-markets mechanism may have disproportionality 0.6862; they propose another moving-phantoms rule, called Piecewise-Uniform rule, which is still proportional, and has disproportionality ~2/3. They prove that the worst-case disproportionality of a moving-phantoms mechanism on m issues is at least 1-1/m, and the worst-case disproportionality of any truthful mechanism is at least 1/2; this implies that their mechanisms attain the optimal disproportionality.

Ladder rule

Freeman and Schmidt-Kraepelin study a different measure of dis-proportionality: the L-infinity distance between the outcome and the average (i.e., the maximum difference per project, rather than the sum of differences). They define a new moving-phantoms rule called the Ladder rule, which underfunds a project by at most 1/2-1/(2m), and overfunds a project by at most 1/4; both bounds are tight for moving-phantoms rules.

Other rules

It is an open question whether every anonymous, neutral, continuous and strategyproof rule is a moving-phantoms rule.

Elkind, Suksompong and Teh define various axioms for BPA with L1-disutilities, analyze the implications between axioms, and determine which axioms are satisfied by common aggregation rules. They study two classes of rules: those based on coordinate-wise aggregation (average, maximum, minimum, median, product), and those based on global optimization (utilitarian, egalitarian).

Convex preferences

Nehring and Puppe aim to derive decision rules with as few assumptions as possible on agents' preferences; they call this the frugal model. They assume that the social planner knows the agents' peaks, but does not know their exact preferences; this leads to uncertainty regarding how many people prefer an alternative x to an alternative y.

Given two alternatives x and y, x is a necessary majority winner if it wins over y according to all preferenes in the domain that are consistent with the agents' peaks; x is majority admissible if no other alternative is a necessary-majority-winner over x. Given two alternatives x and y, x is an ex-ante majority winner if its smallest possible number of supporters is at least as high as the smallest possible number of supporters of y, which holds iff its largest possible number of supporters is at least as high as the largest possible number of supporters of y. x is an ex-ante Condorcet winner (EAC) if it is an ex-ante majority winner over every other alternative.

They assume that agents' preferences are convex, which in one dimension is equivalent to single-peakedness. But convexity alone is not enough to attain meaningful results in two or more dimensions (if the peaks are in general position, then all peaks are EAC winners). So they consider two subsets of convex preferences: homogenous quadratic preferences, and separable convex preferences.

• In the homogeneous quadratic model, an EAC winner always exists and it is always a Tukey median.
• In the separable convex model, an EAC winner may not exist, but a "local" EAC winner exists and it minimizes the sum of L1 -distances to the agents’ peaks. This solution can be efficiently computed using a spreadsheet. Note that, even with separable convex preferences, the only strategyproof rules are dictatorships.

They study BPA allowing lower and upper bounds on the spending on each issue.

Fain, Goel and Munagala assume that agents have additive concave utility functions, which represent convex preferences over bundles. In particular, for each agent i and issue j there is a coefficient a_i,j, and for each issue j there is an increasing and strictly concave function g_j; the total utility of agent i from budget allocation x is: $u_{i}(x)=\sum _{j=1}^{m}a_{i,j}\cdot g_{j}(x_{j})$. They study the Lindahl equilibrium of this problem, prove that it is in the core (which is a strong fairness property), and show that it can be computed in polynomial time.

Wagner and Meir study a generalization of BPA in which each agent may propose, in addition to a budget-allocation, also an amount t of tax (positive or negative) that will be taken from all agents and added to the budget. For each agent i there is a coefficient a_i,f that represents the utility of monetary gains and losses, and there is a function f which is strictly convex for negative values and strictly concave for positive values, and $u_{i}(x,d)=\sum _{j=1}^{m}a_{i,j}\cdot g_{j}(x_{j})+a_{i,f}\cdot f(d)$, where d is the monetary gain (which can be negative). For this utility model, they present a variant of the Vickrey–Clarke–Groves mechanism that is strategyproof, but requires side-payments (in addition to the tax).

Empirical evidence

Puppe and Rollmann present a lab experiment comparing the average voting rule and a normalized median voting rule in multidimensional budget aggregation setting. Under the average rule, people act in equilibrium when the equilibrium strategies are easily identifiable. Under normalized median rule, many people play best responses, but these best responses are usually not exactly truthful. Still, the median rule attains much higher social welfare than the average rule.

See also

• Belief aggregation – a similar problem in which experts report probability distributions, and the goal is to select a single probability distribution aggregating their different opinions.
• Spatial model of voting – another model in which agents' preferences are fully determined by their top choice.