Using your Head is Permitted

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 (A₀, A₁,...). Each of these A_i algorithms has a positive mixture probability, P_i, and these probabilities must sum up to 1:

lim_n→∞ ∑_i=0ⁿ P_i = 1

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

∑_i=0ⁿ P_i ≥ 1-ε

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

∑_i=0ⁿ P_i ≥ 2/3;

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

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 A₀,..., A_n, 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 A_i 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 A_i, as happened in Part 1, because A_i may never halt, something that Player 1 cannot, in general, check.

Back to riddle

Back to main page