Nash equilibrium (NE) computation is a class of computational problems in the intersection of game theory and computer science. The input to this problem is a normal-form game, usually represented as a list of payoff matrices. The required output is a Nash equilibrium of the game.
NE computation can be broadly divided into computing mixed-strategy NE vs computing pure-strategy NE. In each of these cases, one can consider computing an exact NE or an epsilon-approximate NE:
In an exact NE, no player can gain by deviating; In an epsilon-approximate NE, no player can gain more than epsilon by deviating. The utilities are normalized to [0,1], so this is actually a multiplicative approximation: the gain cannot be more than epsilon times the highest utility. The special case of NE computation in two-player zero-sum games is known as min-max optimization. The present page studies the more general problem of non-zero-sum games with many players.
Mixed-strategy equilibria 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 , 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 PapadimitriouConstantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou (2009). "The complexity of computing a Nash equilibrium." proved that finding a NE is PPAD-complete in games with four or more players; later, Chen and DengXi Chen and Xiaotie Deng (2006),"Settling the complexity of two-player Nash equilibrium." 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 261–272. 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 bimatrix 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 in fact show that computing an ε-approximate NE is PPAD-complete, if ε is exponentially small (smaller than 2-m, where m is the number of actions per player).
Chen Deng and Teng proved PPAD-hardness even for ε that is polynomially small. In other words, they proved that no algorithm with runtime polynomial in n and 1/ε can compute an ε-approximate Nash equilibrium in a two-player game with n actions per player, unless PPAD ≤ P. In particular, this means that there is probably no FPTAS for NE.
Aviad Rubinstein 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 algorithm.
Smoothed complexity Smoothed analysis has been used to prove that many problems that are computationally-hard in the worst case, are in fact "almost always" easy, that is, if a problem is perturbed randomly, then the perturbed problem is easy. Interestingly, this is not the case for the problem of computing a NE. In particular:
Chen, Deng and Teng 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 simplified variant of Poker for three players, with a unique NE in which all probabilities are linear functions of sqrt(321), which is an irrational number. Another example can be found in : 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 -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 showed that the modification is incorrect (does not always find a NE). Based on their ideas, they proposed a new algorithm that computes all NE in quadratic time for a path graph, and in polynomial time for a general graph of degree at most 2. For general trees, the run-time of this algorithm is exponential even when the tree has bounded degree and its pathwidth is 2, but the same is true for any algorithm of the same kind. Finding a NE for a degree-3 graphical game with constant pathwidth and 2 actions per player is PPAD-complete.
Bramoulle, Kranton and D'Amours 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