Game Theory

Follow this topic Ask about this topic

Game theory models situations where each participant’s outcome depends on the choices of others, using concepts such as Nash, correlated, and evolutionary equilibria. Researchers analyze when these solutions exist and are efficient, design auctions and incentives, and develop learning methods including best-response dynamics, regret minimization, and multi-agent reinforcement learning. Applications range from routing, resource allocation, and security to bargaining and interactions among language-model agents. A central challenge is that equilibrium guarantees can be hard to compute and may not predict which outcomes real or learning agents reach, or whether those outcomes are fair and socially beneficial.

Latest papers

240 papers27 papers in the last four weeks, down 13% on the four weeks before. 0.2% of all new papers.

Apr 3, 2026

A Network Formation Game for Katz Centrality Maximization: A Resource Allocation Perspective

In this paper, we study a network formation game in which agents seek to maximize their influence by allocating constrained resources to connections with other agents. We use Katz centrality to model agents' influence in the network. Allocations are restricted to neighbors in a given unweighted network, encoding topological constraints. The allocation by each agent determines the weights of its outgoing edges, and the allocations of all agents thereby induce a network. This defines a strategic-form game in which agents' utilities are given by their Katz centralities. We characterize the Nash equilibrium networks of this game and analyze their properties. We propose a sequential Best Response Dynamics (BRD) to model the network formation process and show that it converges to the set of Nash equilibria under bounded budgets and the assumption that every agent takes a best response infinitely often. For complete underlying topologies, we show that Katz centralities are proportional to agents' budgets at Nash equilibria. For general underlying topologies in which each agent has a self-loop, we show that hierarchical networks form at Nash equilibria. Finally, simulations illustrate our findings.

Balaji R, Prashil Wankhede, Pavankumar Tallapragada

Indian Institute of Science, Bengaluru, India.

Game Theory Nash Equilibrium

Apr 1, 2026

On rankings in multiplayer games with an application to the game of Whist

We propose a novel extension of the Bradley-Terry model to multiplayer games and adapt a recent algorithm by Newman [1] to our model. We demonstrate the use of our proposed method on synthetic datasets and on a real dataset of games of cards.

Alexis Coyette, Charles Modera, Candy Sonveaux +14

Department of Mathematics, Naxys, Unamur, Belgium · Department of Physics and Astronomy, CSDC, University of Florence, Italy

Bradley–Terry Model Game Theory

Apr 1, 2026

Internal State-Based Policy Gradient Methods for Partially Observable Markov Potential Games

This letter studies multi-agent reinforcement learning in partially observable Markov potential games. Solving this problem is challenging due to partial observability, decentralized information, and the curse of dimensionality. First, to address the first two challenges, we leverage the common information framework, which allows agents to act based on both shared and local information. Second, to ensure tractability, we study an internal state that compresses accumulated information, preventing it from growing unboundedly over time. We then implement an internal state-based natural policy gradient method to find Nash equilibria of the Markov potential game. Our main contribution is to establish a non-asymptotic convergence bound for this method. Our theoretical bound decomposes into two interpretable components: a statistical error term that also arises in standard Markov potential games, and an approximation error capturing the use of finite-state controllers. Finally, simulations across multiple partially observable environments demonstrate that the proposed method using finite-state controllers achieves consistent improvements in performance compared to the setting where only the current observation is used.

Wonseok Yang, Thinh T. Doan

University of Texas at Austin, Austin, TX, 78712 USA

Natural Policy Gradient Multi-Agent Reinforcement Learning Partially Observable Stochastic Games Policy Gradient Game Theory Partially Observable Markov Decision Processes

Mar 29, 2026

Computational Foundations for Strategic Coopetition: Formalizing Sequential Interaction and Reciprocity

Strategic coopetition in multi-stakeholder systems requires understanding how cooperation persists through time without binding contracts. This technical report extends computational foundations for strategic coopetition to sequential interaction dynamics, bridging conceptual modeling (i* framework) with game-theoretic reciprocity analysis. We develop: (1) bounded reciprocity response functions mapping partner deviations to finite conditional responses, (2) memory-windowed history tracking capturing cognitive limitations over k recent periods, (3) structural reciprocity sensitivity derived from interdependence matrices where behavioral responses are amplified by structural dependencies, and (4) trust-gated reciprocity where trust modulates reciprocity responses. The framework applies to both human stakeholder interactions and multi-agent computational systems. Comprehensive validation across 15,625 parameter configurations demonstrates robust reciprocity effects, with all six behavioral targets exceeding thresholds: cooperation emergence (97.5%), defection punishment (100%), forgiveness dynamics (87.9%), asymmetric differentiation (100%), trust-reciprocity interaction (100%), and bounded responses (100%). Empirical validation using the Apple iOS App Store ecosystem (2008-2024) achieves 43/51 applicable points (84.3%), reproducing documented cooperation patterns across five ecosystem phases. Statistical significance confirmed at p < 0.001 with Cohen's d = 1.57. This report concludes the Foundations Series (TR-1 through TR-4) adopting uniaxial treatment where agents choose cooperation levels along a single continuum. Companion work on interdependence (arXiv:2510.18802), trust (arXiv:2510.24909), and collective action (arXiv:2601.16237) has been prepublished. Extensions Series (TR-5 through TR-8) introduces biaxial treatment where cooperation and competition are independent dimensions.

