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) the agents' preferences are given by their 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.

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.

The average rule

The average rule is a simple aggregation rule that 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 strategyproof - it is easy to manipulate. For example, if 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.

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 median rule

The median 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:

• As stated by the median voter theorem, the median is a Condorcet winner - it beats every other option in a majority vote.
• Assuming the agents' preferences are single-peaked, the median rule is strategyproof, and even group strategyproof.
• Assuming 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 is not the only strategyproof rule. One can construct alternative rules 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.

For example, suppose we add two phantoms, at 33% and 66%. Suppose there are three votes: 10%, 10%, 90%. Without phantoms, the median rule selects 10%. In contrast, the median rule with phantoms selects 33%, which is arguably fairer, as it treats the minority voter better.

Moulin proves the following two characterization results:

• Every rule that is anonymous and strategyproof for all single-peaked preferences is equivalent to a median rule with at most n+1 phantoms.
• Every rule that is anonymous, strategyproof and Pareto-efficient for all single-peaked preferences is equivalent to a median rule with at most n-1 phantoms.

Some special cases of phantom-median rules are:

• If there are n-1 phantoms at 0%, then the median rule returns the minimum of all real votes.
• If there are n-1 phantoms at 100%, then the median rule returns the maximum of all real votes.
• If there are n-1 phantoms at 50%, then the median rule returns 1/2 if some ideal points are above and some are below 1/2; otherwise, it returns the vote closest to 1/2.

The Uniform Phantom median rule

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

Rules for the multi-dimensional case

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.

Freeman, Pennock, Peters and Vaughan suggest a solution called moving phantoms, where the n-1 phantoms increase continuously until the outcome equals the total budget. They prove that the mechanism remains strategyproof, and it is also proportional.

Caragiannis, Christodoulou and Protopapas extend the above fairness notions.

See also

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