Arrow's Impossibility Theorem

Arrow’s Impossibility Theorem states that, when there are three or more candidates, no voting system can convert the preferences of all voters (local rankings) into a complete preference (a global ranking) if it has to satisfy certain conditions.

Let

• $A$ be the set of all candidates,
• $V=\{1, \ldots,N\}$ the set of all voters,
• $L(A)$ the set of all linear orderings of $A$.

One can think of $R \in L(A)$ as a function $R: A \rightarrow \bf{R}$ (the reals) so that if candidate $a$ is preferred over $b$ then $R(a)>R(b)$. Each voter $1, \ldots, N$ then casts a "ballot" $R_1, \ldots, R_N$, respectively.

A "decision" function $$F: L(A)^N \to L(A)$$ converts any "election" (a combination of voters' preferences) into a single election result (a global preference): $$F(R_1, \ldots, R_N)=R.$$

Then the following three conditions are incompatible, i.e., such function $F$ doesn't exist, if $N \geq 3$:

Unanimity: If two candidates are ranked relative to each other the same way by all voters, then they are ranked this way by the election results as well:

If $R_i(a)>R_i(b)$ for each $i=1, \ldots, N$, then $R(a)>R(b)$.

Non-dictatorship: There is no voter whose preferences always prevail:

There is no $ i \in \{1, \ldots,N\} $ such that $R=F(R_1,R_2, \ldots, R_N) = R_i$ for any $R_1, \ldots, R_N$.

Independence of irrelevant alternatives: For two candidates, if no voter has changed his relative ranking for them from the election to the next, then the relative positions of the candidates haven't changed in the election results either:

Given $a,b \in A$, suppose $R_i(a)>R_i(b)$ and $S_i(a)>S_i(b)$, where $R_i,S_i \in L(A)$, for all $i=1, \ldots, N$, and $R=F(R_1,R_2, \ldots, R_N)$ and $S=F(S_1,S_2, \ldots, S_N) $, then $R(a)>S(a)$.

The last condition is often criticized as too restrictive because it prohibits all "cyclic preferences", such as:

• voter 1: A > B > C,
• voter 2: B > C > A,
• voter 3: C > A > B.

It is interesting that the presence of cycles is what creates problems for PageRank (see also acyclic ranking).

Also: probabilistic analysis of electoral systems.