Repeated Game

A game in which the same stage game is played over many rounds by the same players, who can condition their actions on history. Repetition changes the strategic calculus: outcomes unreachable as equilibria of the one-shot game (notably mutual cooperation in a Social Dilemma) can be sustained because future reward and punishment discipline present behaviour — the content of the folk theorems. The Iterated Prisoners Dilemma and Axelrod’s tournaments are the canonical studies, and repeated-game structure is what makes Reciprocity and Indirect Reciprocity effective among self-interested agents.

In this vault

Backlinks

Linked Pages

Social Dilemma

A strategic situation in which individually rational choices produce a collectively worse outcome than mutual cooperation would — the tension between self-interest and group welfare. Canonical instances include the Prisoner’s Dilemma, the public-goods game, and the tragedy of the commons; the defining feature is that defection dominates for each player yet universal defection is Pareto-inferior. Social dilemmas are the testbed for studying when and how Reciprocity, reputation, and Indirect Reciprocity can sustain cooperation, including among LLM Agents.

In this vault

Iterated Prisoners Dilemma

The repeated version of the classical prisoner’s dilemma game: each round, both players choose cooperate or defect, with payoffs T > R > P > S (temptation > reward > punishment > sucker), and play continues for an indefinite number of rounds with discount factor w. Unlike the one-shot game (where defection is dominant), iterated play with sufficient w makes cooperation rationally sustainable via reciprocal strategies like Tit-for-Tat. The standard testbed for cooperative MAS / cooperative-AI research, made canonical by Axelrod’s tournaments (1979–1984).

In this vault

The Evolution of Cooperation

Reference: Axelrod, R. (1984). The Evolution of Cooperation. Basic Books, New York. (Revised 2006 with new afterword by Axelrod and a foreword by Richard Dawkins. Underlying conference papers: Axelrod, R. & Hamilton, W. D. (1981). The Evolution of Cooperation. Science 211(4489), pp. 1390–1396.) Science 1981 DOI · Internet Archive borrow (book)

Summary

Axelrod investigates how cooperation can arise and persist among self-interested agents in the absence of central authority — by running computer tournaments of strategies for the iterated prisoner’s dilemma (IPD). In the one-shot prisoner’s dilemma, defection is the dominant strategy and rational play leads both parties to a Pareto-inferior outcome. Axelrod’s central question is whether iteration changes the picture. He invited game theorists to submit strategies; in two tournaments (1979 and 1980, the second much larger and including strategies designed to exploit the first round’s lessons) tit-for-tat — submitted by Anatol Rapoport, only four lines of code (cooperate on the first move, then copy the opponent’s previous move) — won both. The book’s analytic contribution is identifying why. Axelrod isolates four properties of successful IPD strategies: niceness (never defect first), retaliation (punish defection promptly), forgiveness (return to cooperation as soon as the opponent does), and clarity (be predictable so the opponent can learn to cooperate with you). He proves an evolutionary-stability result: a population of tit-for-tat players cannot be invaded by any non-cooperative strategy if the discount factor (probability of further interaction) is sufficiently high. The book extends the analysis to historical case studies — most famously the live-and-let-live system in WWI trench warfare — and to biological evolution of cooperation in symbiosis and group selection. Axelrod’s framework supplies the foundation for mechanism-design approaches to multi-agent cooperation, the theoretical underpinning of trust-and-reputation systems, and the contemporary literature on cooperative AI.

Key Ideas

