Reactive strategies and completeness in repeated games

Abstract In evolutionary game dynamics, strategies undergo mutation and natural selection. Owing to practical limitations, many studies simulate evolution in a restricted strategy space. This is especially true for repeated games, where long-run strategies can be arbitrarily complex. It can be challenging to find a suitable space, which does not exclude relevant strategies. In a payoff-complete space, any opponent strategy may be precisely emulated by a strategy that is in the space. Completeness ensures that simulations do not contrive stable outcomes by excluding superior strategies. In this paper, we study repeated games with finitely many actions and discounted payoffs. We assume that the payoffs in each round are additive: each player's payoff is a sum of two terms, one from each player's action. This includes the donation game, a simple Prisoner's Dilemma. We show that the reactive memory-1 strategies, which respond to the opponent's previous action, are payoff-complete. We show that for some other Prisoner's Dilemma games, the reactive memory-1 strategy space satisfies a weaker completeness property. Overall, our work supports the use of reactive strategies in evolutionary game theory within an appropriate parameter regime.