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.
Motivation 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 is easily manipulated. 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.
Preconditions 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 pi:
If pi > a > b, then agent i prefers a to b; If b > a > pi, 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 > pi > b, then the agent may prefer either a to b or b to a.
Procedure Each agent i in 1,...,n is asked to report the value of pi. The values are sorted in ascending order p1 ≤ ... ≤ pn. 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 pn/2):choice = median(p1, ..., pn).
Proof of strategyproofness 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.
Generalized median rules
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". 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 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 2n parameters, bS 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 bS).
Additional characterizations Moulin's characterizations consider only rules that are "peak only", that is, the rule depends only on the n peaks. Ching 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 2n 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:
… excerpt ends here. Continue reading the full article.
