CS Paper Radar

Expanding and Evaluating the Applicability of Safe Pareto Improvements

Nathaniel Sauerberg, Caspar Oesterheld

cs.GT ·submitted 2026-11-17 23:07 UTC · v1
published

Abstract

Even when players can make credible joint commitments in games, disagreement about the game's default outcome (e.g., about equilibrium selection) can prevent them from agreeing on any particular payoff profile. We study safe Pareto improvements (SPIs): commitments that sidestep this obstacle by inducing a new game that is isomorphic to the original (after iteratively removing strictly dominated actions) but entrywise Pareto better. We do so by constructing token games: cheap-talk games rendered meaningful by commitments to take payoff-relevant actions (in prior work, strategies in the original game) as a function of the token outcome. Since these token games preserve the original game's strategic structure, players should expect them to be played isomorphically and hence agree that they Pareto improve on the original. In this work, we study token game SPIs under three additional commitment abilities: (1) burning utility, (2) transferring utility between players, and (3) transferring utility with an outside party conditional on the token outcome (e.g., via insurance-like contracts). We characterize when SPIs exist in each case and give efficient algorithms for optimizing over them. Finally, we propose evaluating SPI frameworks by how often they enable SPIs in randomly generated games. In such experiments, our methods substantially outperform prior work.

Comment
An earlier version was presented at GAIW'26

Closest papers

Nearest neighbours by meaning across the whole index.

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

Equilibria of Round-Robin: Computational Hardness and Fairness for Few Subadditive Agents

cs.GT cs.CCcs.DS ·2026-09-16 ·Paul W. Goldberg, Alexandros Hollender, Giannis Tyrovolas
theory similarity 0.65
Abstract

The round-robin procedure is a simple and well-studied fair division mechanism where agents pick goods in turns. Motivated by draft mechanisms in sports leagues, we investigate strategic behaviour in online round-robin for subadditive agents. This gives rise to an extensive-form game, and we study the computational problem of computing a subgame perfect Nash equilibrium (SPNE). We show that for just two submodular agents, computing an SPNE is $\mathsf{PSPACE}$-hard. Even for the class of $\mathit{OXS}$ utilities, which are a special case of submodular utilities, computing an SPNE remains $\mathsf{NP}$-hard for a small number of agents. We complement our computational results with normative results. We show that for just three additive agents, there exist instances where every equilibrium violates EF1. This separates the online and the direct revelation games. On the positive side, we show that for additive agents every equilibrium allocation is proportional up to one good (PROP1) and for two additive agents it is also EF1. Finally, by showing that round-robin is bossy at equilibrium, we prove that the number of equilibrium allocations can be exponential even if agents have lexicographic preferences.

0.19

On the Convergence of Iterated Round Robin

cs.GT ·2026-10-16 ·Maxime Lucet, Henri Surugue, Nawal Benabbou, Aurélie Beynier, Nicolas Maudet +1 more
similarity 0.60
Abstract

Round Robin (RR) is a simple and widely used picking sequence mechanism for allocating indivisible goods, known to guarantee envy-freeness up to one item (EF1) when preferences are additive. Despite being manipulable (meaning that agents may have an incentive to strategically misreport their preferences), it is known to always admit at least one pure Nash equilibrium. In this paper, we study an iterated variant of RR, in which agents observe the outcome of the mechanism at each iteration and may revise their reported preferences through a best-response dynamics. We first consider a full-information setting, where agents observe both the outcome and the reported preferences of all the agents. In this setting, we show that cycles can occur even under strong restrictions on the manipulations carried out by the agents. We nonetheless identify a natural restriction (item-preserving swaps), under which convergence to a pure Nash equilibrium is guaranteed to exist for any number of agents and items. We also show that restricting to adjacent swaps guarantees convergence for two agents and a limited number of items, leaving the question open for unbounded number of items. We then turn to a partial-information setting, in which agents only observe the resulting allocation and must then infer the preference profiles of the others assuming consistency with the RR sequence. We study three behaviours guiding the agents when deciding how to manipulate under uncertainty on the other agents' preferences. We show that two of the studied behaviours, despite being quite natural, may cycle while a more cautious rule guarantees iterated RR to be strategyproof.

0.10

Refundable Deposits: How to Restore Cooperation in Finitely Repeated Games

cs.GT econ.TH ·2026-08-27 ·Giulio Salizzoni, Domenico Mergoni Cecchelli, Edward Plumb, Maryam Kamgarpour, Galit Ashkenazi-Golan
similarity 0.60
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.

0.18

Matching Tasks to Agents: Mechanism Design for Multi-Agent Contracts

cs.GT ·2026-10-22 ·Matteo Bollini, Matteo Castiglioni, Alberto Marchesi
benchmark similarity 0.59
Abstract

We study task assignment under adverse selection and moral hazard. In the single-task setting, agents privately know their types, which determine their success probabilities and effort costs. Based on the agents' reported types, the principal selects an agent to perform the task and offers a success-contingent payment. Although optimal Bayesian contract design is generally computationally intractable and Myerson's characterization does not directly extend to settings with hidden actions and multidimensional private information, we show that the single-task problem admits a simple Myerson-style characterization. Our key insight is that incentive constraints depend only on the ratio between effort cost and success probability. We characterize an optimal mechanism and show that it can be computed in polynomial time. We also establish a tight $Θ(1/(NK))$ worst-case bound on the ratio between the optimal profit and the full-information benchmark, where $N$ is the number of agents and $K$ is the number of types per agent. We then extend our analysis to multiple tasks, showing that an optimal mechanism may not exist. Nevertheless, for a constant number of agents, we provide a polynomial-time approximation scheme for the supremum profit.

0.31

A Weakly Group Strategy-Proof and Pareto-Stable Matching Mechanism with Two-Sided Indifferences under Gross Substitutes

cs.GT econ.TH ·2026-10-22 ·Yasushi Kawase, Ryosuke Sato
similarity 0.59
Abstract

We study finite many-to-one matching markets with indifferences on both sides and publicly known firm preferences over sets of workers. A standard approach breaks ties uniformly at random and runs deferred acceptance, which is strategy-proof for workers but may select a weakly stable matching that is Pareto dominated under the agents' original preferences. For the broad class of markets in which each firm's preferences admit a gross substitutes (GS) representation, we construct a deterministic generalized deferred acceptance mechanism that is weakly stable, Pareto efficient with respect to both sides, worker weakly group strategy-proof, and implementable in strongly polynomial time given value oracles for the GS representations. This domain includes nonresponsive firm preferences, such as additive scores under matroid constraints and assignment values. Our analysis bridges ordinal matching with indifferences and competitive equilibria under imperfectly transferable utility. Although the mechanism uses only ordinal comparisons, it returns a seller-optimal equilibrium matching of a tiered auxiliary market, and the equilibrium structure of this market yields the stability, efficiency, and incentive guarantees.

0.07

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.59
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

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.58
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