Non-degenerate systems

As background, it is typically assumed that any non-degenerate (i.e. actually useful) voting system non-dictatorship:

• Non-dictatorship—at least two voters can affect the outcome of the election. (The system does not just ignore every vote except one, or even ignore all of the votes and always elect the same candidate.)

Most proofs use additional assumptions to simplify deriving the result, though Robert Wilson proved these to be unnecessary.^[7] Older proofs have taken as axioms:

• Non-negative response—adding support for an outcome should not cause it to lose. While originally considered "obvious" for any practical system, this criterion is failed by instant-runoff voting. Arrow later gave another proof applying to systems with negative response.
• Pareto efficiency—if every voter agrees one candidate is better than another, the system will agree as well. (A candidate with unanimous support should win.) This assumption replaces non-negative response in Arrow's second proof, extending it to include instant-runoff voting.
• Majority rule—if most voters prefer ${\displaystyle A}$ to ${\displaystyle B}$, then ${\displaystyle A}$ should defeat ${\displaystyle B}$. This form was proven by the Marquis de Condorcet with his discovery of the voting paradox.
• Universal domain—Some authors are explicit about the assumption that the social welfare function is a function over the domain of preferences (not just a partial function).
  • In other words, the system cannot simply "give up" and refuse to elect a candidate in some elections.

Independence of irrelevant alternatives (IIA)

The IIA condition is an important assumption governing rational choice. The axiom says that adding irrelevant—i.e. rejected—options should not affect the outcome of a decision. From a practical point of view, the assumption prevents electoral outcomes from behaving erratically in response to the arrival and departure of candidates.^[8]

Arrow defines IIA slightly differently, by stating that the social preference between alternatives ${\displaystyle A}$ and ${\displaystyle B}$ should only depend on the individual preferences between ${\displaystyle A}$ and ${\displaystyle B}$; that is, it should not be able to go from ${\displaystyle A\succ B}$ to ${\displaystyle B\succ A}$ by changing preferences over some irrelevant alternative, e.g. whether ${\displaystyle A\succ C}$. This is equivalent to the above statement about independence of spoiler candidates when using the standard construction of a placement function.

Intuition

Arrow's requirement that the social preference ${\displaystyle A\succ B}$ only depend on individual preferences ${\displaystyle A\succ _{i}B}$ is extremely restrictive. May's theorem shows the only "fair" way to choose between two candidates based on ordinal preferences is majority voting. This means that assumptions only slightly stronger than Arrow's are already enough to lock us into the class of Condorcet methods. At this point, the existence of the voting paradox is enough to show the impossibility of rational behavior.

While the above argument is intuitive, it is not formal, and it requires additional assumptions not used by Arrow.

Formal statement

Let A be a set of outcomes, N a number of voters or decision criteria. We denote the set of all total orderings of A by L(A).

An ordinal (ranked) social welfare function is a function:

${\displaystyle F:\mathrm {L(A)} ^{N}\to \mathrm {L(A)} }$

which aggregates voters' preferences into a single preference order on A.

An N-tuple (R₁, …, R_N) ∈ L(A)^N of voters' preferences is called a preference profile. We assume two conditions:

Pareto efficiency

If alternative a is ranked strictly higher than b for all orderings R₁ , …, R_N, then a is ranked strictly higher than b by F(R₁, R₂, …, R_N). This axiom is not needed to prove the result,^[7] but is used in both proofs below.

Non-dictatorship

There is no individual i whose strict preferences always prevail. That is, there is no i ∈ {1, …, N} such that for all (R₁, …, R_N) ∈ L(A)^N and all a and b, when a is ranked strictly higher than b by R_i then a is ranked strictly higher than b by F(R₁, R₂, …, R_N).

Then, this rule must violate independence of irrelevant alternatives:

Independence of irrelevant alternatives

For two preference profiles (R₁, …, R_N) and (S₁, …, S_N) such that for all individuals i, alternatives a and b have the same order in R_i as in S_i, alternatives a and b have the same order in F(R₁, …, R_N) as in F(S₁, …, S_N).

Formal proof

More information decisive over an ordered pair ...

Proof by decisive coalition

