Overview

Nash equilibrium describes outcomes in strategic settings where each player’s choice is a best response to the others, making it a tool for analyzing competition, coordination, and incentives. Researchers compute equilibria in matrix games, poker, and stochastic or partially observable games using methods such as complementarity solvers, regret minimization, and policy-space response oracles. Learning approaches—including fictitious play, mirror descent, and multi-agent reinforcement learning—seek equilibria from observed payoffs or sampled interactions, with guarantees often depending on game structure and feedback available to players. A central challenge is that convergence, computational tractability, equilibrium selection, and social welfare do not always align: a stable outcome may be inefficient, and different algorithms may reach different equilibria.

Latest papers

65 papers4 papers in the last four weeks, up 33% on the four weeks before. 0.0% of all new papers.

Aug 15, 2023

Simulation-Based Evaluation of Energy-Constrained Quantum-Classical Competition

This paper develops a simulation-based framework for evaluating the energy implications of quantum and classical computing firms competing in a market with limited energy resources. We model providers as differentiated Cournot competitors whose feasible service capacity is induced by technology-specific energy scaling laws: polylogarithmic for quantum algorithms that achieve an equivalent computational target and polynomial for classical emulation. For symmetric groups of quantum and classical firms, the equilibrium reduces to a tractable two-equation system that supports large scenario sweeps over market size, technology mix, and hardware coefficients. We characterize the capacity-constrained Nash equilibrium, prove the existence of a demand scale beyond which quantum service becomes more energy efficient, and report numerical experiments calibrated to trapped-ion and Rydberg platforms. The results identify when quantum energy advantage is only asymptotic and when it becomes operationally relevant.
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.
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.
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 nn-player games, as well as scalable approximation algorithms.
Sep 17, 2021

Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness

We consider the problem of fairly allocating a set of indivisible goods to a set of strategic agents with additive valuation functions. We assume no monetary transfers and, therefore, a mechanism in our setting is an algorithm that takes as input the reported -- rather than the true -- values of the agents. Our main goal is to explore whether there exist mechanisms that have pure Nash equilibria for every instance and, at the same time, provide fairness guarantees for the allocations that correspond to these equilibria. We focus on two relaxations of envy-freeness, namely envy-freeness up to one good (EF1), and envy-freeness up to any good (EFX), and we positively answer the above question. In particular, we study two algorithms that are known to produce such allocations in the non-strategic setting: Round-Robin (EF1 allocations for any number of agents) and a cut-and-choose algorithm of Plaut and Roughgarden [SIAM Journal of Discrete Mathematics, 2020] (EFX allocations for two agents). For Round-Robin we show that all of its pure Nash equilibria induce allocations that are EF1 with respect to the underlying true values, while for the algorithm of Plaut and Roughgarden we show that the corresponding allocations not only are EFX but also satisfy maximin share fairness, something that is not true for this algorithm in the non-strategic setting! Further, we show that a weaker version of the latter result holds for any mechanism for two agents that always has pure Nash equilibria which all induce EFX allocations.