Payoff equivalence and complete strategy spaces of direct reciprocity

Repeated games and stochastic games are important frameworks to study direct reciprocity. Individuals react strategically to their coplayers' previous behavior. While strategies in such games can be arbitrarily complex, explorations of evolutionary dynamics are often done in specific strategy spaces. Individuals may consider a fixed number of past rounds, or only some of the partner's previous actions. Such restrictions can make the interpretation of the results difficult. Strategies found to be superior within a restricted set may lose stability when more complex strategies are permitted. We discuss two notions of completeness that rule out this possibility. If a strategy space, S, is best-reply-complete, then any strategy in S is guaranteed to have a best reply in S. If a space, S, is payoff-complete, then any strategy playing against an opponent in S can be replaced by an equivalent strategy within S without affecting either player's payoff. Sufficient conditions for best-reply-completeness have been given in a seminal paper by Levínský et al. Here, we show that for strategies of bounded memory, the same conditions are sufficient for payoff-completeness. Furthermore, using those conditions, we illustrate how to construct many complete spaces for simple games. Taken together, our findings highlight the importance of complete strategy spaces, which are particularly useful when interpreting evolutionary simulations and determining best responses.