Vik Pant, Eric Yu

Faculty of Information, University of Toronto, 140 St George St, Toronto, ON M5S 3G6, Canada

Repeated Games Game Theory

Mar 28, 2026

A Controllability Perspective on Steering Follow-the-Regularized-Leader Learners in Games

Follow-the-regularized-leader (FTRL) algorithms have become popular in the context of games, providing easy-to-implement methods for each agent, as well as theoretical guarantees that the strategies of all agents will converge to some equilibrium concept (provided that all agents follow the appropriate dynamics). However, with these methods, each agent ignores the coupling in the game, and treats their payoff vectors as exogenously given. In this paper, we take the perspective of one agent (the controller) deciding their mixed strategies in a finite game, while one or more other agents update their mixed strategies according to continuous-time FTRL. Viewing the learners' dynamics as a nonlinear control system evolving on the relative interior of a simplex or product of simplices, we ask when the controller can steer the learners to a target state, using only its own mixed strategy and without modifying the game's payoff structure. For the two-player case we provide a necessary and sufficient criterion for controllability based on the existence of a fully mixed neutralizing controller strategy and a rank condition on the projected payoff map. For multi-learner interactions we give two sufficient controllability conditions, one based on uniform neutralization and one based on a periodic-drift hypothesis together with a Lie-algebra rank condition. We illustrate these results on canonical examples such as Rock-Paper-Scissors and a construction related to Brockett's integrator.

Heling Zhang, Siqi Du, Roy Dong

Department of Electrical and Computer Engineering at Illinois Grainger Engineering, University of Illinois Urbana-Champaign. · Department of Industrial and Enterprise Systems Engineering at Illinois Grainger Engineering, University of Illinois Urbana-Champaign.

Game Theory Multi-Agent Control Follow-the-Regularized-Leader

Mar 26, 2026

Learning in Proportional Allocation Auctions Games

The Kelly or proportional allocation mechanism is a simple and efficient auction-based scheme that distributes an infinitely divisible resource proportionally to the agents bids. When agents are aware of the allocation rule, their interactions form a game extensively studied in the literature. This paper examines the less explored repeated Kelly game, focusing mainly on utilities that are logarithmic in the allocated resource fraction. We first derive this logarithmic form from fairness-throughput trade-offs in wireless network slicing, and then prove that the induced stage game admits a unique Nash equilibrium NE. For the repeated play, we prove convergence to this NE under three behavioral models: (i) all agents use Online Gradient Descent (OGD), (ii) all agents use Dual Averaging with a quadratic regularizer (DAQ) (a variant of the Follow-the-Regularized leader algorithm), and (iii) all agents play myopic best responses (BR). Our convergence results hold even when agents use personalized learning rates in OGD and DAQ (e.g., tuned to optimize individual regret bounds), and they extend to a broader class of utilities that meet a certain sufficient condition. Finally, we complement our theoretical results with extensive simulations of the repeated Kelly game under several behavioral models, comparing them in terms of convergence speed to the NE, and per-agent time-average utility. The results suggest that BR achieves the fastest convergence and the highest time-average utility, and that convergence to the stage-game NE may fail under heterogeneous update rules.

Younes Ben Mazziane, Cleque-Marlain Mboulou Moutoubi, Eitan Altman +1

LIA, Avignon university, Avignon, France · INRIA, Sophia Antipolis, France

Game Theory Online Resource Allocation Nash Equilibrium Computation

Mar 23, 2026

Strategic Infrastructure Design via Multi-Agent Congestion Games with Joint Placement and Pricing

