Using your Head is Permitted

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 S_i 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 S_i across the first n rounds.

We are interested in characterising the Nash Equilibria in this game. A Nash Equilibrium is a pair of strategies (Algorithm₀, Algorithm₁), 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:

Part 2:

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:

Part 2: