Arrow's Impossibility Theorem is false if the set of agents is infinite

This is a standard result which I had heard about and mentioned in my earlier post on Arrow’s Theorem. Fishburn’s paper where this was first proven is behind an Elsevier paywall, but the result does not seem too hard to prove. Here is an attempt.

UPDATE (2013/10/29). Got a look at Fishburn. He doesn’t mention ultrafilters by name but uses the equivalent formulation of a finitely additive 0-1 probability measure. Apparently a better reference for the ultrafilter treatment is Kirman, Alan P., and Dieter Sondermann. “Arrow’s theorem, many agents, and invisible dictators.” Journal of Economic Theory 5, no. 2 (1972): 267-277, but that too is behind a paywall.

The existence of non-principal ultrafilters

Let $X$ be the set of agents which is infinite. Let $\mathscr{F}$ be the collection of subsets of $X$ whose complements are finite. This is a filter. It dosen’t contain the null set since $X$ is infinite (this is the crucial step that will not work for a finite set). The other filter properties are easy to check.

We know from the ultrafilter lemma (which is an easy consequence of Zorn’s Lemma) that there exists an ultrafilter $\mathscr{U}$ over $X$ of which $\mathscr{F}$ is a subset. For every $\alpha \in X$ the set $\{\alpha\}^c$ belongs to $\mathscr{F}$ and hence $\mathscr{U}$. Since a filter contains either a set or its complement $\{\alpha\} \notin \mathscr{U}$.

Thus $\mathscr{U}$ is not a principal ultrafilter.

Definition of social preference relation

We choose some non-principal ultrafilter $\mathscr{U}$ over $X$ (we have shown that at least one exists) and keep it fixed for the rest of our analysis.

For any alternatives $x$ and $y$ we specify the social preference $x \succ y$ if and only if there is a set $A \in \mathscr{U}$ such that $x \succ_\alpha y$ for all $\alpha \in \mathscr{U}$.

We show that the social preference relation defined thus satisfies the conditions for a strong ordering.

Asymmetric: $x \succ y \Rightarrow y \nsucc x$

Suppose there are two alternatives $x$ and $y$ such that both $x \succ y$ and $y \succ x$. Then there must exist sets $A$ and $B$ in $\mathscr{U}$ such that $x \succ_\alpha y$ for all $\alpha \in A$ and $y \succ_\beta x$ for all $\beta \in B$. Since $\mathscr{U}$ is a filter, $(A \cap B)$ lies in $\mathscr{U}$ and is nonempty. For agents $\gamma$ in this set we must have both $x \succ_\gamma y$ and $y \succ_\gamma x$ which is not possible by the asymmetry of individual preferences.

Negatively transitive: $x \nsucc y$ and $y \nsucc z$ implies $x \nsucc z$.

For any two alternatives $u$ and $v$ we define the set $$P(u,v) = \{\xi \in X \mid u \succ_\xi v\}.$$ From our defintion of social preferences $u \succ v$ iff $P(u,v) \in \mathscr{U}$. Since an ultrafilter contains either a set or its complement it follows that $u \nsucc v$ iff $[P(u,v)]^c \in \mathscr{U}$.

Suppose $x \nsucc y$ and $y \nsucc z$. Then $[P(x,y)]^c \in \mathscr{U}$ and $[P(y,z)]^c \in \mathscr{U}$. From the finite intersection property of filters $$([P(x,y)]^c \cap [P(y,z)]^c) \in \mathscr{U}.$$ From the negative transitivity of individual preferences $$[P(x,z)]^c \supset ([P(x,y)]^c \cap [P(y,z)]^c)$$ We have shown that the set on the right-hand side of the above equation belongs to $\mathscr{U}$. Since a filter contains a set if it contains one of its subsets, it follows that $[P(x,z)]^c$ also belongs to $\mathscr{U}$.

Hence we have shown that $x \nsucc z$.

Arrow’s Conditions

We verify that the social preference relation we have defined satisfies all the four properties that Arrow’s Impossibility Theorem says are impossible to satisfy with a finite set of alternatives with more than two elements.

Paretian Property

Follows from the fact that from the definition of a filter $X \in \mathscr{U}$.

Universal Domain

We have not put any restrictions on individual preferences.

Independence of Irrelevant Alternatives

Our definition of social preferences over alternatives $x$ and $y$ makes use of individual preferences only over $x$ and $y$.

Nondictatorial

Consider an arbitrary agent $\alpha$. Consider the following pattern of individual preferences $$\begin{align*} x \succ_\alpha y\\ y \succ_\beta x&\qquad \beta \neq \alpha \end{align*}$$

By construction $\{\alpha\}^c \in \mathscr{U}$. It follows from our definition of social preferences that $y \succ x$. This shows that $\alpha$ is not a dictator.