Real-world infrastructure planning increasingly involves strategic interactions among autonomous agents competing over congestible, limited resources. Applications such as Electric Vehicle (EV) charging, emergency response, and intelligent transportation require coordinated resource placement and pricing decisions, while anticipating the adaptive behaviour of decentralised, self-interested agents. We propose a novel multi-agent framework for joint placement and pricing under such interactions, formalised as a bi-level optimisation model. The upper level represents a central planner, while the lower level captures agent responses via coupled non-atomic congestion games. Motivated by the EV charging domain, we study a setting where a central planner provisions chargers and road capacity under budget and profitability constraints. The agent population includes both EV drivers and non-charging drivers (NCDs), who respond to congestion, delays, and costs. To solve the resulting NP-hard problem, we introduce ABO-MPN, a double-layer approximation framework that decouples agent types, applies integer adjustment and rounding, and targets high-impact placement and pricing decisions. Experiments on benchmark networks show that our model reduces social cost by up to 40% compared to placement- or pricing-only baselines, and generalises to other MAS-relevant domains.

Niloofar Aminikalibar, Farzaneh Farhadi, Maria Chli

Aston University, Birmingham, UK, B4 7ET

Congestion Games Multi-Agent System Optimization Game Theory Bilevel Optimization

Mar 20, 2026

On the existence of fair zero-determinant strategies in the periodic prisoner's dilemma game

Stochastic games are a framework for investigating long-term interdependence of multi-agent systems with environmental feedback. When the number of environmental states is one, they are reduced to repeated games. In repeated games, zero-determinant (ZD) strategies attract much attention in evolutionary game theory, since they can unilaterally control payoffs. Especially, fair ZD strategies unilaterally equalize the payoff of the focal player and the average payoff of the opponents, and they were found in several games including the social dilemma games. Although the existence condition of ZD strategies in repeated games was specified, its extension to stochastic games remains largely unclear. Here, we investigate the existence condition of fair ZD strategies in the periodic prisoner's dilemma game, which is one of the simplest stochastic games. The periodic prisoner's dilemma game consists of two environmental states and the two states alternate deterministically. Whereas each stage game is not necessarily the prisoner's dilemma game, the whole game can be regarded as the prisoner's dilemma game on average. We show that fair ZD strategies do not necessarily exist in the periodic prisoner's dilemma game, in contrast to the repeated prisoner's dilemma game. Furthermore, we also prove that the Tit-for-Tat strategy, which imitates the opponent's action, is not necessarily a fair ZD strategy in the periodic prisoner's dilemma game, whereas the Tit-for-Tat strategy is always a fair ZD strategy in the repeated prisoner's dilemma game. Our results highlight difference between ZD strategies in the periodic prisoner's dilemma game and those in the standard repeated prisoner's dilemma game.

Ken Nakamura, Masahiko Ueda

Graduate School of Sciences and Technology for Innovation, Yamaguchi University, Yamaguchi 753-8512, Japan · Department of Physics, Tokyo Metropolitan University, Tokyo 192-0397, Japan

Game Theory Repeated Games

Mar 19, 2026

Interleaved Information Structures in Dynamic Games: A General Framework with Application to the Linear-Quadratic Case

A fundamental problem in noncooperative dynamic game theory is the computation of Nash equilibria under different information structures, which specify the information available to each agent during decision-making. Prior work has extensively studied equilibrium solutions for two canonical information structures: feedback, where agents observe the current state at each time, and open-loop, where agents only observe the initial state. However, these paradigms are often too restrictive to capture realistic settings exhibiting interleaved information structures, in which each agent observes only a subset of other agents at every timestep. To date, there is no systematic framework for modeling and solving dynamic games under arbitrary interleaved information structures. To this end, we make two main contributions. First, we introduce a method to model deterministic dynamic games with arbitrary interleaved information structures as Mathematical Program Networks (MPNs), where the network structure encodes the informational dependencies between agents. Second, for linear-quadratic (LQ) dynamic games, we leverage the MPN formulation to develop a systematic procedure for deriving Riccati-like equations that characterize Nash equilibria. Finally, we illustrate our approach through an example involving three agents exhibiting a cyclic information structure.

Janani S K, Kushagra Gupta, Ufuk Topcu +1

Department of Engineering Design, Indian Institute of Technology Madras, Chennai, India · Department of Electrical and Computer Engineering, The University of Texas at Austin, Austin, TX 78712, USA · Department of Aerospace Engineering and the Oden Institute for Computational Engineering and Sciences, The University of Texas at Austin, Austin, TX 78712, USA

Game Theory Nash Equilibrium Computation Imperfect-Information Games

Mar 19, 2026

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

Mar 17, 2026

Asymmetric Nash Seeking via Best Response Maps: Global Linear Convergence and Robustness to Inexact Reaction Models

