Game Theory

Follow this topic Ask about this topic

Momentum

21 papers in the last four weeks, up 200% on the four weeks before. 0.2% of all new papers.

Jul 13Week of Sep 28

Latest papers 159

Apr 30, 2026cs.AI

A Collective Variational Principle Unifying Bayesian Inference, Game Theory, and Thermodynamics

Collective intelligence emerges across biological, physical, and artificial systems without central coordination, yet a unifying principle governing such behaviour remains elusive. The Free Energy Principle explains how individual agents adapt through variational inference, while game theory formalises strategic interactions. Here we introduce the Game-Theoretic Free Energy Principle, a unified framework showing that multi-agent systems performing local free-energy minimisation implicitly implement a stochastic game. We prove that, under bounded rationality and local information constraints, stationary points of collective free energy correspond to approximate Nash equilibria of an induced game. Conversely, a broad class of cooperative games admits a variational representation in which equilibria arise as Gibbs distributions over coalitions, establishing a bridge between Bayesian inference and strategic interaction. To characterise higher-order effects, we introduce a free-energy formulation of the Harsanyi dividend, isolating irreducible multi-agent synergy. This yields a predictive theory of cooperation, including a falsifiable non-monotonic relationship between sensory precision and agent influence. We validate this prediction across neural, biological, and artificial multi-agent systems. These results identify a common variational principle underlying inference, thermodynamics, and game-theoretic equilibrium.

Djamel Bouchaffra, Faycal Ykhlef, Mustapha Lebbah +1

1DAVID Lab, University of Paris-Saclay, UVSQ, 78035 Versailles, France. · 2TSAM, ASM, Centre for Development of Advanced Technologies, Algiers, Algeria. · 3LIPN, UMR CNRS 7030, Sorbonne Paris Nord University, Villetaneuse, France.

Nash Equilibrium Cooperative Game Theory Game Theory Bayesian Inference Free Energy Principle Multi-Agent Systems+2

Apr 30, 2026cs.GT

Can We Volunteer Out of the Peer Review Crisis?

The volume of scientific manuscripts is growing faster than the capacity to evaluate them, yet the institutions that govern peer review have remained largely unchanged. The result is a widening mismatch: reviewer scarcity, noisier assessments, and declining confidence in editorial decisions. Every scientist wants better reviews, but review quality depends on the total burden, which no single author can shift. To isolate this tension, we provide a game-theoretic thought experiment: a voluntary lottery in which authors accept a chance of random pre-review rejection, reducing reviewer burden and improving the quality of surviving evaluations. We show that a Nash equilibrium emerges in which authors voluntarily enter the lottery. Scientists who care about the literature they read, not just the papers they publish, will opt in, raising the quality of published science for all.

Theo Tang, Toby Handfield, Julian Garcia

Department of Data Science and Artificial Intelligence, Monash University, Melbourne, Australia · SOPHIS, Monash University, Melbourne, Australia

Mechanism Design Game Theory Scholarly Peer Review

Apr 29, 2026cs.GT

What Suppresses Nash Equilibrium Play in Large Language Models? Mechanistic Evidence and Causal Control

LLM agents are known to deviate from Nash equilibria in strategic interactions, but nobody has looked inside the model to understand why, or asked whether the deviation can be reversed. We do both. Working with four open-source models (Llama-3 and Qwen2.5, 8B to 72B parameters) playing four canonical two-player games, we establish the behavioral picture through self-play and cross-play experiments, then open up the 32-layer Llama-3-8B model and examine what actually happens during a strategic decision. The mechanistic findings are clear. Opponent history is encoded with near-perfect fidelity at the first layer (96% probe accuracy) and consumed progressively, while Nash action encoding is weak throughout, never exceeding 56%. There is no dedicated Nash module. Instead, the model privately favors the Nash action through most of its forward pass, but a prosocial override rooted in pretraining on human text concentrated in the final layers reverses this, reaching 84% probability of cooperation at layer 30. Injecting a learned Nash direction into the residual stream shifts behavior bidirectionally and causally, confirmed through concept clamping. The behavioral experiments surface six scale- and architecture-dependent findings, the most notable being that chain-of-thought reasoning worsens Nash play in small models but achieves near-perfect Nash play above 70B parameters. The cross-play experiments reveal three phenomena invisible in self-play: a small model can unravel any partner's cooperation by defecting early; two large models reinforce each other's cooperative instincts indefinitely; and who moves first determines which Nash equilibrium the system reaches. LLMs do not lack Nash-playing competence. They compute it, then suppress it.

Paraskevas V. Lekeas, Giorgos Stamatopoulos

DreamWorks Animation, Glendale, USA · Department of Economics, University of Crete2026 Rethymno, Crete, Greece

Nash Equilibrium Game Theory LLM Interpretability Causal Interventions in Language Models Multi-Agent LLMs Nash Equilibrium Computation

Apr 28, 2026cs.AI

StratFormer: Adaptive Opponent Modeling and Exploitation in Imperfect-Information Games

