Median voting rule

Last updated

The median voting rule is a rule for group decision-making along a one-dimesional spectrum. An example is members of a city-council who have to decide on the total amount of annual city budget. Another example is several people working in the same office who have to decide on the air-conditioning temperature. Each member has in mind an ideal amount (called a "peak"), and prefers the actual amount to be as close as possible to his peak.

Contents

A simple way to decide is the average voting rule: ask each member what his peak is, and take the average of all peaks. But this rule easily manipulable. For example, suppse 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:

Note that single-peakedness does not imply any particular distance-measure between the alternatives. In particular, if a > pi > b, then the agent may prefer either a to b or b to a.

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

Proof of strategyproofness

Here is a proof that the median rule is strategyproof:

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:

Moulin [1] proved the following characterizations:

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 2n parameters.

Berga and Serizawa [3] characterized 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.

Border and Jordan [4] and Barbera, Gul and Stacchetti [5] generalized the notions of single-peaked preferences and median voting rules to multidimensional settings.

The median voter theorem says that if voters prefer will necessarily choose the candidate closest to the voter whose peak is the median of all peaks. [6]

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. This is because voters hold single-peaked preferences over outcomes, not scores; voters typically care more about who wins than about each candidate's vote total.

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 applices only to a restricted preference domain - the domain of single-peaked preferences.

Dummet and Farquharson present a sufficient condition for stability in voting games. [7] [ further explanation needed ]

Related Research Articles

Arrow's impossibility theorem is a celebrated result and key impossibility theorem in social choice theory. It shows that no ranked-choice voting rule can produce a logically coherent ranking of candidates. Specifically, no such procedure can satisfy a key criterion of decision theory, called independence of irrelevant alternatives or independence of spoilers: that the choice between and should not depend on the quality of a third, unrelated outcome .

The Gibbard–Satterthwaite theorem is a theorem in voting theory. It was first conjectured by the philosopher Michael Dummett and the mathematician Robin Farquharson in 1961 and then proved independently by the philosopher Allan Gibbard in 1973 and economist Mark Satterthwaite in 1975. It deals with deterministic ordinal electoral systems that choose a single winner, and states that for every voting rule of this form, at least one of the following three things must hold:

  1. The rule is dictatorial, i.e. there exists a distinguished voter who can choose the winner; or
  2. The rule limits the possible outcomes to two alternatives only; or
  3. The rule is susceptible to tactical voting: in some situations, a voter's sincere ballot may not best defend their opinion.

In political science and social choice theory, the median voter theorem states that if voters and candidates are distributed along a one-dimensional spectrum and voters have single peaked preferences, any voting method satisfying the Condorcet criterion will elect the candidate preferred by the median voter.

In social choice theory, a dictatorship mechanism is a rule by which, among all possible alternatives, the results of voting mirror a single pre-determined person's preferences, without consideration of the other voters. Dictatorship by itself is not considered a good mechanism in practice, but it is theoretically important: by Arrow's impossibility theorem, when there are at least three alternatives, dictatorship is the only ranked voting electoral system that satisfies unrestricted domain, Pareto efficiency, and independence of irrelevant alternatives. Similarly, by Gibbard's theorem, when there are at least three alternatives, dictatorship is the only strategyproof rule.

Single-peaked preferences are a class of preference relations. A group has single-peaked preferences over a set of outcomes if the outcomes can be ordered along a line such that:

  1. Each agent has a "best outcome" in the set, and
  2. For each agent, outcomes that are further from his or her best outcome are preferred less.
<span class="mw-page-title-main">Arunava Sen</span> Indian researcher and teacher

Arunava Sen is a professor of economics at the Indian Statistical Institute. He works on Game Theory, Social Choice Theory, Mechanism Design, Voting and Auctions.

Maximal lotteries refers to a probabilistic voting system first considered by the French mathematician and social scientist Germain Kreweras in 1965. The method uses preferential ballots and returns so-called maximal lotteries, i.e., probability distributions over the alternatives that are weakly preferred to any other probability distribution. Maximal lotteries satisfy the Condorcet criterion, the Smith criterion, polynomial runtime, and probabilistic versions of reinforcement, participation, and independence of clones.

In mechanism design, monotonicity is a property of a social choice function. It is a necessary condition for being able to implement the function using a strategyproof mechanism. Its verbal description is:

If changing one agent's type changes the outcome under the social choice function, then the resulting difference in utilities of the new and original outcomes evaluated at the new type of this agent must be at least as much as this difference in utilities evaluated at the original type of this agent.

In economics, dichotomous preferences (DP) are preference relations that divide the set of alternatives to two subsets: "Good" versus "Bad".