Nash equilibria provide a principled framework for modeling interactions in multi-agent decision-making and control. However, many equilibrium-seeking methods implicitly assume that each agent has access to the other agents' objectives and constraints, an assumption that is often unrealistic in practice. This letter studies a class of asymmetric-information two-player constrained games with decoupled feasible sets, in which Player 1 knows its own objective and constraints while Player 2 is available only through a best-response map. For this class of games, we propose an asymmetric projected gradient descent-best response iteration that does not require full mutual knowledge of both players' optimization problems. Under suitable regularity conditions, we establish the existence and uniqueness of the Nash equilibrium and prove global linear convergence of the proposed iteration when the best-response map is exact. Recognizing that best-response maps are often learned or estimated, we further analyze the inexact case and show that, when the approximation error is uniformly bounded by

\varepsilon

, the iterates enter an explicit

O(\varepsilon)

neighborhood of the true Nash equilibrium. Numerical results on a benchmark game corroborate the predicted convergence behavior and error scaling.

Mahdis Rabbani, Navid Mojahed, Shima Nazari

Department of Mechanical and Aerospace Engineering, University of California, Davis, One Shield Ave, Davis, CA 95616.

Nash Equilibrium Computation Game Theory

Mar 16, 2026

Game-Theory-Assisted Reinforcement Learning for Border Defense: Early Termination based on Analytical Solutions

Game theory provides the gold standard for analyzing adversarial engagements, offering strong optimality guarantees. However, these guarantees often become brittle when assumptions such as perfect information are violated. Reinforcement learning (RL), by contrast, is adaptive but can be sample-inefficient in large, complex domains. This paper introduces a hybrid approach that leverages game-theoretic insights to improve RL training efficiency. We study a border defense game with limited perceptual range, where defender performance depends on both search and pursuit strategies, making classical differential game solutions inapplicable. Our method employs the Apollonius Circle (AC) to compute equilibrium in the post-detection phase, enabling early termination of RL episodes without learning pursuit dynamics. This allows RL to concentrate on learning search strategies while guaranteeing optimal continuation after detection. Across single- and multi-defender settings, this early termination method yields 10-20% higher rewards, faster convergence, and more efficient search trajectories. Extensive experiments validate these findings and demonstrate the overall effectiveness of our approach.

Goutam Das, Michael Dorothy, Kyle Volle +1

School of Aeronautics and Astronautics, Purdue University, 610 Purdue Mall, West Lafayette, IN 47907, USA · Army Research Directorate, DEVCOM Army Research Laboratory, APG, MD 21005, USA · Munitions Directorate, Air Force Research Laboratory, Eglin AFB, FL 32542, USA +1

Game-Theoretic RL Reinforcement Learning Sample-Efficient RL Game Theory

Mar 15, 2026

Content Creation with Spillovers: An Incentive Design Approach

The rise of AI amplifies the economic phenomenon of positive spillovers: when creators contribute content that can be reused and adapted by LLMs, one creator's effort may improve the content quality of others through recombination. While such spillovers can improve content quality, they also reshape incentives, as creators may reduce effort when they can benefit from others' contributions. We introduce the Content Creation with Spillovers (CCS) model, a game between a platform and strategic creators. In this game, each creator chooses an effort level, and qualities are jointly determined by all creators' efforts. The platform contracts on qualities while seeking to maximize social welfare. We show that standard contest mechanisms can be unstable, and propose a parametrized family of Provisional Allocation mechanisms that guarantee a Pareto-dominant equilibrium. Although optimizing welfare within this family is hard to approximate in general, we develop approximation algorithms whose guarantees hold either deterministically across structured spillover classes or with high probability under random instances.

Sagi Ohayon, Boaz Taitler, Omer Ben-Porat

Technion—Israel Institute of Technology

Mechanism Design Game Theory

Mar 14, 2026

Chance-Constrained Correlated Equilibria for Robust Noncooperative Coordination

Correlated equilibria enable a coordinator to influence the self-interested agents by recommending actions that no player has an incentive to deviate from. However, the effectiveness of this mechanism relies on accurate knowledge of the agents' cost structures. When cost parameters are uncertain, the recommended actions may no longer be incentive compatible, allowing agents to benefit from deviating from them. We study a chance-constrained correlated equilibrium problem formulation that accounts for uncertainty in agents' costs and guarantees incentive compatibility with a prescribed confidence level. We derive sensitivity results that quantify how uncertainty in individual incentive constraints affects the expected coordination outcome. In particular, the analysis characterizes the value of information by relating the marginal benefit of reducing uncertainty to the dual sensitivities of the incentive constraints, providing guidance on which sources of uncertainty should be prioritized for information acquisition. The results further reveal that increasing the confidence level is not always beneficial and can introduce a tradeoff between robustness and system efficiency. Numerical experiments demonstrate this tradeoff: CC-CE reduces realized coordination cost by up to 35% at intermediate confidence levels, while the proposed information-gain metric consistently identifies effective uncertainty sources to reduce.

