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.

Feb 18, 2026

Control in Hedonic Games

We initiate the study of control in hedonic games, where an external actor influences coalition formation by adding or deleting agents. We consider three basic control goals (1) enforcing that an agent is not alone (NA); (2) enforcing that a pair of agents is in the same coalition (PA); (3) enforcing that all agents are in the same grand coalition (GR), combined with two control actions: adding agents (AddAg) or deleting agents (DelAg). We analyze these problems for friend-oriented and additive preferences under individual rationality, individual stability, Nash stability, and core stability. We provide a complete computational complexity classification for control in hedonic games.

Jiehua Chen, Jakob Guttmann, Merisa Mustajbašić +1

TU Wien Vienna, Austria

Coalition Formation Game Theory Cooperative Game Theory

Feb 16, 2026

Fluid-Agent Reinforcement Learning

The primary focus of multi-agent reinforcement learning (MARL) has been to study interactions among a fixed number of agents embedded in an environment. However, in the real world, the number of agents is neither fixed nor known a priori. Moreover, an agent can decide to create other agents (for example, a cell may divide, or a company may spin off a division). In this paper, we propose a framework that allows agents to create other agents; we call this a fluid-agent environment. We present game-theoretic solution concepts for fluid-agent games and empirically evaluate the performance of several MARL algorithms within this framework. Our experiments include fluid variants of established benchmarks such as Predator-Prey and Level-Based Foraging, where agents can dynamically spawn, as well as a new environment we introduce that highlights how fluidity can unlock novel solution strategies beyond those observed in fixed-population settings. We demonstrate that this framework yields agent teams that adjust their size dynamically to match environmental demands.

Shishir Sharma, Doina Precup, Theodore J. Perkins

Mila – Quebec Artificial Intelligence Institute, Montreal, Canada · McGill University, Montreal, Canada · Ottawa Hospital Research Institute, University of Ottawa, Ottawa, Canada

Multi-Agent Reinforcement Learning Multi-Agent Coordination Game Theory

Feb 16, 2026

Socially-Weighted Alignment: A Game-Theoretic Framework for Multi-Agent LLM Systems

Deploying large language model (LLM) agents in shared environments introduces a fundamental tension between individual alignment and collective stability: locally rational decisions can impose negative externalities that degrade system-level performance. We propose Socially-Weighted Alignment (SWA), a game-theoretic framework that modifies inference-time decision making by interpolating between an agent's private objective and an estimate of group welfare via a social weight

λ\in[0,1]

. In a shared-resource congestion game with

n

agents and congestion severity

β

, we show that SWA induces a critical threshold

λ^*=(n-β)/(n-1)

above which agents no longer have marginal incentive to increase demand under overload, yielding a phase transition from persistent congestion to stable operation near capacity. We further provide an inference-time algorithmic instantiation of SWA that does not require parameter updates or multi-agent reinforcement learning, and use a multi-agent simulation to empirically validate the predicted threshold behavior.

Furkan Mumcu, Yasin Yilmaz

University of South Florida

Congestion Games Multi-Agent LLM Systems LLM Alignment Multi-Agent Coordination Game Theory

Feb 16, 2026

Noncooperative Virtual Queue Coordination via Uncertainty-Aware Correlated Equilibria

Collaborative virtual queueing has been proposed as a mechanism to mitigate airport surface congestion while preserving airline autonomy over aircraft-level pushback decisions. A central coordinator can regulate aggregate pushback capacity but cannot directly control which specific aircraft are released, limiting its ability to steer system-level performance. We propose a noncooperative coordination mechanism for collaborative virtual queueing based on the correlated equilibrium concept, which enables the coordinator to provide incentive-compatible recommendations on aircraft-level pushback decisions without overriding airline autonomy. To account for uncertainty in airlines' internal cost assessments, we introduce chance constraints into the correlated equilibrium formulation. This formulation provides explicit probabilistic guarantees on incentive compatibility, allowing the coordinator to adjust the confidence level with which airlines are expected to follow the recommended actions. We further propose a scalable algorithm for computing chance-constrained correlated equilibria by exploiting a reduced-rank structure. Numerical experiments demonstrate that the proposed method scales to realistic traffic levels up to 210 eligible pushbacks per hour, reduces accumulated delay by up to approximately 8.9% compared to current first-come-first-served schemes, and reveals a trade-off between confidence level, deviation robustness, and achievable cost efficiency.

Jaehan Im, David Fridovich-Keil, Ufuk Topcu

Department of Aerospace Engineering, The University of Texas at Austin, Austin, Texas, USA

Air Traffic Management Multi-Agent Coordination Queueing Theory Game Theory Chance-Constrained Optimization

Feb 2, 2026

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 28, 2025

Reach-Avoid Differential game with Reachability Analysis for UAVs: A decomposition approach

Reach-avoid (RA) games have significant applications in security and defense, particularly for unmanned aerial vehicles (UAVs). These problems are inherently challenging due to the need to consider obstacles, consider the adversarial nature of opponents, ensure optimality, and account for nonlinear dynamics. Hamilton-Jacobi (HJ) reachability analysis has emerged as a powerful tool for tackling these challenges; however, while it has been applied to games involving two spatial dimensions, directly extending this approach to three spatial dimensions is impossible due to high dimensionality. On the other hand, alternative approaches for solving RA games lack the generality to consider games with three spatial dimensions involving agents with non-trivial system dynamics. In this work, we propose a novel framework for dimensionality reduction by decomposing the problem into a horizontal RA sub-game and a vertical RA sub-game. We then solve each sub-game using HJ reachability analysis and consider second-order dynamics that account for the defender's acceleration. To reconstruct the solution to the original RA game from the sub-games, we introduce a HJ-based tracking control algorithm in each sub-game that not only guarantees capture of the attacker but also tracking of the attacker thereafter. We prove the conditions under which the capture guarantees are maintained. The effectiveness of our approach is demonstrated via numerical simulations, showing that the decomposition maintains optimality and guarantees in the original problem. Our methods are also validated in a Gazebo physics simulator, achieving successful capture of quadrotors in three spatial dimensions space for the first time to the best of our knowledge.

Minh Bui, Simon Monckton, Mo Chen

Simon Fraser University, Burnaby, BC V5A 1S6, Canada · Defense Research & Development Canada (DRDC), Medicine Hat, Alberta T1A 8K6, Canada

Game Theory Reachability Analysis Aerial Robotics

Dec 11, 2025

Computing Evolutionarily Stable Strategies in Imperfect-Information Games

We present an algorithm for computing evolutionarily stable strategies (ESSs) in symmetric two-player perfect-recall extensive-form games of imperfect information. The algorithm operates directly in sequence form, avoiding explicit enumeration of normal-form supports. In a biologically motivated cancer signaling game, the algorithm recovers all seven symmetric Nash equilibria and identifies all three ESSs, each with a clear biological interpretation. Experiments on random imperfect-information games evaluate scalability as the numbers of private signals and available actions increase.

Sam Ganzfried

Ganzfried Research, Cornell University

Imperfect-Information Games Game Theory Evolutionary Game Theory

Nov 25, 2025

Computing Evolutionarily Stable Strategies in Multiplayer Games

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

Sam Ganzfried

Ganzfried Research, Cornell University

Game Theory Evolutionary Game Theory

Nov 12, 2025

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, 2025

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, 2025

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, 2025

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 Bayesian Persuasion LLM Reasoning

Sep 30, 2025

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

Sep 27, 2025

Game-Theoretic Understandings of Multi-Agent Systems with Multiple Objectives

Agents in many multi-agent systems must balance several, possibly conflicting, objectives, and the trade-offs an agent can achieve depend on how the other agents behave. We study this setting through the Multi-Objective Markov Game (MOMG), a Markov game in which each agent receives a vector of rewards, and adopt the Pareto-Nash Equilibrium (PNE) as the solution concept: at a PNE, no agent can unilaterally improve one of its objectives without sacrificing another. We show that PNEs always exist and coincide with the Nash equilibria of the linearly scalarized games with strictly positive weights, so standard single-objective Markov-game solvers suffice to compute them. We further define the Weak Pareto-Nash Equilibrium (WPNE), which excludes only unilateral deviations that strictly improve all objectives at once. The associated gap (WPNG) is zero exactly at WPNEs and never exceeds the Nash gap of any linearly scalarized game; hence an approximate Nash equilibrium of a scalarized game is also an approximate WPNE. When the preference profile is known in advance, learning in an MOMG therefore reduces to learning in a single scalarized Markov game, for which we provide a sample-efficient algorithm. When preferences are revealed only after data collection, we design a two-phase algorithm that first explores without any preference information; with high probability, every Nash equilibrium of the learned scalarized game is then an approximate WPNE for every queried preference profile, and the WPNG of any policy can be estimated accurately from the learned model. Experiments on tabular games and four multi-objective multi-agent environments illustrate the theory and show the effect of preference-free exploration.

