Median voting rule

The median voting rule or median mechanism is a rule for group decision-making along a one-dimensional domain. Each person votes by writing down his/her ideal value, and the rule selects a single value which is (in the basic mechanism) the median of all votes.

Many scenarions of group decision making involve a one-dimensional domain. Some examples are:

• Members of a city-council have to decide on the total amount of annual city budget.
• Several people working in the same office have to decide on the air-conditioning temperature.
• Parents of schoolchildren should decide how long the annual school vacation should be.
• The public has to decide where to locate a facility along a one-dimensional street.

Each member has in mind an ideal decision, called his "peak". Each agent prefers the actual amount to be as close as possible to his peak.

A simple way to decide is the average voting rule: ask each member what is his peak, and take the average of all peaks. But this rule easily manipulable. For example, suppose Alice's peak is 30, George's peak is 40, and Chana's peak is 50. If all voters report their true peaks, the actual amount will be 40. But Alice may manipulate and say that her peak is actually 0; then the average will be 30, which is Alice's actual peak. Thus, Alice has gained from the manipulation. Similarly, any agent whose peak is different than the outcome has an incentive to manipulate and report a false peak.

In contrast, the median rule determines the actual budget at the median of all votes. This simple change makes the rule strategyproof: no voter can gain by reporting a false peak. In the above example, the median is 40, and it remains 40 even if Alice reports 0. In fact, as Alice's true peak is below the median, no false report by Alice can potentially decrease the median; Alice can only increase the median, but this will make her worse-off.

The median voting rule holds in any setting in which the agents have single peaked preferences. This means that there exists some linear ordering > of the alternatives, such that for each agent i with peak p_i:

• If p_i > a > b, then agent i prefers a to b;
• If b > a > p_i, then agent i prefers a to b.

Once such a linear order exists, the median of any set of peaks can be computed by ordering the peaks along this linear order.

Note that single-peakedness does not imply any particular distance-measure between the alternatives, and does not imply anything on alternatives at different sides of the peak. In particular, if a > p_i > b, then the agent may prefer either a to b or b to a.

Each agent i in 1,...,n is asked to report the value of p_i. The values are sorted in ascending order p₁ ≤ ... ≤ p_n. In the basic mechanism, the chosen value when n is odd is p_(n+1)/2, which equals the median of values (when n is even, the chosen value is p_n/2):

choice = median(p₁, ..., p_n).

Here is a proof that the median rule is strategyproof:

• Consider first a voter whose peak is below the median. Reporting a lower peak will not change the median; reporting a higher peak will either keep the median unchanged or increase the median. In all cases, the voter does not gain.
• Similarly, consider a voter whose peak is above the median. Reporting a higher peak will not change the median; reporting a lower peak will either keep the median unchanged or decrease the median. In all cases, the voter does not gain.

Using similar reasoning, one can prove that the median rule is also group-strategyproof, that is: no coalition has a coordinated manipulation that improves the utility of one of them without harming the others.

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". For every set of phantoms, the rule that chooses the median of the set of real votes + phantoms is group-strategyproof.

For example, suppose the votes are 30, 40, and 50. Without phantoms, the median rule selects 40. If we add two phantoms at 0, then the median rule selects 30; if we add two phantoms at 100, the median rule selects 50; if we add medians at 20 and 35, the median rule selects 35.

Here are some special cases of phantom-median rules, assuming all the votes are between 0 and 100:

• 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 50 if some ideal points are above and some are below 50; otherwise, it returns the vote closest to 50.

Moulin^[1] proved the following characterizations:

• A rule is anonymous, strategyproof and Pareto-efficient for all single-peaked preferences if it is equivalent to a median rule with at most n-1 phantoms.
• A rule is anonymous and strategyproof for all single-peaked preferences if it is equivalent to a median rule with at most n+1 phantoms.
• A rule is strategyproof for all single-peaked preferences iff it is equivalent to a minmax rule of the following form. There are 2ⁿ parameters, b_S for any subset S of voters. The rule returns the minimum over all subsets S, of the maximum of (all peaks of voters in S, and b_S).^{[clarification needed]}

Moulin's characterizations consider only rules that are "peak only", that is, the rule depends only on the n peaks. Ching^[2] proved that all rules that are strategyproof and continuous, even if they are not "peak only", are augmented median rules, that is, can be described by a variant of the median rule with some 2ⁿ parameters.

Moulin's characterizations require the rules to handle all single-peaked preferences. Several other works allow rules that handle only a subset of single-peaked preferences:

