## June 2015 riddle

UPDATE (2 June): Following several queries by readers, here is a clarification: the "programs" that are competing here -- not unlike the programs used in Axelrod's tournaments -- are ones that should be implementable as Turing machines. There are many types of algorithms that are not Turing-machine-implementable. Something requiring, say, an arbitrary real number as part of the program is an example of such an algorithm. Such algorithms are inadmissible in our competition.

SPECIAL ANNOUNCEMENT: In light of the passing of John Nash last week, I've decided to postpone the "100 riddles" festivities to next month. Thank you all for sending your candidate riddles, and please do continue sending them this month as well. This month's riddle, however, will be dedicated to Nash.

In 1980, Robert Axelrod, professor of political science at the University of Michigan, held two tournaments, pitting against each other various strategies for the iterative version of the game known as "The Prisoner's Dilemma".

We will analyse a similar competition, involving an iterative version of a simpler game: "Matching Pennies" (also known as "Odds and Evens"). Matching Pennies is a zero-sum two player game, where in each round each player (which will be here a computer program) can choose either "Heads" or "Tails". If both choose the same, Player 0 wins. If they choose differently, Player 1 wins.

We will, at each round, start both of the contending programs anew, using all of the competition's history (every choice the current player made and every choice its adversary made in all preceding rounds) as the programs' inputs, and let them choose a new coin side. In order to avoid the trivial "50-50 coin toss" solution, we will require our computer programs to be deterministic.

We will let the competition run an infinite number of rounds. (Unlike in Axelrod's experiment, we are not looking at an entire tournament, but only at a repeated match between two players. In a zero-sum game, the extra complications introduced by the tournament scenario make little difference.) Let Si be the number of the winning player in round i (zero or one). The final score of the competition (the payoff to Player 1, the penalty to Player 0) will be the limit, on n approaching infinity, of the average value of Si across the first n rounds.

We are interested in characterising the Nash Equilibria in this game. A Nash Equilibrium is a pair of strategies (Algorithm0, Algorithm1), such that if the players use these as their respective strategies in the competition, neither player has an incentive to switch to any other strategy: no other strategy would give either player a better payoff, given that the other player utilises the equilibrium strategy.

Notably, Nash Equilibria are often mixed strategies, which is to say that they are not one algorithm, but rather a probabilistic choice between several algorithms (perhaps an infinite number of them). We do allow mixed strategies in this competition. Note, however, that a mixed strategy is a probabilistic choice between algorithms, not between individual chosen outputs in a single competition round: whatever probabilistic choice was made in choosing a particular algorithm, it is that algorithm that will now play an infinite number of competition rounds.

This month's question has two parts. Separate solver lists will be maintained for each part.

#### Part 1:

What are the Nash Equilibria if for the participating algorithms a return value of 1 means "Heads", a return value of 0 means "Tails" and any other outcome (including the program not halting) is not legal?

#### Part 2:

What are the Nash Equilibria if for the participating algorithms a return value of 1 means "Heads" and anything else, including the program not halting, means "Tails"?

To characterise a Nash Equilibrium, indicate the final score of the competition at the equilibrium, give an example pair of strategies attaining it, and, as usual, prove your answer.

Notes:

1. This is not a competition that can actually be run in practice. (a) We require an infinite number of rounds, and (b) it is impossible, in general, to determine whether an algorithm will terminate. (In Part 1, this means we cannot verify eligibility of the players; in Part 2, it means we cannot determine what the choice at each round would be.) Nevertheless, the competition and its outcome are well defined.
2. The final score of the competition is described as a limit. There is no a priori guarantee that the limit exists. If you claim that it exists at the equilibrium, you will have to prove this.
3. We allow any probabilistic mixture of algorithms to be a valid mixed strategy. It does not have to satisfy any other condition. So, for example, the mixture probabilities need not be computable.

### List of solvers:

#### Part 1:

Thomas Mack (23 June 14:10)

#### Part 2:

Thomas Mack (23 June 14:10)

Elegant and original solutions can be submitted to the puzzlemaster at riddlesbrand.scso.com. Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.

Enjoy!