Repeated game

A repeated game plays a stage game over several rounds, allowing actions to depend on earlier observations. Its payoff convention must specify a finite horizon, a discount factor or a long-time average; these need not have identical invasion properties.

A history-dependent pure strategy represented by a finite-state machine with an initial automaton state, an action output for each state, and an automaton transition after each observed completed joint action. A grim trigger strategy uses a following state and an absorbing punishment state. Two such deterministic machines jointly form a finite deterministic state system, so their action path is eventually periodic. Its long-run average payoffs are the averages over the eventual cycle; a finite initial prefix has vanishing weight.

The normal-form game played once in each round of a repeated game. Its actions and payoffs are distinct from the repeated interaction's history-dependent pure strategies and aggregate payoffs. The same stage game can produce different incentive constraints under a finite sum, discounting or long-run average payoff criterion.

A family of results describing the large set of Nash equilibrium payoffs available in indefinitely repeated interaction. For a finite game with observed past play, the discounted Nash version supports any feasible, strictly individually rational payoff in a repeated game when players are sufficiently patient.^[ref]

The mechanism is to prescribe a path and punish the first deviator by holding that player's future payoff to its minmax payoff. With long-run average payoffs, a finite gain disappears from the average; with discounting, the promised future loss must outweigh the gain. Weak boundary points require care when a stated theorem assumes strict inequalities. A construction proving a Nash equilibrium need not prove a subgame perfect equilibrium, because the punishers' continuation incentives may fail.

A payoff vector giving every player at least that player's minmax payoff. It is strictly individually rational if every inequality is strict. A player can reject an equilibrium offering less than the guaranteed amount by choosing a securing strategy instead. These bounds concern repeated-game incentives; they are distinct from participation constraints in mechanism design.

The lowest expected payoff to which a player's opponents can hold that player when the player chooses a best response. The opponents' permitted randomization and correlation conventions should be specified for games with several opponents. In a two-player finite game, this equals the player's maximum guaranteed expected payoff by the minimax theorem applied to that player's payoff matrix. This equality does not make the original two-player game a zero-sum game.

The convex hull of the stage game's attainable payoff vectors. Public randomization or deterministic sequences with prescribed limiting frequencies produce such average payoffs. It can be larger than the set attainable using independent mixed strategies in a single stage.

A repeated game criterion evaluating the average stage payoff over increasingly long horizons. State how paths without a limit are treated, for example by using a lower limit. Changing a finite prefix does not change a convergent long-run average payoff. Thus a one-time gain can be outweighed by permanent future punishment without specifying a discount factor.