Budget-proposal aggregation


Budget-proposal aggregation 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, 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. 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. 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 has to be built on a line; each voter has an ideal spot on the line in which the facility should be built ; and the problem is to aggregate the voters' preferences and decide where on the line the facility should be built.

The average 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, and the average of the ideal distributions of the other voters is. Then Alice would be better-off by reporting that her ideal distribution is, since this will pull the average distribution closer to her ideal distribution.

The median 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:
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, while 51% of the population live in the south and therefore their ideal distribution is, The median rule selects the distribution, which is unfair for the citizens living in the north.
This fairness notion is captured by proportionality, which means that, if all agents are single-minded, 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 is a special case of the median rule, with n-1 phantoms at 1/n,..., /n. This rule is strategyproof, 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 means that each agent's utility is at least 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 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.
  • * UFS implies IFS, unanimity and proportionality.
  • Proportional fairness '' 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. All implications are strict.
The following is known about existing rules:
  • The median rule is strategyproof. It satisfies unanimity, but not IFS or PROP.
  • The egalitarian rule satisfies unanimity and IFS, but not PROP. It is also not strategyproof.
  • The Nash rule satisfies PF, but it is not strategyproof.
  • The uniform phantom median rule satisfies PF, 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 pi, from a given budget allocation x, is minus the L1-distance between pi and x. Under this assumption, several aggregation rules were studied.

Utilitarian rules

, Nehring and Puppe consider BPA with discrete amounts. 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. 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, Sakshuwong 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. They prove that, with L1-utilities, the knapsack voting is strategyproof and utilitarian.
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 whereas 40% vote for, then the utilitarian rules would choose and give nothing to the issue important for the minority.