Median mechanism

A median mechanism is a voting rule that allows people to decide on a value in 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.

The median mechanism can be used, for example, to decide on the size of the country's budget: each person says what the ideal budget size should be, and the chosen size is the median of the declared values. Another possible application is deciding how long the annual school vacation should be: each person says the ideal length in days, and the median is selected. A third example is: deciding what temperature the air-conditioner in an office should be set to. A fourth example is a facility location problem in one dimension.

An important feature of the median mechanism is that it is truthful: if the utility of each voter is higher whenever the chosen value is closer to his ideal value, then an optimal strategy for each voter is to declare his true ideal value, regardless of what other voters say. This is in contrast to other natural mechanisms, such as the average mechanism. With the average mechanism, if the current average is lower than a voter's ideal value, then it may be optimal for the voter to declare a higher value (and vice versa), in order to "pull" the chosen value towards his ideal value. The median mechanism is immune to such manipulations.

Moreover, every mechanism that is truthful and anonymous is a generalized median mechanism - a mechanism that inserts some fixed "society votes" and then selects the median (see below).^[1]

Assumptions

Society wants to choose a value from a one-dimensional set, which can be described as a subset of the real line, e.g. the real interval [0,1]. There are some n voters. Each voter i has an ideal value p_i, also called the peak of i.

The utility of voter i depends on the chosen value: the voter is happier if the chosen value is closer to p_i. Formally, the utilities satisfy the single-peaked condition for every two alternatives x, y: if x > y ≥ p_i, or If x < y ≤ p_i, then the agent prefers y to x.

One utility function that satisfies this condition is: u_i(x) = -|x-p_i|; so the utility of the peak is 0, and the utility of other alternatives is negative, and becomes more negative the farther we are from the peak.

Procedure

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

In a generalized median mechanism (GMM), there are some k pre-determined society votes (also called phantom votes), s₁,...,s_k. The chosen value is:

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

Properties

For every selection of the society votes s₁,...,s_k, the GMM is anonymous, strategyproof, and group-strategyproof.

Moreover, if the number of society votes is at most n-1, then the GMM is also Pareto-efficient.^[1] In particular, the GMM satisfies the unanimity property: if all n voters agree on a value, then this value is chosen.

Characterizations

For every anonymous and strategyproof mechanism, there are some n+1 society votes such that the mechanism is equivalent to GMM with these society votes. Note that this includes all GMM-s with n-1 society votes: given some n-1 society votes, one can add a society vote at -∞ (or the smallest possible value) and a society vote at +∞ (or the largest possible value); the median with these n+1 society votes is identical to the median with the original n-1 society votes. Similarly, this class includes all GMM-s with n-3 society votes, n-5 society votes, etc.

Every anonymous, strategyproof and efficient mechanism can be presented as a generalized median mechanism with n-1 society votes.^[1]

Special cases

If all n-1 society votes are -∞ (or the smallest possible value), then the GMM selects min(p₁, ..., p_n) = p₁. Similarly, if all n-1 society votes are +∞ (or the largest possible value), then the GMM selects max(p₁, ..., p_n) = p_n. In general, if k society votes are +∞ and n-1-k are -∞, then the GMM selects p_k+1 - the (k+1)-th highest value. All these mechanisms are truthful.

Application for budget aggregation

The generalized median mechanism has been used to construct a mechanism for truthful aggregation of budget proposals.^[2]

Related concepts

A similar characterization is given by Ching.^[3]

In a median mechanism, each agent reports his/her ideal value ("peak"). 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.

References