Iterated prisoner’s dilemma changes everything: in repeated play with sufficient probability of further interaction, cooperation is rationally sustainable; the shadow of the future makes defection costly.
Tit-for-tat wins both tournaments: the simple strategy of cooperating first, then copying the opponent’s previous move, beats much more sophisticated strategies because it is nice (avoids unprovoked defection), retaliatory (punishes promptly), forgiving (returns to cooperation immediately), and clear (transparent enough that opponents can learn to cooperate).
Four properties of successful strategies: nice (never defect first), retaliating (defect immediately if opponent defects), forgiving (cooperate again as soon as opponent does), clear (recognisable as a tit-for-tat-like strategy).
Evolutionary stability: a population of tit-for-tat players resists invasion by non-cooperative mutants when the discount factor w is high enough (w > (T - R) / (T - P) for the standard payoffs). Cooperation is an evolutionary attractor, not just an analytical curiosity.
Cluster invasion: a small cluster of tit-for-tat players in a sea of all-defect can invade the population if the cluster is large enough that within-cluster interactions dominate cross-cluster interactions — explaining how cooperation can emerge from a non-cooperative starting point.
Trench warfare in WWI: extensive case study of how live-and-let-live systems emerged in static trench positions where the same units faced each other repeatedly — a real-world iterated prisoner’s dilemma in which tit-for-tat-like strategies emerged spontaneously and were eventually suppressed only by the introduction of artillery and unit rotation that reduced the “shadow of the future.”
Recommendations for promoting cooperation: enlarge the shadow of the future (longer-term relationships, more frequent interactions), change the payoffs (reduce the temptation to defect), teach reciprocity, improve recognition (allow opponents to remember each other), enhance retaliation capabilities.

Connections

Conceptual Contribution

Claim: Cooperation among self-interested agents arises and persists in the absence of central authority when interactions are iterated with sufficient probability of further interaction. The successful strategies are nice, retaliating, forgiving, and clear; tit-for-tat is the simplest example. A population of tit-for-tat players is evolutionarily stable; small clusters of cooperators can invade non-cooperative populations.
Mechanism: Two open computer tournaments of IPD strategies; analysis of why tit-for-tat won; isolation of the four properties of successful strategies; evolutionary-stability and cluster-invasion theorems with explicit conditions on the discount factor; case studies (WWI trenches, biological symbiosis); concrete recommendations for institutional design.
Concepts introduced/used: Iterated Prisoners Dilemma, Tit-for-Tat, Reciprocity, Shadow of the Future, Niceness/Retaliation/Forgiveness/Clarity, Evolutionary Stability (in IPD), Cluster Invasion.
Stance: foundational research monograph in cooperative game theory and behavioural economics.
Relates to: Foundational for the trust-and-reputation programme in MAS — Review on Computational Trust and Reputation Models and Inter-Agent Trust Models - A Comparative Study systematise the engineering descendants of Axelrod’s tit-for-tat-with-memory across dozens of computational trust models. Conceptual companion of Lewis (1969) and Schelling (1960) in establishing how cooperation/coordination arise without central authority — the three together supply the standard reading list for emergent-cooperation work in MAS. In the LLM-agent era, the IPD setting is the standard testbed for evaluating cooperative AI; the four properties (nice/retaliating/forgiving/clear) translate directly into design criteria for multi-agent LLM coordination protocols, and the clarity property is particularly relevant to the Why AI Agents Communicate In Human Language critique — natural-language strategies are hard to recognise as tit-for-tat-like, so the cooperation-supporting mechanisms Axelrod identified are weakened. The Cooperative AI research programme (Dafoe et al. 2020) is an explicit modern continuation of Axelrod’s project for the multi-agent LLM era.

In this vault

Do LLM Agents Have Regret

Do LLM Agents Have Regret? A Case Study in Online Learning and Games

Reference: Park, Liu, Ozdaglar & Zhang (2024). Do LLM Agents Have Regret? A Case Study in Online Learning and Games. arXiv:2403.16843 (MIT; UMD). URL. OpenReview: https://openreview.net/forum?id=OhZ4u164cN.

Summary

Park et al. ask a sharp question about LLM agents in interactive settings: do they have regret? — i.e. do they exhibit the no-regret behaviour that classical online-learning and game-theoretic algorithms guarantee, and that is necessary for converging to coarse-correlated equilibria in repeated games?

The paper proceeds in three steps. Empirically, they evaluate GPT-3.5 / GPT-4 / Claude / Llama on canonical online-learning benchmarks (prediction-with-expert-advice; bandit-like sequential decision problems) and on repeated games (matrix games, Cournot, Bertrand, public-goods). Frontier LLMs are often no-regret across these settings and often converge to coarse-correlated or Nash equilibria when playing each other. Theoretically, they offer a partial explanation: under stylised assumptions on supervised pre-training and human rationality, the LLM’s next-action distribution approximates a softmax over historical payoffs — which itself implements a no-regret algorithm. But they identify clean failure cases: there exist simple non-stationary or adversarial online-learning instances where even GPT-4 demonstrably accumulates linear regret.

