Fact-checked by Grok 2 weeks ago

Repeated game

A repeated game in game theory is a model of strategic interactions in which a fixed set of players repeatedly play the same stage game—a one-shot normal-form game—over multiple periods, with payoffs accumulated across periods, either finitely or infinitely many times.^[1] This framework contrasts with single-stage games by incorporating history dependence, where players' strategies can condition actions on past outcomes, enabling phenomena like cooperation and punishment that are impossible in isolated plays.^[2] In finitely repeated games, backward induction typically implies that rational players will play a Nash equilibrium of the stage game in every period, replicating one-shot Nash outcomes, assuming perfect information and common knowledge of rationality (with uniqueness yielding a unique subgame-perfect equilibrium payoff profile).^[1] However, infinitely repeated games, or those with discounting where future payoffs are valued less than immediate ones, allow for a broader set of subgame-perfect equilibria due to the threat of future punishments for deviations.^[1] Discounting is often modeled by a common discount factor \delta \in (0,1), where the total payoff for player i is \sum_{t=1}^\infty \delta^{t-1} g_i(a_t), with g_i the stage-game payoff and a_t the action profile at time t.^[1] A cornerstone of repeated game theory is the folk theorem, which states that if players are sufficiently patient (i.e., \delta close to 1), any feasible payoff vector that is individually rational—meaning each player's payoff exceeds their minimax value in the stage game—can be achieved as the average payoff of a subgame-perfect equilibrium. An early version of this result was established by Friedman (1971) for discounted infinitely repeated games with Nash threats, showing that sufficiently patient players can sustain feasible payoffs above the stage game's Nash equilibrium payoff. Subsequent work, such as Fudenberg and Maskin (1986), extended the folk theorem to subgame-perfect equilibria in discounted games, achieving any strictly individually rational feasible payoff.^[3] This result explains how repetition sustains outcomes like collusion in oligopolies or cooperation in the Prisoner's Dilemma, where defection dominates in the one-shot version.^[3]^[2] The study of repeated games originated in the mid-20th century, with early explorations of supergames—repeated plays with complete information—in Luce and Raiffa's foundational text, which analyzed temporal repetition in non-zero-sum settings like the Prisoner's Dilemma to illustrate reprisal and quasi-equilibria.^[2] Subsequent developments, including the formalization of non-cooperative equilibria in supergames, built on this to characterize sustainable collusion under repeated interactions.^[3] Repeated games have since become essential in economics for modeling dynamic phenomena such as cartel stability, reputation effects, and long-term contracting, with extensions to imperfect monitoring and incomplete information further enriching the theory.^[1]

Fundamentals

Definition and Setup

A repeated game in game theory is an extensive-form game consisting of multiple plays of a fixed underlying game, known as the stage game, where the number of repetitions may be finite or infinite. Unlike one-shot games, where interactions occur only once and players cannot condition their actions on prior outcomes, repeated games allow players' strategies to depend on the history of previous plays, enabling more complex behavioral patterns. The basic components of a repeated game are derived from the stage game, which involves a set of players, each with their own action sets and payoff functions that map joint actions to individual payoffs. In the repeated setting, the total payoff for each player is the aggregate of stage-game payoffs across all periods: for finite repetitions, it is the undiscounted sum; for infinite repetitions, it is a discounted sum that weights future payoffs less heavily to reflect impatience. The history in a repeated game is the sequence of action profiles observed up to the current period, which players use to inform their strategies. Information sets distinguish between perfect monitoring, where all actions are publicly observable after each stage, and imperfect monitoring, where players receive only noisy or private signals about others' actions, introducing uncertainty into the interaction.^[4] Repetition introduces long-term incentives absent in single-shot games, as players can build reputations through consistent behavior and enforce cooperation via the threat of future punishments, fostering outcomes that align with joint interests over time.

Stage Game and Payoffs