Jaehan Im, Ufuk Topcu, David Fridovich-Keil

Department of Aerospace Engineering and Engineering Mechanics, The University of Texas at Austin · The Oden Institute for Computational Engineering and Sciences, The University of Texas at Austin

Game Theory Decision-Making under Uncertainty Chance-Constrained Optimization Value of Information

Mar 10, 2026

Noncooperative Human-AI Agent Dynamics

This paper investigates the dynamics of noncooperative interactions between artificial intelligence agents and human decision-makers in strategic environments. In particular, motivated by extensive literature in behavioral Economics, human agents are more faithfully modeled with respect to the state of the art using Prospect Theoretic preferences, while AI agents are modeled with standard expected utility maximization. Prospect Theory incorporates known cognitive heuristics employed by humans, including reference dependence and greater loss aversion relative to utility to relative gains. This paper runs different combinations of expected utility and prospect theoretic agents in a number of classic matrix games as well as examples specialized to tease out distinctions in strategic behavior with respect to preference functions, to explore the emergent behaviors from mixed population (human vs. AI) competition. Extensive numerical simulations are performed across AI, aware humans (those with full knowledge of the game structure and payoffs), and learning Prospect Agents (i.e., for AIs representing humans). A number of interesting observations and patterns show up, spanning barely distinguishable behavior, behavior corroborating Prospect preference anomalies in the theoretical literature, and unexpected surprises. Code can be found at https://github.com/dylanwaldner/noncooperative-human-AI.

Dylan Waldner, Vyacheslav Kungurtsev, Mitchelle Ashimosi

Prospect Theory Human-AI Decision Making Game Theory Human Behavior Simulation Decision-Making under Uncertainty

Mar 10, 2026

Strategically Robust Multi-Agent Reinforcement Learning with Linear Function Approximation

Provably efficient and robust equilibrium computation in general-sum Markov games remains a core challenge in multi-agent reinforcement learning. Nash equilibrium is computationally intractable in general and brittle due to equilibrium multiplicity and sensitivity to approximation error. We study Risk-Sensitive Quantal Response Equilibrium (RQRE), which yields a unique, smooth solution under bounded rationality and risk sensitivity. We propose RQRE-OVI, an optimistic value iteration algorithm for computing RQRE with linear function approximation in large or continuous state spaces. Through finite-sample regret analysis, we establish convergence and explicitly characterize how sample complexity scales with rationality and risk-sensitivity parameters. The regret bounds reveal a quantitative tradeoff: increasing rationality tightens regret, while risk sensitivity induces regularization that enhances stability and robustness. This exposes a Pareto frontier between expected performance and robustness, with Nash recovered in the limit of perfect rationality and risk neutrality. We further show that the RQRE policy map is Lipschitz continuous in estimated payoffs, unlike Nash, and RQRE admits a distributionally robust optimization interpretation. Empirically, we demonstrate that RQRE-OVI achieves competitive performance under self-play while producing substantially more robust behavior under cross-play compared to Nash-based approaches. These results suggest RQRE-OVI offers a principled, scalable, and tunable path for equilibrium learning with improved robustness and generalization.

Jake Gonzales, Max Horwitz, Eric Mazumdar +1

Department of Electrical & Computer Engineering, University of Washington · Computing & Mathematical Sciences, California Institute of Technology

Multi-Agent Reinforcement Learning Game-Theoretic RL Game Theory Risk-Sensitive RL

Mar 6, 2026

The Coordination Gap: Multi-Agent Alternation Metrics for Temporal Fairness in Repeated Games

Repeated multi-agent interactions require evaluation metrics that capture not only payoff distributions but also their temporal organization. Conventional outcome-based fairness measures can assign similar aggregate scores to temporally distinct coordination patterns, obscuring whether access to a shared resource is genuinely rotating or persistently monopolized. We study this problem in the Honey-Jar Game (HJG), a minimally dynamic repeated threshold-congestion Markov game in which n agents compete for exclusive access to a single high-reward resource. We introduce Perfect Alternation (PA), a reference turn-taking regime corresponding to the n-periodic round-robin picking sequence, together with six novel Alternation (ALT) metrics and a benchmarking methodology mapping ALT values to interpretable PA-equivalent performance. Using Q-learning agents as a minimal adaptive baseline against analytically derived random-policy baselines, we uncover a clear measurement failure: despite deceptively high traditional metrics (e.g., reward fairness often exceeding 0.9), learned policies perform worse than random on every ALT metric, by 34-74% on CALT and up to 92% on EALT, with PA-equivalent coordination falling to roughly one-fifth of the population at n=10. EALT further reveals two distinct failure patterns: without episodic memory (Type-A), the deficit grows from -20% at n=2 to -92% at n=10; with episodic memory (Type-B), it reaches a trough of -76% at n=5 before partially recovering to -10% at n=10. Conventional efficiency and fairness metrics do not reveal these differences. The ALT framework complements the temporal fair division and picking-sequence literature by diagnosing whether temporal fairness emerges spontaneously in decentralized adaptive systems rather than how to enforce it.