Arrow's proof used the concept of decisive coalitions.[8] Definition: A subset of voters is a coalition. A coalition is decisive over an ordered pair ${\displaystyle (x,y)}$ if, when everyone in the coalition ranks ${\displaystyle x\succ _{i}y}$, society overall will always rank ${\displaystyle x\succ y}$. A coalition is decisive if and only if it is decisive over all ordered pairs. Our goal is to prove that the decisive coalition contains only one voter, who controls the outcome—in other words, a dictator. The following proof is a simplification taken from Amartya Sen[9] and Ariel Rubinstein.[10] The simplified proof uses an additional concept: A coalition is weakly decisive over ${\displaystyle (x,y)}$ if and only if when every voter ${\displaystyle i}$ in the coalition ranks ${\displaystyle x\succ _{i}y}$, and every voter ${\displaystyle j}$ outside the coalition ranks ${\displaystyle y\succ _{j}x}$, then ${\displaystyle x\succ y}$. Thenceforth assume that the social choice system satisfies unrestricted domain, Pareto efficiency, and IIA. Also assume that there are at least 3 distinct outcomes. Field expansion lemma — if a coalition ${\displaystyle G}$ is weakly decisive over ${\displaystyle (x,y)}$ for some ${\displaystyle x\neq y}$, then it is decisive. Proof Let ${\displaystyle z}$ be an outcome distinct from ${\displaystyle x,y}$. Claim: ${\displaystyle G}$ is decisive over ${\displaystyle (x,z)}$. Let everyone in ${\displaystyle G}$ vote ${\displaystyle x}$ over ${\displaystyle z}$. By IIA, changing the votes on ${\displaystyle y}$ does not matter for ${\displaystyle x,z}$. So change the votes such that ${\displaystyle x\succ _{i}y\succ _{i}z}$ in ${\displaystyle G}$ and ${\displaystyle y\succ _{i}x}$ and ${\displaystyle z}$ outside of ${\displaystyle G}$. By Pareto, ${\displaystyle y\succ z}$. By coalition weak-decisiveness over ${\displaystyle (x,y)}$, ${\displaystyle x\succ y}$. Thus ${\displaystyle x\succ z}$. ${\displaystyle \square }$ Similarly, ${\displaystyle G}$ is decisive over ${\displaystyle (z,y)}$. By iterating the above two claims (note that decisiveness implies weak-decisiveness), we find that ${\displaystyle G}$ is decisive over all ordered pairs in ${\displaystyle \{x,y,z\}}$. Then iterating that, we find that ${\displaystyle G}$ is decisive over all ordered pairs in ${\displaystyle X}$. Group contraction lemma — If a coalition is decisive, and has size ${\displaystyle \geq 2}$, then it has a proper subset that is also decisive. Proof Let ${\displaystyle G}$ be a coalition with size ${\displaystyle \geq 2}$. Partition the coalition into nonempty subsets ${\displaystyle G_{1},G_{2}}$. Fix distinct ${\displaystyle x,y,z}$. Design the following voting pattern (notice that it is the cyclic voting pattern which causes the Condorcet paradox): ${\displaystyle {\begin{aligned}{\text{voters in }}G_{1}&:x\succ _{i}y\succ _{i}z\\{\text{voters in }}G_{2}&:z\succ _{i}x\succ _{i}y\\{\text{voters outside }}G&:y\succ _{i}z\succ _{i}x\end{aligned}}}$ (Items other than ${\displaystyle x,y,z}$ are not relevant.) Since ${\displaystyle G}$ is decisive, we have ${\displaystyle x\succ y}$. So at least one is true: ${\displaystyle x\succ z}$ or ${\displaystyle z\succ y}$. If ${\displaystyle x\succ z}$, then ${\displaystyle G_{1}}$ is weakly decisive over ${\displaystyle (x,z)}$. If ${\displaystyle z\succ y}$, then ${\displaystyle G_{2}}$ is weakly decisive over ${\displaystyle (z,y)}$. Now apply the field expansion lemma. By Pareto, the entire set of voters is decisive. Thus by the group contraction lemma, there is a size-one decisive coalition—a dictator.

Close

Minimal IIA failures: Majority-rule methods

The first set of methods economists have studied are the majority-rule methods, which limit spoilers to rare situations where majority rule is self-contradictory, and uniquely minimize the possibility of a spoiler effect among rated methods.^[14] Arrow's theorem was preceded by the Marquis de Condorcet's discovery of cyclic social preferences, cases where majority votes are logically inconsistent. Condorcet believed voting rules should satisfy his majority rule principle, i.e. if most voters rank Alice ahead of Bob, Alice should defeat Bob in the election.

Unfortunately, as Condorcet proved, this rule can be self-contradictory (intransitive), because there can be a rock-paper-scissors cycle with three or more candidates defeating each other in a circle. Thus Condorcet proved a weaker form of Arrow's impossibility theorem long before Arrow himself, under the stronger assumption that a voting system in the two-candidate case will consist of a simple majority vote.

Condorcet methods avoid the spoiler effect in non-cyclic elections, where candidates can be chosen by majority rule. Political scientists have found such cycles to be empirically rare, suggesting they are of limited practical concern. Spatial voting models also suggest the paradox is infrequent^[15] or even non-existent.^[16]

No IIA failures: Rated voting

As shown above, the proof of Arrow's theorem relies crucially on the assumption of ranked voting, and is not applicable to rated voting systems. As a result, systems like score voting and graduated majority judgment pass independence of irrelevant alternatives.^[1] These systems ask voters to rate candidates on a numerical scale (e.g. from 0–10), and then elect the candidate with the highest average (for score voting) or median (graduated majority judgment).

While Arrow's theorem does not apply to graded systems, Gibbard's theorem still does: no electoral system is fully strategy-free,^[21] so the informal dictum that "no voting system is perfect" still has some mathematical basis.^[22]

Esoteric solutions

In addition to the above practical resolutions, there exist unusual (impractical) situations in which Arrow's conditions can be satisfied.