Zixin Lin, Qianyi Tan, Sihong He +1

Department of Electrical and Computer Engineering, Department of Computer Science, University of Central Florida, Orlando, FL 32816

Game Theory Multi-Objective Reinforcement Learning Multi-Agent Reinforcement Learning

Aug 5, 2025

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 Computation Multi-Agent System Optimization Reinforcement Learning Average-Reward RL Game Theory Distributionally Robust Optimization+5

Jul 22, 2025

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, 2025

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.

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

Jun 23, 2025

Online Learning in Stabilized Linear Dynamical Games with Adversarial Disturbances

We study online learning in linear dynamical games where multiple strategic agents act on a shared state evolving according to a linear dynamical system subject to adversarial disturbances. This setting lies beyond both single-agent nonstochastic online control and classical linear-quadratic games, which typically focus on quadratic objectives and noiseless or stochastic dynamics. Each agent seeks to minimize its own sequence of convex losses under full-state observability. Following the stabilizing-baseline paradigm in nonstochastic online control, we assume access to linear controllers that stabilize the noiseless system and focus on online adaptation by learning disturbance-action corrections. This extends adversarial online control to strategic multi-agent shared-state systems, where each agent's actions shape the state trajectory and hence the realized losses of all learners. Under state-only and aggregate-input feedback models, we analyze agents running online gradient descent with memory to update their own disturbance-action policies. We prove per-agent regret bounds that are sublinear and near-optimal in the time horizon, with population dependence that varies under the specified feedback, opponent policy, and stability assumptions. In the common-interest case, where all agents have identical cost functions, we show that the induced online problem forms a time-varying potential game and derive equilibrium tracking guarantees. Together, our results provide a theoretical framework for adversarial online learning in stabilized linear dynamical games, connecting online control with learning in games.

Anas Barakat, John Lazarsfeld, Georgios Piliouras +1

Singapore University of Technology and Design* · Centre for Quantum Technologies, National University of Singapore · Archimedes/Athena RC, Greece

Online Learning Multi-Agent Control Game Theory Dynamic Regret Minimization

May 19, 2025

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 Social Welfare Maximization

Apr 11, 2025

Learning in Structured Stackelberg Games

We initiate the study of structured Stackelberg games, a novel form of strategic interaction between a leader and a follower where contextual information can be predictive of the follower's (unknown) type. Motivated by applications such as security games and AI safety, we show how this additional structure can help the leader learn a utility-maximizing policy in both the online and distributional settings. In the online setting, we first prove that standard learning-theoretic measures of complexity do not characterize the difficulty of the leader's learning task. Notably, we find that there exists a learning-theoretic measure of complexity, analogous to the Littlestone dimension in online classification, that tightly characterizes the leader's instance-optimal regret. We term this the Stackelberg-Littlestone dimension, and leverage it to provide a provably optimal online learning algorithm. In the distributional setting, we provide analogous results by showing that two new dimensions control the sample complexity upper- and lower-bound.

Maria-Florina Balcan, Kiriaki Fragkia, Keegan Harris

Carnegie Mellon University, Pittsburgh, USA · University of California, Berkeley, USA

Game Theory Stackelberg Games Statistical Learning Theory Online Learning

Feb 12, 2025

Randomly Wrong Signals: Bayesian Auction Design with ML Predictions

Machine learning can help sellers predict buyers' willingness to pay, but its predictions may be plausible and yet entirely unrelated to a buyer's value. We introduce a Bayesian auction model that distinguishes such hallucinations from ordinary measurement noise. We characterize revenue-maximizing auctions with publicly disclosed predictions in the benchmark where informative predictions are exact. For a single buyer, this characterization explains when the seller should follow a prediction and when to hedge against its failure by ignoring it or capping the price. These insights guide the design of simple auctions that account for both hallucinations and measurement noise. Numerical experiments show that the resulting auctions achieve near-optimal revenue.

Ilan Lobel, Humberto Moreira, Omar Mouchtaki

NYU Stern School of Business · FGV/EPGE Escola Brasileira de Economia e Finança

Game Theory Predict-Then-Optimize

Nov 18, 2024

Nonlinear Equilibrium Transitions in a Potential Game Model for Federated Learning

