Today, we present a curious “practical” application of ultrafilters, especially relevant in this election season. We will eventually consider elections with infinitely many voters, but let us first look at the classical case with a finite electorate.
Suppose that there are three or more political candidates, named , vying for political office, and finitely many voters in the electorate. Each voter ranks the candidates in the order in which they prefer them, and the outcome of the election is a collective ranking of the candidates. (We will not deal here with elections in which the result is a single winner rather than a complete ranking, but similar results hold there. We will also not deal with elections between two candidates.)
It has long been clear that aggregating individual rankings into a collective ranking in a “fair” way is a tough problem. Difficulties already arise in the following simple example: Suppose there are three candidates: A, B, and C, and three voters: U, V, and W. Suppose U’s ranking is ABC, V’s is BCA, and W’s is CAB. No collective ranking seems particularly good here. ABC, for example, seems unfair since two of the three voters in fact prefer C to A, while the collective ranking has A first and C last! Similar problems arise with the other possibilities. This particular example was recognized by the Marquis de Condorcet (for whom Condorcet voting methods are named) in 1785.
While the best way to aggregate individual rankings into a collective ranking is unclear, there are some criteria one would expect a good system to satisfy.
- (Unanimity) If every voter has the same ranking of candidates, then that ranking is the final outcome.
- (Irrelevant Alternatives) The relative ranking of two candidates and in the final outcome depends only on the relative ranking of those two candidates in the individual votes.
Let us call a system for converting individual rankings into a collective ranking a voting system. One particular type of voting system is what we will call a dictatorial voting system. In a dictatorial voting system, there is one distinguished voter (call this voter D) such that, regardless of the votes of the other voters, the final ranking will be exactly the ranking in D’s vote. In the context of this vote, at least, D is a dictator who single-handedly determines the outcome of the election.
A dictatorial voting system satisfies the unanimity and irrelevant alternatives criteria for somewhat trivial reasons. It is obviously not, though, what one has in mind when thinking of free, democratic, elections, as the voices of all voters except one are entirely irrelevant. However, a remarkable and famous result of Kenneth Arrow shows that, if one wants to avoid a dictatorial voting system, one must violate either the unanimity or irrelevant alternatives criterion. This result, and others that followed it, are often paraphrased as stating that there are no perfect voting systems.
Arrow’s Impossibility Theorem: Suppose that, in an election with finitely many voters and three or more candidates, a voting system satisfies the unanimity and irrelevant alternatives criteria. Then it is a dictatorial voting system.
Let us remove now our assumption that there are only finitely many voters, while retaining the assumption that only finitely many candidates run in any given election. The notion of a voting system still makes sense, as do the unanimity and irrelevant alternatives criteria. And here ultrafilters make their entrance. Ultrafilters can be seen as ways of choosing between finitely many alternatives, and, as such, they provide natural voting systems.
Let us be a bit more precise. Suppose that, in an election in which voters rank all candidates, is the set of voters and is the list of candidates, where is a natural number. Let be an ultrafilter on . By the properties of an ultrafilter, if we partition into finitely many pieces, then exactly one of those pieces is in . This allows us to define a voting system, which we will call the -voting system, as follows. For every possible ranking of the candidates, let be the set of voters with individual ranking . Since there are candidates, there are (i.e. ) possible rankings of these candidates. In particular, there are only finitely many, so there is some ranking such that . The -voting system then declares to be the collective ranking.
These voting systems mesh with our intuition that an ultrafilter is a mechanism for specifying which subsets of a given set should be considered “large.” In an election, we expect the final outcome to reflect the desires of a “large” portion of the electorate; one way to do this is to use an ultrafilter to specify exactly which sets of voters should be considered “large” and then to declare the result of the election to be the ranking chosen by a large set.
What happens if is a principal ultrafilter? Then there is one voter such that . In this case, the -voting system will simply return the ranking of voter as the collective ranking, ignoring the other voters. In other words, the -voting system is a dictatorial voting system.
If is an ultrafilter on , then the -voting system is easily seen to satisfy the unanimity and irrelevant alternatives criteria. What might be surprising is that these are the only such voting systems! Namely, we can generalize Arrow’s Impossibility Theorem to allow for a possibly infinite electorate as follows.
Generalized Arrow’s Impossibility Theorem: Suppose that, in an election, is the set of voters and is the list of candidates, where is a natural number. Then any voting system which satisfies the unanimity and irrelevant alternatives criteria must be the -voting system for some ultrafilter on .
First note that this theorem truly does generalize Arrow’s Impossibility Theorem: if is finite, then any ultrafilter on must be principal and thus yield a dictatorial voting system. Also note that, with an infinite electorate, there are voting systems that satisfy the unanimity and irrelevant alternatives criteria but are not dictatorial: any -voting system in which is a non-principal ultrafilter will do the trick.
Before you write to Congress suggesting that we move towards elections with infinitely many voters based on non-principal ultrafilters, though, note that these voting systems, at least naively implemented, may not be what we actually want. For, consider a -voting system, where is a non-principal ultrafilter on an infinite electorate . Suppose that the electorate consists of, say, two sexes: male and female. Then one of these sexes will comprise a set in , while the votes of the other will be entirely irrelevant. Or suppose that our infinite electorate is divided amongst our current fifty states. Then the set of voters in one of these states (Kansas, say) will be in the ultrafilter, in which case the election will depend solely on the votes of the Kansas voters. Perhaps this just means, though, that the members of our infinite electorate should not be so simply categorized or placed on a linear spectrum, as any attempt to do so necessarily disenfranchises certain groups. Perhaps this has something to say about finite societies as well. Perhaps…
That’s enough for today. I will not give the proof of the generalized impossibility theorem here. It’s not terribly difficult, but it is somewhat long and technical. Interested readers can consult David Galvin’s notes on ultrafilters. Come back next week, when I will present and actually prove a similar result about infinite lightbulb-switching schemes.