In repeated games, the stage game refers to the underlying one-shot strategic interaction among a finite set of players, typically represented in normal form as G = \langle N, (A_i)_{i \in N}, (u_i)_{i \in N} \rangle, where N is the set of players, A_i is the finite set of actions available to player i, and u_i: A \to \mathbb{R} is player i's payoff function, with A = \prod_{i \in N} A_i denoting the set of action profiles.^[5] This bimatrix (for two players) or multimatrix form captures strategies, outcomes, and payoffs for zero-sum or non-zero-sum interactions in each period.^[6] Payoffs in repeated games accumulate from the stage game outcomes across periods. In finite repetitions over T periods, each player's total payoff is the undiscounted sum U_i = \sum_{t=1}^T u_i(a_t), where a_t \in A is the action profile chosen in period t.^[5] In infinite repetitions, payoffs are aggregated as the discounted sum U_i = \sum_{t=1}^\infty \delta^{t-1} u_i(a_t), where \delta \in (0,1) is the common discount factor reflecting players' patience or the probability of continuation.^[5] Often, the normalized (average) payoff is considered as (1-\delta) U_i to align with per-period stage payoffs.^[6] The feasible payoff set in repeated games consists of all payoff vectors achievable as convex combinations of stage game payoff profiles, formally the convex hull V = \mathrm{co} \{ u(a) \mid a \in A \}, where u(a) = (u_i(a))_{i \in N}.^[5] Payoffs are individually rational if each player's component exceeds their minimax value, defined as v_i^* = \min_{a_{-i} \in A_{-i}} \max_{a_i \in A_i} u_i(a_i, a_{-i}), ensuring no player receives less than what they can secure unilaterally against worst-case opponents.^[5] A canonical example is the Prisoner's Dilemma as the stage game, where two players choose to cooperate (C) or defect (D), with payoffs illustrating the tension between mutual cooperation and individual temptation to defect:

	C	D
C	3, 3	0, 5
D	5, 0	1, 1

Here, mutual cooperation yields (3,3), but defection dominates for each player in the one-shot game, leading to (1,1); in repetitions, this setup highlights potential for sustained cooperation.^[5]

Finite Repeated Games

Backward Induction

Backward induction is a fundamental solution concept used to analyze finite repeated games, where players interact over a known, fixed number of periods. The method involves solving the game recursively by beginning at the final period and working backward to the initial period, determining optimal strategies in each subgame. In the last period, since no future play follows, players revert to the Nash equilibrium of the underlying stage game, selecting actions that maximize their immediate payoffs given others' responses. For each preceding period, players anticipate rational play in all subsequent subgames and choose actions accordingly, ensuring subgame perfect equilibrium. This process guarantees that the strategy profile is robust to deviations at any decision point, as it constitutes a Nash equilibrium for every subgame.^[5] The application of backward induction relies on several key assumptions: all players possess perfect information about past actions, rationality is common knowledge among players, and the finite horizon T is publicly known to everyone. Under these conditions, the solution eliminates any incentives for non-equilibrium behavior, as players can perfectly foresee outcomes from any point onward. Perfect information ensures that histories are observable, allowing precise anticipation of future subgames, while common knowledge of rationality implies that no player expects others to err in future decisions. The finite horizon T is crucial, as it provides a clear terminal point where stage-game incentives dominate. These assumptions align the repeated game with the structure of extensive-form games, enabling the recursive solution.^[5] Historically, the concept of backward induction traces back to John von Neumann's 1928 work on zero-sum games of strategy, where he formalized the minimax theorem and implicit recursive reasoning for finite extensive games. This approach was later extended to non-zero-sum games by Harold W. Kuhn in 1953, who proved that every finite extensive-form game with perfect information admits a subgame perfect equilibrium via backward induction, establishing its general applicability. Kuhn's theorem underpins the use of backward induction in repeated games, confirming the existence of pure-strategy equilibria that solve the game completely.^[7]^[8] A prominent illustration of backward induction occurs in the finitely repeated Prisoner's Dilemma, where mutual cooperation would yield higher joint payoffs but defection dominates in the stage game. In the final period, rational players defect, achieving the stage-game Nash equilibrium. Anticipating this, players in the penultimate period also defect, as cooperation would be exploited without future reciprocity. This logic unravels inductively: defection becomes optimal in every period, leading to the unique subgame perfect equilibrium of universal defection across all T rounds. Thus, despite the potential for sustained cooperation in infinite settings, finite repetition under backward induction precludes it entirely.^[5]

Equilibria and Unraveling

In finite repeated games, the subgame perfect Nash equilibrium (SPNE) refines the Nash equilibrium concept by requiring that the strategy profile induces a Nash equilibrium in every subgame.^[9] This ensures sequential rationality, eliminating non-credible threats or promises that might sustain suboptimal outcomes in coarser equilibria. In the context of finitely repeated games with a known horizon, backward induction—applied to the extensive-form representation—yields the SPNE.^[10] When the stage game has a unique Nash equilibrium, the finite repetition admits a unique SPNE in which players follow myopic play, replicating the stage-game Nash equilibrium in every period regardless of history.^[11] This outcome arises because, in the final period, players have no future to consider and thus play the stage Nash; anticipating this, no incentive exists for cooperation in the penultimate period, and the logic unravels backward to the first period.^[12] This phenomenon, known as the unraveling theorem, demonstrates that for generic stage games—those with a unique Nash equilibrium and generic payoffs—sustained cooperation fails in finite repetitions with a fixed horizon, as deviations become rational starting from the end.^[12] In the classic Prisoner's Dilemma stage game, for instance, the unique SPNE yields mutual defection every period, resulting in total payoffs of T \times (d, d) for horizon T, compared to the cooperative outcome of T \times (r, r) (where d < r) that would require credible future enforcement, which unravels.^[11] Exceptions occur in non-generic stage games with multiple Nash equilibria, where additional SPNE can support cooperation in early periods by leveraging less grim punishments in later subgames.^[13] Benoit and Krishna (1985) show that, under such conditions, any feasible and individually rational payoff vector can be approximated arbitrarily closely by SPNE payoffs as the horizon lengthens, partially mitigating unraveling.^[13] Similarly, small noise or payoff perturbations can sustain approximate cooperation through trembling-hand perfect equilibria, where minor errors prevent exact unraveling but allow near-efficient outcomes in sufficiently long horizons.^[9]