In federated learning (FL), a central server typically allocates training efforts to clients. However, from a market-oriented perspective, clients may independently choose their training efforts based on rational self-interest. To study this setting, we propose a potential game framework in which each client's payoff is determined by its individual effort and the rewards provided by the server. The rewards are influenced by the collective efforts of all clients and can be modulated by a reward factor. We first establish the existence of Nash equilibria (NEs) and then investigate their uniqueness in a stationary setting. We show that the NEs depend nonlinearly on the reward factor and exhibit a nonsmooth transition at a critical value, where the stationary potential loses strict curvature, leading to nonunique NEs and a jump between low-effort and high-effort branches. Furthermore, we prove the convergence of the best-response algorithm for computing NEs in our FL game. Finally, we apply the clients' rational efforts derived from the NEs to FL training with various datasets and models, thereby validating the effectiveness of the identified critical reward factor. The source code is available at https://github.com/DCN-FAU-AvH/FL-Potential-Game

Kang Liu, Ziqi Wang, Enrique Zuazua

Institut de Mathématiques de Bourgogne, Université Bourgogne Europe, CNRS, Dijon, 21000, France · Chair for Dynamics, Control, Machine Learning and Numerics – Alexander von Humboldt Professorship, Department of Mathematics, Friedrich-Alexander-Universität Erlangen-Nürnberg, Cauerstrasse 11, Erlangen, 91058, Germany · Chair of Computational Mathematics, Fundación Deusto, Avenida de las Universidades, 24, Bilbao, 48007, Basque Country, Spain +1

Nash Equilibrium Game Theory Potential Games Federated Learning Nash Equilibrium Computation

Sep 2, 2024

Decentralized Best-Response-Based Learning in Two-Player Zero-Sum Stochastic Games: A Finite-Sample Analysis

We present a finite-sample analysis of decentralized learning in two-player zero-sum matrix games and stochastic games, with a focus on best-response-based learning algorithms. In matrix games, the learning algorithm is payoff-based and symmetric: each player updates its policy using only its own payoff observations, incrementally moving toward an estimated smoothed best response to the opponent's latest policy. For stochastic games, we build on this matrix-game primitive to develop a learning algorithm called value iteration with smoothed best response (VI-SBR), which combines smoothed-best-response learning in induced matrix games with a decentralized, model-free approximation of minimax value iteration. We establish finite-sample guarantees in both settings. For matrix games, our results imply a sample complexity of

\mathcal{O}(ε^{-1})

for finding an

ε

-Nash distribution and, with explicit exploration,

\tilde{\mathcal{O}}(ε^{-8})

for finding an

ε

-Nash equilibrium. For stochastic games, we prove that the exploration-enhanced VI-SBR algorithm achieves a sample complexity of

\tilde{\mathcal{O}}(ε^{-8})

for finding an

ε

-Nash equilibrium. Technically, our analysis develops a coupled Lyapunov-drift framework. This framework simultaneously handles stochastic iterative algorithms with multiple interacting stochastic iterates, the non-zero-sum auxiliary games generated by independently updated value functions, and the time-inhomogeneous Markovian noise induced by time-varying policies. The resulting tools may be useful more broadly for analyzing learning algorithms with coupled stochastic iterates and nonstationary sampling processes.

Zaiwei Chen, Kaiqing Zhang, Eric Mazumdar +2

IE, Purdue University. · ECE, University of Maryland, College Park. · CMS, Caltech. +1

Nash Equilibrium Game Theory Zero-Sum Games Decentralized MARL Nash Equilibrium Computation

Apr 30, 2024

Neural Dynamic Data Valuation via Stochastic State-Adjoint Trajectories

Classical data valuation defines a data point's value through the finite marginal contribution

U(C\cup\{i\})-U(C)

, but estimating this quantity over coalitions requires repeated training and does not describe the contribution made along a stochastic training path. We ask whether marginal contributions of data points can be estimated from one coupled trajectory while retaining a verifiable relation to coalition-based values. To this end, we introduce Neural Dynamic Data Valuation (NDDV), which models each data point as a controlled stochastic state and computes a first-order marginal-contribution score via the adjoint equation of the Stochastic Maximum Principle (SMP). This raw sensitivity is then calibrated by a mass-preserving redistribution that increases one data point's participation while redistributing the same total weight over the remaining data points. We prove that the resulting backward adjoint recursion is the exact reverse-mode adjoint of the frozen-aggregate Euler system, bound its discrepancy from the mean-field sensitivity, and express each finite coalition marginal as an integral of local sample-weight sensitivities. These results yield pair-specific error bounds and sufficient conditions for ordering agreement with Shapley, Banzhaf, and leave-one-out values. Experiments on existing benchmarks evaluate marginal-contribution fidelity, score-release cost, corrupted-sample detection, ablations, and failure regimes. NDDV is a one-run, trajectory-conditioned estimator, not an unconditional replacement for cooperative-game values.

Zhangyong Liang, Ji Zhang, Huanhuan Gao

National Center for Applied Mathematics Tianjin University Tianjin 300072, China · School of Mathematics, Physics and Computing University of Southern Queensland Toowoomba, Queensland 4350, Australia · School of Mechanical and Aerospace Engineering Jilin University Changchun 130025, China

Cooperative Game Theory Game Theory Shapley Value Attribution Data Valuation Training Data Attribution

Mar 22, 2024

PPA-Game: Characterizing and Learning Competitive Dynamics Among Online Content Creators

In this paper, we present the Proportional Payoff Allocation Game (PPA-Game), which characterizes situations where agents compete for divisible resources. In the PPA-game, agents select from available resources, and their payoffs are proportionately determined based on heterogeneous weights attributed to them. Such dynamics simulate content creators on online recommender systems like YouTube and TikTok, who compete for finite consumer attention, with content exposure reliant on inherent and distinct quality. We first conduct a game-theoretical analysis of the PPA-Game. While the PPA-Game does not always guarantee the existence of a pure Nash equilibrium (PNE), we identify prevalent scenarios ensuring its existence. Simulated experiments further prove that the cases where PNE does not exist rarely happen. Beyond analyzing static payoffs, we further discuss the agents' online learning about resource payoffs by integrating a multi-player multi-armed bandit framework. We propose an online algorithm facilitating each agent's maximization of cumulative payoffs over

T

rounds. Theoretically, we establish that the regret of any agent is bounded by

O(\log^{1 + η} T)

for any

η> 0

. Empirical results further validate the effectiveness of our online learning approach.

Renzhe Xu, Haotian Wang, Xingxuan Zhang +2

MoE Key Laboratory of Interdisciplinary Research of Computation and Economics, Institute for Theoretical Computer Science, Shanghai University of Finance and Economics, Shanghai, China · College of Computer Science and Technology, National University of Defense Technology, Changsha, China · Department of Computer Science and Technology, Tsinghua University, Beijing, China +1

Game Theory Multi-Agent Resource Allocation Nash Equilibrium Multi-Agent Bandits

Jun 5, 2023

Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents

We introduce Calibrated Stackelberg Games (CSGs), a generalization of the standard Stackelberg Games (SGs) framework. In CSGs, a principal repeatedly interacts with an agent who (contrary to standard SGs) does not have direct access to the principal's action but instead best-responds to calibrated forecasts about it. This framework provides a powerful and realistic modeling tool that goes beyond assuming that agents use ad hoc and highly specified algorithms for interacting in strategic settings and instead builds on statistical foundations of forecasts and calibration. We show that in CSGs, despite both the principal and the agent having less information than in standard SGs, the principal's optimal utility remains upper and lower bounded by the Stackelberg value of the one-shot game, in both finite and continuous settings. Alongside CSGs, we develop stronger notions of calibration and corresponding algorithms that address two central challenges for calibration in game-theoretic environments. First, achieving point-wise calibration typically incurs an error that scales exponentially with the dimension of the strategy space. Second, the principal's convergence rate in CSGs depends critically on the adaptivity of the agent's calibration algorithm. To address these challenges, we establish a meaningful, efficiently achievable relaxation of calibration based on conditioning on best-response regions. This yields the first notion of calibration in games with a statistical rate that only depends on the number of agents' actions rather than the dimension of the principal's strategy space and that leads to no-swap regret for the agent. We further develop adaptive calibration algorithms for the agents that provide fine-grained, any-time calibration guarantees against adversarial sequences, enabling the principal to achieve faster convergence in CSGs.

Nika Haghtalab, Chara Podimata, Kunhe Yang

University of California, Berkeley · Massachusetts Institute of Technology

Imperfect-Information Games Game Theory Stackelberg Games Regret Minimization

Oct 29, 2022

Observable Perfect Equilibrium

