25 June 2007

A note on ultrafilters and voting.

Terence Tao has a very nice discussion of ultrafilters in his most recent post. In his comment thread, I posed two problems (and provided an embarrassingly incorrect solution to one of them), which I will repeat here; then I'll write about another aspect of Tao's post.

Problem (1): Construct (with Axiom of Choice, of course) a bounded sequence and an ultrafilter so that the sequence has no large convergent subsequences.

Problem (2): Open-ended. Continuum Hypothesis, I've heard it claimed, is (at least sufficient to guarantee that) ultrapowers by different (nonprinciple) ultrafilters are equivalent. I first heard (a version of) this claim from Conway, and I believe he suggested that this was actually equivalent to CH, although that could be a faulty memory. A commenter says that it's not the case that two nonprinciple ultrafilters are themselves isomorphic (in the sense of there existing a bijection on \N that takes one ultrafilter to the other), but it's not clear to me why not. So, why not? And, more generally, is there a reasonably easy way to see the first claim in this paragraph?

Lastly, I would like to point out another extremely cool fact that Tao breezes through. To explain ultrafilters, Tao uses an analogy with voting theory: an ultrafilter is a way of deciding which side wins when infinitely many people vote.

This, then, suggests a proof of Arrow's Theorem.

Let me explain.

Given a set A of alternatives, and a set P of people, let's define a social welfare function (SWF) as a function that takes as input each person's (linear) rankings of the elements of A and gives as output a global ranking of the elements of A (the output may have ties). There are many conditions a "fair" SWF might satisfy; Arrow singles out three:
  1. Pareto (P): if the input consists of identical lists, then this list is the produced output,<\li>
  2. Independence of Irrelevant Alternatives (IIA): given two separate inputs such that, person-by-person, the relative rankings of two particular alternatives x and y are the same, then the outputs have the same relative rankings of alternatives

  3. Monotonicity (M): Say the output has x higher-ranked than y. Then if some people who originally ranked y above x switch their positions, then the output will still have x above y. Except for the possibility of ties, this property is strictly stronger than property P.

By the way, although originally we allowed SWF to produce ties in the output, properties P and IIA are sufficient to guarantee (if A has at least three alternatives) that ties never occur. Indeed, say a certain input yields a tie between x and y. Let X be the set of people who prefer x to y, and Y the set of people who prefer y to x. Taking another alternative z, we can, using IIA, insert it so that all of X prefer x>z>y and all of Y prefer z>y>x; then IIA says x and y are still tied, and P says z>y and hence also x; inserting so that, for X, x>y>z, and for Y, y>z>x, then P says z<y and hence also x; but the relative rankings of z and x are the same in each insertion, so IIA gives us the desired contradiction. Thus, from now on, I will assume that our SWF does not result in ties.

Arrow's theorem says that, if A has size at least three, and if P is finite, then the only SWF satisfying both P and IIA is a single-person dictatorship. Since M is also natural, and since the book* I'm glancing at for my definitions does so too, I will show that SWFs satisfying all three conditions are single-person dictatorships.

Well, an ultrafilter \F can give us a SWF: if you want to know the relative ranking of x versus y, just see whether the set of people who put x above y is \F-large (i.e. in \F) or not. This binary relation is then definitely an ordering, because of ultrafilter properties: for instance, if x > y and y > z in the output, then there are \F-large sets X and Y in P, but then X \cap Y is \F-large, and so since the individual rankings are linear orderings, we must have x > z in the final ranking. Such a SWF obviously satisfies properties IIA and M (and hence P) above.

On the other hand, a SWF \F satisfying IIA and M gives us an ultrafilter. How? Let's pick two particular elements a and b in A. Then for any X \subseteq P, consider feeding \F a collection of rankings so that everyone in X put a > b everyone else puts b > a. If the SWF declares a > b, then declare X to be an a,b-large subset of P. IIA makes this well-defined, and M guarantees that supersets of large sets are large. But this definition does not depend on the choices of a and b: given another c, inserting so that X ranks a>b>c and everyone else ranks b>c>a, then by P, \F yields a>b>c, and so X is a,c-large; similarly, it's c,b-large by a different insertion, and by continuing this type of argument you can get that an a,b-large X is x,y-large for any x,y\in A.

