Arrow's Impossibility Theorem and Ultrafilters

Just by coincidence I have been studying Arrow’s Impossibility Theorem (AIT) and ultrafilters at the same time, and learnt that the proof of AIT can be organised very nicely in the language of ultrafilters. This was apparently first presented in a paper by Fishburn in the 1970s. Here’s how it goes.

UPDATE (2013/10/29). Apparently a better reference than Fishburn 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 is behind a paywall. Definitions

We first begin with some essential definitions. For more background see Amartya Sen’s Collective Choice and Social Welfare, Chapters 3 and 3*), or Mas-Colell, Whinston and Green’s Microeconomic Theory (MWG), Chapter 21. (Caution: what MWG call decisive Sen calls almost decisive; what MWG call completely decisive Sen calls decisive. I follow Sen). Filters and Ultrafilters

A filter is a nonempty collection $\mathscr{F}$ of subsets of some set $I$ with the following properties

• $\emptyset \notin \mathscr{F}$.
• If $A \in \mathscr{F}$ and $B \in \mathscr{F}$ then $(A \cap B) \in \mathscr{F}$.
• If $A \in \mathscr{F}$ and $B \supset A$ then $B \in \mathscr{F}$.

An ultrafilter is a filter over the set $I$ which is not a proper subset of any other filter on $I$. Ultrafilters have the following useful property: If $\mathscr{U}$ is an ultrafilter, then for any $A \subset I$ either $A$ or $A^c$ belongs to $\mathscr{U}$. In the other direction, any filter with this property is an ultrafilter.

Filters were first used to study convergence in topology. A discussion of this use is in Volume 1 of Bourbaki’s General Topology.

Almost Decisive and Decisive Sets

In the context of Arrow’s theorem a set $A$ of individuals is almost decisive for alternative $x$ over alternative $y$ ($x \neq y$) if the social preference is $x \succ y$ whenever $x \succ_i y$ for $i \in A$ and $y \succ_i x$ for $i \notin A$. An almost decisive set of individuals can make $x$ prevail over $y$ in the face of the strongest opposition.

A (logically) stronger notion is that of decisiveness. A set $A$ of individuals is decisive for alternative $x$ over alternative $y$ ($x \neq y$) if the social preference is $x \succ y$ whenever $x \succ_i y$ for $i \in A$. This condition is logically stronger since we do not specify anything about the preferences of agents not in $A$.

Suppose that the following conditions are satisfied

• There are at least three alternatives.
• The social welfare function (SWF) has a universal domain.
• The SWF has the Paretian property
• The SWF has the property of independence of irrelevant alternatives (IIA).

Then the following facts are true:

• If $A$ is almost decisive for $x$ over $y$ then it is decisive for $x$ over $y$.
• If $A$ is almost decisive for $x$ over $y$ then $A$ is also almost decisive for any other alternative $u$ over any other alternative $v$. (This allows us to talk about decisive and almost decisive sets without mentioning the alternatives).
• The collection of almost decisive sets is an ultrafilter.
• If the number of agents is finite then the SWF is dictatorial.

The proofs of (1) and (2) can be found in Sen and MWG. We are interested in (3) and how that lets us prove (4) which is the AIT.

The Collection of Almost Decisive Sets is an Ultrafilter

I call a set of individuals almost decisive if every individual in the set is almost decisive. Let the collection of all almost decisive sets of individuals be denoted by $\mathscr{A}$. Let the set of all individuals be denoted by $I$. $I \in \mathscr{A}, \emptyset \notin A$.

Both follow from the Paretian property of the social welfare function. If $S \in \mathscr{A}$ and $T \in \mathscr{A}$, then$(S \cap T) \in \mathscr{A}$.

For three distinct alternatives $x$, $y$ and $z$, consider a set of individual preferences with the following rankings.

$$\begin{align*} y \succ x \succ z &\qquad S\cap T^c\\ z \succ y \succ x &\qquad T\cap S^c\\ x \succ z \succ y &\qquad S\cap T\\ y \succ z \succ x &\qquad (S\cup T)^c \end{align*}$$

Then $x \succ z$ by the almost decisiveness of $S$, $z \succ y$ by the almost decisiveness of $T$, and then by the transitivity of social preferences $x \succ y$. By independence of irrelevant alternatives (IIA) this proves the almost decisiveness of $S \cap T$ for $x$ over $y$ and hence its almost decisiveness. If $S \in \mathscr{A}$ and $T \supset S$ then $T \in \mathscr{A}$.

For three distinct alternatives $x$, $y$ and $z$, consider a set of individual preferences with the following rankings.

$$\begin{align*} x \succ y \succ z &\qquad S\\ y \succ x \succ z &\qquad T\cap S^c\\ y \succ z \succ x &\qquad T^c \end{align*}$$

Then $x \succ y$ by the almost decisiveness of $S$, $y \succ z$ by the Paretian property of the SWF. By the transitivity of social preference $x \succ z$. But since $S \subset T$, the above along with IIA shows that $T$ is almost decisive for $x$ over $z$ and hence almost decisive.

The above show that $\mathscr{A}$ is a filter. We next show that it is in fact an ultrafilter. For any $S$, either $S \in \mathscr{A}$ or $S^c \in \mathscr{A}$

For three distinct alternatives $x$, $y$ and $z$, consider a set of individual preferences with the following rankings.

$$\begin{align*} x \succ z \succ y &\qquad S\\ y \succ x \succ z &\qquad S^c \end{align*}$$

Given these individual preferences, if the social preference is $x \succ y$ then this shows that $S$ is almost decisive for $x$ over $y$ and hence almost decisive.

The other possibility is $y \succeq x$. Since we have from the Paretian property that $x \succ z$ it follows in this case that $y \succ z$ which shows that $S^c$ is almost decisive for $y$ over $z$ and hence almost decisive. On a finite set all ultrafilters are principal ultrafilters.

A principal ultrafilter is an ultrafilter consisting of all subsets of $I$ which contain a particular element $i$. The result we wish to prove is purely a result about ultrafilters and is independent of AIT.

Let $I$ be a finite set consisting of elements $x_i, i=1,\ldots,n$. Let $\mathscr{U}$ be an ultrafilter on $I$. Since it is an ultrafilter, for every $S \subset I$ either $S$ or $S^c$ belongs to $\mathscr{U}$. Consider the sets $\{x_i\}, i=1,\ldots,n$. If any of the sets belongs to $\mathscr{U}$ then $\mathscr{U}$ is a principal ultrafilter.

Suppose on the contrary for every $i$ the set $\{x_i\}^c \in \mathscr{U}$. Then because $I$ is finite, we can use property (2) of a filter and mathematical induction to conclude that $\cap_{i=1}^n \{x_i\}^c$ must also belong to $\mathscr{U}$. But this set is empty since each $x_i$ is missing from one of the sets, which contradicts property (1) of a filter, which we had assumed $\mathscr{U}$ to be.

Arrow’s Impossibility Theorem Holds

We have shown that the set of almost decisive sets is an ultrafilter. Since the set of agents is finite it is a principal ultrafilter, i.e. it contains some singleton $\{x\}$. So $x$ is almost decisive. Since every almost decisive agent is decisive it follows that $x$ is a dictator.

The above proof would not work for an infinite set of agents since then ever ultrafilter is not necessary a principal ultrafilter. I believe Fishburn gives counterexamples to show that AIT does not hold when the number of agents is infinite.