Arrow's Impossibility Theorem and Ultrafilters

Oct. 28, 2013

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 II with the following properties

  • \emptyset \notin \mathscr{F}.
  • If AA \in \mathscr{F} and BB \in \mathscr{F} then (AB)(A \cap B) \in \mathscr{F}.
  • If AA \in \mathscr{F} and BAB \supset A then BB \in \mathscr{F}.

An ultrafilter is a filter over the set II which is not a proper subset of any other filter on II. Ultrafilters have the following useful property: If 𝒰\mathscr{U} is an ultrafilter, then for any AIA \subset I either AA or AcA^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 AA of individuals is almost decisive for alternative xx over alternative yy (xyx \neq y) if the social preference is xyx \succ y whenever xiyx \succ_i y for iAi \in A and yixy \succ_i x for iAi \notin A. An almost decisive set of individuals can make xx prevail over yy in the face of the strongest opposition.

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

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 AA is almost decisive for xx over yy then it is decisive for xx over yy.
  • If AA is almost decisive for xx over yy then AA is also almost decisive for any other alternative uu over any other alternative vv. (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 II. I𝒜,AI \in \mathscr{A}, \emptyset \notin A.

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

For three distinct alternatives xx, yy and zz, consider a set of individual preferences with the following rankings.

yxzSTczyxTScxzySTyzx(ST)c \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 xzx \succ z by the almost decisiveness of SS, zyz \succ y by the almost decisiveness of TT, and then by the transitivity of social preferences xyx \succ y. By independence of irrelevant alternatives (IIA) this proves the almost decisiveness of STS \cap T for xx over yy and hence its almost decisiveness. If S𝒜S \in \mathscr{A} and TST \supset S then T𝒜T \in \mathscr{A}.

For three distinct alternatives xx, yy and zz, consider a set of individual preferences with the following rankings.

xyzSyxzTScyzxTc \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 xyx \succ y by the almost decisiveness of SS, yzy \succ z by the Paretian property of the SWF. By the transitivity of social preference xzx \succ z. But since STS \subset T, the above along with IIA shows that TT is almost decisive for xx over zz 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 SS, either S𝒜S \in \mathscr{A} or Sc𝒜S^c \in \mathscr{A}

For three distinct alternatives xx, yy and zz, consider a set of individual preferences with the following rankings.

xzySyxzSc \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 xyx \succ y then this shows that SS is almost decisive for xx over yy and hence almost decisive.

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

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

Let II be a finite set consisting of elements xi,i=1,,nx_i, i=1,\ldots,n. Let 𝒰\mathscr{U} be an ultrafilter on II. Since it is an ultrafilter, for every SIS \subset I either SS or ScS^c belongs to 𝒰\mathscr{U}. Consider the sets {xi},i=1,,n\{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 ii the set {xi}c𝒰\{x_i\}^c \in \mathscr{U}. Then because II is finite, we can use property (2) of a filter and mathematical induction to conclude that i=1n{xi}c\cap_{i=1}^n \{x_i\}^c must also belong to 𝒰\mathscr{U}. But this set is empty since each xix_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}\{x\}. So xx is almost decisive. Since every almost decisive agent is decisive it follows that xx 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.