The paper’s constructive contribution is a new regret-loss training objective. Unlike supervised pretraining loss, regret-loss does not require labels of optimal actions — only the historical sequence of plays and payoffs. The authors prove a statistical generalisation bound for regret-loss minimisation and an optimisation guarantee that minimising it can recover known no-regret learning algorithms (e.g. FTRL). Empirically, regret-loss-finetuned models close the gap on the failure cases. The paper is a foundational reference for any analysis of LLM agents in markets, auctions, or interactive coordination — a category that includes Virtual Agent Economies, Mechanism Design for Large Language Models, Learning Collusion in Episodic Inventory-Constrained Markets, and Language Models Can Reduce Asymmetry in Information Markets.

Key Ideas

Regret as a diagnostic for LLM agents in interactive settings: do they no-regret-learn against arbitrary opponents?
Empirical screen: frontier LLMs (GPT-3.5/4, Claude, Llama) on canonical online-learning + repeated-game benchmarks.
Often no-regret in benign settings, often converging to coarse-correlated / Nash equilibria when playing each other.
Theoretical bridge: under stylised pretraining + human-rationality assumptions, the LLM’s next-action distribution resembles a softmax over payoffs — itself a no-regret algorithm.
Identified failure cases: simple non-stationary / adversarial online-learning instances where GPT-4 has linear regret.
Regret-loss objective: label-free training loss that explicitly incentivises no-regret behaviour; statistical and optimisation guarantees.
Recovery of classical algorithms: minimising regret-loss can converge to algorithms like FTRL.

Connections

Conceptual Contribution

Claim: Whether LLM agents exhibit no-regret behaviour in interactive settings is the right diagnostic for whether they can be deployed in markets, auctions, and coordination protocols. Frontier LLMs are often but not always no-regret; specific failure cases can be fixed by an explicit regret-minimising training objective.
Mechanism: Empirical benchmark of LLMs on online learning + repeated games (regret + equilibrium convergence); theoretical link from supervised pretraining to softmax-over-payoffs (a no-regret update); construction of a label-free regret-loss with generalisation + optimisation guarantees; recovery of FTRL-like algorithms as the loss is minimised.
Concepts introduced/used: No-Regret Learning, Regret-Loss, Online Learning, Repeated Game, Coarse-Correlated Equilibrium, FTRL, LLM Agents
Stance: empirical + theoretical
Relates to: Cousin work to Cicero Human-Level Play in Diplomacy in the “LLMs as game-theoretic agents” thread. Provides the analytical foundation for the systemic-risk claims in Virtual Agent Economies and the collusion experiments in Learning Collusion in Episodic Inventory-Constrained Markets; mechanism-design implications for Mechanism Design for Large Language Models; the trust assumption behind Language Models Can Reduce Asymmetry in Information Markets depends on agents being approximately no-regret.

CoopEval - Benchmarking Cooperation-Sustaining Mechanisms and LLM Agents in Social Dilemmas

CoopEval: Benchmarking Cooperation-Sustaining Mechanisms and LLM Agents in Social Dilemmas

Reference: Tewolde, Zhang, Guzman Piedrahita, Conitzer & Jin (2026). CoopEval: Benchmarking Cooperation-Sustaining Mechanisms and LLM Agents in Social Dilemmas. arXiv:2604.15267 [cs.GT]. URL.

Summary

CoopEval asks whether the game-theoretic mechanisms classically designed to make rational agents cooperate in equilibrium also work when the agents are LLM Agents. The motivating observation is a safety concern: despite their stronger reasoning, frontier LLMs tend to defect in single-shot mixed-motive games such as the prisoner’s dilemma. Rather than treating this as a fixed property of the models, the authors ask which institutional structures layered around the agents can shift them toward cooperative outcomes — making cooperation a property of the mechanism, not just the model.

