CS Paper Radar

On the Fragility of Efficiency: Uncoupled Learning with a Deviant

Vade Shah, Jason R. Marden

cs.GT ·submitted 2026-10-05 15:40 UTC · v1
hot direction

Abstract

An important question in learning in games is whether players can learn to achieve efficient outcomes, those that maximize the sum of their utilities, without communication or coordination. Completely uncoupled learning algorithms, which use only each player's own past actions and utilities, can guarantee this in broad classes of games, but they typically require every player to follow the same algorithm. In this work, we ask whether one can design welfare-maximizing learning algorithms that are robust to a deviant player. To study this question, we take a well-studied welfare-maximizing learning algorithm as a testbed and consider what happens when every player except one follows it. First, we consider a deviant player who either (i) always plays the same action or (ii) selects their action uniformly at random. We show that such a player can significantly alter the long-run behavior of this algorithm, leading to states that are far from welfare-maximizing, and that no completely uncoupled learning algorithm is robust to such a player in every game. Next, we consider a strategic deviant player who acts in their own interest and show that this player can adopt a different learning algorithm to shift the long-run outcome in their favor. Moreover, we show that under any completely uncoupled welfare-maximizing learning algorithm, there is a game in which some player benefits from switching to a different completely uncoupled learning algorithm. These results show that completely uncoupled welfare-maximizing learning is fragile, even to a single deviant player, suggesting that robustness may require communication or coordination.

Closest papers

Nearest neighbours by meaning across the whole index.

Multi-Agent Learning of Reactive Strategies in Iterated Games

cs.GT physics.soc-phq-bio.PE ·2026-10-10 ·James P. Wolfe, Joshua B. Plotkin
theorycode/data similarity 0.72
Abstract · 27 pages, 14 figures (12 pages + 3 figures main text; 15 pages + 11 figures Supplemental Material). Code: https://github.com/james-wolfe/rea…

Learning agents, whether humans or algorithms, adapt to one another rather than to a fixed environment. Selfish learning need not produce a good outcome for the group, especially when learners face a social dilemma. The iterated prisoner's dilemma (IPD) is the classical example, but it is usually studied in populations of agents who imitate successful strategies. Here, we instead study selfish gradient ascent learners on the two-dimensional space of reactive strategies. A reactive strategy is described by two continuous traits: reciprocity, the chance of cooperating after the co-player cooperates, and forgiveness, the chance of cooperating after the co-player defects. Each learner updates its strategy in the direction that most rapidly improves its payoff against all other learners, by an amount governed by its learning rate. We show that heterogeneity in learning rates can qualitatively change the long-term outcome: a population with uniform learning rates converges to always-defect (ALLD), whereas a population with variable learning rates approaches generous-tit-for-tat (GTFT), which produces nearly optimal collective payoffs. In simulations, every population passes through a transient state of minimal forgiveness, in which the distribution of reciprocity determines the outcome. Variable learning rates promote cooperation because slow learners preserve high reciprocity until the population reaches this state. We prove sufficient conditions on the distribution of reciprocity for convergence to ALLD or to tit-for-tat (TFT). Variable learning rates also allow cooperation to recover from perturbation, which is provably impossible under uniform learning. These results suggest that purely selfish and myopic learning can produce persistent cooperation provided the population has intrinsic variability in learning rates.

0.40

Regret, equilibrium, and learning in games: A guided tour

cs.GT cs.LGmath.OC ·2026-08-10 ·Panayotis Mertikopoulos
publishedtheory similarity 0.70
Abstract · 44 pages, 3 figures; to appear as a chapter in "Equilibria in Games: Existence, Selection, and Dynamics", edited by Sylvain Sorin and Bernha…

This note aims to serve as an entry point to the literature on learning in games, a topic with significant theoretical appeal and a wide range of applications -- from machine learning and data science to economics and beyond. Our presentation is structured around two complementary viewpoints: We first consider a single agent -- the learner -- engaged in a sequential decision process in an unknown, non-stationary, and possibly adversarial environment. We then examine what happens when the environment is shaped by the decisions of several interacting agents, not necessarily aware of each other's actions or goals, and all seeking to improve their individual rewards. In this general context, we examine a family of regularized learning policies based on best-responding to the past history of play, up to a regularization penalty intended to encourage exploration and prevent over-commitment to suboptimal choices. In the single-agent setting, we present some basic regret bounds for regularized learning in adversarial multi-armed bandits; in the multi-agent setting, we describe an ergodic equilibrium convergence result for zero-sum games in the spirit of classical results on fictitious play, as well as a "folk theorem" linking strategic and dynamic notions of stability -- Nash equilibria and attracting points of regularized learning, respectively. We pay special attention to the information available to the players and, through a unified analysis framework, we study both oracle- and payoff-based (bandit) methods. Our goal is to provide a coherent and comprehensible -- albeit, by necessity, not comprehensive -- account of some recent ideas in the field, and to discuss their implications for the study of rationality.

