I'm attempting to read this PDF on Arrow's impossibility theorem and ultrafilters. I find myself unconvinced that the proof of their Lemma 13 demonstrates what they say it does. I'm hoping someone can help shed light on whether the proof works, and if it does, how it works.
First, I will introduce (what I hope is,) enough of the descriptions of the notation used for others to be able to follow along without needing to read the PDF.
The PDF defines a voting system as a tuple $(A, V, F)$ consisting of a set of candidates $A$, a set of voters $V$ and a function $F$ which given a collection of voter preferences $(C_v)_{v ∈ V}$ produces a chain of candidates, representing the election results.
The following potential properties of voting systems are defined as follows in the PDF:
- (Unanimity) For any $a, b ∈ A$, for any preference profile $(C_v)_{v∈V}$, if for all $v∈V$, $a <^{C_v} b$, then in the election result $C$ also $a <^C b$. In other words,if $b$ is preferred to $a$ by every voter, then in the election result $b$ is also preferred to $a$.
- (Independence of irrelevant alternatives) For any $a, b∈A$, for any two preference profiles $(C_v)_{v∈V}$ and $(D_v)_{v∈V}$, if for all $v∈V$, $a <^{C_v} b$ if and only if $a <^{D_v} b$, then $a <^C b$ if and only if $a <^D b$, where $C$ and $D$ are the election results for $(C_v)_{v∈V}$ and $(D_v)_{v∈V}$. In other words, introduction of other candidates than $a$ or $b$ should not influence their order in an election.
Also relevant is this definition of a decisive voter ...
For a voting system $(A, V, F)$, a subset $X$ of $V$ is called decisive if for any chain $C$ with universe $A$ and any preference profile $(C_v)_{v∈V}$, if $C_v=C$ for all $v∈X$, then $F((C_v)_{v∈V}) = C$. We say that $v∈V$ is decisive if $\{v\}$ is decisive.
... which is used in this definition of what it means for a voter to be decisive for a pair of candidates:
For $(A, V, F)$ a voting system and $a \neq b$ both in $A$, we say that a subset $X$ of $V$ is decisive for the pair $(a, b)$ if for any chain $C$ with universe $A$ and any preference profile $(C_v)_{v∈V}$, if $a <^{C_v} b$ for all $v∈X$, then $a <^{F((C_v)_{v∈V})} b$. We say that $v∈V$ is decisive for $(a, b)$ if $\{v\}$ is decisive for $(a, b)$.
Here's a quote from the PDF regarding some further notation:
...we introduce some notation. Fix a voting system $(A, V, F)$ and distinct $v_1, v_2, v_3 ∈ V$. We will write (for example) $ \begin{array}{lr} v_1: & a_1a_2a_3... a_n \\ v_2: & b_1b_2b_3... b_m \\ v_3: & c_1c_2c_3... c_k \\ \hline \text{Outcome}: & d_1d_2d_3... d_r \end{array} \\ $
If for some preference profile $(C_v)_{v ∈ V}$, if $C_{v_1} \vDash a_1< a_2. . . < a_n$, $C_{v_2} \vDash b_1< b_2<. . . < b_m$, and $C_{v_3} \vDash c_1< . . . < c_k$, then $ F((C_v)_{v ∈ V}) \vDash d_1< d_2< . . . < d_r.$ Note that, by the independence of irrelevant alternatives, if this holds for some preference profiles, this holds for all preference profiles satisfying the given orderings.
With all that background, we can finally introduce Lemma 13.
Lemma 13. Assume $(A, V, F)$ is a voting system with $|V|= 2$ satisfying unanimity and the independence of irrelevant alternatives. Assume $v∈V$ and $a, b, c$ are distinct elements of $A$. If $v$ is decisive for $(a, b)$, then $v$ is decisive for $(a, c)$ and decisive for $(b, c)$. Proof. Write $V=\{v, w\}$. Since $v$* is decisive for $(a, b)$, we have:
$ \begin{array}{lr} v: & ab \\ w: & ba \\ \hline \text{Outcome}: & ab \end{array} $
By unanimity ($c$ is after $b$ in both rankings):
$ \begin{array}{lr} v: & abc \\ w: & bca \\ \hline \text{Outcome}: & abc \end{array} $
By the independence of irrelevant alternatives:
$ \begin{array}{lr} v: & ac \\ w: & ca \\ \hline \text{Outcome}: & ac \end{array} $
This shows that $v$ is decisive for $(a, c)$. Now using unanimity (adding $b$ before $a$ in both ranking)
$ \begin{array}{lr} v: & bac \\ w: & cba \\ \hline \text{Outcome}: & bac \end{array} $
Thus by the independence of irrelevant alternatives:
$ \begin{array}{lr} v: & bac \\ w: & cba \\ \hline \text{Outcome}: & bac \end{array} $
This shows that $v$ is decisive for $(b, c)$.
The above proof has 5 instances of the introduced notation involving rows of pertaining to voters above an outcome row. I'll call these steps 1 to five based on the order they appear in the proof.
The part I take issue with is, given we used $b$ in step 2 here ...:
$ \begin{array}{lr} v: & abc \\ w: & bca \\ \hline \text{Outcome}: & abc \end{array} $
... I question the legitimacy of the move from step 3 here...:
$ \begin{array}{lr} v: & ac \\ w: & ca \\ \hline \text{Outcome}: & ac \end{array} $
... to step 4 here:
$ \begin{array}{lr} v: & bac \\ w: & cba \\ \hline \text{Outcome}: & bac \end{array} $
using the independence of irrelevant alternatives criteria. I think this move would be fine if we were adding in a heretofore unused candidate, say $d$, giving us
$ \begin{array}{lr} v: & dac \\ w: & cda \\ \hline \text{Outcome}: & dac \end{array} $
but I don't see why it's legitimate to identify $b$ and $d$ here, particularly since the order is changed when the $b$ preference rankings were put back. If the order is changed, that seems like a distinct set of votes to me, so I don't see how it is legitimate to make conclusions that seems to rely on two different chains of candidates, (with different orders) as being the same.
It seems to me that this is trying to prove that given $v$ is decisive for $(a, b)$, $v$ is always decisive for $(a, c)$ and $(b, c)$, but it only seems to prove that given $v$ is decisive for $(a, b)$, $v$ may be decisive for $(a, c)$, given one set of canditate chains and separately may be decisive for $(b, c)$, given a different set of candidate chains, which does not seem to allow conclusions to be drawn about properties of a set of voters given all possible sets of candidate chains with a given universe.
Can someone explain if I've misunderstood something here? And if so how/what? Alternately, if I have in fact found a problem with this proof, can the same conclusion be drawn given these definitions?
*: this was $X$ in the original but I think $v$ is correct here.
It would be more clear if we separated out the claim into two parts:
The first part of this claim is what we prove in the first half of Lemma 13.
The second part of this claim is what we prove in the second half of Lemma 13, but I've changed the variable names slightly for clarity. So let me give the proof again.
If $v$ is decisive for $(a,b)$, that means if $v$ has any ranking compatible with $a<b$ and $w$ has any ranking compatible with $b<a$, the outcome will have $a<b$.
Now suppose $v$ has any ranking compatible with $c<a<b$ and $w$ has any ranking compatible with $b<c<a$. The outcome will have $a<b$ by the above; it will have $c<a$ because both voters vote $c<a$; therefore the outcome will have $c<a<b$.
This means that if $v$ has a ranking compatible with $c<b$ and $w$ has a ranking compatible with $b<c$, then for one way to insert $a$ into those rankings, the outcome will have $c<b$. By independence of irrelevant alternatives, the outcome must have $c<b$ for all ways to insert $a$ into those rankings. The conclusion is exactly what it means for $v$ to be decisive for $(c,b)$.
To go from $(a,b)$ to $(b,c)$ in this way; first, apply the first half of the claim to go from $(a,b)$ to $(a,c)$. Then, apply the second half with $(a,c)$ playing the role of $(a,b)$ and $b$ playing the role of the third candidate to go from $(a,c)$ to $(b,c)$.