Ultrafilters and Social Choice

I was somewhat suprised recently to learn that Arrow’s well-known impossibility theorem (which, as many of you will know, states that there is in general no way of aggregating individual preferences into a single ordering satisfying certain natural conditions) fails for infinitely many voters. If anything, shouldn’t it be more difficult to come up with a “fair” voting procedure for an infinite electorate? Well, as it turns out, the answer to this question has to do with an abstract notion often used in topology and model theory, that of an ultrafilter. For those already familiar with this notion, Arrow’s theorem essentially corresponds to the statement that every ultrafilter on a finite set is principal.

Let us first define a more general notion. A filter \mathcal{F} on a set X is a family of subsets of X such that:

  • \emptyset\notin \mathcal{F} (non-triviality)
  • A\in\mathcal{F} ~ \& ~ A\subseteq B \subseteq X \Rightarrow B \in\mathcal{F} (superset property)
  • A,B\in\mathcal{F} \Rightarrow A\cap B \in\mathcal{F} (finite intersection property)

An ultrafilter \mathcal{F} is a filter such that for all A\subseteq X:

  • A\in\mathcal{F} \vee X \backslash A\in\mathcal{F} (maximality)

By non-triviality and the finite intersection property, only one of these options can hold, hence every ultrafilter on X is maximal in the sense that it cannot be extended to a larger filter on X. A trivial example of an ultrafilter is provided by the family \mathcal{F}_a(X) of subsets of X which contain a given element a. Such ultrafilters are called “principal”. It is easy to show that every ultrafilter on a finite set is principal. On the other hand, the existence of non-principal ultrafilters (also called “free”) cannot be proven in ZF. Proving their existence requires adding a non-constructive choice principle to the axioms of ZF. In particular, assuming that every filter can be extended to an ultrafilter is equivalent to the Boolean prime ideal theorem, a principle strictly weaker than the Axiom of Choice but still independent of ZF. Applying this to, for example, the filter of cofinite subsets of an infinite set yields a free ultrafilter.

The intuitive interpretation of an (ultra)filter is that it specifies which subsets are to be considered “large”. A property holds for “almost all” elements of a set if the set of elements for which it holds is contained in the relevant (ultra)filter – for example, if its complement is finite. (This is a generalization of the measure-theoretic notion of “almost everywhere”, i.e. on a set of full measure. Indeed, an ultrafilter can be thought of as a finitely additive zero-one measure.) This interpretation suggests a natural connection to social choice theory – if “almost all” voters prefer A to B, we would ideally like to rank A higher than B.

And indeed, this is what Arrow’s conditions imply (the following proof is based on these notes by A. McLennan [pdf]). Arrow considers a situation in which we have a set of voters V, each linearly ordering a set of three or more alternatives A according to his preferences (we will symbolize the i-th voter’s ordering by \prec_i). The task is to find a reasonable procedure (“social welfare function”) for aggregating their preferences into a single linear ordering of social preference (\prec). The natural conditions which Arrow imposes on this procedure are:

  • If every voters prefers x to y, the society prefers x to y. (unanimity)
  • The social preference between x and y depends only on the voters’ preferences between x and y, i.e. not on their ranking of other alternatives. (independence of irrelevant alternatives)

We will say that a set of voters C_{xy} is decisive for x over y if, whenever all the voters in C_{xy} prefer x to y and the rest of the voters V \backslash C_{xy} prefer y to x, the society prefers x to y. First let us prove that if C is a decisive coalition for some x over some y, it is decisive for every alternative over any other. If C is decisive for x over y, then let us consider a set of voter preferences such that x \succ_i y \succ _i z for i \in C and y \succ_i z \succ_i x for i \in V \backslash C. Because C is decisive for x over y, we have x \succ y, unanimity implies y \succ z and transitivity means that x \succ z. Therefore (by IIA), C is also decisive for x over z. A symmetric argument shows that C is also decisive for t over z for any t,z.

We now wish to prove that the family of decisive sets does in fact form an ultrafilter. First, non-triviality immediately follows from unanimity. Second, the intersection property. Let us assume that C and D are decisive and consider the set of voter preferences defined thus:

  • x \succ_i z \succ_i y for i \in C \cap D
  • z \succ_i y \succ_i x for i \in C \backslash D
  • y \succ_i x \succ_i z for i \in D \backslash C
  • y \succ_i z \succ_i x for i \in V \backslash (C \cap D)

Then x \succ z by the decisiveness of D and z \succ y by the decisiveness of C, hence x \succ y by transitivity and C \cap D is decisive by IIA.

Third, maximality. Consider the set of preferences x \succ_i z \succ_i y for C and y \succ_i x \succ_i z for V \backslash C. If neither C nor V \backslash C were decisive, then x cannot be socially preferred to y, nor y to z, but by unanimity x \succ z.

And finally, the superset property follows from the fact that if C \subseteq D and C is decisive, V \backslash D cannot be decisive (by the finite intersection property and non-triviality).

If V is finite, we can conclude the proof of Arrow’s theorem by noting that every ultrafilter on V is principal, i.e. for some a \in V, \{a\} is a decisive coalition and the social preference is always simply a copy of a’s preferences. Therefore, every social welfare function for a finite number number of voters at least three alternatives which satisfies unanimity and IIA is dictatorial in this sense.

For an infinite number of voters, the existence of such a function cannot be disproven and in fact follows from the Axiom of Choice or the weaker Boolean Prime Ideal Theorem (although calling it a “procedure” is somewhat hyperbolic due to the non-constructive nature of free ultrafilters). If there are only two alternatives to choose from, Arrow’s result is complemented by May’s theorem, which states that simple majority voting is the canonical choice.

And an interesting, if only tangentially related factoid to end with: for exactly three choices and a large number of voters, the relative prevalence of the Condorcet effect (cycles in social preference which prevent us from applying a simple majority rule) tends to 1 - \frac{3}{\pi}\arccos\left(\frac{1}{\sqrt{3}}\right) \approx 9 \% according to this paper by G.-T. Guilbaud [pdf].

Tags: , , ,

3 Responses to “Ultrafilters and Social Choice”

  1. Lizzie Says:

    Cool. I think 🙂

  2. Voting Theory & My First Coursera Experience | justincarcher Says:

    […] During week five I was critical of the proof the instructor gave for a certain result (taken from this paper). Also, it is noticed how ultrafilters play an important role in many of the impossibility theorems of social choice theory (incl Arrow’s Thm). […]

  3. The impossible democracy – Nadir Says:

    […] the blog Algorithmically Incompressible Thoughts, (“Ultrafilters and social choice”, part 1 and part 2). I always wanted to have a clear and accessible presentation of this subject, but I […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: