Ultrafilters and Social Choice II

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 V, each voting by imposing a linear order \prec_i on a set of alternatives A, |A| \geq 3 (we will call any such V-tuple of linear orders a “profile”). This time, however, our goal is more modest: we only wish to pick a single winning alternative from A (i.e. provide a function c from the set of voter preferences \Pi to A, 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 i, the winning alternative when i votes according to his sincere preferences is preferred by i to the alternatives which would win if i 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 \mathcal{F} of subsets of a non-empty set X satisfying the following conditions is an ultrafilter:

  • A \in \mathcal{F} ~ \& ~ A \subseteq B \subseteq X \Rightarrow B \in \mathcal{F}
  • A \in \mathcal{F} \Leftrightarrow X \backslash A \notin \mathcal{F}
  • A,B,C \in \mathcal{F} \Rightarrow A \cap B \cap C \neq \emptyset

Proof: if \emptyset \in \mathcal{F}, then we would have both X \in \mathcal{F} and X \notin \mathcal{F}, therefore \emptyset \notin \mathcal{F} (non-triviality). Now let us assume that A,B \in \mathcal{F}, but A \cap B \notin \mathcal{F}. Then X \setminus (A \cap B) \in \mathcal{F}, but A \cap (X \setminus (A \cap B)) \cap B = \emptyset. Therefore \mathcal{F} has the finite intersection property and is an ultrafilter.

Now, back to social choice theory. Let’s say that for a profile \pi, the collective choice is c(\pi)=x. We would like know what happens when some of the voters change their preferences. For notational convenience, let V_{xy} be the set of voters which prefer x to y.

Lemma (about stable collective choice):

For any stable collective choice procedure c, if c(\pi)=x and V_{xy}(\pi^\prime) \supseteq V_{xy}(\pi), then c(\pi^\prime) \neq y.

Proof: first, we will define a function \varphi_i^{xy}(\pi) which takes a profile as an argument and returns the set of all profiles which result from applying the follow operation to \pi:

  • if voter i prefers x to y in \pi, the pair x, y gets moved to the beginning of his ranking in this order in \pi^\prime
  • if voter i prefers y to x in \pi, the pair x, y gets moved to the beginning of his ranking in either order in \pi^\prime
  • every other ranking in the profile remains the same

In other words, x and y get moved to the front of \pi_i and x doesn’t drop in ranking relative to y. Likewise, \varphi^{xy} is the set of all profiles which result from successively applying this operation to every voter.

It is not difficult use the stability of c to prove that since c(\pi)=x, we have c[\varphi_i^{xy}(\pi)]=\{x\} (meaning: every profile which results from applying the operation to \pi picks out x). By applying this to each voter, we obtain the same result for \varphi^{xy}.

Now, by the hypothesis of this theorem, \varphi^{xy}(\pi^\prime) \subseteq \varphi^{xy}(\pi) (\pi^\prime places at least as many constraints on the operation as \pi). Thus, c[\varphi^{xy}(\pi^\prime)]=\{x\}. But if it were the case that c(\pi^\prime)=y for some y \neq x, we would have c[\varphi^{yx}(\pi^\prime)]=\{y\}, which is a contradiction, since \varphi^{xy}(\pi^\prime) and \varphi^{yx}(\pi^\prime) have a non-empty intersection.

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

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

Lemma (about preventing families):

  1. \mathcal{F}_{xy} is non-empty: trivial
  2. S\in\mathcal{F}_{xy} \Leftrightarrow \exists \pi: V_{xy}(\pi) = S \& c(\pi)=x: follows easily from the weak Pareto property
  3. S\in\mathcal{F}_{xy} \& S \subseteq T \Rightarrow T\in\mathcal{F}_{xy}: by the previous property and the theorem about collective choice
  4. S\in\mathcal{F}_{yx} \Leftrightarrow V\setminus S \notin \mathcal{F}_{xy}: easy application of the weak Pareto property

It would seem reasonable to demand that \mathcal{F}_{xy} be the same for every x, y. Fortunately, we do not have to, as the following theorem shows:

Lemma (neutrality of stable collective choice procedures):

\mathcal{F}_{xy} = \mathcal{F}_{zt} = \mathcal{F} for any x, y, z, t.

Proof: let us first show that \mathcal{F}_{xy} \subseteq \mathcal{F}_{xz} (hence \mathcal{F}_{xy} = \mathcal{F}_{xz}) for any x, y, z. Pick S\in\mathcal{F}_{xy} and T\in\mathcal{F}_{yz} and consider a profile \pi such that x, y, z are the top three choices of every voter and:

  • x >_i z >_i y for i \in S \setminus T
  • x >_i y >_i z for i \in S \cap T
  • y >_i z >_i x for i \in T \setminus S
  • z >_i y >_i x for i \in V \setminus (S \cup T)

Then by the weak Pareto property, c(\pi) \in \{x, y, z\}, but S \in \mathcal{F}_{xy} \Rightarrow c(\pi) \neq y and T \in \mathcal{F}_{yz} \Rightarrow c(\pi) \neq z. Thus, c(\pi)=x and by property (2) of preventing families, S \in \mathcal{F}_{xz}.

The same reasoning applied to S\in\mathcal{F}_{xy}, T\in\mathcal{F}_{zx} and the profile:

  • x \succ_i z \succ_i y for i \in S \setminus T
  • z \succ_i x \succ_i y for i \in S \cap T
  • y \succ_i z \succ_i x for i \in T \setminus S
  • y \succ_i x \succ_i z for i \in V \setminus (S \cup T)

shows that S\in\mathcal{F}_{zy}.

Applying this result to properties (3) and (4) of preventing families, we see that the unique preventing family \mathcal{F} 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.


The preventing family \mathcal{F} is an ultrafilter.

Proof: the first two conditions of the ultrafilter lemma are satisfied. As for the last one, let us assume that S, T, U \in \mathcal{F}, but S \cap T \cap U = \emptyset. We could then construct a profile \pi such that:

  • x \succ_i y for i \in S
  • y \succ_i z for i \in T
  • z \succ_i x for i \in U
  • x \succ_i y \succ_i z otherwise

By the weak Pareto property, c(\pi) \in \{x, y, z\}. But since S, T, U \in \mathcal{F}, c(\pi) \neq y, c(\pi) \neq z, c(\pi) \neq x.

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).

Tags: , ,

2 Responses to “Ultrafilters and Social Choice II”

  1. Anonymous Says:

    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.

  2. The impossible democracy – Nadir Says:

    […] 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 […]

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: