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.

1. I’m missing something here – I think the same thing Charles was missing in the comments on the earlier post.

I can see how, once Player 1 has some information about what Player 2 is playing, Player 1 is guaranteed to lose at most finitely many more rounds.

What I can’t see is how that means that “At the end [Player 1] must have won all but finitely many moves”. Because by the time that the strategy can be implemented, he will already have lost infinitely many moves. That’s because the strategy can’t be implemented at 12, and at any time after 12, Player 2 will, with probability 1, have won infinitely many games if Player 2 plays a mixed strategy with prob 1/2 for 1 at each move.

2. Ok, I’m not sure I understood what Charles was getting at before, so maybe this will clarify things for me.

By ‘player 1 has a winning strategy’, I just mean that he has a strategy such that, if he implements it at every point in the game, he will win.

You said: “by the time that the strategy can be implemented, he will already have lost infinitely many moves.” But this is not true: if he had been following the strategy at every previous move, he will only have lost finitely many moves up to that point.

Of course, the weird thing is that if he does manage to follow this strategy, then it’s not possible for player 2 to follow the pure strategy I mentioned in the post. As for the mixed strategy you suggested – its not impossible for her to follow it, but like you said, things with probability zero would start happening.

4. There are some weird quantifier shifts going on here. Maybe it would be better if we moved away from the tricky set theoretic cases to something simpler.

Here’s a simple game. Player 1 and 2 will play a countable infinity of rounds of a zero-sum game. Player 2 doesn’t have any choices in the game. Player 1’s choice is limited to stating a finite number n, any number she likes, at the start of the game. For any game r, if r is less than n, Player 1 wins game r, otherwise Player 1 loses game r.

Now for every r, player 1 has a strategy that wins game r. Indeed for any finite set of games, Player 1 has a strategy for winning those games.

But whatever Player 1 does, Player 2 will win more games. If we just add up who wins the most games, Player 2 will win more games, whatever Player 1 does.

I think that’s just like the situation in your game. Whenever Player 1 moves, she can guarantee that she’ll lose at most finitely many more games. (In my variant, she loses 0 more games.) But that doesn’t matter, because she has to pick a time to move. And that time has to be after 12. Picking how close it is to 12 that she moves is like picking a high but finite n. The closer (higher) that she picks, the ‘better’, but Player 2 will still do infinitely better.

5. Ok, I followed you up until the last paragraph. But the sequence of rounds you describe is crucially different from the one I described: player 1 (or player 2 for that matter) doesn’t have to ‘pick a time’ at which to start following the strategy. Throughout the whole period from 12 till 1, both players are playing rounds whereby player 1 says 1 or 0 and player 2 responds. Either player 1 followed the strategy at every time between 12 and 1, or she didn’t. If she did, then she must have won all but finitely many rounds.

I guess problems might arise if player 1 had to choose which strategy to play after the game had started. Let’s just stipulate that the strategy was chosen well before 12.