Nikolaos Al. Papadopoulos, Ismael Tito Freire, Marti Sanchez-Fibla +1

Department of Applied Informatics, University of Macedonia, Egnatia 156, Thessaloniki 54636, Greece · Institut des Systèmes Intelligents et de Robotique (ISIR), Sorbonne Université, Paris, France · Department of Information and Communication Technologies, Universitat Pompeu Fabra, Barcelona, Spain

Multi-Agent Coordination Game Theory

Mar 1, 2026

Artificial Superintelligence May be Useless: Equilibria in the Economy of Multiple AI Agents

With recent development of artificial intelligence, it is more common to adopt AI agents in economic activities. This paper explores the economic actions of agents, including human agents and AI agents, in an economic game of trading products/services, and the equilibria in this economy involving multiple agents. We derive a range of equilibrium results and their corresponding conditions using a Markov chain stationary distribution based model. One distinct feature of our model is that we consider the long-term utility generated by economic activities instead of their short-term benefits. For the model consisting of two agents, we fully characterize all the possible economic equilibria and conditions. Interestingly, we show that unless each agent can at least double (not merely increase) its marginal utility by purchasing the other agent's products/services, purchasing the other agent's products/services will not happen in any economic equilibrium. We further extend our results to three and more agents, where we characterize more economic equilibria. We find that in some equilibria, the more powerful'' AI agents contribute zero utility to less capable'' agents.

Huan Cai, Ziqing Lu, Catherine Xu +2

Department of Economics and Business, Cornell College, Mount Vernon, IA, 52314. · Program of Applied Mathematical and Computational Sciences, University of Iowa, Iowa City, IA 52242. · Iowa City Math Circle and Club, Iowa. +2

Multi-Agent Systems Game Theory

Feb 27, 2026

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 Conservative RL Offline RL Multi-Agent Reinforcement Learning Game-Theoretic RL

Feb 26, 2026

Zeroth-Order Stackelberg Control in Combinatorial Congestion Games

We study Stackelberg (leader--follower) tuning of network parameters (tolls, capacities, incentives) in combinatorial congestion games, where selfish users choose discrete routes (or other combinatorial strategies) and settle at a congestion equilibrium. The leader minimizes a system-level objective (e.g., total travel time) evaluated at equilibrium, but this objective is typically nonsmooth because the set of used strategies can change abruptly. We propose ZO-Stackelberg, which couples a projection-free Frank--Wolfe equilibrium solver with a zeroth-order outer update, avoiding differentiation through equilibria. We prove convergence to generalized Goldstein stationary points of the true equilibrium objective, with explicit dependence on the equilibrium approximation error, and analyze subsampled oracles: if an exact minimizer is sampled with probability

κ_m

, then the Frank--Wolfe error decays as

\mathcal{O}(1/(κ_m T))

. We also propose stratified sampling as a practical way to avoid a vanishing

κ_m

when the strategies that matter most for the Wardrop equilibrium concentrate in a few dominant combinatorial classes (e.g., short paths). Experiments on real-world networks demonstrate that our method achieves orders-of-magnitude speedups over a differentiation-based baseline while converging to follower equilibria.

Saeed Masiha, Sepehr Elahi, Negar Kiyavash +1

EPFL School of Management of Technology · EPFL Department of Computer and Communications Sciences

Frank-Wolfe Algorithms Stackelberg Games Congestion Games Game Theory Zeroth-Order Optimization Constrained Optimization

Feb 26, 2026

Robust Information Design for Multi-Agent Systems with Complementarities: Smallest-Equilibrium Threshold Policies

We study information design in multi-agent systems (MAS) with binary actions and strategic complementarities, where an external designer influences behavior only through signals. Agents play the smallest-equilibrium of the induced Bayesian game, reflecting conservative, coordination-averse behavior typical in distributed systems. We show that when utilities admit a convex potential and welfare is convex, the robustly implementable optimum has a remarkably simple form: perfect coordination at each state: either everyone acts or no one does. We provide a constructive threshold rule: compute a one-dimensional score for each state, sort states, and pick a single threshold (with a knife-edge lottery for at most one state). This rule is an explicit optimal vertex of a linear program (LP) characterized by feasibility and sequential obedience constraints. Empirically, in both vaccination and technology-adoption domains, our constructive policy matches LP optima, scales as

