CS Paper Radar

Refundable Deposits: How to Restore Cooperation in Finitely Repeated Games

Giulio Salizzoni, Domenico Mergoni Cecchelli, Edward Plumb, Maryam Kamgarpour, Galit Ashkenazi-Golan

cs.GT econ.TH ·submitted 2026-08-27 15:53 UTC · v1

Abstract

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.

Closest papers

Nearest neighbours by meaning across the whole index.

The Game of Marginal Utilities

cs.GT math.OC ·2026-08-11 ·Isaac M. Sonin, Georgy Gaitsgori, Yaakov Malinovsky
theory similarity 0.68
Abstract · 29 pages

We study a noncooperative resource-allocation game in which $m$ players distribute fixed resources among $n$ projects and the payoff of player $j$ is given by \[ F^j(x) = \sum_{i=1}^n \frac{a_i x_i^j}{b_i+\sum_{\ell=1}^m x_i^\ell}, \] where $a_i$ and $b_i$ are project parameters, while $x_i^j$ is the amount of resources player $j$ allocates to project $i$. This specification combines diminishing returns with congestion generated by competitors. We prove that the game has a unique Nash equilibrium and characterize it by an equimarginal principle. We show that, after the projects are ordered by $a_i/b_i$, each player invests in an initial segment of projects, and these segments are nested across players, so the equilibrium decomposes into consecutive activity zones; players with larger resources invest weakly more in every project. In the fully active regime, where every player invests in every project, we reduce the equilibrium to a single scalar nonlinear equation for the aggregate marginal-utility rate; all individual marginal rates, investments, and payoffs then follow from explicit formulas. We also provide a projected marginal-utility algorithm with global linear convergence under an explicit step-size condition, together with a structure-exploiting \textit{Block Pandora} algorithm that reconstructs and certifies the equilibrium conditional on a proposed nested cutoff structure.

0.10

Sender-Receiver Games with Payment Commitments

cs.GT ·2026-10-04 ·Ivan Geffner
similarity 0.66
Abstract

We study sender-receiver games in which players commit, before the state is drawn, to payments contingent on the subsequently verified state and the receiver's action. Payments may be transferred or burned, serving as contractual guarantees or promised tips. We analyze equilibrium guarantees, welfare, and computational complexity. For arbitrary finite action sets, we characterize pessimistic utility guarantees under unilateral commitments. Sender-only and sender-first commitments have worst-equilibrium welfare equal to the best constant-action welfare. Simultaneous commitments can instead reduce welfare below every equilibrium of the original game. Neither simultaneous nor sender-first commitments always admit an efficient equilibrium. Receiver-first commitments always admit an efficiently computable welfare-maximizing equilibrium, but can also reduce worst-equilibrium welfare. For binary actions, we characterize their entire equilibrium payoff region. With binary actions, optimal receiver commitments are computable in linear time, whereas optimizing deterministic sender commitments is NP-hard. Privately randomized sender commitments admit an exact $O(n\log n)$ algorithm, with an optimal lottery over at most two schemes differing at only one state. This yields an additive approximation by deterministic commitments. For arbitrary finite action sets, optimal privately randomized sender payoffs equal Bayesian persuasion values: ordinary persuasion with burning alone, and persuasion with nonnegative compliance payments when transfers are allowed. These equivalences yield polynomial-time algorithms with polynomial-size commitment lotteries.

0.16

Revisiting the Fairness of Pure Nash Equilibria of Round-Robin

cs.GT ·2026-10-16 ·Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Federico Fusco, Stefano Leonardi +1 more
theory similarity 0.65
Abstract · Corrects the claim in arXiv:2109.08644 (WINE 2021; Math. Oper. Res. 49(4), 2024) that every pure Nash equilibrium of Round-Robin is EF1. We …

We prove that for additive valuations, not every pure Nash equilibrium of the Round-Robin mechanism induces an allocation that is envy-free up to one good (EF1) with respect to the agents' true valuations. This corrects an earlier claim of Amanatidis et al. (WINE 2021; Math. Oper. Res. 2024). On the positive side, every pure Nash equilibrium of every fixed recursively balanced picking sequence mechanism induces an allocation that is $1/2$-EF1 and proportional up to one good (PROP1). We prove the approximate EF1 guarantee through a potential function comparing two executions, and the proportionality guarantee via a deviation that preserves the agent's most valuable goods. We also give a family of Round Robin equilibria showing that it is not possible to have a strictly better guarantee than $2/3$-EF1 for all equilibria.

0.06

A Resource Allocation Tournament

cs.GT math.OCecon.TH ·2026-10-22 ·Adam Nathaniel, Refael Hassin
similarity 0.65
Abstract

We introduce and analyze a round-robin simultaneous resource allocation contest, motivated by sports leagues and other competitive environments where agents must distribute limited resources across multiple encounters. Players allocate resources in advance to matches against all opponents, and match outcomes are determined by relative allocations. We study two payoff schemes: total points, where players accumulate rewards for each win, and winner-takes-all, where only the tournament winner is rewarded. For three players, we provide complete equilibrium characterizations under both schemes. For four or more players, we show that the total points payoff admits Blotto-type equilibria, while the winner-takes-all payoff requires numerical and algorithmic analysis. To address this, we develop a best-response dynamics algorithm with stochastic inertia and use it to approximate equilibria in games with four and five players.

