Nash equilibrium computation

When mixed strategies are allowed, every game has a Nash equilibrium. This was proved by John Nash in 1950 using the Kakutani fixed-point theorem, and later in 1951 using the Brouwer fixed-point theorem. For games with a small number of actions per player, a NE can be computed manually by solving a set of equations. However, when the number of actions per player grows, the number of possible strategy vectors grows exponentially, and the computation becomes computationally hard. Non-polynomial-time algorithms There are various algorithms that work well in practice, but do not guarantee termination in polynomial time. One of the most famous such algorithms is the Lemke–Howson algorithm. Porter, Nudelman and Shoham present an algorithm based on simple search heuristics, that performs well in practice on a large variety of games. They use the GAMUT testbed for testing the performance of their algorithm. Lipton, Markakis and Mehta presented a Quasi-polynomial time algorithm for computing an approximate NE. It takes time n^{\log n}, where n is the number of possible actions per player. They do it by proving the existence of an approximate NE strategies with support logarithmic in n, and proving that the payoffs to all players in any exact NE can be ε-approximated by such an approximate NE. They also prove that, if the payoff matrices have constant rank, then an exact NE can be found in polytime. Computational hardness Daskalakis, Goldberg and Papadimitriou proved that finding a NE is PPAD-complete in games with four or more players; later, Chen and Deng extended the result even for two-player games (bimatrix games). Under standard complexity assumptions, these hardness results imply that no polynomial-time algorithm is expected for general equilibrium computation. Computing a Nash equilibrium is PPAD-complete even for win-lose bimartix games, that is, two-player games in which the payoff of each player is either 0 or 1. Etessami and Yannakkis (who defined the complexity class FIXP) proved that computing an exact or approximate NE for 3 or more players is FIXP-complete. They also show that computing an approximate NE with any approximation factor smaller than 1/2 is at least as hard as the square-root sum problem, as well as a more general arithmetic circuit decision problem. Approximation algorithms Tsaknakis and Spirakis presented a polytime algorithm that finds an 0.3393-approximate NE for a bimatrix game (that is, the gain from deviation cannot be more than 0.3393 times the maximum utility). Their algorithm minimizes a certain function, representing the distance from NE, using gradient descent. The procedure converges in polynomial time to local optima which are 0.3393-approximate NE. Deligkas, Fearnley, Savani and Spirakis extend the descent techniques to polymatrix games, attaining an (0.5+δ)-approximate NE in time polynomial in the input size and 1/δ. For general n-player games, the approximation ratio increases with n (e.g. it is 0.6022 for n=3 and 0.7153 for n=4). Approximation hardness The PPAD-completeness results in showed that finding an ε-approximate Nash equilibrium is PPAD-complete even for a simple class of games: graphical games of degree three, in which each agent has only two actions; and even when ε is a constant. In particular, there is no PTAS for NE in general games (He also proved inapproximability for other related problems, such as: Bayesian Nash equilibrium in a two-player game, relative ε-Nash equilibrium in a two-player game, market equilibrium in a non-monotone market as well as approximate competitive equilibrium from equal incomes). Later, Rubinstein proved that, assuming the Exponential time hypothesis for PPAD, there exists a positive constant ε such that computing ε-approximate NE in a two-player game with n actions per player requires quasi-polynomial time, as in the proved that no algorithm for computing NE in a two-player game has smoothed complexity polynomial in n and 1/s, where s is the input perturbation size, unless PPAD ≤ RP. In particular, the smoothed complexity of the Lemke-Howson algorithm is probably not polynomial. • Boodaghians, Brakensiek, Hopkins and Rubinstein prove that computing NE in a 2-player game is PPAD-hard (under randomized reductions) even when smoothing with noise of constant magnitude. Irrationality of outcomes All two-player games with rational payoff matrices always have only NE with rational probabilities. However, there are three-player games with rational payoff matrices, in which every NE requires irrational probabilities, which cannot be output accurately in finite time. An example was already shown by Nash: it is a three-player game where each player has only two possible actions "0" and "1". There is a unique NE in which all players choose "0" with probabilities that are linear functions of sqrt(409). Datta shows that every real algebraic variety is isomorphic to the set of totally mixed Nash equilibria of some three-person game, and also to the set of totally mixed Nash equilibria of an n-person game in which each player has two actions. This means that, in each of these classes, there are games whose probabilities require roots of any real polynomial. Orzech and Rinard show that, for any n ≥ 4, there is an n-player game where all payoffs are in {0,1,2}, with a unique NE in which all the probabilities are irradical numbers (algebraic numbers that cannot be expressed with m-th roots for any integer m). Two-Player Zero-Sum Games Two-player zero-sum games represent the most fundamental class with polynomial-time equilibrium computation. In these games, one player's gain equals the other's loss, creating a pure conflict scenario. The key insight is that NE in zero-sum games correspond to minimax strategies, which can be computed via linear programming. For a zero-sum game with payoff matrix A for the row player, the minimax theorem of John von Neumann establishes that the game value can be computed by solving dual linear programs. Since linear programming can be solved in polynomial time using interior-point methods or the ellipsoid algorithm, NE can be computed in time polynomial in the size of the payoff matrices. Anonymous games In an anonymous game, the payoff of each player depends only on his own strategy and on the number of players taking every strategy, but not on their identity. Anonymous games admit efficient computation of approximate NE. In particular: • Daskalakis and Papadimitriou presented polytime approximation algorithms for games with many players but few strategies (s strategies per player). Their algorithm computes a s^2L-approximate pure NE, where L is the Lipschitz constant of the utility functions. They also show a PTAS for mixed NE when s=2. In a later work, they prove that approximate mixed NE in anonymous games can be computed in polytime to any desired accuracy, if the number of strategies is a constant (i.e., there is a PTAS). Moreover, if the utility functions are Lipschitz continuous, one can compute in polytime an approximate pure NE, whose quality depends on the number of strategies and the Lipschitz constant. If the game has two strategies, there always exists an approximate NE in which either only a small number of players randomize, or of those who do, they all randomize the same way. • Cheng, Diakonikolas and Stewart present other algorithms for finding approximate mixed NE in anonymous games, where the strategies of the players are "simple": each player plays one strategy with probability 1—δ, for some small δ, and plays uniformly at random with probability δ. • In contrast, Chen Durfee and Orfanou prove that, if the approximation parameter is exponentially small in the number of players, then the problem is PPAD-complete when there are at least 7 strategies. Graphical Games Graphical games represent strategic interactions using graphs where each player's payoff depends only on neighbors' actions, enabling algorithms that exploit sparsity. In general, computing NE on graphical games is still PPAD-hard, even if the graph degree is at most 3 and each player has only 2 actions. However, when the graph is a tree with a bounded degree, more efficient algorithms are possible. Kearns, Littman and Singh presented a dynamic programming algorithm for computing all NE of a tree-graphical game (with two actions per player); its run-time is exponential, but it allows to compute approximate NE in polynomial time. The algorithm requires only messages between neighboring nodes, and thus can be implemented in a distributed fashion. They then proposed a modification that can find a single NE in polytime. However, Elkind, Goldberg and Goldberg study graphical games in which the best response function of each player is a linear function of the actions of his neighbors. They prove that the Nash equilibrium depends only on a single parameter of the graph: the smallest eigenvalue of the matrix representing the graph. Hence, it can be computed efficiently. Win-Lose Games Win-lose games are games in which all payoffs are either 0 or 1. • Codenotti, Leoncini and Resta presented a linear-time algorithm for win-lose bimatrix games where the number of winning positions per strategy of each of the players is at most two. • Liu, Li and Deng showed that, for polymatrix games, approximating a Nash equilibrium with polynomial precision is PPAD-hard, even for sparse win-lose games. Bounded-rank bimatrix games Rank-1 bimatrix games have payoff matrices that can be written as outer products of vectors. Adsul, Garg, Mehta and Sohoni presented a polytime algorithm for exact NE. They also presented an algorithm to enumerate all the NE of a rank-1 game.\ Bounded rank bimatrix games: Lipton, Markakis and Mehta) clearly have pure-strategy NE that can be computed efficiently. But even for first-price auctions, which do not have dominant strategies, it is often possible to compute NE directly, by direct computation using knowledge of agents' distributions. For example, when all n buyers have uniform valuations on [0,1], the equilibrium bidding function is: b(v) = (n-1)v/n. == Pure-strategy equilibria ==