In the fields of mechanism design and social choice theory, Gibbard's theorem is a result proven by philosopher Allan Gibbard in 1973. It states that for any deterministic process of collective decision, at least one of the following three properties must hold:

  1. The process is dictatorial, i.e. there is a single voter whose vote chooses the outcome.
  2. The process limits the possible outcomes to two options only.
  3. The process is not straightforward; the optimal ballot for a voter depends on their beliefs about other voters' ballots.

The highest median voting rules are a class of graded voting rules where the candidate with the highest median rating is elected.

Multiwinner approval voting, also called approval-based committee (ABC) voting, is a multi-winner electoral system that uses approval ballots. Each voter may select ("approve") any number of candidates, and multiple candidates are elected. The number of elected candidates is usually fixed in advance. For example, it can be the number of seats in a country's parliament, or the required number of members in a committee.

Fractional social choice is a branch of social choice theory in which the collective decision is not a single alternative, but rather a weighted sum of two or more alternatives. For example, if society has to choose between three candidates: A B or C, then in standard social choice, exactly one of these candidates is chosen, while in fractional social choice, it is possible to choose "2/3 of A and 1/3 of B". A common interpretation of the weighted sum is as a lottery, in which candidate A is chosen with probability 2/3 and candidate B is chosen with probability 1/3. Due to this interpretation, fractional social choice is also called random social choice, probabilistic social choice, or stochastic social choice. But it can also be interpreted as a recipe for sharing, for example:

Fractional approval voting is an electoral system using approval ballots, in which the outcome is fractional: for each alternative j there is a fraction pj between 0 and 1, such that the sum of pj is 1. It can be seen as a generalization of approval voting: in the latter, one candidate wins and the other candidates lose. The fractions pj can be interpreted in various ways, depending on the setting. Examples are:

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 the median of all votes.

Ordinal Pareto efficiency refers to several adaptations of the concept of Pareto-efficiency to settings in which the agents only express ordinal utilities over items, but not over bundles. That is, agents rank the items from best to worst, but they do not rank the subsets of items. In particular, they do not specify a numeric value for each item. This may cause an ambiguity regarding whether certain allocations are Pareto-efficient or not. As an example, consider an economy with three items and two agents, with the following rankings:

Budget-proposal aggregation (BPA) 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.

Belief aggregation, also called risk aggregation,opinion aggregation or probabilistic opinion pooling, is a process in which different probability distributions, produced by different experts, are combined to yield a single probability distribution.

The average voting rule is a rule for group decision-making when the decision is a distribution, and each of the voters reports his ideal distribution. This is a special case of budget-proposal aggregation. It is a simple aggregation rule, that returns the arithmetic mean of all individual ideal distributions. The average rule was first studied formally by Michael Intrilligator. This rule and its variants are commonly used in economics and sports.

In mechanism design, a regret-free truth-telling mechanism is a mechanism in which each player who reveals his true private information does not feel regret after seeing the mechanism outcome. A regret-free mechanism incentivizes agents who want to avoid regret to report their preferences truthfully.

References

  1. ↑ Moulin, H. (1980-01-01). "On strategy-proofness and single peakedness". Public Choice. 35 (4): 437–455. doi:10.1007/BF00128122. ISSN   1573-7101. S2CID   154508892.
  2. ↑ Ching, Stephen (1997-12-01). "Strategy-proofness and "median voters"". International Journal of Game Theory. 26 (4): 473–490. doi:10.1007/BF01813886. hdl: 10722/177668 . ISSN   1432-1270. S2CID   42830689.
  3. ↑ Berga, Dolors; Serizawa, Shigehiro (2000-01-01). "Maximal Domain for Strategy-Proof Rules with One Public Good". Journal of Economic Theory. 90 (1): 39–61. doi:10.1006/jeth.1999.2579. ISSN   0022-0531.
  4. ↑ https://academic.oup.com/restud/article-abstract/50/1/153/1568395 . Retrieved 2023-11-15.{{cite web}}: Missing or empty |title= (help)
  5. ↑ Barberà, Salvador; Gul, Faruk; Stacchetti, Ennio (1993-12-01). "Generalized Median Voter Schemes and Committees". Journal of Economic Theory. 61 (2): 262–289. doi:10.1006/jeth.1993.1069. ISSN   0022-0531.
  6. ↑ Black, Duncan (1948-02-01). "On the Rationale of Group Decision-making". Journal of Political Economy. 56 (1): 23–34. doi:10.1086/256633. ISSN   0022-3808. S2CID   153953456.
  7. ↑ Dummett, Michael; Farquharson, Robin (1961). "Stability in Voting". Econometrica. 29 (1): 33–43. doi:10.2307/1907685. ISSN   0012-9682. JSTOR   1907685.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.