Infinite Repeated Games

Discounting and Patience

In infinite repeated games, the discount factor \delta \in [0, 1) captures players' impatience by weighting future payoffs less than immediate ones, with higher values of \delta indicating greater patience and a willingness to prioritize long-term outcomes over short-term gains.^[5] This factor relates to the continuous-time discount rate r \geq 0 through the formula \delta = \frac{1}{1+r}, where a lower r (slower discounting) yields a \delta closer to 1, fostering behaviors that emphasize sustained cooperation or strategic depth across periods.^[5] Player i's normalized payoff, which represents the long-run average per-period utility adjusted for discounting, is given by

u_i(\sigma) = (1 - \delta) \sum_{t=0}^{\infty} \delta^t g_i(a_t),

where g_i(a_t) denotes the stage-game payoff from action profile a_t at time t, and \sigma is the strategy profile.^[5] This formulation ensures payoffs are bounded and comparable across different \delta values, with the factor (1 - \delta) normalizing the infinite sum to reflect an effective average utility.^[5] The degree of patience encoded by \delta profoundly influences equilibrium outcomes: as \delta \to 1, the discrete-time model converges to a continuous-time framework, where the granularity of periods diminishes and players can credibly commit to future-oriented actions.^[5] In contrast, low \delta promotes myopic play, where players effectively revert to one-shot stage-game strategies, as the shadow of the future carries little weight.^[5] Unlike finite repetitions, where backward induction unravels cooperation regardless of patience, infinite horizons with sufficiently high \delta enable non-myopic equilibria.^[5] A canonical illustration arises in the Prisoner's Dilemma stage game, where mutual cooperation yields payoffs of 3 each, defection against cooperation gives 5 to the defector and 0 to the cooperator, and mutual defection yields 1 each; here, a grim trigger strategy—cooperating until deviation, then defecting forever—sustains cooperation in equilibrium if \delta > \frac{1}{2}, as the discounted value of ongoing cooperation exceeds the one-time gain from defection.^[5]

Folk Theorem

The Folk Theorem provides a foundational characterization of the equilibrium payoffs achievable in infinitely repeated games under discounting. Formulated by Fudenberg and Maskin (1986), the theorem states that if players are sufficiently patient—meaning the common discount factor \delta is close enough to 1—then any feasible and individually rational payoff vector can be approximated arbitrarily closely by subgame perfect equilibrium payoffs of the repeated game.^[14] Here, a payoff vector is feasible if it lies in the convex hull of the stage game's payoff set (accounting for mixed strategies), and it is individually rational if each player's payoff strictly exceeds their minimax value, defined as the lowest payoff they can be forced to by others' optimal punishing strategies in the stage game.^[14] The theorem applies to games with perfect monitoring, where actions are publicly observed each period, and assumes a finite stage game with a finite action space for each player. For two-player games, the result holds without additional restrictions, but for three or more players, the stage game's feasible payoff set must satisfy a full-dimensionality condition: it must contain a nonempty open ball in \mathbb{R}^n, where n is the number of players, ensuring that punishments can be tailored precisely to deter deviations by any subset of players.^[14] Fudenberg and Maskin (1986) prove the theorem for uniformly discounted payoffs, where each player's total payoff is the sum \sum_{t=0}^\infty \delta^t g_i(a_t) with g_i denoting stage payoffs and the same \delta applying across periods and players.^[14] An alternative formulation uses the limit-of-means criterion, where payoffs are evaluated as \lim_{T \to \infty} \frac{1}{T} \sum_{t=1}^T g_i(a_t); under this undiscounted average, a similar folk theorem holds for patient play (approximated by low discounting or long horizons), yielding the same set of sustainable outcomes provided the full-dimensionality condition is met.^[14] A sketch of the proof involves constructing subgame perfect equilibrium strategies that sustain the target payoff vector v. Players cooperate by cycling through a finite sequence of stage-game action profiles (possibly mixed) over blocks of lengths chosen to increase with \delta, ensuring the discounted average converges to v. Upon detecting any deviation (via perfect monitoring), all players permanently revert to a Nash equilibrium of the stage game that minimaxes the deviator's payoff. To verify incentive compatibility, the one-period gain from unilateral deviation must not exceed the present-value loss from subsequent punishment: for player i, if d is the deviation gain and m_i is i's minimax payoff, then d \leq \frac{\delta}{1-\delta} (v_i - m_i). As \delta \to 1, the right-hand side grows without bound, making cooperation sustainable for any feasible, individually rational v. Off-path punishments are credible because reversion to the static minimax equilibrium is itself subgame perfect.^[14] The theorem has limitations inherent to its assumptions. It requires perfect public monitoring; under imperfect or private information, fewer payoffs may be sustainable. Additionally, the result covers only payoffs achievable for [\delta](/page/Delta) sufficiently close to 1; for lower [\delta](/page/Delta), the set of subgame perfect equilibria shrinks, often reverting toward static Nash payoffs as impatience increases.^[14]

