Arrow's impossibility theorem

From electowiki
(Redirected from Arrow's theorem)
Wikipedia has an article on:

Arrow’s impossibility theorem, or Arrow’s paradox demonstrates the impossibility of designing a set of rules based on Ordinal Voting for social decision making that would obey every ‘reasonable’ criterion required by society.

The theorem is named after economist Kenneth Arrow, who proved the theorem in his Ph.D. thesis and popularized it in his 1951 book Social Choice and Individual Values. Arrow was a co-recipient of the 1972 Bank of Sweden Prize in Economic Sciences in Memory of Alfred Nobel (popularly known as the “Nobel Prize in Economics”).

Summary

The premise for the theorem is roughly as follows: A society needs to agree on a preference order among several different options, but each individual in the society has a particular personal preference order. The problem is to find a general mechanism, called a social choice function, which transforms the set of individual preference orders into a global societal preference order. Arrow defined several desirable (“fair”) properties:

  • unrestricted domain or the universality criterion: the social choice function should create a deterministic, complete societal preference order from every possible set of individual preference orders. (The vote must have a result that ranks all possible choices relative to one another, the voting mechanism must be able to process all possible sets of voter preferences, and it should always give the same result for the same votes, without random selection.)
  • non-imposition or citizen sovereignty: every possible societal preference order should be achievable by some set of individual preference orders. (Every result must be achievable somehow.)
  • non-dictatorship: the social choice function should not simply follow the preference order of a single individual while ignoring all others.
  • positive association of social and individual values or monotonicity: if an individual modifies his or her preference order by promoting a certain option, then the societal preference order should respond only by promoting that same option or not changing, never by placing it lower than before. (An individual should not be able to hurt an option by ranking it higher.)
  • independence of irrelevant alternatives: if we restrict attention to a subset of options, and apply the social choice function only to those, then the result should be compatible with the outcome for the whole set of options. (Changes in individuals’ rankings of “irrelevant” alternatives [i.e., ones outside the subset] should have no impact on the societal ranking of the “relevant” subset.)

Arrow’s theorem shows that if the decision-making body has at least two members and at least three options to decide among, then it is impossible to design a social choice function that satisfies all these conditions at once.

Notes

Another version of Arrow’s theorem can be obtained by replacing the monotonicity criterion with that of:

  • unanimity or Pareto efficiency: if every individual prefers a certain option to another, then so must the resulting societal preference order.

This statement is stronger, because assuming both monotonicity and independence of irrelevant alternatives implies Pareto efficiency.

With a narrower definition of “irrelevant alternatives” which excludes those candidates in the Smith set, some Condorcet methods meet all the criteria.

Statement

No ordinal voting system can be designed that always satisfies these three "fairness" criteria:

  1. Pareto Criterion
  2. Independence of Irrelevant Alternatives
  3. There is neither "dictator" nor "prophet": no single voter possesses the power or the knowledge to always determine the group's preference.

Systems which violate only one of Arrow's criteria

MCA-P, as a rated rather than ranked system, violates only unrestricted domain. A system which arbitrarily chose two candidates to go into a runoff would violate only sovereignty. Random ballot violates only non-dictatorship. None of the methods described on this wiki violate only monotonicity. The Schulze method violates only independence of irrelevant alternatives, although it actually satisfies the similar independence of Smith-dominated alternatives criterion.

Systems which evade Arrow's criteria

Arrow's theorem only applies to ordinal voting and not cardinal voting. It is, therefore, possible for several cardinal systems to pass all three fairness criteria.[1][2][3][4][5] The typical example is score voting but there are also several multi-winner systems[clarification needed] which purport to pass all three of Arrow's original criteria. Additionally, there are cardinal systems which do not pass all criteria, but this is not due to Arrow's theorem; for example Ebert's Method fails Monotonicity.

Benefits

There are two main "benefits" that come from evading Arrow's theorem: when candidates enter or drop out of the race, this doesn't impact the choice between the remaining candidates, and when voters are trying to impact the race between a certain set of candidates, they need only alter the portions of their ballot that show their preferences among that set of candidates.

However, note that to obtain the first benefit, one of the assumptions used in Arrow's Theorem is that voters do not change their preferences on a given set of candidates regardless of whether candidates not in the set are running or not running. Suppose that an election is being conducted using a rated method that passes IIA. If the voters normalize their rated ballots, the first benefit is lost. For example:

1: A:10 B:6 C:0

1: B:10 C:4 A:0

1: C:10 A:5 B:0

Scores are A 15, B 16, and C 14, with B winning in Score voting. If C were to drop out, and all voters normalized in response, the election becomes:

1: A:10 B:0

1: B:10 A:0

1: A:10 B:0

Scores are A 20, B 10, and now A wins in Score voting. This example uses the standard Condorcet paradox, but presented in rated form.

In addition, if the voters vote strategically, the first benefit is also lost.

See also

References

  1. Ng, Y. K. (1971-11-01). "The Possibility of a Paretian Liberal: Impossibility Theorems and Cardinal Utility". Journal of Political Economy. 79 (6): 1397–1402. doi:10.1086/259845. ISSN 0022-3808. Retrieved 2020-03-20. In the present stage of the discussion on the problem of social choice, it should be common knowledge that the General Impossibility Theorem holds because only the ordinal preferences is or can be taken into account. If the intensity of preference or cardinal utility can be known or is reflected in social choice, the paradox of social choice can be solved
  2. Kemp, Murray; Asimakopulos, A. (1952-05-01). "A Note on "Social Welfare Functions" and Cardinal Utility*". Canadian Journal of Economics and Political Science/Revue canadienne de economiques et science politique. 18 (2): 195–200. doi:10.2307/138144. ISSN 0315-4890. Retrieved 2020-03-20. The abandonment of Condition 3 makes it possible to formulate a procedure for arriving at a social choice. Such a procedure is described below
  3. Harsanyi, John C. (1979-09-01). "Bayesian decision theory, rule utilitarianism, and Arrow's impossibility theorem". Theory and Decision. 11 (3): 289–317. doi:10.1007/BF00126382. ISSN 1573-7187. Retrieved 2020-03-20. It is shown that the utilitarian welfare function satisfies all of Arrow's social choice postulates — avoiding the celebrated impossibility theorem by making use of information which is unavailable in Arrow's original framework..
  4. Vasiljev, Sergei (2008-04-01). Cardinal Voting: The Way to Escape the Social Choice Impossibility. Rochester, NY: Social Science Research Network. Retrieved 2020-03-20. We prove that cardinal voting can satisfy Pareto efficiency, independence of irrelevant alternative, unrestricted domain, and at the same time it can be nondictatorship in disproof of Arrow’s impossibility theorem.
  5. "Podcast 2012-10-06: Interview with Nobel Laureate Dr. Kenneth Arrow". The Center for Election Science. 2015-05-25. Retrieved 2020-03-20. CES: Now, you mention that your theorem applies to preferential systems or ranking systems. Dr. Arrow: Yes CES: But the system that you’re just referring to, Approval Voting, falls within a class called cardinal systems. So not within ranking systems. Dr. Arrow: And as I said, that in effect implies more information.

External links

This page uses Creative Commons Licensed content from Wikipedia (view authors).