We present StratFormer, a transformer-based meta-agent that learns to simultaneously model and exploit opponents in imperfect-information games through a two-phase curriculum. The first phase trains an opponent modeling head to identify behavioral patterns from action histories while the agent plays a game-theoretic optimal (GTO) policy. The second phase progressively shifts the policy toward best-response (BR) exploitation, guided by a per-opponent regularization schedule tied to exploitability. Our architecture introduces dual-turn tokens -- feature vectors constructed at both agent and opponent decision points -- coupled with bucket-rate features that encode opponent tendencies across five strategic contexts. On Leduc Hold'em, a small poker variant with six cards and two betting rounds, we test against six opponent archetypes at two strength levels each, with exploitability ranging from 0.15 to 1.26 Big Blinds (BB) per hand. StratFormer achieves an average exploitation gain of +0.106 BB per hand over GTO, with peak gains of +0.821 against highly exploitable opponents, while maintaining near-equilibrium safety.

Andy Caen, Mark H. M. Winands, Dennis J. N. J. Soemers

Department of Advanced Computing Sciences, Maastricht University, Maastricht, The Netherlands

Opponent Modeling Game-Playing Agents Transformer Imperfect-Information Games Game Theory Multi-Agent Reasoning

Apr 28, 2026cs.GT

Optimally Auditing Adversarial Agents

Fraud can pose a challenge in many resource allocation domains, including social service delivery and credit provision. For example, agents may misreport private information in order to gain benefits or access to credit. To mitigate this, a principal can design strategic audits to verify claims and penalize misreporting. In this paper, we introduce a general model of audit policy design as a principal-agent game with multiple agents, where the principal commits to an audit policy, and agents collectively choose an equilibrium that minimizes the principal's utility. We examine both adaptive and non-adaptive settings, depending on whether the principal's policy can be responsive to the distribution of agent reports. Our work provides efficient algorithms for computing optimal audit policies in both settings and extends these results to a setting with limited audit budgets.

Sanmay Das, Fang-Yi Yu, Yuang Zhang

Virginia Tech · George Mason University

Algorithmic Auditing Game Theory

Apr 27, 2026cs.GT

Asymmetric-Information Resource Allocation Games: An LP Approach to Purposeful Deception

In this work, we introduce the Deceptive Resource Allocation Game (DRAG), which studies purposeful deception within a Bayesian game framework. In DRAG, a Defender allocates resources across the true asset and several decoys to influence an Attacker's beliefs and actions, with the goal of diverting the Attacker away from the true asset. We seek to characterize purposeful deception, whereby the Defender deceives only when doing so improves its performance. To this end, we solve for the Perfect Bayesian Nash Equilibrium (PBNE) of the corresponding game. We show that, despite the coupled belief-policy interdependence, the problem admits an efficient, non-iterative linear programming formulation. Numerical results demonstrate that the resulting policies naturally balance effective allocation and belief manipulation, giving rise to purposeful and emergent deceptive behaviors.

Longxu Pan, Yue Guan, Daigo Shishika +1

School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, GA, USA · College of Engineering and Computing, George Mason University, Fairfax, VA, USA

Imperfect-Information Games Game Theory Linear Programming Nash Equilibrium Computation

Apr 23, 2026cs.GT

Mechanism Design for Decentralized Risk Detection: Strict Propriety, Network Coalitions, and the Backfiring Mandat

Competing firms that share a population of risky customers face a decentralized risk detection problem in which each firm holds fragmentary information whose aggregation would generate social value, but private incentives impede truthful sharing. We develop a dynamic mechanism design framework for this setting and identify three strategic frictions that distinguish it from classical mechanism design with decentralized information: compliance moral hazard, adversarial adaptation, and information destruction through intervention. A temporal value assignment (TVA) mechanism credits firms using a strictly proper scoring rule applied to discounted verified outcomes; under stated assumptions, TVA implements truthful posterior reporting as a Bayes--Nash equilibrium (uniquely optimal at each edge in large federations, with

O(1/m)

shading in finite systems). A network Shapley characterization shows that under edge-additive coalition value, each firm's marginal contribution is proportional to its weighted cross-firm interaction degree, yielding a sharp prescription for coalition design that prioritizes inter-firm volume over firm size. Embedding TVA in a model of competition among firms, we establish a welfare ordering across four regulatory regimes (autarky, voluntary federation, mandated full sharing, TVA) and identify conditions under which information-sharing mandates without compatible incentive design reduce welfare below autarky: a ``backfiring mandate.'' We illustrate the framework on a 1.4M-transaction synthetic anti-money-laundering benchmark; the same machinery extends to platform fraud, cybersecurity threat intelligence, and supply chain risk detection.

Jian Ni, Lecheng Zheng, John R Birge

Pamplin College of Business, Virginia Tech · Booth School of Business, University of Chicago

Mechanism Design Game Theory

Apr 23, 2026cs.CR

Strategic Heterogeneous Multi-Agent Architecture for Cost-Effective Code Vulnerability Detection

