Nash equilibrium computation

Nash equilibrium 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 , so this is actually a multiplicative approximation: the gain cannot be more than epsilon times the highest utility.
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 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. 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 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. 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 -approximate NE in time polynomial in the input size and 1/δ. For general n-player games, the approximation ratio increases with n.

Approximation hardness

The PPAD-completeness results in in fact show that computing an ε-approximate NE is PPAD-complete, if ε is exponentially small.
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.
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

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 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, 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.
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, with a unique NE in which all the probabilities are irradical numbers.

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. 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. 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 ; 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. 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.