• Berga and Serizawa^[3]: Sec.3 allow rules to handle only minimally-rich preferences. They prove that, even in this smaller domain, the strategyproof rules are exactly the generalized median rules.
• Masso and Moreno^[4] allow rules that handle only symmetric single-peaked preferences (symmetry means that an outcome farther away from the peak should be less preferred than an outcome nearer to the peak, even if the outcomes are on different sides of the peak). The class of strategyproof mechanisms in this smaller domain is strictly larger than the class of generalized median rules. In particular, rules can be disturbed by discontinuity points. Their result allows to design rules that deal with feasibility constraints.
• Border and Jordan^{[5]: Sec.3,4,5} allow rules that handle only quadratic preferences. In the one-dimensional setting, this is equivalent to utility functions of the form ${\displaystyle u_{i}(x)=-|x-p_{i}|}$. In this domain, they prove that any strategyproof rule that respects the unanimity criterion is uncompromising, that is: if the agent's peak is to the right of the outcome, and he moves his peak further to the right, then the outcome does not change; and similarly to the left. Conversely, every uncompromising rule is strategyproof. They prove that a rule is uncompromising if it has at most 2ⁿ phantom voters (that is, at most 2ⁿ points that may be elected even if they are not the peak of any voter), and its elect correspondence (mapping each profile to the set of indices of real+phantom voters whose peak is elected) has a closed graph. As a corollary, every uncompromising rule is continuous. However, an uncompromising rule that is also differentiable must be dictatorial.

Berga and Serizawa^[3]: Sec.4 seek rules that are both strategyproof and satisfy a condition they call "no vetoer": no individual should be able to avoid any alternative to be the outcome by declaring some preference. They characterize generalized median rules as the only strategyproof rules on "minimally-rich domains". They proved that the unique maximal domain that includes a minimally-rich domain, which allows for the existence of strategyproof rules satisfying the "no vetoer" condition, is the domain of convex preferences.

Barbera, Gul and Stacchetti^[6] also generalize the notions of single-peaked preferences and median voting rules to multidimensional settings.

Barbera and Jackson^[7] characterized strategyproof rules for weakly-single-peaked preferences, in which the maximal set may contain two alternatives.

Moulin characterized strategyproof rules on single-plateau preferences - a generalization of single-peaked in which each agent is allowed to have an entire interval of ideal points.^[8]

Border and Jordan^{[5]: Sec.6,7} generalize the notions of single-peaked preferences and median voting rules to multidimensional settings (see star-shaped preferences). They consider three classes of preferences:

• Separable (${\displaystyle u_{i}(x)=\sum _{j=1}^{m}u_{i,j}(x_{j})}$, where each v_i,j is a single-peaked utility function);
• Quadratic (${\displaystyle u_{i}(x)=-(x-p)^{T}A(x-p)}$ where A is a symmetric positive definite matrix);
• Their intersection separable quadratic (${\displaystyle u_{i}(x)=-\sum _{j=1}^{m}a_{i,j}\cdot (x_{j}-p_{j})^{2}}$, where a_i,j are positive constants).

In quadratic non-separable domains, the only strategyproof mecanisms are dictatorial. But in separable domains, there are multidimensional strategyproof mechanisms that are composed of one-dimensional strategyproof mechanisms, one for each coordinate.

In 1954, the Iranian Oil Consortium has adopted a median-like rule to determine Iran's total annual oil output. Annually, each member company's role was weighted by its fixed share of the total output. The chosen output, x, was the highest level such that the sum of the shares of members voting for levels as high as x was at least 70%.^{[9]: 103-108}

The median voter theorem relates to ranked voting mechanisms, in which each agent reports his/her full ranking over alternatives. The theorem says that, if the agents' preferences are single-peaked, then every Condorcet method always selects the candidate preferred by the median voter (the candidate closest to the voter whose peak is the median of all peaks).

Highest median voting rules are an attempt at applying the same voting rule to elections by asking voters to submit judgments (scores) for each candidate. However, the strategyproof nature of the median voting rule does not extend to choosing candidates unless the voters have single-peaked preferences over each candidate's final score. This may be a reasonable model of expressive voting, but the rule will not be strategyproof in situations where voters have single-peaked preferences over the outcome (winner) of the election.

The Gibbard–Satterthwaite theorem says that every strategyproof rule on three or more alternatives must be a dictatorship. The median rule apparently contradicts this theorem, because it is strategyproof and it is not a dictatorship. In fact there is no contradiction: the Gibbard-Satterthwaite theorem applies only to rules that operate on the entire preference domain (that is, only to voting rules that can handle any set of preference rankings). In contrast, the median rule applies only to a restricted preference domain—the domain of single-peaked preferences.

Dummet and Farquharson present a sufficient condition for stability in voting games.^{[10][further explanation needed]}