Monday, August 25, 2008

Friday, August 22, 2008

An ultrafilter game

The following post is inspired by a cute game-theoretic result about ultrafilters in the slides (PDF) from a talk by Andreas Blass.

Let's start with a bit of finite game theory. Suppose G is a two-player, deterministic, zero-sum, sequential, finite game with perfect information (e.g., Go played by two omniscient beings). Then either player I has an winning strategy or player II has a winning strategy. The (informal) proof of this is simple. Player I can either force player II into an unwinnable position, or he can't. If he can, player I has a winning strategy, by definition. If he can't, then player II has a winning strategy: avoid unwinnable positions. When the game ends after finitely many moves, player II wins, by definition.

Venturing further into the lofty mountains of abstraction, let us allow the number of turns to be infinite. Here's a simple infinite game. Suppose A is a collection of sets of whole numbers. For concreteness, let A be the collection of all sets containing infinitely many odd numbers. The game G(A) is played as follows. Players I and II take turns choosing finitely many whole numbers. (Choosing no numbers on a turn is allowed.) Once a number is chosen, it can never be chosen again by either player. After infinitely many moves, player I has chosen a possibly infinite set X of numbers, and player II has chosen a possibly infinite set Y of numbers not in X. If X is in the collection A, then player I wins. Otherwise, player II wins.

Player I has a simple winning strategy for G(A): just pick the least odd number that hasn't already been picked. Let's try G(B) where B is the collection of all sets containing at least twenty primes. Again, player I can always win: he can pick twenty primes on his first move. Well, what about G(C), where C is the collection of all sets that contain all but finitely many of the even numbers? Player II can always win by always picking the least even number available.

So, is every infinite game of this form is determined, meaning either player I of player II has a winning strategy? The answer depends on your axioms of set theory. The mainstream answer of mathematicians is "no, because of the axiom of choice." (This is my answer, too.) However, the axiom of choice has counterintuitive consequences. Moreover, a beautiful theory has been built up from the axiom of determinacy, which asserts that the answer to our game-theoretic question is "yes."

A particularly interesting consequence of the axiom of choice is that there exist wonderful objects called free ultrafilters. A free ultrafilter (on the whole numbers) is a collection U of sets of whole numbers with the following properties.

  • Every set in U is infinite.
  • If X and Y are in U, then their intersection is in U.
  • For every set of numbers X, either X is in U, or the set of numbers not in X is in U.
(I omitted the traditionally included property that if X is in U and X is a subset of Y, then Y is in U. This property follows from the above listed properties, and it is not relevant to this blog post.)

It follows from these properties that the set of all whole numbers is in U. Also, if two sets are disjoint (e.g., the multiples of 4 and the primes), then they can't both be in U. Moreover, for any element X of U, and any partition of X into two pieces Y and Z, one of Y and Z must be in U, and the other must not be in U. Because such partitions can be arbitrarily complex, it takes an infinite (in fact, uncountably infinite) sequence of choices to "build" an ultrafilter. The axiom of choice says such sequences exist, even though we might not be able to specify any particular such sequence with a finite number of words/symbols.

Now, let's analyze the game G(U). It turns out neither player has a winning strategy. For the sake of argument, suppose player I has a winning strategy---call it S. The trouble is that the game G(U) has enough symmetry that if player I can use S, then player II can use it too. Suppose player I follows S, and that F is the set of numbers he picks on his first turn. Now suppose player II pretends that she's player I following S and that her opponent chose nothing after she chose F. Let X be the set of numbers chosen by player I and Y be the set of numbers chosen by player II. Then X is in U because S always wins. But the union of Y and F is also in U because S always wins. Therefore, the intersection of these two sets, which is F, is in U. This is impossible because all members of U are infinite. Therefore, player I does not have a winning strategy.

Does player II have a winning strategy? Suppose she did, and let T be such a strategy. Let's modify T a little bit, producing another winning strategy T'. The idea behind T' is that choosing more numbers on her turn can't hurt player II; it will just make things harder for player I. Let's be more precise. On every turn, T' says to choose the numbers T says to choose, along with the least number not already chosen by either player. Technically, this will only work on player II's first turn, because on player II's second turn, T could say, "sorry, you didn't follow my advice last turn." But there's an easy work-around. Ask T, "what would you advise in the situation where that extra number you didn't want me to choose were chosen on player I's last turn, in addition to what he actually chose?" In general, T' says to do what T would say to do if each extra number previously chosen by player II were chosen on player I's last turn, in addition to what player I actually chose. Then T' says to also choose the least number not already chosen. Now we can see that T' is a winning strategy. If player I could beat T', then he could also beat T by additionally choosing the appropriate extra number on each turn. But player I can't beat T, so player I can't beat T' either.

Now suppose player II follows T'. Further suppose player I pretends that he's player II following T' and that his opponent chose nothing on her first turn. Again let X be the set of numbers chosen by player I and Y be the set of numbers chosen by player II. Then neither X nor Y is in U because T' always wins. But, because of how we constructed T', every number is eventually chosen by player I or player II. Therefore, Y is the set of all numbers not in X. This is impossible, for it implies either X or Y is in U. Therefore, player II has no winning strategy.

Sunday, August 17, 2008

Arnold Kling has posted some interesting first-hand history of Freddie-Mac.

Friday, August 15, 2008

Superbugs, or, gram-negative multidrug-resistant bacteria that are currently untreatable.

Thursday, August 14, 2008

A philosopical romp, or, how I was unproductive this afternoon

First, Tyler Cowen points me to "the infinitarian challenge to aggregative ethics." Hyperreals are seriously discussed, and that tickled my fancy, but ultimately the paper is to me another reason not to base my ethics on aggregative utilitarianism.

In the same post, Cowen pointed me to this short, simple anthropic explanation of time's arrow. I read this comment, which blew the argument apart. I then followed its link to a blog post describing how Boltzmann made the same mistake. The reductio ends with you most likely being a "Boltzmann brain," which is a brain in a vat, except that the vat is a region of space-time with the minimal extent needed for your brain to experience what it is experiencing at the moment, including illusary recollections of yesterday.

Reading comments there led me to "canonical quantum gravity and the problem of time," which has more equations than anything I've linked to above, but is still philosophy, just natural philosophy. Bottom line: I like the mathematics and concepts of the consistent histories interpretation best, but I don't accept with the many-worlds interpretation of quantum physics that is typically held by proponents of consistent histories.

Frustrating, indeed:
France and China can build nuclear electric plants in just years; in the U.S. it takes a decade. Brazil will bring offshore oil online in 24 months, while for U.S. companies it takes 10 years. New refineries are virtually illegal to build. New electricity-generating plants using coal are now unable to obtain financing because of environment constraints.

Monday, August 11, 2008

An interesting bit of science:
A trustworthy face, at its most extreme, has a U-shaped mouth and eyes that form an almost surprised look. An untrustworthy face, at its most extreme, is an angry one with the edges of the mouth curled down and eyebrows pointing down at the center. The least dominant face possible is one resembling a baby's with a larger distance between the eyes and the eyebrows than other faces. A threatening face can be obtained by averaging an untrustworthy and a dominant face.

Sunday, August 10, 2008