2026/01/29 by Philip LaPorte, Christian Hilbe, Nikoleta E. Glynatsi +1 · 1 voice · 3 citations
Decision Sciences · Social Sciences · #Best response #Bounded function #Equivalence (formal languages) #Evolutionarily stable strategy #Evolutionary Game Theory and Cooperation #Experimental Behavioral Economics Studies #Game Theory and Applications #Set (abstract data type) #Simple (philosophy) #Stability (learning theory) #Stochastic game #Strategic dominance
paper · doi:10.1073/pnas.2518486123
published in Proceedings of the National Academy of Sciences 123(5), e2518486123 (National Academy of Sciences)
openalex publication_date 2026/01/29 · openalex created_date 2026/01/30 · openalex updated_date 2026/07/31
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.