0.25

How Learning Selects Equilibria and When It Leads to Collusion

cs.GT ·2026-10-26 ·Hanzhang Wang, Manxi Wu
benchmark similarity 0.68
Abstract

We study how learning algorithm design shapes equilibrium selection in infinite-horizon discounted Markov games with finite states and actions. Each episode, players choose smooth best responses to beliefs about opponents' policies, test them using noisy observations, and resample rejected beliefs or explore at rates determined by increasing transformations of their discounted values. We show that stochastically stable states induce approximate stationary Nash equilibria maximizing the minimum transformed discounted value across players, with transformations governing which players selection favors. In repeated games with bounded recall of noisy public signals, longer recall weakly increases the selected minimum transformed value. In repeated Cournot games, every stochastically stable state induces an approximate public perfect equilibrium whose minimum discounted profit across firms exceeds the Cournot-Nash benchmark. Collusion is therefore inevitable under these conditions and learning dynamics. For symmetric firms, selected profits can approach the monopoly benchmark arbitrarily closely. These results offer a novel equilibrium-selection perspective on algorithmic collusion.

0.17

Learning Rewards in Strategic Games

cs.GT cs.AIcs.LGcs.MA ·2026-10-15 ·Antoine Bergerault, Cyrille Kone, Giorgia Ramponi
similarity 0.67
Abstract

Understanding the objectives that drive agents' behavior is crucial in strategic environments, where multiple agents interact and adapt to one another. This challenge arises in domains such as cybersecurity, autonomous driving, and online markets, where agents' underlying incentives are typically unknown and must be inferred from their observed behavior. Inverse reinforcement learning (IRL) provides a natural framework for this problem, but extending IRL to strategic multi-agent settings introduces a fundamental challenge: a reward that explains observed behavior does not necessarily induce optimal strategies when used for decision-making. In this work, we study this problem through the lens of \emph{strategic identifiability}, and show that learning from a fixed policy pair can be insufficient to strategically identify rewards, independent of the number of expert samples $K$. Motivated by this, we introduce an active IRL algorithm for two-player repeated Stackelberg games, in which the leader adaptively selects policies to elicit informative responses about the follower's reward. Combining maximum-likelihood estimation with experimental design, we derive finite-sample guarantees on the Stackelberg sub-optimality induced by the learned reward, matching up to polylogarithmic factors a new minimax learning rate of $K^{-1/2}$. Finally, we evaluate our approach in a realistic anti-poaching setting, demonstrating the benefits of active exploration for reward recovery and downstream strategic performance.

0.21

Fictitious Play When Agents Are Not Expected-Utility Maximizers: A Geometric Analysis in $2$-Action Games

cs.GT eess.SYmath.OC ·2026-11-12 ·Hao Liang, Solaleh Mohammadi, Kaiqing Zhang
similarity 0.66
Abstract

Fictitious play (FP) is one of the earliest and most fundamental learning procedures in games, where each agent independently chooses a best response to the empirical distribution of opponents' past actions by maximizing the expected payoff with respect to it. However, learning agents may not always be expected-utility maximizers: they may use nonlinear evaluation functionals to account for the uncertainty induced by the opponents, e.g., via risk measures. In this work, we study nonlinear fictitious play (NL-FP), in which each pure action is evaluated by a general, possibly nonlinear functional of the payoff distribution induced by the opponent's empirical belief. To analyze NL-FP, we first identify a single-crossing property (SCP) of evaluation functionals that preserves the classical geometry of FP in $2\times2$ games. Furthermore, we conduct a novel geometric analysis of the convergence behavior of NL-FP in $2\times2$ games, even when the SCP fails. Beyond $2\times2$ games, we show that the convergence of NL-FP in $2\times n$ ($n\ge3$) games may fail even for continuous-time NL-FP, when the two-action player uses conditional value-at-risk (CVaR) in a $2\times3$ game. In addition, we identify a finite-crossing condition that ensures convergence of the selected continuous-time dynamics and the discrete-time iterates in general $2\times n$ games, which also provides new insights into the global landscape of continuous-time classical FP in such games.

