Editing Arrow's impossibility theorem (section)

=== Formal proof ===
{{Collapse top|title=Proof by decisive coalition}}

Arrow's proof used the concept of ''decisive coalitions''.<ref name="Arrow 1963234"/>

Definition:

* A subset of voters is a '''coalition'''.
* A coalition is '''decisive over an ordered pair <math>(x, y)</math>''' if, when everyone in the coalition ranks <math>x \succ_i y</math>, society overall will always rank <math>x \succ y</math>.
* 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 [[Dictatorship mechanism|dictator]].

The following proof is a simplification taken from [[Amartya Sen]]<ref>{{Cite book |last=Sen |first=Amartya |url=https://www.degruyter.com/document/doi/10.7312/mask15328-003/html |title=The Arrow Impossibility Theorem |date=2014-07-22 |publisher=Columbia University Press |isbn=978-0-231-52686-9 |pages=29–42 |chapter=Arrow and the Impossibility Theorem |doi=10.7312/mask15328-003}}</ref> and [[Ariel Rubinstein]].<ref>{{Cite book |last=Rubinstein |first=Ariel |url=https://openlibrary.org/books/OL29649010M/Lecture_Notes_in_Microeconomic_Theory |title=Lecture Notes in Microeconomic Theory: The Economic Agent |publisher=Princeton University Press |year=2012 |isbn=978-1-4008-4246-9 |edition=2nd |at=Problem 9.5 |ol=29649010M}}</ref> The simplified proof uses an additional concept:

* A coalition is '''weakly decisive''' over <math>(x, y)</math> if and only if when every voter <math>i</math> in the coalition ranks <math>x \succ_i y</math>, ''and'' every voter <math>j</math> outside the coalition ranks <math>y \succ_j x</math>, then <math>x \succ y</math>.

Thenceforth assume that the social choice system satisfies unrestricted domain, Pareto efficiency, and IIA. Also assume that there are at least 3 distinct outcomes.
{{Math theorem
| math_statement = if a coalition <math>G</math> is weakly decisive over <math>(x, y)</math> for some <math>x \neq y</math>, then it is decisive.
| name = Field expansion lemma
| note = 
}} {{Math proof|proof=Let <math>z</math> be an outcome distinct from <math>x, y</math>.

Claim: <math>G</math> is decisive over <math>(x, z)</math>.

Let everyone in <math>G</math> vote <math>x</math> over <math>z</math>. By IIA, changing the votes on <math>y</math> does not matter for <math>x, z</math>. So change the votes such that <math>x \succ_i y \succ_i z</math> in <math>G</math> and <math>y \succ_i x</math> and <math>y \succ_i z</math> outside of <math>G</math>.

By Pareto, <math>y \succ z</math>. By coalition weak-decisiveness over <math>(x, y)</math>, <math>x \succ y</math>. Thus <math>x \succ z</math>.  <math>\square</math>

Similarly, <math>G</math> is decisive over <math>(z, y)</math>.

By iterating the above two claims (note that decisiveness implies weak-decisiveness), we find that <math>G</math> is decisive over all ordered pairs in <math>\{x, y, z\}</math>. Then iterating that, we find that <math>G</math> is decisive over all ordered pairs in <math>X</math>.}} {{Math theorem
| math_statement = If a coalition is decisive, and has size <math>\geq 2</math>, then it has a proper subset that is also decisive.
| name = Group contraction lemma
| note = 
}} {{Math proof|proof=Let <math>G</math> be a coalition with size <math>\geq 2</math>. Partition the coalition into nonempty subsets <math>G_1, G_2</math>.

Fix distinct <math>x, y, z</math>. Design the following voting pattern (notice that it is the cyclic voting pattern which causes the Condorcet paradox):

<math>\begin{align}
  \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{align}</math>

(Items other than <math>x, y, z</math> are not relevant.)

Since <math>G</math> is decisive, we have <math>x \succ y</math>. So at least one is true: <math>x \succ z</math> or <math>z \succ y</math>.

If <math>x \succ z</math>, then <math>G_1</math> is weakly decisive over <math>(x, z)</math>. If <math>z \succ y</math>, then <math>G_2</math> is weakly decisive over <math>(z, y)</math>. 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.
{{Collapse bottom}}

{{Collapse top|title=Proof by showing there is only one pivotal voter}}
Proofs using the concept of the '''pivotal voter''' originated from Salvador Barberá in 1980.<ref>{{Cite journal |last=Barberá |first=Salvador |date=January 1980 |title=Pivotal voters: A new proof of arrow's theorem |journal=Economics Letters |volume=6 |issue=1 |pages=13–16 |doi=10.1016/0165-1765(80)90050-6 |issn=0165-1765}}</ref> The proof given here is a simplified version based on two proofs published in ''[[Economic Theory (journal)|Economic Theory]]''.<ref name="Gean"/><ref>{{cite journal |last1=Yu |first1=Ning Neil |year=2012 |title=A one-shot proof of Arrow's theorem |journal=[[Economic Theory (journal)|Economic Theory]] |volume=50 |issue=2 |pages=523–525 |doi=10.1007/s00199-012-0693-3 |jstor=41486021 |s2cid=121998270}}</ref>

==== Setup ====

Assume there are ''n'' voters. We assign all of these voters an arbitrary ID number, ranging from ''1'' through ''n'', which we can use to keep track of each voter's identity as we consider what happens when they change their votes. [[Without loss of generality]], we can say there are three candidates who we call '''A''', '''B''', and '''C'''. (Because of IIA, including more than 3 candidates does not affect the proof.)

We will prove that any social choice rule respecting unanimity and independence of irrelevant alternatives (IIA) is a dictatorship. The proof is in three parts:
# We identify a ''pivotal voter'' for each individual contest ('''A''' vs. '''B''', '''B''' vs. '''C''', and '''A''' vs. '''C'''). Their ballot swings the societal outcome.
# We prove this voter is a ''partial'' dictator. In other words, they get to decide whether A or B is ranked higher in the outcome.
# We prove this voter is the same person, hence this voter is a [[Dictatorship mechanism|dictator]].

==== Part one: There is a pivotal voter for A vs. B ====
[[File:Diagram_for_part_one_of_Arrow's_Impossibility_Theorem.svg|right|thumb|Part one: Successively move '''B''' from the bottom to the top of voters' ballots. The voter whose change results in '''B''' being ranked over '''A''' is the ''pivotal voter for'' '''B''' ''over'' '''A'''.]]
Consider the situation where everyone prefers '''A''' to '''B''', and everyone also prefers '''C''' to '''B'''. By unanimity, society must also prefer both '''A''' and '''C''' to '''B'''. Call this situation ''profile[0, x]''.

On the other hand, if everyone preferred '''B''' to everything else, then society would have to prefer '''B''' to everything else by unanimity. Now arrange all the voters in some arbitrary but fixed order, and for each ''i'' let ''profile i'' be the same as ''profile 0'', but move '''B''' to the top of the ballots for voters 1 through ''i''. So ''profile 1'' has '''B''' at the top of the ballot for voter 1, but not for any of the others. ''Profile 2'' has '''B''' at the top for voters 1 and 2, but no others, and so on.

Since '''B''' eventually moves to the top of the societal preference as the profile number increases, there must be some profile, number ''k'', for which '''B''' ''first'' moves ''above'' '''A''' in the societal rank. We call the voter ''k'' whose ballot change causes this to happen the ''pivotal voter for '''B''' over '''A'''''. Note that the pivotal voter for '''B''' over '''A''' is not, [[A priori knowledge|a priori]], the same as the pivotal voter for '''A''' over '''B'''. In part three of the proof we will show that these do turn out to be the same.

Also note that by IIA the same argument applies if ''profile 0'' is any profile in which '''A''' is ranked above '''B''' by every voter, and the pivotal voter for '''B''' over '''A''' will still be voter ''k''. We will use this observation below.

==== Part two: The pivotal voter for B over A is a dictator for B over C ====
In this part of the argument we refer to voter ''k'', the pivotal voter for '''B''' over '''A''', as the ''pivotal voter'' for simplicity. We will show that the pivotal voter dictates society's decision for '''B''' over '''C'''. That is, we show that no matter how the rest of society votes, if ''pivotal voter'' ranks '''B''' over '''C''', then that is the societal outcome. Note again that the dictator for '''B''' over '''C''' is not a priori the same as that for '''C''' over '''B'''. In part three of the proof we will see that these turn out to be the same too.
[[File:Diagram_for_part_two_of_Arrow's_Impossibility_Theorem.svg|right|thumb|Part two: Switching '''A''' and '''B''' on the ballot of voter ''k'' causes the same switch to the societal outcome, by part one of the argument. Making any or all of the indicated switches to the other ballots has no effect on the outcome.]]
In the following, we call voters 1 through ''k − 1'', ''segment one'', and voters ''k + 1'' through ''N'', ''segment two''. To begin, suppose that the ballots are as follows:

* Every voter in segment one ranks '''B''' above '''C''' and '''C''' above '''A'''.
* Pivotal voter ranks '''A''' above '''B''' and '''B''' above '''C'''.
* Every voter in segment two ranks '''A''' above '''B''' and '''B''' above '''C'''.

Then by the argument in part one (and the last observation in that part), the societal outcome must rank '''A''' above '''B'''. This is because, except for a repositioning of '''C''', this profile is the same as ''profile k − 1'' from part one. Furthermore, by unanimity the societal outcome must rank '''B''' above '''C'''. Therefore, we know the outcome in this case completely.

Now suppose that pivotal voter moves '''B''' above '''A''', but keeps '''C''' in the same position and imagine that any number (even all!) of the other voters change their ballots to move '''B''' below '''C''', without changing the position of '''A'''. Then aside from a repositioning of '''C''' this is the same as ''profile k'' from part one and hence the societal outcome ranks '''B''' above '''A'''. Furthermore, by IIA the societal outcome must rank '''A''' above '''C''', as in the previous case. In particular, the societal outcome ranks '''B''' above '''C''', even though Pivotal Voter may have been the ''only'' voter to rank '''B''' above '''C'''. [[Condorcet paradox|By]] IIA, this conclusion holds independently of how '''A''' is positioned on the ballots, so pivotal voter is a dictator for '''B''' over '''C'''.

==== Part three: There exists a dictator ====
[[File:Diagram_for_part_three_of_Arrow's_Impossibility_Theorem.svg|thumb|Part three: Since voter ''k'' is the dictator for '''B''' over '''C''', the pivotal voter for '''B''' over '''C''' must appear among the first ''k'' voters. That is, ''outside'' of segment two. Likewise, the pivotal voter for '''C''' over '''B''' must appear among voters ''k'' through ''N''. That is, outside of Segment One.]]
In this part of the argument we refer back to the original ordering of voters, and compare the positions of the different pivotal voters (identified by applying parts one and two to the other pairs of candidates). First, the pivotal voter for '''B''' over '''C''' must appear earlier (or at the same position) in the line than the dictator for '''B''' over '''C''': As we consider the argument of part one applied to '''B''' and '''C''', successively moving '''B''' to the top of voters' ballots, the pivot point where society ranks '''B''' above '''C''' must come at or before we reach the dictator for '''B''' over '''C'''. Likewise, reversing the roles of '''B''' and '''C''', the pivotal voter for '''C''' over '''B''' must be at or later in line than the dictator for '''B''' over '''C'''. In short, if ''k''<sub>X/Y</sub> denotes the position of the pivotal voter for '''X''' over '''Y''' (for any two candidates '''X''' and '''Y'''), then we have shown

: ''k''<sub>B/C</sub> ≤ k<sub>B/A</sub> ≤ ''k''<sub>C/B</sub>.

Now repeating the entire argument above with '''B''' and '''C''' switched, we also have

: ''k''<sub>C/B</sub> ≤ ''k''<sub>B/C</sub>.

Therefore, we have

: ''k''<sub>B/C</sub> = k<sub>B/A</sub> = ''k''<sub>C/B</sub>

and the same argument for other pairs shows that all the pivotal voters (and hence all the dictators) occur at the same position in the list of voters. This voter is the dictator for the whole election.
{{Collapse bottom}}