Is the finite intersection of two large sets also large? It suffices to show that the division of a large set into two sets yields a large set and a small set. Say X = Y \cup Z is large, with Y and Z disjoint; then assign Y as b>a>c and Y gets a>c>b and everyone else gets c>b>a. As X is large, certainly \F assigns a>c. Of the three possible (relative) places for \F to put b, either b>c, in which case Y is large, or a>b, in which case Z is large.

Thus \F generates an ultrafilter on A. Writing A! for the set of permutations on A, it's clear how a SWF=ultrafilter \F acts: take our P-sequence of points in A!, and take the (ultra)limit. In the case when A is finite, then the ultraproduct of A! is just A! — i.e. the limit is just another permutation.

In any case, Arrow's theorem is thus equivalent to the statement that there are no nonprinciple ultrafilters on a finite set.

Some discussion is warranted. In justifying that a SWF satisfying the desired criteria is an ultrafilter, I all but proved Arrow's theorem. Given that the statement that "there are no nonprinciple ultrafilters on a finite set" is rather trivial, this is not too surprising. Also, I had to use the fact that A had at least three elements throughout the argument, because Arrow's theorem fails when there are only two options (for instance, Majority Rules works). So it's not immediate to translate Arrow's criteria into the definition of an ultrafilter. Possibly, though, my argument could be cleaned a bit to make it more immediate. Also, it seems that monotonicity is required in guaranteeing that our SWF gives an ultrafilter, but Arrow's theorem holds even if you drop that condition.

On the other hand, this analysis does allow us to understand Arrow-style voting systems with infinitely many people. Or with continuously many people. Or other topologies. And, you know the US is very large — if we could use Axiom of Choice in practice, then perhaps we can pretend that the population of the US is infinite and pick a nonprinciple ultrafilter to be our voting system.

* For a very fine text, suitable for someone who's never seen any mathematics or someone who's seen a lot, on Arrow's Theorem and related topics, I highly recommend Mathematics and Politics: Strategy, Voting, Power, and Proof by Alan D. Taylor (Springer, 1995).


Theo said...

In any case, the answer to Problem (1), that an ultrafilter limit is not necessarily the limit of a large subsequence, is easy enough, when I remember how to do it.

Let me consider the following filter on ${\mathbb N}^2 = {\mathbb N}_1 \cup {\mathbb N}_2 \cup {\mathbb N}_3 \cup \dots$, where ${\mathbb N}_i$ is a copy of the natural numbers. I'll say that a set $A$ is large if, for cofinitely many $i$, $A \cap {\mathbb N}_i$ is cofinite. This generates an ultrafilter $\cal F$ via Zorn, and the following two kinds of sets are definitely small in $\cal F$: sets that are cofinitely contained in only one of the ${\mathbb N}_i$; and sets that have finite intersection with every ${\mathbb N}_i$.

Now partition the unit interval $[0,1]$ into pieces $[1/2,1]$, $[1/4,1/2]$, etc. Each of these pieces contains countably many rational numbers, so use whatever ordering of the rationals that you like to identify ${\mathbb N}_i$ with ${\mathbb Q} \cap [1/2^{i-1},1/2^i]$. Putting these all together and, via whatever zig-zagging you prefer, identifying ${\mathbb N}^2 = {\mathbb N}$, we get an ultrafilter $\cal F$ on ${\mathbb N}$ and a sequence $q_n$ (dense) in $[0,1]$.

Then $\cal F$ definitely picks a unique limit $q \in [0,1]$, and if $q_n$ has any large convergent subsequences, then they definitely converge to $q$. There are two (and a half) possibilities:
(1) If $q \in (1/2^{i-1},1/2^i)$ for some $i$, then any large convergent subsequence must be cofinitely in ${\mathbb N}_i$, but all such subsequences are $\cal F$-small.
(1.5) If $q = 1/2^i$, then any large convergent subsequence must be cofinitely within ${\mathbb N}_i \cup {\mathbb N}_{i-1}$, but all such subsequences are small.
(2) If $q = 0$, then any large convergent subsequence has only finitely many points in any interval $[\epsilon, 1]$ for $\epsilon > 0$, and so certainly has only finitely many points in each and every ${\mathbb N}_i$, and hence is also $\cal F$-small.

Eric said...

Re problem 2: Any countable nonprincipal ultraproduct is aleph_1-saturated. Under CH, all countable nonprincipal ultrapowers of the reals have cardinality aleph_1 and are elementarily equivalent, and hence are isomorphic by saturation. I do think I've heard of the converse before, but I don't know where and certainly have no idea of the proof.