## June 2015 solution

#### Part 1:

There are no Nash equilibria in this game.

To prove this, let us assume, on the contrary, that a Nash equilibrium exists and in it Player 1's strategy is a mixture of the algorithms (A0, A1,...). Each of these Ai algorithms has a positive mixture probability, Pi, and these probabilities must sum up to 1:

limn→∞i=0n Pi = 1

Per the definition of "lim", this means that for any ε there is an n such that

i=0n Pi ≥ 1-ε

So, for example, let us choose ε to be 1/3, then

i=0n Pi ≥ 2/3;

This means that with probability of at least 2/3, the chosen strategy is one of the finite range A0,..., An.

We can now define a strategy B for Player 0 as follows:

```Let {x_r} be Player 0's previous bits.
Let {y_r} be Player 1's previous bits.
Let i = |{r | x_r != y_r }|
# This is the number of rounds where Player 0 "lost".
If i>n:
Return 0
Else:
Return the result of A_i on the input ({y_r},{x_r}).
# i.e., return what Player 1 would have returned if its strategy was A_i.
```

If Player 0 was to follow this strategy and Player 1's algorithm, as determined probabilistically from the mixed strategy, was one of A0,..., An, the total number of rounds that Player 0 would have lost in would have been bounded by n, so the final score would have been 0 -- a flat out win for Player 0. This happens in probability of at least 2/3. In the remaining 1/3, at worst Player 1 wins every round. This would bring the total final score to at most 1/3. In other words, regardless of what Player 1's strategy is, Player 0 can always ensure an expected score of 1/3 or lower. Any Nash equilibrium must therefore have this as its score.

However, we can just as easily design the corresponding strategy for Player 1, defending against a known strategy mix from Player 0. This would be identical to the program described above, with only a change in the final line. Now it would be:

```  Return the complement of the result of A_i on the input ({y_r},{x_r}).
```

In this way, by exactly the same argument as before, Player 1 can ensure an expected final score in excess of 2/3, so any Nash equilibrium must, similarly, have at least 2/3 as its score. We reach a contradiction.

#### Part 2:

In Part 2 there is an infinite number of Nash equilibria, but all of them have the same score: 0. The following is an example of a strategy for Player 0 that attains this score. It forms a Nash equilibrium in conjunction with any strategy used by Player 1.

```Let {x_r} be Player 0's previous bits.
Let {y_r} be Player 1's previous bits.
Let i = |{r | x_r != y_r }|
# This is the number of rounds where Player 0 "lost".
Return the result of A_i on the input ({y_r},{x_r}), where {A_i} is an
enumeration over all possible Turing machines.
```

It is not difficult to enumerate over all Turing machines, if one is willing to enumerate also over non-halting machines (which, in this part of the riddle, we are willing to do). Player 1's algorithm, regardless of what mixed strategy it was chosen from, is ultimately equivalent to a Turing machine. So, it is some Ai in our enumeration over Turing machines. That being the case, the total number of rounds Player 0 will have lost during the game can never exceed the constant i, so the final score will be 0.

As there is nothing Player 1 can do about this, and as a score of 0 is the best possible outcome for Player 0, the strategy forms a Nash equilibrium together with any strategy by Player 1.

We remark that in this part Player 1 cannot copy the same idea, inverting the output of Ai, as happened in Part 1, because Ai may never halt, something that Player 1 cannot, in general, check.