Source-linked AI summary
Refundable Deposits: How to Restore Cooperation in Finitely Repeated Games
Giulio Salizzoni, Domenico Mergoni Cecchelli, Edward Plumb, Maryam Kamgarpour, Galit Ashkenazi-Golan
TL;DR
Finitely repeated games have a smaller equilibrium set than infinitely repeated games, while cooperation fails in the Prisoner’s Dilemma. The paper introduces a deposit mechanism requiring no player commitment and shows that, with voluntary deposits and a terminal payoff, sufficiently long finite repetition can recover the Nash-threat folk-theorem equilibrium, with payoffs approaching the infinite-horizon benchmark.
Problem
Finitely repeated games can have a smaller equilibrium set than infinitely repeated games, and cooperation fails in the Prisoner’s Dilemma.
Method
The paper introduces a deposit mechanism for arbitrary games that requires no commitment from players and analyzes the resulting finite multistage game using observed actions.
Results
A sufficiently long finite horizon with voluntary deposits and a terminal payoff recovers the Nash-threat folk-theorem equilibrium, with realised payoffs matching the infinite-horizon benchmark up to discounted deposit costs.
Takeaways & Limitations
The self-enforcing deposit mechanism enlarges the equilibrium set of finitely repeated games toward the infinite-horizon benchmark.
Takeaways & Limitations
The construction requires a reliable deposit mechanism, and its bound is driven by the ratio ¯w_i/d_i as δ approaches one.
Abstract
from arXiv · showhide
While infinitely repeated games admit a rich set of Nash equilibria, finitely repeated games typically have a much smaller and often inefficient one. We show how to enlarge this set using deposits: in each period a player may place a refundable sum with a neutral intermediary, returned when the game ends and forfeited following a deviation. Paying these deposits is voluntary and incentive compatible at every stage, so no commitment by the players is assumed, the only commitment required being that of the intermediary to a refund rule fixed before play begins. The mechanism sustains payoff profiles more efficient than those of the standard equilibria, without altering the underlying game and without transfers between players. We demonstrate it on the prisoner's dilemma, a congestion game, and a public goods game, all settings where cooperation cannot emerge in the standard finitely repeated version. We also apply it to a dynamic common-pool resource, suggesting that the construction extends beyond repeated stage-games.
1 Introduction
Finitely repeated games can collapse to repeated stage-game Nash equilibrium play, unlike infinitely repeated games, where cooperation may be sustained. The paper introduces voluntary refundable deposits to enlarge finite-horizon equilibrium outcomes without changing the stage-game or transferring payments between players.
- The finite-horizon problem: Backward induction restricts finitely repeated games to repeated stage-game Nash equilibrium play when the horizon is fixed.In the Prisoner’s Dilemma, the final period is effectively one-shot, and the reasoning propagates backward.
- Motivation: The paper asks whether finite interaction fundamentally causes the inefficiency of standard finitely repeated equilibria.Prior approaches modify information, the horizon, rationality, enforcement, or the equilibrium concept.
- Deposit mechanism: The proposed mechanism lets players voluntarily deposit money with a neutral intermediary, which refunds accumulated stakes when the game ends.The intermediary commits to a refund rule fixed before play, while players need not commit themselves.
- Deposit mechanism: Deposits do not alter the underlying stage-game or create transfers between agents, and equilibrium payment is individually incentive compatible at every stage.The mechanism instead uses forfeiture after deviation to support cooperation.
- Main contribution: The mechanism sustains every feasible payoff vector giving each player strictly more than that player’s lowest stage-game Nash-equilibrium payoff.This set contains, and generally exceeds, payoffs that strictly Pareto-dominate one fixed stage-game Nash equilibrium.
- Scope: The construction applies to arbitrary stage-games and sufficiently long finite horizons, including a dynamic common-pool resource whose stage-game evolves with the state.The paper also presents applications to the Prisoner’s Dilemma, congestion, and public goods settings.
2 Environment and mechanism
The augmented game adds voluntary deposit decisions and terminal payoffs to a finite repetition of a finite-player stage-game. Deposits act like continuation payoffs: refunding them preserves incentives, while forfeiture after deviation lowers the deviator’s payoff.
- Stage-game environment: The environment is a finite-player stage-game with finite action sets, mixed actions, and a nonempty compact set of stage-game Nash equilibria.For each player, the worst Nash-equilibrium payoff is well defined.
- Period structure: Each period consists of simultaneous action choices, observed stage payoffs, and a subsequent binary decision on whether to pay a deposit.Players observe the full action and deposit histories.
- Terminal payoffs: At the terminal date, each player receives a history-dependent terminal payoff funded by deposits paid during the repeated game.The feasibility condition rules out cross-subsidisation and external funding.
- Implementation: The intermediary holds deposits and returns them according to a predetermined terminal-payoff rule rather than acting as a strategic player.Players’ own deposits fund the terminal payoff, distinguishing the construction from earlier terminal-payoff mechanisms.
- Incentive logic: A deposit returned only when nobody deviates lowers a deviator’s payoff like a reduced continuation value, recreating an incentive to cooperate.Off-path play switches to the stage-game Nash equilibrium that minimises the first deviator’s payoff.
- Supported payoffs: For sufficiently patient players, the supported sequence class generates every feasible payoff vector strictly above each player’s worst stage-game Nash payoff.The target can be delivered by a deterministic pure-action path whose continuation values remain within η of the target.
3 Main result
For any target action sequence with a strict Nash-threat margin, sufficiently long finite repetition can reproduce its on-path play using deposits and terminal payoffs. The resulting strategy profile is subgame perfect, with the finite-horizon payoff gap arising from discounted deposit costs.
- Deposit and refund rules: The deposit rule pays on the equilibrium path and stops payments after any deviation, while terminal refunds depend on the first deviator and actual deposits.Refunds are capped by each player’s own deposits, preserving feasibility on every history.
- Theorem 3: For every sufficiently long horizon T ≥ T∗, a deposit scheme and terminal-payoff rule support the truncated target sequence as a subgame perfect equilibrium.The threshold depends on the stage-game, discount factor, and strict incentive margins.
- Equilibrium verification: No on-path or off-path action or deposit deviation is profitable under the constructed strategies.The proof verifies this using the one-shot deviation principle.
- Theorem 3: Theorem 3 constructs a subgame perfect equilibrium of a finite augmented game that reproduces the on-path actions and stage-payoff sequence of any sequence in A∗.The construction uses deposits on path and switches permanently to a Nash equilibrium minimising the first deviator’s payoff after deviation.
- Payoff approximation: The realised finite-horizon payoffs differ from the infinite-horizon benchmark only through discounted deposit costs, which can be driven to zero by lengthening the horizon and shrinking per-period deposits.For a fixed horizon, the mechanism sustains the target exactly; the trade-off concerns deposit cost rather than play.
- Corollary 4: The Nash-threat folk theorem with deposits attains feasible profiles strictly above each player’s worst stage-game Nash payoff, up to a vanishing deposit cost.For every sufficiently long finite horizon, the normalised on-path payoff can lie within ξ of any target v in the relevant payoff set.
4 Optimal deposit design
The paper formulates cost-minimising refundable-deposit design as a per-player linear program balancing incentive, feasibility, liquidity, and robustness requirements. Deposits are costly because they are held over time, while terminal rewards must cover residual incentive gaps.
- Program and objective: Theorem 3 establishes feasibility using a constant per-period deposit, while the optimal program searches for cheaper deposit streams for a fixed target and horizon.The design problem is solved independently for each player because deposits are self-funded and never transferred between players.
- Program and objective: The program imposes incentive constraints, self-funding feasibility, and a liquidity bound limiting each period’s deposit to the player’s on-path payoff.The liquidity bound can make otherwise valid target strategies infeasible, especially when a player receives nothing in some periods.
- Optimal structure: At every optimum, the terminal reward is maximised subject to feasibility, and the cost-minimising deposit scheme need not be unique.Changing the final-period deposit and terminal reward together can preserve both the objective and incentive constraints.
- Optimal structure: A unit deposited at date t costs δt−1 −δT−1 in present value, so earlier deposits are more expensive than later ones.The cost reflects the value lost while the intermediary holds the deposit until termination.
- Lower bounds: Any feasible scheme must provide a terminal reward bounded below by a quantity determined by the target, horizon, and no-deposit incentive gaps.The bound applies even without imposing the liquidity cap or self-funding feasibility.
- Extensions: Adding a robustness margin η raises optimal cost and shifts deposits earlier, while intermediary fees increase the required stake and therefore the player’s cost.The linear-program structure remains intact when robustness requirements or intermediary fees are added.
5 Examples
Four examples show that refundable deposits can restore cooperation across symmetric, asymmetric, lenient-punishment, and dynamic settings. The mechanism can require very short horizons in prisoner’s dilemmas and remains applicable with endogenous state variables.
- 5.3 Public goods game: In the public goods game, deposits sustain gentler continuation punishments rather than requiring reversion to universal defection.Retaining k cooperators raises off-path welfare but increases the deviator’s free-riding payoff λk/n and the terminal reward needed for deterrence.
- 5.4 Tragedy of the commons: In the dynamic common-pool resource, the construction extends beyond repeated stage-games when deviation gains are uniformly bounded, with deposits closing incentives except near the end.A terminal reward financed by accumulated deposits restores cooperation in the final bounded number of periods, given sufficient horizon feasibility.
- 5.1 Repeated prisoner’s dilemma: In repeated prisoner’s dilemmas above rcoop = 1 −δ, deposits restore cooperation, with Tmin increasing near the boundary and reaching Tmin = 2 away from it.Below the boundary, cooperation cannot be sustained even with an infinite horizon.
- 5.1 Repeated prisoner’s dilemma: For most canonical prisoner’s dilemmas, two or three periods suffice to sustain cooperation, far below the sufficient threshold T∗ from Theorem 3.The examples illustrate that limited commitment can be enough in empirically relevant parametrisations.
- 5.2 Congestion game: In the congestion game, deposits sustain an efficient rotating allocation in which players take turns using the resource.The allocation maximises aggregate welfare but is not self-enforcing without deposits; depositing costs are minimal and zero for player 1.
- 5.2 Congestion game: The congestion-game terminal stake grows with n because the cooperative reward becomes sparser while the temptation to deviate persists.The mechanism therefore accommodates asymmetric costs across players, including zero cost for some players.
6 Conclusion
The paper introduces a self-enforcing refundable-deposit mechanism that restores cooperation in finitely repeated games without changing the stage game or requiring player commitment. It characterizes its costs, scope, and boundaries, including applications to dynamic interactions with endogenous states.
- Main result: The mechanism restores the Nash-threat folk theorem in finite time by supporting suitable pure-action payoff profiles as subgame perfect equilibria.It applies when the target sequence is sustainable by Nash threats with a strict margin in the infinitely repeated game.
- Mechanism: Deposits create a terminal stake that disciplines closing-period behavior, while their discounted cost can vanish as the horizon lengthens and per-period deposits shrink.Deposits are costly in present value, but their undiscounted accumulation grows with the horizon, allowing a sufficiently large terminal reward at vanishing discounted cost.
- Mechanism: Refundable deposits are voluntary and incentive compatible at every stage, while commitment is required only from a neutral intermediary enforcing a precommitted refund rule.The intermediary holds deposits and returns them according to the rule fixed before play; the construction therefore relocates, rather than eliminates, commitment.
- Design trade-offs: Cost minimization defers deposits, whereas robustness margins and liquidity caps require earlier deposits to make commitment credible against early withdrawal.The authors formulate target-specific thresholds, deposits, and terminal rewards, with cost minimization represented by separate linear programs.
- Scope: The construction applies to arbitrary finite-player stage games, asymmetric targets, gentler deposit-supported off-path continuations, and dynamic interactions with endogenous states.The dynamic extension requires only a uniform bound on one-shot deviation gains rather than stationary payoffs.
- Limitations: The analysis assumes observed actions, observed deposit decisions, complete information, and an intermediary able to commit to the refund rule and remain solvent.Extending the mechanism to noisy monitoring, intermediary failure, heterogeneous discounting, asymmetric liquidity, and experimental settings is left for future work.
Funding
The authors acknowledge support from the Swiss National Science Foundation and the SNSF NCCR Automation Grant.
- Giulio Salizzoni acknowledges support from the Swiss National Science Foundation, grant number 207984.
- The authors also acknowledge support from the SNSF NCCR Automation Grant.
Declaration of generative AI usage
During preparation, the authors used Claude for grammatical corrections, typo correction, and smoothing the final version of the paper.
- Claude was used to correct grammatical mistakes and typos and smooth the final version of the human-written paper.
- The authors reviewed and edited the content after using the tool.
- The authors take full responsibility for the published article's content.