0.13

Beyond Supra-Competitive Outcomes: Collusive Behaviour in Deep Reinforcement Learning for Optimal Execution Games

cs.AI q-fin.TR ·2026-09-30 ·Christos Spyridon Koulouris, Carlo Campajola
benchmark similarity 0.65
Abstract

In this paper, we extend earlier findings of supra-competitive outcomes in optimal-execution games by identifying a learned punitive mechanism that deters deviations and provides behavioural evidence of collusion. We investigate this mechanism in a two-player, finite-horizon Almgren-Chriss liquidation game. Independent proximal policy optimisation agents with access to within-episode price and action histories achieve costs below the Nash benchmark. We identify a profitable deviation by training against the mean learned liquidation schedule, then impose its first trade on one of the original agents. The opponent responds by accelerating liquidation. This response more than offsets the deviator's gain in every run and both player roles, while leaving the punisher's average payoff materially unchanged relative to not punishing under the same deviation. The punisher imposes greater losses on the deviator while preserving its own average payoff, despite the availability of more profitable, less punitive liquidation plans. Matching deviations and subsequent additional selling rise and later decline during training, while final policies retain an effective punitive response. We formalise two checks: whether punishment outweighs the gain from deviating, and whether the change in trading behaviour is large enough to account for the loss imposed. Both checks hold for the tested deviation. Together, these findings provide behavioural and economic evidence supporting a collusive interpretation of the learned supra-competitive outcomes.

0.27

Planning Against Learning in Rank-1 Games

cs.GT ·2026-08-18 ·William Overman
similarity 0.65
Abstract

Learning algorithms are often used to make decisions in repeated multi-agent environments. When another player understands how a learner adapts from past experience, that player can plan strategically across rounds to influence the learner's future behavior. Recent work shows that optimizing against Replicator Dynamics, the continuous-time analogue of Multiplicative Weights Update, is tractable in zero-sum games but can be hard in unrestricted general-sum games. We study the first structured class beyond zero sum: bimatrix games satisfying $\text{rank}(A+B)=1$, for which Nash equilibria can be computed in polynomial time. Our main result shows that this equilibrium tractability does not extend to planning against learning dynamics. Unless $\mathsf{P}=\mathsf{NP}$, approximating the optimizer's optimal continuous-time reward within a fixed additive constant is NP-hard even when $\text{rank}(A+B)=1$, the learner starts from the uniform state, and the optimizer is restricted to constant strategies. The hardness persists for bounded payoff matrices and polynomially bounded horizons. We complement this result with structural characterizations of several tractable special cases. Thus rank-one games already separate efficient equilibrium computation from strategic planning against a learning opponent.

0.06

Who Bears the Burden? Learning Responsibility for Shared Constraints in Multi-Agent Reinforcement Learning

cs.LG cs.AIcs.GTcs.MA ·2026-10-05 ·Xiaoyang Cao, Jingqi Li, Zhe Fu, Alexandre M. Bayen
code/data similarity 0.64
Abstract · 20 pages, 2 figures, 4 tables. Project page with code: https://lira-marl.github.io

When multiple agents share a cost budget, a common Lagrange multiplier can enforce the aggregate constraint but does not determine how its penalty should be allocated across agents. Uniform penalties ignore heterogeneity in the rewards agents sacrifice, while agent-specific multipliers may still rely on the same aggregate cost signal. We introduce Lagrangian Responsibility Allocation (LiRA), which learns each agent's share of a common multiplier by optimizing social welfare over a finite training horizon. The multiplier enforces the aggregate budget, while responsibility shares redistribute its influence without modifying the original rewards or constraints. For convex games under standard regularity conditions, varying these shares induces a smooth family of normalized generalized Nash equilibria in which active constraints remain at their budgets while welfare varies. To optimize responsibility before convergence, we derive a welfare gradient that accounts for both learning updates and the induced change in data distribution. Across CityLearn, MABIM, Harvest, and MetaDrive, spanning 3 to 400 agents, LiRA improves average social welfare by up to 29% over uniform and agent-specific multiplier baselines. Grid and driving costs remain within budget, inventory violations decrease, and Harvest makes more effective use of available budget.

0.36