0.26

Who Pays for a Connected Public Good?

cs.GT math.CO ·2026-08-27 ·Marco Tulio Angulo
theory similarity 0.65
Abstract

Connectivity can turn separate contributions into a public good that benefits participants and nonparticipants alike. Yet only participants pay for it, and each can avoid her charge by withdrawing while enjoying whatever public output survives. How do network connections constrain who can or must pay, and how large a cost can the group bear? We study a participation game in which public output equals the size of the largest connected group of active players, whose members divide a fixed operating cost. The output a participant destroys by withdrawing is her withdrawal responsibility and bounds her payment. These bounds determine the group's cost-bearing capacity and, whenever the group can be kept active, which participants must pay. We prove that among connected networks with at least five players, the path uniquely maximizes the cost-bearing capacity of a group, yet minimizes the expected surviving output after a uniformly selected participant withdraws. As the group grows, the ratio of maximal capacity to gross social benefit under full participation converges to one quarter. Fragility can therefore strengthen voluntary finance, but even the most financeable network cannot close the gap between the value it creates and what its participants will pay to sustain it.

0.14

Performance of Zero-determinant Strategies in Repeated Games without Discounting

cs.MA physics.soc-pheess.SY ·2026-10-02 ·Masahiko Ueda
similarity 0.64
Abstract · 4 pages, 1 figure

Zero-determinant (ZD) strategies are a class of strategies in repeated games, which unilaterally control payoffs. It has been shown that several ZD strategies promote cooperation in social dilemma games. It has been widely believed that the performance of ZD strategies is expressed as ``unilaterally enforce linear relations between payoffs''. However, in order to interpret properties of ZD strategies in repeated games without discounting, previous studies assumed that the limit of the Cesaro average of the probability distribution of the action profile exists. Here, we explain the performance of ZD strategies without this assumption, which leads to a stronger result than previous ones.

0.41

RARE: Response-Aware Rational Equilibrium in Budget-Constrained Pricing Games

cs.GT ·2026-10-28 ·Bhaskar Ray Chaudhury, Jugal Garg, Xin Huang, Eklavya Sharma
theory similarity 0.62
Abstract · Changes in v2: improved title, exposition, and bibliography

We study a pricing game in markets with budget-constrained buyers, where each seller offers a single good and sets its price. We consider both non-rivalrous goods, such as datasets, and rivalrous goods, such as physical goods. For non-rivalrous goods, each buyer chooses a utility-maximizing bundle within her budget. For rivalrous goods, an allocation rule selects a Pareto-optimal allocation subject to the buyers' budgets and the goods' supply constraints. Pure Nash equilibria often fail to exist in this game. A key reason is that Nash equilibrium assumes that the other sellers keep their prices fixed when one seller deviates. In practice, however, sellers harmed by a price change may respond, for example, by matching the new price. We propose a new equilibrium notion called Response-Aware Rational Equilibrium (RARE). At a RARE, every deviation by a seller can be deterred by a response from the other sellers, in which no responder earns less than she did right after the deviation. Every Nash equilibrium is a RARE. Assuming that the allocation rule is continuous in prices, we show that a RARE always exists for rivalrous goods, and for non-rivalrous goods when buyers have equal budgets. Moreover, the RARE that we construct extracts the buyers' entire budget. For non-rivalrous goods with unequal budgets, we show that an approximate RARE exists, where a deviating seller can increase her revenue by a factor equal to the ratio of the average budget to the minimum budget. We also study a natural dynamic in which sellers repeatedly raise their prices to earn the revenue that they could guarantee themselves by deviating. We show that, in the settings where we prove exact existence, this dynamic reaches a RARE with additive error $δ$ within $\lfloor B/δ\rfloor$ rounds, where $B$ is the buyers' total budget. This paper's main results have been formally verified in Lean 4.

0.24

On the Fragility of Worst-Case Nash Equilibria in Atomic Congestion Games

cs.GT ·2026-09-10 ·Colton Hill, Brandon Collins, Philip N. Brown
similarity 0.61
Abstract

Aggregate performance in smart mobility systems depends heavily on the emergent behavior of selfish, resource-sharing agents that participate within the systems. As a result, recent work has focused on how a system designer can leverage incentives to influence behavior so that system cost (e.g., traffic congestion) is minimized. These results show that worst-case equilibria can be quite inefficient compared to system-optimal allocations. However, it is unclear to what extent agents are ``satisfied'' with their decisions in these worst-case scenarios. We demonstrate that in any incentivized atomic congestion game, agents' aggregate satisfaction at equilibrium (relative to their actions in an optimal allocation) is correlated with the efficiency of the corresponding system cost, in the sense that if agents are very satisfied with their equilibrium choices, the equilibrium must be relatively efficient. Further, we show that worst-case Nash equilibria are fragile, as every agent is indifferent between their action in a worst-case equilibrium and their action in a system-optimal allocation. In summary, at equilibrium, either agents are highly satisfied with their decisions or their decisions are highly inefficient, but both cannot be true simultaneously. This work adds to recent results for other classes of games which indicate that worst-case equilibrium efficiency guarantees only occur when agents are indifferent about their decisions.

0.27