 November 19, 2008

I’ve been thinking about variations on the coin tossing puzzle I posted about a month or so back. This is one I find particularly weird, and seems to violate principles of free choice. You can have a two player game where both players have a winning strategy, but only one player can win. In particular, this implies that if one player follows her winning strategy, the other player can’t. So, although at every point in the game the second player is free to follow the strategy, she is not free to follow the strategy at every point in the game. (I intend there to be some kind of scope difference there.)

The games I am interested in are defined as follows. First I shall define a round: player one chooses 1 or 0, then player two chooses 1 or 0 (having heard player one’s choice.) Player one wins if player two chooses the same number as he did, player two wins if her number is different. Next, a game is a sequence of rounds. Player 2 wins if she wins every round, player 1 wins otherwise.

A strategy for one of these games is a function taking sequences of 1’s and 0’s (provided the order type of the sequences are initial segments of the game order type) to {0, 1}. A winning strategy for a player is a strategy $\sigma$, such that, if at each point in the game, s, you played $\sigma(s)$ then you would win.

Now clearly player one does not have a winning strategy for any game that is a finite sequence of rounds – and indeed, this holds for any game that is a well founded sequences of rounds. Obviously, player two has a winning strategy, since she may always say the opposite to what player one says. Since on well founded games, only one player can have a winning strategy, player one never has a winning strategy.

Bizarrely, however, player on does have winning strategies on non-well founded games. Suppose they play on a backwards omega sequence, e.g. a move takes place at each 1/n hours past 12pm, and the game ends at 1pm. Then you divide the possible sequences that player two might play into equivalence classes according to whether they differ by at most finitely many moves. If player one picks a representative from each class, then at each point in the game he can work out what class he’s in, and he can play the same move that the representative sequence predicts player two will play. At the end he must have won all but finitely many moves (I discussed the strategy a bit more here.

So both player one and player two have a winning strategy. But clearly, they can’t both win – so it follows that at least one of them can’t follow their strategy in a given game. This is particularly weird, since at each point in the game they are free to follow their strategy – there’s nothing physically preventing them from them from doing so – but they are not free to to follow it at all of the moves.

This contradicts what I shall call the ‘free choice principle’, that if a rational agent is free and able to do something, and wants to do it, she will do it. For the game above we can formulate this as follows. Let $\Diamond_i$ be read roughly as ‘player i (i = 1 or 0) is free to make it the case that’, and let $P_in$ say ‘at round n, player i (i=1 or 0) follows his/her strategy’. Round n is the n’th round from the end of the game. The free choice principle reads:

• $\forall n (\Diamond_i P_in \rightarrow P_in)$

If at a given round each player is free to follow their strategy, then each player does follow their strategy. We assume tacitly that the players we are concerned with want to follow their strategy, and are physically able to carry it out, etc… We may formulate the principle that at each point in the game, both players are free to follow their strategy as follows

• $\forall n\Diamond_i P_in$

But this entails the impossible conclusion: $\forall n (P_1n \wedge P_2n)$. At least one player has to lose.

As far as I can see, the premise that at each point in the game each player is free to play according to her strategy is fine. It’s been stipulated that nothing is preventing them from following the strategy, and there are no other relevant limitations.

So it has to be the principle of free choice that goes. There will be a round such that one of the two perfectly rational players wants to follow her strategy, intends to follow it, can follow it in the sense that nothing is preventing her, yet doesn’t follow it. Strange.