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 n log n {\displaystyle 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 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.
… excerpt ends here. Continue reading the full article.