Automated code vulnerability detection is critical for software security, yet existing approaches face a fundamental trade-off between detection accuracy and computational cost. We propose a heterogeneous multi-agent architecture inspired by game-theoretic principles, combining cloud-based LLM experts with a local lightweight verifier. Our "3+1" architecture deploys three cloud-based expert agents (DeepSeek-V3) that analyze code from complementary perspectives - code structure, security patterns, and debugging logic - in parallel, while a local verifier (Qwen3-8B) performs adversarial validation at zero marginal cost. We formalize this design through a two-layer game framework: (1) a cooperative game among experts capturing super-additive value from diverse perspectives, and (2) an adversarial verification game modeling quality assurance incentives. Experiments on 262 real samples from the NIST Juliet Test Suite across 14 CWE types, with balanced vulnerable and benign classes, demonstrate that our approach achieves a 77.2% F1 score with 62.9% precision and 100% recall at $0.002 per sample - outperforming both a single-expert LLM baseline (F1 71.4%) and Cppcheck static analysis (MCC 0). The adversarial verifier significantly improves precision (+10.3 percentage points, p < 1e-6, McNemar's test) by filtering false positives, while parallel execution achieves a 3.0x speedup. Our work demonstrates that game-theoretic design principles can guide effective heterogeneous multi-agent architectures for cost-sensitive software engineering tasks.

Zhaohui Geoffrey Wang

University of Southern California Los Angeles, CA, USA

Game Theory Software Vulnerability Detection LLMs for Cybersecurity Multi-Agent Coding

Apr 19, 2026cs.GT

Study and Improvement of Search Algorithms in Multi-Player Perfect-Information Games

In this article, we generalize Unbounded Minimax, the state-of-the-art search algorithm for zero sums two-player games with perfect information to the framework of multiplayer games with perfect information. We experimentally show that this generalized algorithm also achieves better performance than the main multiplayer search algorithms.

Quentin Cohen-Solal

LAMSADE, Universit´e Paris-Dauphine, PSL, CNRS, Paris, France

Game-Playing Agents Tree Search Game Theory

Apr 18, 2026cs.GT

From Necklaces to Coalitions: Fair and Self-Interested Distribution of Coalition Value Calculations

A key challenge in distributed coalition formation within characteristic function games is determining how to allocate the calculation of coalition values across a set of agents. The number of possible coalitions grows exponentially with the number of agents, and existing distributed approaches may produce uneven or redundant allocations, or assign coalitions to agents that are not themselves members. In this article, we present the \emph{Necklace-based Distributed Coalition Algorithm} (N-DCA), a communication-free algorithm in which each agent independently determines its own coalition value calculation allocation using only its identifier and the total number of agents. The approach builds on the notion of Increment Arrays (IAs), for which we develop a complete mathematical framework: equivalence classes under circular shifts, periodic IAs, and a rotated designation scheme with formal load-balance guarantees (tight bounds). We establish a bijection between canonical representative IAs and two-colour combinatorial necklaces, enabling the use of efficient necklace generation algorithms to enumerate allocations in constant amortised time. N-DCA is, to the best of our knowledge, the only distributed coalition value calculation algorithm for unrestricted characteristic function games to provably satisfy five desirable properties: no inter-agent communication, equitable allocation, no redundancy, balanced load, and self-interest. An empirical evaluation against DCVC (Rahwan and Jennings 2007) demonstrates that, although DCVC is faster by a constant factor, this difference becomes negligible under realistic characteristic-function evaluation costs, while N-DCA offers advantages in working memory, scalability, and the self-interest guarantee.

Terry R. Payne, Luke Riley

School of Computer Science and Informatics, University of Liverpool, Liverpool, UK. · Quant, London, UK.

Cooperative Game Theory Multi-Agent Coordination Game Theory Fair Resource Allocation Combinatorial Optimization

Apr 17, 2026cs.LG

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback

We study the problem of learning in zero-sum matrix games with repeated play and bandit feedback. Specifically, we focus on developing uncoupled algorithms that guarantee, without communication between players, the convergence of the last-iterate to a Nash equilibrium. Although the non-bandit case has been studied extensively, this setting has only been explored recently, with a bound of

\mathcal{O}(T^{-1/8})

on the exploitability gap. We show that, for uncoupled algorithms, guaranteeing convergence of the policy profiles to a Nash equilibrium is detrimental to the performance, with the best attainable rate being

Ω(T^{-1/4})

in contrast to the usual

Ω(T^{-1/2})

rate for convergence of the average iterates. We then propose two algorithms that achieve this optimal rate up to constant and logarithmic factors. The first algorithm leverages a straightforward trade-off between exploration and exploitation, while the second employs a regularization technique based on a two-step mirror descent approach.

Côme Fiegel, Pierre Ménard, Tadashi Kozuno +2

ENSAE Paris - CREST, Palaiseau, France · Inria - FairPlay · ENS Lyon, Lyon, France +3

Nash Equilibrium Last-Iterate Convergence Game Theory Zero-Sum Games Convergence Analysis Mirror Descent+1

Apr 17, 2026cs.GT

The Price of Paranoia: Robust Risk-Sensitive Cooperation in Non-Stationary Multi-Agent Reinforcement Learning

Cooperative equilibria are fragile. When agents learn alongside each other rather than in a fixed environment, the process of learning destabilizes the cooperation they are trying to sustain: every gradient step an agent takes shifts the distribution of actions its partner will play, turning a cooperative partner into a source of stochastic noise precisely where the cooperation decision is most sensitive. We study how this co-learning noise propagates through the structure of coordination games, and find that the cooperative equilibrium, even when strongly Pareto-dominant, is exponentially unstable under standard risk-neutral learning, collapsing irreversibly once partner noise crosses the game's critical cooperation threshold. The natural response to apply distributional robustness to hedge against partner uncertainty makes things strictly worse: risk-averse return objectives penalize the high-variance cooperative action relative to defection, widening the instability region rather than shrinking it, a paradox that reveals a fundamental mismatch between the domains where robustness is applied and instability originates. We resolve this by showing that robustness should target the policy gradient update variance induced by partner uncertainty, not the return distribution. This distinction yields an algorithm whose gradient updates are modulated by an online measure of partner unpredictability, provably expanding the cooperation basin in symmetric coordination games. To unify stability, sample complexity, and welfare consequences of this approach, we introduce the Price of Paranoia as the structural dual of the Price of Anarchy. Together with a novel Cooperation Window, it precisely characterizes how much welfare learning algorithms can recover under partner noise, pinning down the optimal degree of robustness as a closed-form balance between equilibrium stability and sample efficiency.

Deep Kumar Ganguly, Chandradithya S Jonnalagadda, Pratham Chintamani +1

Technical University of Munich (TU Munich) · Brown University · Indian Institute of Technology Tirupati (IIT Tirupati)

Cooperative Game Theory Multi-Agent Coordination Non-Stationary RL Game Theory Risk-Sensitive RL Robust RL+2

Apr 16, 2026cs.GT

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

It is increasingly important that LLM agents interact effectively and safely with other goal-pursuing agents, yet, recent works report the opposite trend: LLMs with stronger reasoning capabilities behave less cooperatively in mixed-motive games such as the prisoner's dilemma and public goods settings. Indeed, our experiments show that recent models -- with or without reasoning enabled -- consistently defect in single-shot social dilemmas. To tackle this safety concern, we present the first comparative study of game-theoretic mechanisms designed to enable cooperative outcomes between rational agents in equilibrium. Across four social dilemmas testing distinct components of robust cooperation, we evaluate four families of mechanisms: (1) repeating the game for many rounds, (2) reputation systems, (3) third-party mediators to delegate decision making to, and (4) contract agreements for outcome-conditional payments between players. Among our findings, we establish that contracting and mediation are most effective in achieving cooperative outcomes between capable LLM models, and that repetition-induced cooperation deteriorates drastically when co-players vary. Moreover, we demonstrate that the mechanisms become more effective under evolutionary pressures to maximize individual payoffs.

Emanuel Tewolde, Xiao Zhang, David Guzman Piedrahita +2

Carnegie Mellon University · Foundations of Cooperative AI Lab (FOCAL) · Jinesis Lab, University of Toronto & Vector Institute +3

Social Dilemmas Cooperative Game Theory Multi-Agent Coordination Mechanism Design Game Theory LLM Agent Evaluation+1

Apr 16, 2026cs.LG

Optimal last-iterate convergence in matrix games with bandit feedback using the log-barrier

We study the problem of learning minimax policies in zero-sum matrix games. Fiegel et al. (2025) recently showed that achieving last-iterate convergence in this setting is harder when the players are uncoupled, by proving a lower bound on the exploitability gap of Omega(t^{-1/4}). Some online mirror descent algorithms were proposed in the literature for this problem, but none have truly attained this rate yet. We show that the use of a log-barrier regularization, along with a dual-focused analysis, allows this O-tilde(t^{-1/4}) convergence with high-probability. We additionally extend our idea to the setting of extensive-form games, proving a bound with the same rate.

Come Fiegel, Pierre Menard, Tadashi Kozuno +2

ENSAE Paris – CREST, France · ENS Lyon, France · Isara Labs +2

Last-Iterate Convergence Imperfect-Information Games Game Theory Zero-Sum Games Min-Max Optimization Convergence Analysis

Mar 19, 2026cs.GT

Evolutionarily Stable Stackelberg Equilibrium

We present a new solution concept called evolutionarily stable Stackelberg equilibrium (SESS). We study the Stackelberg evolutionary game setting in which there is a single leading player and a symmetric population of followers. The leader selects an optimal mixed strategy, anticipating that the follower population plays an evolutionarily stable strategy (ESS) in the induced subgame and may satisfy additional ecological conditions. We consider both leader-optimal and leader-pessimal selection among ESSs, which arise as special cases of our framework. Prior approaches to Stackelberg evolutionary games either define the follower response via evolutionary dynamics or assume rational best-response behavior, without explicitly enforcing stability against invasion by mutations. We present algorithms for computing SESS in discrete and continuous games, and validate the latter empirically. Our model applies naturally to biological settings; for example, in cancer treatment the leader represents the physician and the followers correspond to competing cancer cell phenotypes.

Sam Ganzfried

Ganzfried Research, Cornell University

Game Theory Stackelberg Games Evolutionary Game Theory

Feb 27, 2026cs.AI

Conservative Equilibrium Discovery in Offline Game-Theoretic Multiagent Reinforcement Learning

Offline learning of strategies takes data efficiency to its extreme by restricting algorithms to a fixed dataset of state-action trajectories. We consider the problem in a mixed-motive multiagent setting, where the goal is to solve a game under the offline learning constraint. We first frame this problem in terms of selecting among candidate equilibria. Since datasets may inform only a small fraction of game dynamics, it is generally infeasible in offline game-solving to even verify a proposed solution is a true equilibrium. Therefore, we consider the relative probability of low regret (i.e., closeness to equilibrium) across candidates based on the information available. Specifically, we extend Policy Space Response Oracles (PSRO), an online game-solving approach, by quantifying game dynamics uncertainty and modifying the RL objective to skew towards solutions more likely to have low regret in the true game. We further propose a novel meta-strategy solver, tailored for the offline setting, to guide strategy exploration in PSRO. Our incorporation of Conservatism principles from Offline reinforcement learning approaches for strategy Exploration gives our approach its name: COffeE-PSRO. Experiments demonstrate COffeE-PSRO's ability to extract lower-regret solutions than state-of-the-art offline approaches and reveal relationships between algorithmic components empirical game fidelity, and overall performance.

Austin A. Nguyen, Michael P. Wellman

University of Michigan

Reinforcement Learning Game Theory Offline RL Multi-Agent Reinforcement Learning

Feb 26, 2026cs.LG

Multi-agent imitation learning with function approximation: Linear Markov games and beyond

In this work, we present the first theoretical analysis of multi-agent imitation learning (MAIL) in linear Markov games where both the transition dynamics and each agent's reward function are linear in some given features. We demonstrate that by leveraging this structure, it is possible to replace the state-action level "all policy deviation concentrability coefficient" (Freihaut et al., arXiv:2510.09325) with a concentrability coefficient defined at the feature level which can be much smaller than the state-action analog when the features are informative about states' similarity. Furthermore, to circumvent the need for any concentrability coefficient, we turn to the interactive setting. We provide the first, computationally efficient, interactive MAIL algorithm for linear Markov games and show that its sample complexity depends only on the dimension of the feature map

d

. Building on these theoretical findings, we propose a deep MAIL interactive algorithm which clearly outperforms BC on games such as Tic-Tac-Toe and Connect4.

Luca Viano, Till Freihaut, Emanuele Nevali +3

1EPFL · University of Zurich · 3Earth Species Project

Game Theory Imitation Learning Interactive Imitation Learning Policy Learning Linear Function Approximation

Feb 18, 2026cs.MA

Evaluating Collective Behaviour of Hundreds of LLM Agents

LLM-powered AI assistants acting on behalf of users can produce poor collective outcomes at scale. We introduce a framework for evaluating their emergent behaviour in social dilemmas, applied to three iterated games (Public Goods, Collective Risk, Common Pool Resource). We prompt each model to produce a natural-language strategy, then have the same model translate it into code. This aims to isolate strategic reasoning from input-parsing, enables pre-deployment inspection, and scales to populations of hundreds of agents. We propose three analyses: behavioural fingerprinting via exhaustive evaluation over opponent histories; self-play robustness across mixtures of a model's strategies with either a Selfish or Collective disposition; and cultural evolution under payoff-biased imitation. Applied to three state-of-the-art LLMs, we find substantial cross-model differences in self-play welfare, and that cultural evolution converges to low-welfare, Selfish-dominant equilibria in larger groups.

Richard Willis, Jianing Zhao, Yali Du +1

King’s College London London, United Kingdom · King’s College London · Turing Institute +1

Social Dilemmas Multi-Agent LLM Systems Cultural Evolution Game Theory LLM Agent Evaluation Large Language Model-Based Social Simulation+1

Feb 2, 2026cs.LG

Local exponential stability of mean-field Langevin descent-ascent and associated particle system

We study the mean-field Langevin descent-ascent (MFL-DA), a coupled optimization dynamics on the space of probability measures for entropically regularized two-player zero-sum games, together with its associated interacting particle system. For general nonconvex-nonconcave payoffs, Wang and Chizat (COLT 2024) asked whether the original single-timescale MFL-DA converges to the mixed Nash equilibrium and, if so, at what rate. We prove a local affirmative answer in Wasserstein space: if the initial datum is sufficiently close to the mixed Nash equilibrium, then the mean-field dynamics converges to it exponentially fast at a quantitative rate. We further show that the finite-

N

particle system inherits this stability up to times exponential in

N

, with an

N

-independent exponential rate modulo a finite-particle error floor. Combined with the recent counterexample of Mourrat and Pillaud-Vivien for MFL-DA, which shows that global convergence cannot hold in general, our theorem completes the positive local counterpart of the Wang-Chizat question: the mixed Nash equilibrium has a robust basin of attraction, stable under both the mean-field flow and its finite-particle approximation.

Geuntaek Seo, Minseop Shin, Pierre Monmarché +1

Nash Equilibrium Lyapunov Stability Game Theory Wasserstein Gradient Flows Zero-Sum Games Mean-Field Theory+1

Dec 11, 2025cs.GT

Computing Evolutionarily Stable Strategies in Imperfect-Information Games

We present an algorithm for computing evolutionarily stable strategies (ESSs) in symmetric perfect-recall extensive-form games of imperfect information. Our main algorithm is for two-player games, and we describe how it can be extended to multiplayer games. The algorithm is sound and computes all ESSs in nondegenerate games and a subset of them in degenerate games which contain an infinite continuum of symmetric Nash equilibria. The algorithm is anytime and can be stopped early to find one or more ESSs. We experiment on an imperfect-information cancer signaling game as well as random games to demonstrate scalability.

Sam Ganzfried

Ganzfried Research, Cornell University · Cornell University

Imperfect-Information Games Game Theory Evolutionary Game Theory

Nov 25, 2025cs.GT

Computing Evolutionarily Stable Strategies in Multiplayer Games

We present an algorithm for computing all evolutionarily stable strategies in nondegenerate normal-form games with three or more players.

Sam Ganzfried

Ganzfried Research, Cornell University

Game Theory Evolutionary Game Theory

Nov 12, 2025cs.GT

Steering Noncooperative Games Through Conjecture Design

In dynamic noncooperative games, each player makes conjectures about other players' reactions before choosing a strategy. However, resulting equilibria may be multiple and do not always lead to desirable outcomes. These issues are typically addressed separately, for example, through opponent modelling and incentive design. Drawing inspiration from conjectural variations games, we propose an incentive design framework in which a coordinator first computes an equilibrium by optimizing a predefined objective function, then communicates this equilibrium as a target for the players to reach. In a centralized setting, the coordinator also optimizes the conjectures to steer the players towards the target. In decentralized settings, players independently compute conjectures and update their strategies based on individual targets. We provide a guarantee of equilibrium existence in both cases. This framework uses conjectures not only to guide the system towards desirable outcomes but also to decouple the game into independent optimization problems, enabling efficient computation and parallelization in large-scale settings. We illustrate our theoretical results on classical representative noncooperative games, demonstrating its application potential.

Francesco Morri, Hélène Le Cadre, David Salas +1

Inria, Univ. Lille CNRS, Centrale Lille · Instituto de Ciencias de la Ingeniería Universidad de O’Higgins · Laboratoire PROMESUPR 8521 Université de Perpignan, Tecnosud

Mechanism Design Game Theory

Nov 6, 2025cs.AI

Large language models replicate and predict human cooperation across experiments in game theory

Large language models (LLMs) are increasingly deployed as decision-making agents in high-stakes domains and as imitators of human behavior in the social and behavioral sciences. Yet how closely LLMs mirror human decision-making remains poorly understood. This gap is critical: misalignment could produce harmful outcomes in practice, while failure to replicate human behavior renders LLMs ineffective as social simulators. Here, we address this gap by replicating large-scale game-theoretic experiments and by introducing a systematic prompting and probing framework for machine-behavioral evaluation. We test three open models typically used to power agents (Llama, Mistral, and Qwen). Across 121 dyadic games spanning four classical game types, Llama reproduces human cooperation patterns with high fidelity, while Qwen aligns closely with Nash equilibrium predictions. Characterizing models through behavioral phenotyping, we find that humans and Llama share an envious decision profile, while Qwen and Mistral exhibit different profiles. An attention-based analysis of payoff salience reveals Llama processes payoff information in a structured, layer-dependent manner absent in Qwen and Mistral, suggesting a mechanistic basis for its closer alignment with human behavior. Population-level behavioral replication is achieved without persona-based prompting, simplifying the simulation process. Extending the experimental parameter space beyond the original human-tested games, we generate and preregister testable hypotheses for novel game configurations. Our findings demonstrate appropriately configured LLMs can replicate aggregate human behavioral patterns, exhibit human-like decision phenotypes, and enable systematic exploration of unexplored experimental spaces, offering a complementary approach to traditional behavioral research that generates new empirical predictions about human social decision-making.

Andrea Cera Palatsi, Samuel Martin-Gutierrez, Ana S. Cardenal +1

Department for Computational Social Sciences and Humanities, Barcelona Supercomputing Center · Grupo de Sistemas Complejos, Universidad Polit´ecnica de Madrid · School of Law and Political Science, Universitat Oberta de Catalunya +1

LLM Evaluation Game Theory Human Behavior Simulation Large Language Model-Based Social Simulation

Oct 16, 2025cs.GT

Learnable Mixed Nash Equilibria are Collectively Rational

We extend the study of learning in games to dynamics that exhibit non-asymptotic stability. We do so through the notion of uniform stability, which is concerned with equilibria of individually utility-seeking dynamics. Perhaps surprisingly, it turns out to be closely connected to economic properties of collective rationality. Up to strategic equivalence, if a mixed equilibrium is uniformly stable, then it is weakly Pareto optimal; there is no way for all players to improve by jointly deviating from the equilibrium. This is a form of collective rationality that rules out the types of behaviors in the prisoner's dilemma or the tragedy of the commons. Moreover, we show that uniform stability determines the last-iterate convergence behavior for the family of incremental smoothed best-response dynamics, used to model individual and corporate behaviors in the markets. Unlike dynamics around strict equilibria, which can stabilize to socially-inefficient solutions, individually utility-seeking behaviors near mixed Nash equilibria lead to collective rationality.

Geelon So, Yi-An Ma

University of California, San Diego

Nash Equilibrium Algorithmic Stability Game Theory

Oct 15, 2025cs.CL

Make an Offer They Can't Refuse: Grounding Bayesian Persuasion in Real-World Dialogues without Pre-Commitment

Large language models (LLMs) still struggle with strategic persuasion, largely because existing approaches either neglect information asymmetry or rely on unrealistic pre-commitment assumptions. We introduce a type-induced commitment-communication mechanism that grounds Bayesian Persuasion (BP) in natural language dialogue without pre-commitment: the persuader narrates their potential types (e.g., honest vs. dishonest) to dynamically construct an information schema, enabling the persuadee to perform Bayesian belief updates within the conversation itself. We implement two variants: Semi-Formal-Natural-Language (SFNL) and Fully-Natural-Language (FNL), evaluating them against strong baselines across multiple LLMs and human judges. BP strategies consistently outperform baselines: SFNL excels in logical credibility, while FNL shows superior robustness and emotional resonance. We verify that gains stem from genuine Bayesian reasoning rather than superficial formatting, and we further show that supervised fine-tuning enables small models to match the persuasive performance of much larger ones.

Buwei He, Yang Liu, Zhaowei Zhang +6

Beijing University of Posts and Telecommunications · Beijing Institute for General Artificial Intelligence · Peking University +1

Game Theory LLM Decision-Making Persuasion in Language Models LLM Reasoning

Sep 30, 2025cs.GT

Quadratic Programming Approach for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games

There has been significant recent progress in algorithms for approximation of Nash equilibrium in large two-player zero-sum imperfect-information games and exact computation of Nash equilibrium in multiplayer strategic-form games. While counterfactual regret minimization and fictitious play are scalable to large games and have convergence guarantees in two-player zero-sum games, they do not guarantee convergence to Nash equilibrium in multiplayer games. We present an approach for exact computation of Nash equilibrium in multiplayer imperfect-information games that solves a quadratically-constrained program based on a nonlinear complementarity problem formulation from the sequence-form game representation. This approach capitalizes on recent advances for solving nonconvex quadratic programs. Our algorithm is able to quickly solve three-player Kuhn poker after removal of dominated actions. Of the available algorithms in the Gambit software suite, only the logit quantal response approach is successfully able to solve the game; however, the approach takes longer than our algorithm and also involves a degree of approximation. Our formulation also leads to a new approach for computing Nash equilibrium in multiplayer strategic-form games which we demonstrate to outperform a previous quadratically-constrained program formulation.

Sam Ganzfried

Ganzfried Research

Nash Equilibrium Imperfect-Information Games Game Theory Quadratic Programming Nash Equilibrium Computation

Aug 5, 2025cs.MA

Distributionally Robust Markov Games with Average Reward

We propose and study distributionally robust Markov games (DR-MGs) with the average-reward criterion as a crucial framework for multi-agent decision-making under model mismatches and over extended horizons. Under a standard irreducible assumption, we first derive a correspondence between the optimal policies and the solutions of the robust Bellman equation, based on which we further show the existence of a stationary Nash Equilibrium (NE) of the game. We further study DR-MGs under a more general weakly communicating setting. We construct a set-valued map based on the constant-gain optimal robust Bellman operator and show that its value is a subset of the best-response policies. We further prove that this map admits a fixed point, which implies the existence of NE. We then design two algorithms, Robust Nash-Iteration and robust TD Descent, with provably convergent guarantees. Finally, we show that the NE under average-reward can be approximated by the ones for the discounted DR-MGs as the discount factor approaches one. Our studies provide a comprehensive theoretical and algorithmic foundation for decision-making in complex, uncertain, and long-running multi-player environments.

Zachary Roch, Yue Wang

Department of Electrical and Computer Engineering, University of Central Florida, Orlando, Florida, USA. · Department of Computer Science, University of Central Florida, Orlando, Florida, USA.

Nash Equilibrium Multi-Agent System Optimization Reinforcement Learning Average-Reward RL Game Theory Distributionally Robust Optimization+4

Jul 22, 2025physics.soc-ph

Unbeatable imitation of a friend

Imitation sometimes achieves success in multi-agent situations even though it is very simple. In repeated games, success of imitation has been characterized by unbeatability against other agents. Previous studies specified conditions under which imitation is unbeatable against co-players in repeated symmetric games, and clarified that the existence of unbeatable imitation is strongly related to the existence of payoff-controlling strategies, called zero-determinant strategies. However, these results were on the situations in which one repeated game is played by one group of players. It was pointed out that imitation of other players in the same group and imitation of other players in the same role in other groups generally result in different outcomes. Here, we investigate the existence condition of unbeatable imitation in the latter situations, described by two concurrent repeated games played by two different groups of players. We find that the existence condition of unbeatable imitation is stronger than the existence condition of unbeatable zero-determinant strategies, whereas both are very limited. Furthermore, we also find that adding exploration can make an imitation strategy unbeatable even in games where imitation without exploration can be beaten. Our findings suggest a strong relation between unbeatable imitation and payoff control even in the two concurrent repeated game situations.

Masahiko Ueda

Graduate School of Sciences and Technology for Innovation, Yamaguchi University, 1677-1, Yoshida, Yamaguchi, 753-8511, Japan.

Game-Playing Agents Game Theory Repeated Games Evolutionary Game Theory

Jul 13, 2025cs.GT

Efficiency, Feasibility, and Incentive-Awareness in Constrained Online Resource Allocation

We study the dynamic allocation of indivisible resources to strategic agents under long-term constraints, where the planner aims to maximize social welfare, satisfy multiple constraints, and elicit near-truthful reports. We find standard primal-dual methods fragile in this setting: agents easily manipulate their reports to distort dual variables, sacrificing social efficiency for individual utility. To address this, we propose the Incentive-Aware Primal-Dual (IAPD) framework. On the primal side, we integrate three components to suppress manipulation: a VCG-based payment neutralizes immediate misreporting benefits, while epoch-based lazy updates and random exploration together ensure potential future gains are outweighed by immediate penalties. On the dual side, to overcome a learning barrier due to lazy updates -- which we call the "price of incentives" -- we design a novel optimistic online learning algorithm, O-FTRL-FP. It utilizes a fixed-point oracle to resolve the circular dependency between optimistic dual variables and the resulting allocations. Ultimately, our mechanism attains

\tilde{\mathcal O}(\sqrt T)

social welfare regret, satisfies all long-term constraints, and induces a near-truthful equilibrium. It also smoothly generalizes to multi-unit multi-demand allocation problems. Notably, this

\tilde{\mathcal O}(\sqrt T)

regret near-matches the non-strategic

Ω(\sqrt T)

lower bound, demonstrating that incentive-awareness can be accommodated at nearly no cost.

Yan Dai, Negin Golrezaei, Patrick Jaillet

Operations Research Center, MIT. · Sloan School of Management, MIT. · Department of EECS, MIT.

Primal-Dual Optimization Online Convex Optimization Mechanism Design Game Theory Constrained Optimization Online Resource Allocation

May 19, 2025cs.GT

Non-Obvious Manipulability in Additively Separable and Fractional Hedonic Games

Hedonic Games are a well-established model for describing the formation of coalitions. In this work, we considered the design of Non-Obviously Manipulable (NOM) mechanisms, that are mechanisms that bounded rational agents may fail to recognize as manipulable, for two relevant classes of succinctly representable Hedonic Games, namely Additively Separable and Fractional Hedonic Games. In these classes, agents have cardinal scores towards other agents, and their preferences towards different coalitions are determined by aggregating these scores. Moreover, the quality of an outcome can also be easily evaluated through these scores by means of the utilitarian social welfare. We first prove that, when scores can be arbitrary, every welfare-maximizing mechanism is NOM, and, when scores are limited in a continuous interval, then there exist tie-breaking rules making welfare-maximizing mechanisms NOM. Next, we focus on efficient NOM mechanisms, since there is no known polynomial-time algorithm to compute welfare-maximizing outcomes in the considered classes of hedonic games. To this aim, we first prove a characterization of NOM mechanisms that simplifies the class of mechanisms of interest. Then, we design a NOM mechanism returning approximations that essentially match the best-known approximation achievable in polynomial time. Finally, we turn our attention to discrete scores, and specifically, the case that scores are

\{-x, 0, 1\}

for

x > 0

. We prove that the ability to design welfare-maximizing NOM mechanisms depends on the magnitude of the scores. In particular, for

x > 1

, we prove that a welfare-maximizing NOM mechanism exists only when

x

is very large. For

x \leq 1

, instead, we observe that a welfare-maximizing NOM mechanism always exists except when

x

lies in the interval

[a, b]

where

a \approx 2/n^2

and

b \approx 1/n

.

Diodato Ferraioli, Maria Fomenko, Giovanna Varricchio

University of Salerno, Italy · University of Calabria, Italy

Cooperative Game Theory Mechanism Design Game Theory