Another example of the use of ultrafilters in social choice theory is provided by the Gibbard-Satterthwaite theorem, which states that any non-dictatorial election in which it is possible for any candidate to win is susceptible to tactical voting. That is, in some situations, a voter will achieve a better result, according to his genuine preferences, by not voting according to his genuine preferences. The Duggan-Schwartz theorem is a related result concerning elections with multiple winners.

More explicitly: we again have a set of voters , each voting by imposing a linear order on a set of alternatives (we will call any such -tuple of linear orders a “profile”). This time, however, our goal is more modest: we only wish to pick a single winning alternative from (i.e. provide a function from the set of voter preferences to , called the collective choice procedure). Our demands are:

- every candidate can win, given a suitable set of voter preferences (non-imposition)
- knowing the votes of other voters does not give anyone an incentive to change their own vote (stability / non-manipulability)

That is, given the preferences of all voters except for , the winning alternative when votes according to his sincere preferences is preferred by to the alternatives which would win if voted otherwise. We will demonstrate that again, any function which satisfies these two demands is dictatorial in the sense of simply returning the top preference of some particular voter. (The proof is based on the paper Stability of Aggregation Procedures, Ultrafilters and Simple games by P. Bateau, J.-M. Blin and B. Monjardet. I tried to make the argument as informal as possible without losing the rigour. For the definition of an ultrafilter, see the previous post.)

First, a quick ultrafilter lemma:

**Lemma** (a characterization of ultrafilters):

Every family of subsets of a non-empty set satisfying the following conditions is an ultrafilter:

**Proof**: if , then we would have both and , therefore (non-triviality). Now let us assume that , but . Then , but . Therefore has the finite intersection property and is an ultrafilter.

Now, back to social choice theory. Let’s say that for a profile , the collective choice is . We would like know what happens when some of the voters change their preferences. For notational convenience, let be the set of voters which prefer to .

**Lemma** (about stable collective choice):

For any stable collective choice procedure , if and , then .

**Proof**: first, we will define a function which takes a profile as an argument and returns the set of all profiles which result from applying the follow operation to :

- if voter prefers to in , the pair , gets moved to the beginning of his ranking in this order in
- if voter prefers to in , the pair , gets moved to the beginning of his ranking in either order in
- every other ranking in the profile remains the same

In other words, and get moved to the front of and doesn’t drop in ranking relative to . Likewise, is the set of all profiles which result from successively applying this operation to every voter.

It is not difficult use the stability of to prove that since , we have (meaning: every profile which results from applying the operation to picks out ). By applying this to each voter, we obtain the same result for .

Now, by the hypothesis of this theorem, ( places at least as many constraints on the operation as ). Thus, . But if it were the case that for some , we would have , which is a contradiction, since and have a non-empty intersection.

Combining this lemma with the assumption of non-imposition yields the weak Pareto property: if everyone prefers to , cannot be the collective choice.

Armed with these results, we can now explore the structure of “preventing families”. A set of voters is said to be a member of the preventing family for a collective choice procedure iff can never get chosen by the procedure when all members of prefer to (the members of can prevent from being chosen by unanimously preferring ).

**Lemma** (about preventing families):

- is non-empty: trivial
- : follows easily from the weak Pareto property
- : by the previous property and the theorem about collective choice
- : easy application of the weak Pareto property

It would seem reasonable to demand that be the same for every . Fortunately, we do not have to, as the following theorem shows:

**Lemma** (neutrality of stable collective choice procedures):

for any .

**Proof**: let us first show that (hence ) for any . Pick and and consider a profile such that are the top three choices of every voter and:

- for
- for
- for
- for

Then by the weak Pareto property, , but and . Thus, and by property (2) of preventing families, .

The same reasoning applied to and the profile:

- for
- for
- for
- for

shows that .

Applying this result to properties (3) and (4) of preventing families, we see that the unique preventing family in fact satisfies the first two conditions of the ultrafilter lemma. The last step of the proof of the Gibbard-Satterthwaite theorem will be to show that it also satisfies the last one.

**Lemma**:

The preventing family is an ultrafilter.

**Proof**: the first two conditions of the ultrafilter lemma are satisfied. As for the last one, let us assume that , but . We could then construct a profile such that:

- for
- for
- for
- otherwise

By the weak Pareto property, . But since , .

In view of the fact that every ultrafilter on a finite set is principal (consists precisely of its subsets containing a given element), this concludes the proof of the Gibbard-Satterthwaite theorem: every stable, non-imposed collective choice procedure for at least three alternatives is dictatorial. Conversely, a free ultrafilter on an infinite set corresponds to a stable non-dictatorial collective choice procedure (or, more accurately, a collective choice function).

April 10, 2014 at 1:56 pm

Proof of lemma about stable collective choice is incorrect. Starting from the words “now, by the hypothesis of this theorem” there is an incorrect statement, because actually there’s no restriction on \pi’ profile for elements except x and y. So as a set \phi^{xy}(\pi) can have zero intersection with \phi^{xy}(\pi) in case when some voters change their opinion completely.

March 12, 2021 at 5:20 pm

[…] 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 didn’t […]