Namespaces
Variants
Actions

Difference between revisions of "Arrow impossibility theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
a1107101.png
 +
$#A+1 = 36 n = 0
 +
$#C+1 = 36 : ~/encyclopedia/old_files/data/A110/A.1100710 Arrow impossibility theorem
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
In 1951, K. Arrow [[#References|[a1]]] discovered a troubling result about decisions involving three or more alternatives. After posing innocuous conditions that seemingly are satisfied by all reasonable procedures, he proved that they require a dictator. This counter-intuitive assertion is one of the better known results in the social and decision sciences; it is part of Arrow's 1972 Nobel Prize.
 
In 1951, K. Arrow [[#References|[a1]]] discovered a troubling result about decisions involving three or more alternatives. After posing innocuous conditions that seemingly are satisfied by all reasonable procedures, he proved that they require a dictator. This counter-intuitive assertion is one of the better known results in the social and decision sciences; it is part of Arrow's 1972 Nobel Prize.
  
Arrow's first condition, unrestricted domain, allows each voter to rank the candidates in any complete, transitive manner (without ties). The Pareto condition requires that when the voters unanimously agree on the strict ranking of two candidates, then that is society's relative ranking of this pair. Independence of irrelevant alternatives, (IIA), requires society's relative ranking of a pair to depend only on how the voters rank them; it is not influenced by their views of other  "irrelevant"  alternatives. This condition eliminates paradoxes, where an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a1107101.png" /> relative outcome can change by voters varying their <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a1107102.png" /> ranking but keeping their <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a1107103.png" /> rankings fixed. Finally, the procedure has transitive outcomes.
+
Arrow's first condition, unrestricted domain, allows each voter to rank the candidates in any complete, transitive manner (without ties). The Pareto condition requires that when the voters unanimously agree on the strict ranking of two candidates, then that is society's relative ranking of this pair. Independence of irrelevant alternatives, (IIA), requires society's relative ranking of a pair to depend only on how the voters rank them; it is not influenced by their views of other  "irrelevant"  alternatives. This condition eliminates paradoxes, where an $  A \succ C $
 +
relative outcome can change by voters varying their $  B $
 +
ranking but keeping their $  \{ A, C \} $
 +
rankings fixed. Finally, the procedure has transitive outcomes.
  
Arrow proved that with more than two alternatives, a dictator is the only procedure satisfying these conditions, i.e., society's ranking is determined by the dictator. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a1107104.png" /> is the set of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a1107105.png" /> transitive rankings of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a1107106.png" /> candidates, then decision procedures are mappings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a1107107.png" />, where a dictator is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a1107108.png" /> that is the identity mapping on one variable; e.g., there is a component <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a1107109.png" /> so that for any profile <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071010.png" />, one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071011.png" />.
+
Arrow proved that with more than two alternatives, a dictator is the only procedure satisfying these conditions, i.e., society's ranking is determined by the dictator. If $  P  ^ {n} $
 +
is the set of all $  n! $
 +
transitive rankings of the $  n $
 +
candidates, then decision procedures are mappings $  F : {\prod P  ^ {n} } \rightarrow {P  ^ {n} } $,  
 +
where a dictator is an $  F $
 +
that is the identity mapping on one variable; e.g., there is a component $  j $
 +
so that for any profile $  \mathbf p = ( \mathbf p _ {1} \dots \mathbf p _ {a} ) \in \prod P  ^ {n} $,  
 +
one has $  F ( \mathbf p ) \equiv \mathbf p _ {j} $.
  
 
==Explanation.==
 
==Explanation.==
With the many extensions (see [[#References|[a3]]]) and mathematical proofs of Arrow's theorem, ranging from ultrafilters to geometry [[#References|[a4]]] to algebraic topology [[#References|[a2]]], it is surprising that it admits an elementary explanation with a benign re-interpretation [[#References|[a4]]], [[#References|[a5]]]. To explain this, notice that the theorem is meaningless unless voters have transitive preferences. (For instance, if all voters had the same cyclic preferences, then Pareto forces a non-transitive outcome.) However, IIA vitiates this critical transitivity assumption. To see why, for each pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071012.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071013.png" /> be the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071014.png" />-relative ranking of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071015.png" />; e.g., if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071016.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071017.png" />. IIA requires <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071018.png" /> to be decomposed into the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071019.png" /> mappings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071020.png" />, where the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071021.png" /> domain depends only on the voters' rankings of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071022.png" />. Letting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071023.png" /> denote the set of all
+
With the many extensions (see [[#References|[a3]]]) and mathematical proofs of Arrow's theorem, ranging from ultrafilters to geometry [[#References|[a4]]] to algebraic topology [[#References|[a2]]], it is surprising that it admits an elementary explanation with a benign re-interpretation [[#References|[a4]]], [[#References|[a5]]]. To explain this, notice that the theorem is meaningless unless voters have transitive preferences. (For instance, if all voters had the same cyclic preferences, then Pareto forces a non-transitive outcome.) However, IIA vitiates this critical transitivity assumption. To see why, for each pair $  \{ A _ {i} , A _ {j} \} $,  
 +
let $  F _ {i, j }  ( \mathbf p ) $
 +
be the $  \{ A _ {i} , A _ {j} \} $-
 +
relative ranking of $  F ( \mathbf p ) $;  
 +
e.g., if $  F ( \mathbf p ) = A _ {2} \succ A _ {3} \succ A _ {1} $,  
 +
then $  F _ {1, 3 }  ( \mathbf p ) = A _ {3} \succ A _ {1} $.  
 +
IIA requires $  F $
 +
to be decomposed into the $  ( \begin{array}{c}
 +
n \\
 +
2
 +
\end{array}
 +
) $
 +
mappings $  \{ F _ {i,j }  \} _ {i < j }  $,  
 +
where the $  F _ {i,j }  $
 +
domain depends only on the voters' rankings of $  \{ A _ {i} , A _ {j} \} $.  
 +
Letting $  B  ^ {n} $
 +
denote the set of all
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071024.png" /></td> </tr></table>
+
$$
 +
2 ^ {\left ( \begin{array}{c}
 +
n \\
 +
2
 +
\end{array}
 +
\right ) }
 +
$$
  
ways to list the strict rankings of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071025.png" /> pairs, IIA requires <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071026.png" /> to be expressible as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071027.png" />. This domain allows IIA-admissible procedures to be used by unsophisticated voters without transitive rankings. Similarly, the implicit independence condition conferred on the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071028.png" /> functions by IIA renders them incapable of sequencing the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071029.png" /> pairwise outcomes into transitivity.
+
ways to list the strict rankings of the $  ( \begin{array}{c}
 +
n \\
 +
2
 +
\end{array}
 +
) $
 +
pairs, IIA requires $  F $
 +
to be expressible as $  F : {\prod B  ^ {n} } \rightarrow {B  ^ {n} } $.  
 +
This domain allows IIA-admissible procedures to be used by unsophisticated voters without transitive rankings. Similarly, the implicit independence condition conferred on the $  \{ F _ {i,j }  \} $
 +
functions by IIA renders them incapable of sequencing the $  ( \begin{array}{c}
 +
n \\
 +
2
 +
\end{array}
 +
) $
 +
pairwise outcomes into transitivity.
  
Thus, the transitivity assumption is a domain restriction; the goal is to identify those IIA-procedures where the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071030.png" /> restriction is sufficiently severe to force the outcomes to be in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071031.png" />. Trivially, this includes a dictator. However, when the rankings of two or more voters are involved, some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071032.png" /> level sets contain transitive and non-transitive profiles, where the non-transitive profile determines a non-transitive <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071033.png" /> outcome. Arrow's assertion, then, holds, because IIA prohibits procedures from recognizing transitivity. This permits the alternative interpretation that rational (transitive) outcomes cannot be expected from procedures intended for highly irrational voters.
+
Thus, the transitivity assumption is a domain restriction; the goal is to identify those IIA-procedures where the $  \prod P  ^ {n} $
 +
restriction is sufficiently severe to force the outcomes to be in $  P  ^ {n} $.  
 +
Trivially, this includes a dictator. However, when the rankings of two or more voters are involved, some $  F $
 +
level sets contain transitive and non-transitive profiles, where the non-transitive profile determines a non-transitive $  F $
 +
outcome. Arrow's assertion, then, holds, because IIA prohibits procedures from recognizing transitivity. This permits the alternative interpretation that rational (transitive) outcomes cannot be expected from procedures intended for highly irrational voters.
  
 
==Resolution.==
 
==Resolution.==
To resolve the problem, one replaces IIA with a condition that recognizes rational preferences. One is intensity of irrelevant alternatives (IIIA), where society's relative ranking of two candidates is determined by each voter's relative ranking and the number of alternatives separating them. Replacing Arrow's negative conclusion is that [[#References|[a4]]], [[#References|[a5]]] the Borda count is a procedure with transitive outcomes satisfying unrestricted domain, IIIA and Pareto. (The Borda count assigns <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071034.png" /> points to a voter's <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071035.png" />th ranked candidate, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110710/a11071036.png" />; the candidates are ranked according to the sum of assigned points.) Thus, if rational outcomes are desired, use procedures designed for rational voters.
+
To resolve the problem, one replaces IIA with a condition that recognizes rational preferences. One is intensity of irrelevant alternatives (IIIA), where society's relative ranking of two candidates is determined by each voter's relative ranking and the number of alternatives separating them. Replacing Arrow's negative conclusion is that [[#References|[a4]]], [[#References|[a5]]] the Borda count is a procedure with transitive outcomes satisfying unrestricted domain, IIIA and Pareto. (The Borda count assigns $  n - j $
 +
points to a voter's $  j $
 +
th ranked candidate, $  j = 1 \dots n $;  
 +
the candidates are ranked according to the sum of assigned points.) Thus, if rational outcomes are desired, use procedures designed for rational voters.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  K. Arrow,  "Social choice and individual values" , Wiley  (1963)  (Edition: Second)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  G. Chichilnisky,  "The topological equivalence of the Pareto condition and the existence of a dictator"  ''J. Econ. Theory'' , '''9'''  (1982)  pp. 223–234</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J. Kelly,  "Social choice bibliography"  ''Soc. Choice Welfare'' , '''8'''  (1991)  pp. 97–169</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  D.G. Saari,  "Basic geometry of voting" , Springer  (1995)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  D.G. Saari,  "Arrow's and Sen's theorems revisited and resolved"  ''Social Choice Welfare'' , '''to appear'''  (1997)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  K. Arrow,  "Social choice and individual values" , Wiley  (1963)  (Edition: Second)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  G. Chichilnisky,  "The topological equivalence of the Pareto condition and the existence of a dictator"  ''J. Econ. Theory'' , '''9'''  (1982)  pp. 223–234</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J. Kelly,  "Social choice bibliography"  ''Soc. Choice Welfare'' , '''8'''  (1991)  pp. 97–169</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  D.G. Saari,  "Basic geometry of voting" , Springer  (1995)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  D.G. Saari,  "Arrow's and Sen's theorems revisited and resolved"  ''Social Choice Welfare'' , '''to appear'''  (1997)</TD></TR></table>

Latest revision as of 18:48, 5 April 2020


In 1951, K. Arrow [a1] discovered a troubling result about decisions involving three or more alternatives. After posing innocuous conditions that seemingly are satisfied by all reasonable procedures, he proved that they require a dictator. This counter-intuitive assertion is one of the better known results in the social and decision sciences; it is part of Arrow's 1972 Nobel Prize.

Arrow's first condition, unrestricted domain, allows each voter to rank the candidates in any complete, transitive manner (without ties). The Pareto condition requires that when the voters unanimously agree on the strict ranking of two candidates, then that is society's relative ranking of this pair. Independence of irrelevant alternatives, (IIA), requires society's relative ranking of a pair to depend only on how the voters rank them; it is not influenced by their views of other "irrelevant" alternatives. This condition eliminates paradoxes, where an $ A \succ C $ relative outcome can change by voters varying their $ B $ ranking but keeping their $ \{ A, C \} $ rankings fixed. Finally, the procedure has transitive outcomes.

Arrow proved that with more than two alternatives, a dictator is the only procedure satisfying these conditions, i.e., society's ranking is determined by the dictator. If $ P ^ {n} $ is the set of all $ n! $ transitive rankings of the $ n $ candidates, then decision procedures are mappings $ F : {\prod P ^ {n} } \rightarrow {P ^ {n} } $, where a dictator is an $ F $ that is the identity mapping on one variable; e.g., there is a component $ j $ so that for any profile $ \mathbf p = ( \mathbf p _ {1} \dots \mathbf p _ {a} ) \in \prod P ^ {n} $, one has $ F ( \mathbf p ) \equiv \mathbf p _ {j} $.

Explanation.

With the many extensions (see [a3]) and mathematical proofs of Arrow's theorem, ranging from ultrafilters to geometry [a4] to algebraic topology [a2], it is surprising that it admits an elementary explanation with a benign re-interpretation [a4], [a5]. To explain this, notice that the theorem is meaningless unless voters have transitive preferences. (For instance, if all voters had the same cyclic preferences, then Pareto forces a non-transitive outcome.) However, IIA vitiates this critical transitivity assumption. To see why, for each pair $ \{ A _ {i} , A _ {j} \} $, let $ F _ {i, j } ( \mathbf p ) $ be the $ \{ A _ {i} , A _ {j} \} $- relative ranking of $ F ( \mathbf p ) $; e.g., if $ F ( \mathbf p ) = A _ {2} \succ A _ {3} \succ A _ {1} $, then $ F _ {1, 3 } ( \mathbf p ) = A _ {3} \succ A _ {1} $. IIA requires $ F $ to be decomposed into the $ ( \begin{array}{c} n \\ 2 \end{array} ) $ mappings $ \{ F _ {i,j } \} _ {i < j } $, where the $ F _ {i,j } $ domain depends only on the voters' rankings of $ \{ A _ {i} , A _ {j} \} $. Letting $ B ^ {n} $ denote the set of all

$$ 2 ^ {\left ( \begin{array}{c} n \\ 2 \end{array} \right ) } $$

ways to list the strict rankings of the $ ( \begin{array}{c} n \\ 2 \end{array} ) $ pairs, IIA requires $ F $ to be expressible as $ F : {\prod B ^ {n} } \rightarrow {B ^ {n} } $. This domain allows IIA-admissible procedures to be used by unsophisticated voters without transitive rankings. Similarly, the implicit independence condition conferred on the $ \{ F _ {i,j } \} $ functions by IIA renders them incapable of sequencing the $ ( \begin{array}{c} n \\ 2 \end{array} ) $ pairwise outcomes into transitivity.

Thus, the transitivity assumption is a domain restriction; the goal is to identify those IIA-procedures where the $ \prod P ^ {n} $ restriction is sufficiently severe to force the outcomes to be in $ P ^ {n} $. Trivially, this includes a dictator. However, when the rankings of two or more voters are involved, some $ F $ level sets contain transitive and non-transitive profiles, where the non-transitive profile determines a non-transitive $ F $ outcome. Arrow's assertion, then, holds, because IIA prohibits procedures from recognizing transitivity. This permits the alternative interpretation that rational (transitive) outcomes cannot be expected from procedures intended for highly irrational voters.

Resolution.

To resolve the problem, one replaces IIA with a condition that recognizes rational preferences. One is intensity of irrelevant alternatives (IIIA), where society's relative ranking of two candidates is determined by each voter's relative ranking and the number of alternatives separating them. Replacing Arrow's negative conclusion is that [a4], [a5] the Borda count is a procedure with transitive outcomes satisfying unrestricted domain, IIIA and Pareto. (The Borda count assigns $ n - j $ points to a voter's $ j $ th ranked candidate, $ j = 1 \dots n $; the candidates are ranked according to the sum of assigned points.) Thus, if rational outcomes are desired, use procedures designed for rational voters.

References

[a1] K. Arrow, "Social choice and individual values" , Wiley (1963) (Edition: Second)
[a2] G. Chichilnisky, "The topological equivalence of the Pareto condition and the existence of a dictator" J. Econ. Theory , 9 (1982) pp. 223–234
[a3] J. Kelly, "Social choice bibliography" Soc. Choice Welfare , 8 (1991) pp. 97–169
[a4] D.G. Saari, "Basic geometry of voting" , Springer (1995)
[a5] D.G. Saari, "Arrow's and Sen's theorems revisited and resolved" Social Choice Welfare , to appear (1997)
How to Cite This Entry:
Arrow impossibility theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Arrow_impossibility_theorem&oldid=12728
This article was adapted from an original article by D. Saari (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article