The paper conducts what it describes as the first comparative evaluation of cooperation-sustaining mechanisms for LLM agents across four social dilemma scenarios. It pits four classical mechanisms against each other: (1) repeating the game over many rounds (the Axelrod route to reciprocity); (2) reputation systems; (3) third-party mediators that take delegated decisions on the players’ behalf; and (4) contract agreements with outcome-conditional payments. Each is a different way of changing the payoff structure or information environment so that cooperation becomes individually rational.

The headline finding is that contracting and mediation are the most effective at producing cooperation between capable LLM models, while repetition-induced cooperation deteriorates drastically when co-players vary — i.e., the reciprocity that sustains cooperation against a fixed partner does not transfer to a churning population. The authors further show these mechanisms become more effective under evolutionary pressure to maximise individual payoff, suggesting they are robust rather than fragile equilibria. The work positions mechanism design — not just model capability — as a lever for safe, cooperative multi-agent LLM ecosystems.

Key Ideas

Defection is the default: capable LLMs reliably defect in single-shot social dilemmas, a safety concern as such agents are deployed into mixed-motive interactions.
Cooperation as a mechanism property: the question is reframed from “do LLMs cooperate?” to “which institutions make rational agents cooperate, and do they work on LLMs?”
Four mechanisms benchmarked: repeated play, reputation systems, third-party mediation (delegated decisions), and outcome-conditional contracts.
Four social-dilemma scenarios provide the evaluation arena.
Contracting and mediation win: both reliably induce cooperation between capable models; contracts bind payoffs, mediators delegate the decision to a cooperative third party.
Repetition is brittle: repetition-induced cooperation collapses when co-players change — reciprocity tied to a fixed partner does not survive a varying population.
Robust under evolutionary pressure: the effective mechanisms strengthen, not weaken, when agents are selected to maximise individual payoff.

Connections

Conceptual Contribution

Claim: Whether LLM agents cooperate in mixed-motive settings is governed less by raw capability — capable models default to defection — than by the institutional mechanism wrapped around them. Outcome-conditional contracts and third-party mediation are the most effective cooperation-sustaining mechanisms for capable LLMs, while repetition-based reciprocity is brittle once the partner population varies.
Mechanism: A comparative benchmark across four social-dilemma scenarios that evaluates four classical cooperation-sustaining mechanisms (repeated play, reputation, mediation, contracting) on LLM agents, including under evolutionary selection toward individual-payoff maximisation.
Concepts introduced/used: Social Dilemma, Mechanism Design, Iterated Prisoners Dilemma, Reputation, Mediation, Contract (Mechanism), Reciprocity, LLM Agents
Stance: empirical / benchmark
Relates to: Sits squarely in the “LLMs as game-theoretic agents” thread alongside Do LLM Agents Have Regret (no-regret diagnostics) and Talk Judge Cooperate - Gossip-Driven Indirect Reciprocity in Self-Interested LLM Agents (gossip-based reputation as one of the very mechanisms benchmarked here); extends the Axelrod reciprocity lineage by showing where repetition fails for LLM populations; complements the collusion findings of Learning Collusion in Episodic Inventory-Constrained Markets and the systemic concerns of Virtual Agent Economies.

Indirect Reciprocity

A mechanism for the evolution of cooperation (Nowak & Sigmund) in which an agent helps those who have a reputation for helping others, rather than only those who helped it directly (direct Reciprocity / Tit-for-Tat). Cooperation is repaid by third parties via reputation rather than by the original beneficiary — “I help you, someone else helps me” — which requires a way to observe and transmit reputational information, classically through gossip or a shared score. It is the social principle behind language-mediated reputation among LLM Agents in ALIGN.

In this vault

Reciprocity

The principle of returning like for like: cooperation for cooperation, defection for defection. The mechanism behind Tit-for-Tat’s success in IPD play and behind much of human social cooperation (Trivers 1971 Reciprocal Altruism; Fehr & Gächter 2002 Strong Reciprocity). In MAS, reciprocity is the operative principle of most computational trust models — agents track partners’ past behaviour and modulate cooperation accordingly. The information conditions for reciprocity to support cooperation (recognition of partners across rounds, memory of past interactions, sufficient shadow of the future) are non-trivial design constraints for any open multi-agent system.