While Nash equilibrium has emerged as the central game-theoretic solution concept, many important games contain several Nash equilibria and we must determine how to select between them in order to create real strategic agents. Several Nash equilibrium refinement concepts have been proposed and studied for sequential imperfect-information games, the most prominent being trembling-hand perfect equilibrium, quasi-perfect equilibrium, proper equilibrium, and recently one-sided quasi-perfect equilibrium. These concepts are robust to certain arbitrarily small mistakes, and are guaranteed to always exist; however, we argue that none of these is the correct concept for developing strong agents in sequential games of imperfect information. We define a new equilibrium refinement concept for extensive-form games called observable perfect equilibrium in which the solution is robust over trembles in publicly-observable action probabilities (not necessarily over all action probabilities that may not be observable by opposing players). Observable perfect equilibrium correctly captures the assumption that the opponent is playing as rationally as possible given mistakes that have been observed (while previous solution concepts do not). We prove that observable perfect equilibrium is always guaranteed to exist, and demonstrate that it selects a unique equilibrium in a simplified no-limit poker game where the prior extensive-form refinements retain a continuum of equilibria. We expect observable perfect equilibrium to be a useful equilibrium refinement concept for modeling many important imperfect-information games of interest in artificial intelligence.

Sam Ganzfried

Ganzfried Research

Nash Equilibrium Imperfect-Information Games Game Theory

Sep 28, 2022

Generalizing Liquid Democracy to multi-agent delegation: A Voting Weight Measure and Equilibrium Analysis

In this study, we propose a generalization of the classic model of liquid democracy that allows fractional delegation of voting weight, while simultaneously allowing for the existence of equilibrium states. Our approach empowers agents to partition and delegate their votes to multiple representatives, all while retaining a fraction of the voting power for themselves. We introduce a penalty mechanism for the length of delegation chains. We discuss the desirable properties of a reasonable generalization of the classic model, and prove that smaller penalty factors bring the model closer to satisfying these properties. In the subsequent section, we explore the presence of equilibrium states in a general delegation game utilizing the proposed voting measure. In contrast to the classical model, we demonstrate that this game exhibits pure strategy Nash equilibria, contingent upon the imposition of a penalty on the length of delegation chains.

Francisco M. Bersetche

Centro Atómico Bariloche; CONICET · ANID, FONDECYT Project 3220254

Social Choice Theory Nash Equilibrium Game Theory

Jan 12, 2022

Safe Equilibrium

The standard game-theoretic solution concept, Nash equilibrium, assumes that all players behave rationally. If we follow a Nash equilibrium and opponents are irrational (or follow strategies from a different Nash equilibrium), then we may obtain an extremely low payoff. On the other hand, a maximin strategy assumes that all opposing agents are playing to minimize our payoff (even if it is not in their best interest), and ensures the maximal possible worst-case payoff, but results in exceedingly conservative play. We propose a new solution concept called safe equilibrium that models opponents as behaving rationally with a specified probability and behaving potentially arbitrarily with the remaining probability. We prove that a safe equilibrium exists in all strategic-form games (for all possible values of the rationality parameters), and prove that its computation is PPAD-hard. We present exact algorithms for computing a safe equilibrium in both 2 and

n

-player games, as well as scalable approximation algorithms.

Sam Ganzfried

Ganzfried Research

Game Theory Nash Equilibrium Nash Equilibrium Computation

Feb 17, 2015

On Sex, Evolution, and the Multiplicative Weights Update Algorithm

We consider a recent innovative theory by Chastain et al. on the role of sex in evolution [PNAS'14]. In short, the theory suggests that the evolutionary process of gene recombination implements the celebrated multiplicative weights updates algorithm (MWUA). They prove that the population dynamics induced by sexual reproduction can be precisely modeled by genes that use MWUA as their learning strategy in a particular coordination game. The result holds in the environments of weak selection, under the assumption that the population frequencies remain a product distribution. We revisit the theory, eliminating both the requirement of weak selection and any assumption on the distribution of the population. Removing the assumption of product distributions is crucial, since as we show, this assumption is inconsistent with the population dynamics. We show that the marginal allele distributions induced by the population dynamics precisely match the marginals induced by a multiplicative weights update algorithm in this general setting, thereby affirming and substantially generalizing these earlier results. We further revise the implications for convergence and utility or fitness guarantees in coordination games. In contrast to the claim of Chastain et al.[PNAS'14], we conclude that the sexual evolutionary dynamics does not entail any property of the population distribution, beyond those already implied by convergence.

Reshef Meir, David Parkes

Harvard University

Evolutionary Game Theory Game Theory