Budget-proposal aggregation

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.[7]
• 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),[1] 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.

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[8] 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 (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.[1]^: Prop.1
• UPM is the only rule satisfying strategyproofness and proportionality among all single-peaked preferences.[9]

Aziz, Lam, Lee and Walsh[10] 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[1] 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[11]^: Cor.1 prove that the only rule satisfying continuity, anonymity, proportionality and strategyproofness is UPM.