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 on a set is a family of subsets of such that:

• (non-triviality)
• (superset property)
• (finite intersection property)

An ultrafilter is a filter such that for all :

• (maximality)

By non-triviality and the finite intersection property, only one of these options can hold, hence every ultrafilter on is maximal in the sense that it cannot be extended to a larger filter on . A trivial example of an ultrafilter is provided by the family of subsets of which contain a given element . 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 , each linearly ordering a set of three or more alternatives according to his preferences (we will symbolize the -th voter’s ordering by ). The task is to find a reasonable procedure (“social welfare function”) for aggregating their preferences into a single linear ordering of social preference (). 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 is decisive for x over y if, whenever all the voters in prefer x to y and the rest of the voters prefer y to x, the society prefers x to y. First let us prove that if is a decisive coalition for some x over some y, it is decisive for every alternative over any other. If is decisive for x over y, then let us consider a set of voter preferences such that for and for . Because is decisive for x over y, we have , unanimity implies and transitivity means that . Therefore (by IIA), is also decisive for x over z. A symmetric argument shows that 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 and are decisive and consider the set of voter preferences defined thus:

• for
• for
• for
• for

Then by the decisiveness of and by the decisiveness of , hence by transitivity and is decisive by IIA.

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

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

If is finite, we can conclude the proof of Arrow’s theorem by noting that every ultrafilter on is principal, i.e. for some , 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 according to this paper by G.-T. Guilbaud [pdf].

Tags: arrow's theorem, social choice, social choice theory, ultrafilters