A pure-strategy Nash equilibrium (PNE) is not guaranteed to exist in general games, though there are special classes of games in which a PNE always exists. Deciding existence Gottlob, Greco and Sarcello prove that, even in very restrictive settings, deciding the existence of a PNE is NP-hard. Deciding the existence of a strong Nash equilibrium is even harder: it is ΣP2-complete. However, when the utility function for each player depends only on the actions of a logarithmically small number of other players (that is, the dependency graph of the game has a small degree), then finding a PNE can be done in polytime. For graphical games, these problems are LOGCFL-complete. Anonymous games Daskalakis and Papadimitriou This immediately gives a simple algorithm: start with any strategy profile; while some player can improve their payoff by switching strategies - let that player switch to a better strategy; return the final strategy profile (guaranteed to be a Nash equilibrium). However, this algorithm might go through exponentially many different states before it converges. Fabrikant, Papadimitriou and Talwar studied the special case of congestion games (which are equivalent to exact potential games). They proved that: • PNE can be found in polytime in the special case of symmetric network congestion games. Such a game is represented by a directed graph with two nodes marked as "source" and "target". The set of actions available to each player is the set of paths from the source to the target. For each edge, there is a delay which is a function of the number of players who use it. The payoff to each player is minus the total delay on his chosen path. In this special case, a PNE can be computed in polynomial time by maximizing the potential, through reduction to min-cost flow. • In contrast, for asymmetric network congestion games (which are network congestion games in which each player has a different source and a different target), computing a PNE is PLS-complete. The same holds for non-network congestion games (games in which all agents have the same set of strategies, but it is not the set of paths in any graph), whether symmetric or not. The proof implies that there are examples of such games in which some improvement paths are exponentially long. It also implies that the problem of finding a PNE reachable from a given input state is PSPACE-complete. • The class of ordinal potential games is even larger than the class of congestion games: every problem in the class PLS can be presented as an ordinal potential game, where the set of PNE coincides with the set of local optima. They also study the case of nonatomic congestion games. Computing a PNE in a nonatomic congestion game can be rephrased as a convex optimization problem, and thus can be approximated in wealky-polynomial time (e.g. by the ellipsoid method). Fabrikant, Papadimitriou and Talwar prove that, if the strategy space of each player consists of the bases of a matroid over the set of resources, then all best-response sequences converge in polynomial number of steps, and the matroid property is essential for guaranteeing polynomial-time convergence. They also present a simpler technique for hardness proofs; using this technique, they prove that computing a PNE in (asymmetric) network congestion games is PLS-complete for directed and undirected networks, even if all delay functions are linear. Chien and Sinclair study an "ε-greedy dynamics" in which, at each step, some player plays a move that decreases its cost by at least a factor of (1+ε). They prove that, in symmetric congestion games, when the delay functions satisfy some technical condition they call "bounded-jump", this ε-greedy dynamics converges to an ε-approximate PNE in a number of steps polynomial in the number of players and 1/ε. This result holds for various update policies and sequences, as long as they satisfy the weak condition that each player has an opportunity to play eventually. The result holds even when a constant number of resources have arbitrary cost functions. Skopalik and Vocking prove that, in general congestion games, even computing an ε-approximate PNE, for any polynomial-time computable ε, is PLS-complete. Their reduction also implies that computing an ε-approximate equilibrium reachable from a given initial state is PSPACE-complete. They also present asymmetric congestion with the bounded-jump condition in which, for some states, every ε-greedy sequence might have exponential length. Caragiannis, Fanelli, Gravin and Skopalik study general congestion games (possibly asymmetric). They present an algorithm that computes a constant-factor approximation PNE. In particular: • With linear delay functions, the approximation ratio is 2+ε, and the runtime is polynomial in the number of players, the number of resources, and 1/ε. • When delay functions are degree-d polynomials, the approximation ratio is dO(d). Their algorithm identifies a short sequence of best-response moves, that leads to an approximate equilibrium. They also show that, for congestion games with more general delay functions (not bounded-degree polynomial), attaining any polynomial approximation of PNE is PLS-complete. Del-Pia, Ferris and Michini introduce totally-unimodular (TU) CGs, where the players’ strategies are binary vectors in polyhedra defined by totally unimodular constraint matrices. This is a generalization of network CGs. They prove that: • In symmetric TUCGs, there is a strongly-polytime algorithm for finding a PNE, and for maximizing the social welfare, if the delay functions are convex. The technique can be adapted to matroid CGs. • In asymmetric TUCGs, in the special cases in which the strategies are matchings, vertex covers, edge covers, or independent sets of a bipartite graph, it is PLS-complete to find a PNE even with linear delays, and welfare maximization is NP-hard even with weakly convex delays. Harks, Klimm and Peis present a pseudo-polytime algorithm that computes a PNE for polymatroid CGs with player-specific delay functions and polynomially-bounded demands. Even-Dar, Kesselman and Mansour analyze a job scheduling setting where each job is a player. Each job is mapped to a machine. The cost of each job is determined by the load on that machine (all jobs mapped to the same machine have the same cost). Each job in turn moves to a machine that decreases or minimizes its cost (that is, plays a better response or a best response). They study how much steps are required for the system to converge to a Nash equilibrium. They study scheduling on Identical machines, uniform machines and unrelated machines; they also study various policies regarding the sequence of jobs that are allowed to make an improving move. Their upper bound for the most general case (unrelated machines, general real weights) is \min\left([O(\frac{n}{Km}+1)]^{Km}, m^n\right), where m is the number of machines, n the number of jobs, and K the number of different weights. On the other extreme, for the case of identical machines, there are policies that converge in at most n steps, or in O(n2) steps. Fabrikant, Jaggard and Schapira study weakly-acyclic games - a generalization of potential games in which, from any starting state, there is a sequence of better-response moves that leads to a PNE, so that natural distributed dynamics cannot enter "inescapable oscillations". Babichenko and Rubinstein prove that finding a NE (possibly mixed) in congestion games is equivalent to finding an exponential precision fixed point of the gradient descent dynamics of a smooth function, which can be given either by an\ arithmetic circuit or by a degree-5 polynomial. This implies that these problems are complete for the intersection of PPAD and PLS. Generalized congestion games A weighted CG is a congestion game in which each player may have a different weight, and the delay of a resource is the sum of weights of the players using the resource. A player-specific-cost CG is a congestion game in which each player has a different delay function. Both these generalized CGs do not necessarily have a potential, and do not necessarily have a PNE. Dunkel and Schulz prove that deciding whether a given network weighted CG has a PNE is strongly NP-hard. This is true even if the flow is splittable (i.e., each player may split his flow among different routes). If the flow is unsplittable, the problem is strongly NP-hard even for a fixed number of players. Milchtaich proves that deciding whether a given network CG has a PNE is NP-hard even in the following cases: • Weighted network CG with two players with the same delay functions; all players are allowed to use all paths; all delay functions are nonnegative. • Unweighted network CG with two players with different delay functions; all delay functions are nonnegative. The proof is by reduction from the directed edge-disjoint paths problem. Fotakis, Kontogiannis and Spirakis present an algorithm that, in any weighted network CG with linear delay functions, finds a PNE in pseudo-polynomial time (polynomial in the number of players n and the sum of players' weights W). Their algorithm is a greedy best-response algorithm: players enter the game in descending order of their weight, and choose a best-response to existing players' strategies. Panagopoulou and Spirakis show empirical evidence that the algorithm of Fotakis, Kontogiannis and Spirakis in fact runs in time polynomial in n and log W. They also propose an initial strategy-vector that dramatically speeds this algorithm. Caragiannis, Fanelli, Gravin and Skopalik present an algorithm that computes a constant-factor approximation PNE in weighted CGs. In particular: • With linear delay functions, the approximation ratio is \frac{3+\sqrt{5}}{2}+O(\epsilon), and the runtime is polynomial in the number of playres, the number of resources, and 1/ε. • When delay functions are degree-d polynomials, the approximation ratio is d^{2d + o(d)}. To prove their results, they show that, although weighted CGs may not have a potential function, every weighted CG can be approximated by a certain potential game. This lets them show that every weighted CG has a (d!)-approximate PNE. Their algorithm identifies a short sequence of best-response moves, that leads to such an approximate PNE. Local effect games Dunkel and Schulz proves, using fixed-point arguments, that some submodular games always have a PNE. Two algorithms, corresponding to fictitious play in dynamic games, generate sequences of feasible joint decisions converging monotonically to a PNE. Concave Games Concave games (where each player's payoff function is concave in their own strategy) admit efficient computation via convex optimization techniques. == Correlated equilibria ==

Correlated equilibria are, in general, computationally easier to find. Hart and Mas-Collel present a dynamic called ‘regret-matching’, in which players depart from their current play with probabilities proportional to regret for not having used other strategies previously. These dynamics converge with probability 1 to the set of correlated equilibria. Papadimitriou and Roughgarden studied the computational problem of finding a correlated equilibrium (CE). They presented a polytiime algorithm for finding a CE in various multiplayer games, such as graphical games, symmetric (anonymous) games, polymatrix games, congestion games, scheduling games and local effect games. They also studied the problem of optimizing a linear function of the set of CE. For this problem, they give a polytime algorithm for two cases: symmetric games, and graphical games of bounded treewidth; and prove NP-hardness for the other classes of games. Siddharth Barman and Katrina Ligett further studied the question of how to find a "good" CE (a CE with a high social welfare). They proved strong negative results in multiplayer games with succinct representation, it is NP-hard to compute any coarse CE with utilitarian welfare strictly better than the worst possible. Similar results hold for CE. Similar results hold also for egalitarian welfare and for Pareto efficiency. On the positive side, they present a polytime algorithm for computing an approximate CE with near-optimal welfare in aggregative games. == Repeated games ==

In a repeated game, the strategy of each player is a finite-state machine. Gilboa studies the following problem: given a game and the FSM-s of some n-1 players, find a best response FSM for the n-th player. The problem is polytime solvable when n is fixed, but computationally hard when n is part of the input. Littman and Stone present a polytime algorithm computing NE for an average-payoff repeated game between two players. Their algorithm relies on the folk theorem. It computes finite-state equilibrium strategies which can be succinctly represented. == Related computational problems ==

Besides the problem of computing a NE, other related problems have been studied. Gilboa and Zemel study the following decision problems: • Is there a NE in which all players' expected payoff is at least r (given in the input)? This is NP-hard (NP-complete for 2 players). • Is there a unique NE? This is NP-hard (CoNP-complete for 2 players). • Is there a NE in which each player i plays only actions from a subset Ti (given in the input)? This is NP-hard (NP-complete for 2 players). • Is there a NE in which each player i plays all actions from a subset Ti (given in the input) with positive probability? This is NP-hard (NP-complete for 2 players). • Is there a NE in which each player i plays at least r (given in the input) actions with positive probability? This is NP-hard (NP-complete for 2 players). • Is there a NE in which each player i plays at most r (given in the input) actions with positive probability? This is NP-hard (NP-complete for 2 players; NP-hard even for zero-sum games). For correlated equilibria, problems 1--5 are polytime solvable, whereas problem 6 is still NP-hard even for zero-sum games (NP-complete for any number of players). Conitzer and Sandholm prove the following hardness results, even for symmetric games for two players: • It is NP-hard to approximate some maximization problems on the set of NE; • It is #P-hard to count the Nash equilibria; • It is NP-complete to decide whether a pure-strategy Bayes–Nash equilibrium exists in a Bayesian game; • It is PSPACE-hard to decide whether a pure-strategy Nash equilibrium exists in a Markov game. Bilo and Mavronicolas they study a more general decision problem: does a given game nas a NE with certain natural properties? They show, using a general reduction, that most decision problems proved to be NP-complete for two player games, becomes ∃\mathbb{R}-complete for multiplayer games. == Concave games ==

A concave game is a generalization of a normal-form game in which the space of strategy profiles can be an arbitrary convex set (rather than just a Cartesian product of simplices). Papadimitriou, Vlatakis-Gkaragkounis and Zampetakis prove that computing an equilibrium in a concave game is PPAD-complete. In fact, they prove that the problem is in PPAD even for general concave games, and it is PPAD-hard even in the special case of strongly-concave utilities that can be expressed as multivariate polynomials of a constant degree with axis aligned box constraints. Chernov presents some numeric approaches, related to convex optimization, for computing an equilibrium == Recent developments and modern approaches ==

Machine learning methods Deep learning approaches have emerged as promising techniques for large-scale equilibrium computation. Li, Long and Deng introduce the Deep Iterative Nash Equilibrium Solver (DINES), that integrates deep learning into iterative algorithms, achieving polynomial time complexity by leveraging query-based access to utility functions rather than requiring full utility matrices. Reinforcement learning approaches enabled advances in Nash equilibrium computation. Zhang, Wang, Cui, Zhou, Kakade and Du introduce Preference-Based Multi-Agent Reinforcement Learning (PbMARL), which addresses Nash equilibrium identification from preference-only offline datasets. They show that single-policy coverage—sufficient for single-agent reinforcement learning—is inadequate for multi-agent settings, requiring unilateral dataset coverage conditions. Generative adversarial networks Generative Adversarial Networks (GANs) are a tool for training models for image identification, by modeling this as a game between the identifier and an adversary. Heusel, Ramsauer, Unterthiner, Nessler and Hochreiter introduce a Two Time-Scale Update Rule (TTUR). Using the theory of stochastic approximation, they prove that it converges to a local Nash equilibrium of the GAN training game. Blockchain systems Reynouard, Laraki and Gorelkina apply Nash equilibrium analysis to Blockchain systems through BAR Nash Equilibrium (BARNE) - equilibrium among Byzantine, Altruistic, and Rational agents. This framework addresses the verifier's dilemma in cryptocurrency systems, demonstrating how fines and forced errors can reestablish honest behavior as globally stable equilibria. == Software and practical implementations ==

Computational tools Gambit is the primary comprehensive software package for game theory computations, supporting both extensive-form and strategic-form games. Version 16.0 includes implementations of the Lemke-Howson algorithm, simplicial subdivision methods, and quantal response equilibrium computation, with both GUI and command-line interfaces plus Python integration. Specialized tools include Game Theory Explorer (GTE) for web-based small game analysis, and various research implementations focusing on specific algorithms. Integration with modern deep learning frameworks (PyTorch, TensorFlow) enables scalable implementations and GPU acceleration for large-scale problems. Scalability challenges Computational scaling presents the primary practical limitation, with exponential growth in complexity as games increase in size. Current approaches handle small-to-medium games (up to roughly 100×100 strategies) through approximation algorithms, while larger games require heuristic methods. Numerical stability issues arise from degenerate linear systems and floating-point precision limitations in equilibrium computation. Rational arithmetic implementations provide exact computation but at significant computational cost, making ε-equilibria the practical standard for providing robustness to numerical errors. == Further reading ==