An exhaustive map of binary memory-two direct reciprocity over symmetric two-player games

Abstract

Direct reciprocity, a mechanism for evolution of cooperation, rests on a promise of the future: that the cost of cooperation will be returned in subsequent encounters. Whether reciprocity works is often asked as a question about evolutionary stability: can a population of cooperators resist invasion by mutants that defect? Here we answer this question exhaustively for a large, but finite strategy space projected onto an uncountable infinity of evolutionary games. We take the binary memory-two strategies, in which each of the sixteen possible two-round histories is answered by cooperation or defection up to a small error rate. We work out what every one of them achieves on its own and against every rival, in every symmetric two-player game. Alone, they realise 475 distinct patterns of play carrying 229 distinct cooperation rates. Against each other, a game supports between 299 and 22069 Nash equilibria, that is, resident strategies that no rare mutant can outperform. Efficient strategies, which are those that reach maximum payoff, are present as equilibria at every game, and for 3/8 of games efficient strategies constitute the only equilibria. Those results belong to the limit of a vanishingly small error rate. For any positive error rate the map changes: under 1/4 of all games support no equilibrium, over 3/8 support equilibria but none are efficient, over 1/8 support equilibria and all are efficient, and under 1/4 of games support equilibria of both kinds. Every share quoted here is an exact natural density over the plane of games. The map is the landscape over which any evolutionary dynamics in this strategy space moves.