Cooperation Mechanisms

Trigger Strategies

Trigger strategies are a class of subgame perfect equilibrium strategies in repeated games designed to sustain cooperation by conditioning future play on the history of actions, particularly responding to deviations with punishments.^[3] These strategies were first formalized by Friedman in his analysis of supergames, where he demonstrated that trigger equilibria can enforce non-cooperative outcomes that approximate cooperative payoffs under sufficient patience.^[3] A prominent example is the grim trigger strategy, in which players cooperate in the initial period and continue cooperating as long as no deviation has occurred; upon detecting any deviation, all players revert permanently to a punishment phase, typically the Nash equilibrium strategy of the stage game, for all subsequent periods.^[15] In contrast, forgive-once variants, such as limited punishment triggers, impose a temporary reversion to the punishment strategy for a fixed number of periods before returning to cooperation, thereby allowing recovery from isolated mistakes while still deterring persistent defection.^[16] For these strategies to be incentive compatible and sustainably enforce cooperation, the one-period cooperation payoff must satisfy g_i(a) \geq (1 - \delta) g_i(a_i', a_{-i}) + \delta g_i(a^{NE}), where a is the cooperative action profile, a_i' is the deviating action, and a^{NE} is the Nash punishment action profile; higher patience (larger \delta) expands the set of enforceable outcomes by making punishments more credible.^[15] Grim trigger strategies using Nash equilibrium punishments are optimal in the sense that they achieve feasible and individually rational payoff vectors as per the folk theorem, ensuring the highest possible sustainable cooperation levels without unnecessary inefficiency.^[17] However, such permanent punishments can be vulnerable to renegotiation, as rational players may collectively prefer to abandon inefficient punishment phases; renegotiation-proof refinements thus favor strategies with milder, reversible punishments to avoid these credibility issues while preserving incentive compatibility.^[18] Other variants include stick-and-carrot strategies, which combine punishments for deviations (the "stick") with explicit rewards or reversion to superior payoffs for sustained cooperation (the "carrot"), providing balanced incentives in settings where pure punishment may be overly harsh.^[6] The development of trigger strategies traces back to Friedman's 1971 seminal work, which established their role in equilibrium selection for infinitely repeated supergames, influencing subsequent refinements in game-theoretic literature.^[3]

Examples in Finite Settings

In finite repeated games, cooperation can persist despite the unraveling predicted by backward induction when small probabilities of accidental deviations—known as "trembling hands"—allow players to build reputations for cooperative behavior. Kreps, Milgrom, Roberts, and Wilson (1982) demonstrate this in the finitely repeated prisoner's dilemma, where even a tiny chance of unintended defection creates uncertainty about a player's type, enabling rational players to cooperate early to signal commitment and sustain higher payoffs until near the end.^[19] This reputation effect counters full unraveling by making defection costly if it risks damaging a cooperative image. Experimental studies reveal a paradox of backward induction, where cooperation often endures longer than theory predicts, even in known finite horizons. Murnighan and Roth (1983) conducted laboratory experiments on the finitely repeated prisoner's dilemma with 10 periods, finding that defection typically begins only in the last two or three rounds rather than unraveling immediately from the end; when the horizon was shortened mid-game, cooperation collapsed faster, confirming the role of anticipated future play.^[20] This persistence suggests players anticipate mutual cooperation or overlook full rationality in terminal stages.^[21] In the repeated battle of the sexes—a coordination game where players prefer different joint actions but value matching—alternating between the two pure-strategy equilibria can sustain cooperation in finite settings if the horizon is uncertain or approximately known. Experiments show subjects frequently converge to stable alternation patterns, achieving higher joint payoffs than non-cooperative play, particularly when the exact end is not salient, allowing implicit agreements to hold until late rounds.^[22] Such behavior approximates subgame perfection under bounded foresight.^[23] Recent experiments highlight bounded rationality as a key driver of cooperation in finite repeated games, where players deviate from full backward induction due to cognitive limits. Aoyagi, Fréchette, and Yuksel (2024) analyzed belief formation in finitely repeated prisoner's dilemmas, finding that subjects update beliefs slowly and overweight early cooperation signals, leading to sustained play beyond theoretical unraveling points in games up to 20 periods.^[24] These findings underscore how cognitive frictions enable finite-horizon cooperation without relying on infinite discounting.

Analysis Methods

Solving Approaches

Solving repeated games involves a range of theoretical and algorithmic methods tailored to finite and infinite horizons, leveraging fixed-point theorems, dynamic programming, and equilibrium characterization techniques. In discounted infinite repeated games, the existence and computation of equilibria often rely on fixed-point theorems applied to contraction mappings of the value function operator. Specifically, the discounted payoff structure ensures that the operator mapping current payoffs plus discounted future values to new value estimates is a contraction with modulus δ < 1, guaranteeing a unique fixed point that represents the equilibrium value function via the Banach fixed-point theorem. This approach, foundational in stochastic and repeated game analysis, enables iterative value function updates to converge to equilibria. For finite repeated games, which unfold as extensive-form games with perfect recall, the sequence form provides an efficient representation for computing behavioral strategies and equilibria. In the sequence form, strategies are encoded as probability distributions over sequences of actions rather than full strategy trees, reducing exponential complexity to linear size in the number of sequences, allowing formulation as a linear program (LP) for zero-sum cases or quadratic program for general-sum. This method exploits the game's tree structure to solve for subgame-perfect equilibria without enumerating all pure strategies, making it scalable for moderate horizons.^[25] Dynamic programming forms a core tool across both finite and infinite settings, particularly for characterizing value functions under optimal or equilibrium play. The Bellman equation captures this recursively: for a state s, the value V(s) satisfies

V(s) = \max_a \left[ g(a) + \delta V(s') \right],

where g(a) is the stage payoff from action a, δ is the discount factor, and s' is the resulting state; in multi-player non-zero-sum contexts, maximization is replaced by Nash equilibrium computation over actions. Value iteration applies this equation repeatedly, converging to the fixed point in infinite discounted games due to the contraction property, while in finite games, backward induction solves the system period-by-period from the terminal stage.^[1] Equilibrium computation in repeated games centers on finding strategy profiles that satisfy incentive constraints, ensuring no profitable one-shot deviations in any subgame, as per the one-shot deviation principle. These constraints form a system of inequalities bounding continuation values against deviation payoffs, solvable via linear or nonlinear programming for symmetric or restricted strategy spaces.^[1] However, computational complexity escalates with horizon length: in finite games, the extensive-form tree grows exponentially (O(|A|^T) for T periods and |A| actions), rendering exact solution NP-hard or PPAD-complete even for approximate equilibria in general cases.^[26] Post-2010 advances address these scalability issues through abstraction techniques that compress large state-action spaces while preserving near-optimal equilibria. Methods like counterfactual regret minimization with best-response abstraction (CFR-BR) iteratively refine abstract strategies in extensive-form representations of repeated games, achieving ε-equilibria with bounded regret and reducing effective tree size by orders of magnitude for long-horizon or high-action games.^[27] These approaches, building on sequence-form LPs, enable computation in previously intractable settings like multi-stage security games modeled as repeated interactions.

Computational Tools

Computational tools play a crucial role in analyzing repeated games by enabling the simulation of strategies, computation of equilibria, and approximation of solution sets, particularly when analytical solutions are intractable due to the complexity of infinite horizons or large state spaces. These tools range from specialized software libraries to numerical algorithms that implement dynamic programming principles. The Gambit library is a widely used open-source software suite for computing equilibria in finite and extensive-form games, including repeated games modeled as extensive forms. It supports solving for Nash equilibria in finitely repeated settings through algorithms like Lemke-Howson and supports file formats for importing stage games to construct repeated structures. For infinite repeated games, MATLAB toolboxes such as the Repeated Games Solver provide implementations of dynamic programming methods, including the Abreu-Sannikov algorithm for computing subgame-perfect equilibria in two-player discounted games. This toolbox wraps Java-based solvers to handle continuous-time approximations and payoff calculations. Numerical methods for solving repeated games often rely on iterative techniques derived from dynamic programming. Value iteration, an approximation algorithm, computes value functions by repeatedly applying the Bellman operator to estimate optimal strategies in infinite-horizon games with discounting, converging to the true solution under suitable conditions. For stochastic variants, Monte Carlo methods simulate multiple playouts of the game to estimate expected payoffs and strategy values, particularly useful in high-dimensional state spaces where exact enumeration is infeasible, as demonstrated in reinforcement learning applications to repeated stochastic games. A key application of these tools is in verifying the Folk theorem by computing the set of feasible and individually rational payoffs. This involves formulating the feasible payoff set as a convex hull of stage-game payoffs and solving a linear programming problem to identify sustainable equilibrium payoffs, such as minimizing deviations while ensuring incentive compatibility; for instance, in belief-free equilibria, a two-stage linear programming procedure optimizes over strategy supports and continuation values to bound achievable payoffs. Recent advancements integrate artificial intelligence techniques, notably reinforcement learning, to learn strategies in repeated games without explicit model specification. Post-2020 research has shown that multi-agent reinforcement learning algorithms can approximate Nash equilibria and even sustain collusion consistent with the Folk theorem in discounted settings, as in analyses of strategy profiles emerging from Q-learning in repeated prisoner's dilemma variants. These methods leverage neural networks for policy representation, enabling scalable computation in complex environments like network games. As of 2025, further progress includes using large language models (LLMs) to simulate human-like strategies in finitely repeated games, enhancing empirical analysis of strategic interactions.^[29]

Extensions

Incomplete Information

In repeated games with incomplete information, players possess private types drawn from known prior distributions, which influence their payoffs or strategies but are not directly observable by opponents. These types introduce uncertainty, leading players to update beliefs based on observed actions, akin to signaling in dynamic Bayesian games. A perfect Bayesian equilibrium (PBE) refines the analysis by requiring that strategies and beliefs are sequentially rational at every information set, ensuring consistency between actions and posterior beliefs derived via Bayes' rule where possible.^[30] In such settings, actions serve as signals that convey information about private types over time, potentially enabling cooperation or separation of types in equilibria. Seminal work establishes that the set of PBE payoffs expands beyond static Bayesian Nash outcomes due to repeated interactions allowing for gradual revelation.^[31] Reputation models extend this framework to finite-horizon repeated games, where a small probability of facing an opponent with an "irrational" or commitment type (from a continuum of possible types) can sustain cooperative outcomes that unravel under complete information. In these models, the long-run player builds a reputation for toughness or cooperation by mimicking the commitment type early on, deterring defection as the horizon shortens, even though backward induction predicts defection in finite complete-information games. This reputation effect arises because incomplete information prevents immediate unraveling, allowing payoffs close to the cooperative frontier for sufficiently patient players. The foundational insight traces to early analyses of zero-sum games with incomplete information on one side, where non-revealing strategies preserve value, but reputation models generalize to non-zero-sum settings with infinite type spaces.^[32] Key results show that any feasible, individually rational payoff can be approximated in equilibrium if the prior on commitment types is positive and the game satisfies a full-dimensionality condition on payoffs.^[33] Imperfect monitoring further complicates incomplete information by introducing noisy signals of actions or payoffs, which may be public (observed by all) or private (observed only by the affected player). Under public monitoring, players receive a common noisy signal of the action profile, enabling coordination but limiting punishment precision compared to perfect monitoring. Private monitoring, where each player observes only their own payoff or a signal thereof, exacerbates the free-rider problem in sustaining cooperation, as deviations are harder to detect and attribute. Communication equilibria address this by allowing cheap talk alongside signals, where players publicly announce messages to correlate actions or reveal private information, subject to incentive compatibility. In perfect communication equilibria, full revelation is achievable if signals are sufficiently informative, expanding the feasible payoff set toward the complete-information folk theorem limits.^[34] Recent extensions characterize bounds on equilibrium payoffs under discounting and private monitoring, showing that communication can restore efficiency in some cases but not others depending on signal structure.^[35] Advancements in the 2020s have incorporated learning dynamics into these models, where players update type beliefs via Bayesian inference from noisy signals and adapt strategies accordingly. In settings with short-run players entering periodically, learning enables the informed player to extract value by gradually revealing information, achieving the value of the complete-information game in the limit. These results highlight how reinforcement learning or recursive estimation can converge to PBE in incomplete-information environments, bridging theoretical equilibria with behavioral observations.^[36] More recent works (2023–2025) explore rationality of learning algorithms in such games and applications of large language models (LLMs), which develop strategies like loss aversion in imperfect information settings, enhancing understanding of AI-driven interactions.^[37]^[38]

Stochastic Variants

Stochastic games extend repeated games by incorporating a dynamic state space that evolves probabilistically based on players' actions, capturing environments where outcomes depend on exogenous or endogenous uncertainties beyond mere action histories. Formally, a stochastic game features a finite state space S, finite action sets A_i for each player i, state-dependent payoff functions r_i(s, a) for joint actions a = (a_1, \dots, a_n), and transition probabilities P(s' \mid s, a) that determine the probability of moving to state s' \in S after actions a in state s. These models generalize Markov decision processes to multiple interacting agents, allowing payoffs and future states to vary systematically with the current state.^[39] The primary equilibrium concept in stochastic games is the Markov perfect equilibrium (MPE), a subgame-perfect Nash equilibrium where strategies depend only on the current state, ensuring consistency across subgames and avoiding non-credible threats. In two-player zero-sum discounted stochastic games, Shapley (1953) proved the existence of a unique value and stationary MPE, where policies are state-independent in form but constant over time. For non-zero-sum settings, extensions of the folk theorem apply to discounted stochastic games with perfect monitoring: as the discount factor approaches 1, the set of MPE payoffs approaches the feasible, individually rational payoff set, provided the game is irreducible and monitoring is public. Dutta (1995) established this result, showing that sustainable outcomes mirror those in standard repeated games but account for state transitions. Recent extensions include folk theorems for irreducible stochastic games with imperfect public monitoring (Hörner et al., 2022), broadening applicability.^[39]^[40]^[41] Stochastic games find key applications in economic modeling, such as resource extraction problems where the state represents remaining stock levels, actions are extraction rates, payoffs reflect revenues minus costs, and transitions model stochastic depletion or replenishment processes. In these settings, MPE often leads to over-extraction compared to cooperative outcomes, highlighting tragedy-of-the-commons dynamics under uncertainty. Similarly, in oligopoly models, the state might capture market conditions like demand shocks or inventory levels, with actions as production quantities; transitions then reflect how joint outputs influence future market states, enabling analysis of collusive equilibria in volatile industries.^[42]^[43] For large populations of interacting agents, mean-field games provide an approximation to stochastic games by treating the aggregate behavior as a continuum distribution over states and actions, reducing computational complexity while preserving strategic interactions. Emerging in the late 2000s, this framework models repeated stochastic interactions among many players—such as in crowd dynamics or financial markets—where each agent's payoff depends on the mean field of others' strategies, leading to coupled systems of Hamilton-Jacobi-Bellman and Fokker-Planck equations for equilibrium. Lasry and Lions (2007) laid the foundational theory for these non-zero-sum stochastic differential games, with extensions to discrete-time repeated settings facilitating scalability for high-dimensional populations.

References

[1]
[PDF] Repeated Games - Olivier Gossner
The theory of repeated games models situations in which a group of agents engage in a strategic interaction over and over. The data of the strategic in- ...
[2]
[PDF] et games and decisions - Gwern
From. Chapter 3 through 12 the theory of games is examined: Chapter 3 gives the general model; Chapters 4, 5, and 6 present theories of two-person games, and ...
[3]
[PDF] A Non-cooperative Equilibrium for Supergames - Jerome Mathis
Jan 3, 2020 · It is the purpose of this paper to present a non-cooperative equilibrium concept, applicable to supergames, which fits the Nash (non-cooperative) ...
[4]
https://www.sciencedirect.com/science/article/pii/B9780444537669000021
[5]
[PDF] A Course in Game Theory - Mathematics Department
This book was typeset by the authors, who are greatly indebted to Donald Knuth. (the creator of TEX), Leslie Lamport (the creator of LATEX), and Eberhard ...
[6]
[PDF] Chapter 12 Repeated Games - MIT OpenCourseWare
Here, augmented refers to the fact that one simply augments the payoffs in the stage game by adding the present value of future payoffs under the purported ...
[7]
Zur Theorie der Gesellschaftsspiele | Mathematische Annalen
Zur Theorie der Gesellschaftsspiele. Published: December 1928. Volume 100, pages 295–320, (1928); Cite this article. Download PDF · Mathematische Annalen Aims ...
[8]
https://press.princeton.edu/books/paperback/9780691079356/contributions-to-the-theory-of-games-volume-ii
[9]
Reexamination of the perfectness concept for equilibrium points in ...
Download PDF ... Selten, R. Reexamination of the perfectness concept for equilibrium points in extensive games. Int J Game Theory 4, 25–55 (1975).
[10]
[PDF] Reexamination of the Perfectness Concept for Equilibrium Points in ...
Aug 23, 1974 · The new definition of perfectness has the property that a perfect equilibrium point is always subgame perfect but a subgame perfect equi-.
[11]
Finitely Repeated Games - The Econometric Society
Jul 1, 1985 · Jean-Pierre Benoit, Vijay Krishna. We study subgame perfect equilibria of finitely repeated games. We prove a limit "folk theorem" for these ...
[12]
The chain store paradox | Theory and Decision
The chain store game is a simple game in extensive form which produces an inconsistency between game theoretical reasoning and plausible human behavior. We.
[13]
Finitely Repeated Games - jstor
We study subgame perfect equilibria of finitely repeated games. We prove a limit "folk theorem" for these games. Under weak conditions, any feasible and ...
[14]
the folk theorem in repeated games with discounting or with ... - jstor
[8] FUDENBERG, D., AND E. MASKIN: "Nash and Perfect Equilibrium Payoffs in Discounted. Repeated Games," mimeo, Harvard University, 1986. [9] : " ...
[15]
https://web.stanford.edu/~rjohari/teaching/notes/246_lecture10_2007.pdf
[16]
https://www.worldscientific.com/doi/10.1142/S0219198904000186
[17]
Non-cooperative Equilibrium for Supergames12 - Oxford Academic
James W. Friedman; A Non-cooperative Equilibrium for Supergames12, The Review of Economic Studies, Volume 38, Issue 1, 1 January 1971, Pages 1–12, https://
[18]
[PDF] Renegotiation in Repeated Games* - Harvard University
In repeated games, subgame-perfect equilibria involving threats of punishment may be implausible if punishing one player hurts the other(s). If players can.
[19]
Rational cooperation in the finitely repeated prisoners' dilemma
We show here how incomplete information about one or both players' options, motivation or behavior can explain the observed cooperation.
[20]
The Role of Information in Bargaining: An Experimental Study
Recent experimental studies of bargaining have demonstrated effects due to information not included in the classical models of games of complete information.Missing: backward paradox
[21]
Laboratory Experimentation in Economics: A Methodological Overview
designing prisoner's dilemma experiments Roth and Murnighan (I978) wrote. It is often contended in the literature that if subjects are not informed of the ...
[22]
[PDF] Alternation in the repeated Battle of the Sexes - MIT
This game pits cooperation against the desire to achieve the maximum re- ward on each move. Both players maximize their payoff by coordinating their play and ...
[23]
Learning with repeated-game strategies - PMC - NIH
Abstract. We use the self-tuning Experience Weighted Attraction model with repeated-game strategies as a computer testbed to examine the relative frequency, ...
[24]
[PDF] Beliefs in Repeated Games: An Experiment - Faculty
This paper uses a laboratory experiment to study beliefs and their rela- tionship to action and strategy choices in finitely and indefinitely repeated.
[25]
[PDF] Motives behind cooperation in finitely repeated prisoner's dilemma
Cooperation in FRPD can be motivated by Altruism, Duty, Efficiency-Seeking, and Reciprocity. Efficiency-Seeking best fits experimental data.<|separator|>
[26]
Efficient Strategy Computation in Zero-Sum Asymmetric Repeated ...
Mar 6, 2017 · Using this property, we refine the sequence form, and formulate an LP computation of player strategies that is linear in the size of the ...
[27]
The Complexity of Computing a Nash Equilibrium | SIAM Journal on ...
Computing Nash equilibria is not known to run in polynomial time. This paper shows that finding it in three-player games is PPAD-complete.
[28]
[PDF] Bayesian repeated games - HAL
We consider Bayesian games, with independent private values, in which uniform punishment strategies are available. We establish that the Nash equilibria of the ...
[29]
Bayesian repeated games and reputation - ScienceDirect.com
We consider two-person undiscounted and discounted infinitely repeated games in which every player privately knows his own payoffs (private values).
[30]
[PDF] Kreps, D. and R. Wilson [1982]: "Reputation and Imperfect ...
We show that imperfect information is one such mechanism. Moreover, the effects of imperfect information can be quite dramatic.
[31]
[PDF] Rational Cooperation in the Finitely‑Repeated Prisoners' Dilemma
The purpose of this note is to demonstrate how reputation effects due to informational asymmetries can generate cooperative behavior in finitely repeated ...
[32]
Communication in Repeated Games with Imperfect Private Monitoring
This paper examines repeated games with imperfect private signals and public communication. It explores how revelation constraints and signal imperfections can ...
[33]
Perfect communication equilibria in repeated games with imperfect ...
This paper introduces an equilibrium concept called perfect communication equilibrium for repeated games with imperfect private monitoring.
[34]
[PDF] Repeated Games with Incomplete Information and Short-Run Players
Apr 11, 2022 · Stephan Waizmann ∗†. April 11, 2022. I study repeated zero-sum games ... That is,. Aumann and Maschler's “Cav u” result applies here as well.
[35]
Stochastic Games* | PNAS
In a stochastic game, play proceeds by steps with transition probabilities controlled jointly by two players. The game may not be bounded in length.
[36]
A Folk Theorem for Stochastic Games - ScienceDirect.com
A Folk Theorem for Stochastic Games. Author links open overlay panel. Dutta Prajit K. ... A folk theorem for such games is presented. The result subsumes a ...
[37]
Stochastic games of resource extraction - ScienceDirect.com
We study stochastic games of resource extraction in which the transition probability is a convex combination of stochastic kernels with coefficients ...
[38]
Stochastic Games in Economics and Related Fields: An Overview
(1985) Oligopoly extraction of a common-property natural resource: The inportance of the period of commitment in dynamic games, InternationalEconomic Review ...