O(|Θ|\log|Θ|)

, and avoids the inflated welfare predicted by obedience-only designs that assume the designer can dictate the (best) equilibrium. The result is a general, scalable recipe for robust coordination in MAS with complementarities.

Farzaneh Farhadi, Maria Chli

Aston University, Birmingham, United Kingdom

Information Design Multi-Agent Coordination Game Theory Imperfect-Information Games

Feb 26, 2026

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 25, 2026

Revisiting the Bertrand Paradox via Equilibrium Analysis of No-regret Learners

We study the discrete Bertrand pricing game with a non-increasing demand function. The game has

n \ge 2

players who simultaneously choose prices from the set

\{1/k, 2/k, \ldots, 1\}

, where

k\in\mathbb{N}

. The player who sets the lowest price captures the entire demand; if multiple players tie for the lowest price, they split the demand equally. We study the Bertrand paradox, where classical theory predicts low prices, yet real markets often sustain high prices. To understand this gap, we analyze a repeated-game model in which firms set prices using no-regret learners. Our goal is to characterize the equilibrium outcomes that can arise under different no-regret learning guarantees. We are particularly interested in questions such as whether no-external-regret learners can converge to undesirable high-price outcomes, and how stronger guarantees such as no-swap regret shape the emergence of competitive low-price behavior. We address these and related questions through a theoretical analysis, complemented by experiments that support the theory and reveal surprising phenomena for no-swap regret learners.

Arnab Maiti, Junyan Liu, Kevin Jamieson +1

University of Washington

Swap Regret Game Theory Regret Minimization Repeated Games

Feb 24, 2026

Body-Reservoir Governance in Repeated Games: Embodied Decision-Making, Dynamic Sentinel Adaptation, and Complexity-Regularized Optimization

Standard game theory explains cooperation in repeated games through conditional strategies such as Tit-for-Tat (TfT), but these require continuous computation that imposes physical costs on embodied agents. We propose a three-layer Body-Reservoir Governance (BRG) architecture: (1) a body reservoir (echo state network) whose

d

-dimensional state performs implicit inference over interaction history, serving as both decision-maker and anomaly detector, (2) a cognitive filter providing costly strategic tools activated on demand, and (3) a metacognitive governance layer with receptivity parameter

α\in [0,1]

. At full body governance (

α=1

), closed-loop dynamics satisfy a self-consistency equation: cooperation is expressed as the reservoir's fixed point, not computed. Strategy complexity cost is defined as the KL divergence between the reservoir's state distribution and its habituated baseline. Body governance reduces this cost, with action variance decreasing up to

1600\times

with dimension

d

. A dynamic sentinel generates a composite discomfort signal from the reservoir's own state, driving adaptive

α(t)

: near baseline during cooperation, rapidly dropping upon defection to activate cognitive retaliation. Overriding the body incurs thermodynamic cost proportional to internal state distortion. The sentinel achieves the highest payoff across all conditions, outperforming static body governance, TfT, and EMA baselines. A dimension sweep (

d \in \{5,\ldots,100\}

) shows implicit inference scales with bodily richness (

23\times

to

1600\times

variance reduction), attributable to reservoir dynamics. A phase diagram in

(d, τ_{\mathrm{env}})

space reveals governance regime transitions near

d \approx 20

. The framework reinterprets cooperation as the minimum-dissipation response of an adapted dynamical system -- emergent from embodied dynamics rather than computed.

Yuki Nakamura

The Open University of Japan

Repeated Games Game Theory Embodied AI Emergent Behavior in Multi-Agent Systems

Feb 21, 2026

A potentialization algorithm for games with applications to multi-agent learning in repeated games

We investigate an algorithm that assigns to any game in normal form an approximating game that admits an ordinal potential function. Due to the properties of potential games, the algorithm equips every game with a surrogate reward structure that allows efficient multi-agent learning. Numerical simulations using the replicator dynamics show that 'potentialization' guarantees convergence to stable agent behavior.

Philipp Lakheshar, Sharwin Rezagholi

University of Applied Sciences Technikum Wien, Vienna, Austria

Game Theory Potential Games

Feb 19, 2026

Market Games for Generative Models: Equilibria, Welfare, and Strategic Entry

Generative model ecosystems increasingly operate as competitive multi-platform markets, where platforms strategically select models from a shared pool and users with heterogeneous preferences choose among them. Understanding how platforms interact, when market equilibria exist, how outcomes are shaped by model-providers, platforms, and user behavior, and how social welfare is affected is critical for fostering a beneficial market environment. In this paper, we formalize a three-layer model-platform-user market game and identify conditions for the existence of pure Nash equilibrium. Our analysis shows that market structure, whether platforms converge on similar models or differentiate by selecting distinct ones, depends not only on models' global average performance but also on their localized attraction to user groups. We further examine welfare outcomes and show that expanding the model pool does not necessarily increase user welfare or market diversity. Finally, we design novel best-response training schemes that allow model providers to strategically introduce new models into competitive markets.

Xiukun Wei, Min Shi, Xueru Zhang

The Ohio State University

Game Theory Nash Equilibrium

Feb 19, 2026

Linear Convergence in Games with Delayed Feedback via Extra Prediction

Feedback delays are inevitable in real-world multi-agent learning. They are known to severely degrade performance, and the convergence rate under delayed feedback is still unclear, even for bilinear games. This paper derives the rate of linear convergence of Weighted Optimistic Gradient Descent-Ascent (WOGDA), which predicts future rewards with extra optimism, in unconstrained bilinear games. To analyze the algorithm, we interpret it as an approximation of the Extra Proximal Point (EPP), which is updated based on farther future rewards than the classical Proximal Point (PP). Our theorems show that standard optimism (predicting the next-step reward) achieves linear convergence to the equilibrium at a rate

\exp(-Θ(t/m^{5}))

after

t

iterations for delay

m

. Moreover, employing extra optimism (predicting farther future reward) tolerates a larger step size and significantly accelerates the rate to

\exp(-Θ(t/(m^{2}\log m)))

. Our experiments also show accelerated convergence driven by the extra optimism and are qualitatively consistent with our theorems. In summary, this paper validates that extra optimism is a promising countermeasure against performance degradation caused by feedback delays.

Yuma Fujimoto, Kenshi Abe, Kaito Ariu

CyberAgent, Tokyo, Japan · Soken University, Kanagawa, Japan

Feb 19, 2026

Algorithmic Collusion at Test Time: A Meta-game Design and Evaluation

The threat of algorithmic collusion, and whether it merits regulatory intervention, remains debated, as existing evaluations of its emergence often rely on long learning horizons, assumptions about counterparty rationality in adopting collusive strategies, and symmetry in hyperparameters and economic settings among players. To study collusion risk, we introduce a meta-game design for analyzing algorithmic behavior under test-time constraints. We model agents as possessing pretrained policies with distinct strategic characteristics (e.g., competitive, naively cooperative, or robustly collusive), and formulate the problem as selecting a meta-strategy that combines a pretrained, initial policy with an in-game adaptation rule. We seek to examine whether collusion can emerge under rational choices and how agents co-adapt toward cooperation or competition. To this end, we sample normal-form empirical games over meta-strategy profiles, compute relevant game statistics (e.g., payoffs against individuals and regret against an equilibrium mixture of opponents), and construct empirical best-response graphs to uncover strategic relationships. We evaluate reinforcement-learning, UCB, and LLM-based strategies in repeated pricing games under symmetric and asymmetric cost settings, and present findings on the feasibility of algorithmic collusion and the effectiveness of pricing strategies in practical ``test-time'' environments. The source code is available at: https://github.com/chailab-rutgers/CollusionMetagame.

Yuhong Luo, Daniel Schoepflin, Xintong Wang

Rutgers University · DIMACS, Rutgers University

Algorithmic Collusion Game Theory Repeated Games

Feb 18, 2026

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 18, 2026

Learning Distributed Equilibria in Linear-Quadratic Stochastic Differential Games: An $α$ -Potential Approach

We analyze independent policy-gradient (PG) learning in

N

-player linear-quadratic (LQ) stochastic differential games. Each player employs a distributed policy that depends only on its own state and updates the policy independently using the gradient of its own objective. We establish global linear convergence of these methods to an equilibrium by showing that the LQ game admits an

α

-potential structure, with

α

determined by the degree of pairwise interaction asymmetry. For pairwise-symmetric interactions, we construct an affine distributed equilibrium by minimizing the potential function and show that independent PG methods converge globally to this equilibrium, with complexity scaling linearly in the population size and logarithmically in the desired accuracy. For asymmetric interactions, we prove that independent projected PG algorithms converge linearly to an approximate equilibrium, with suboptimality proportional to the degree of asymmetry. Numerical experiments confirm the theoretical results across both symmetric and asymmetric interaction networks.

Philipp Plank, Yufei Zhang

Department of Mathematics, Imperial College London, London, UK

Game Theory Nash Equilibrium Computation Decentralized MARL Policy Gradient Methods Potential Games