Without placing constraints on player utilities, describing a game of
Even trivial algorithms are capable of finding a Nash equilibrium in a time polynomial in the length of such a large input.
A succinct game is of polynomial type if in a game represented by a string of length n the number of players, as well as the number of strategies of each player, is bounded by a polynomial in n[1] (a formal definition, describing succinct games as a computational problem, is given by Papadimitriou & Roughgarden 2008[2]).
is the greatest number of players by whose actions any single player is affected (that is, it is the indegree of the game graph), the number of utility values needed to describe the game is
[4] The problem of finding a (possibly mixed) Nash equilibrium in a graphical game is PPAD-complete.
[5] Finding a correlated equilibrium of a graphical game can be done in polynomial time, and for a graph with a bounded treewidth, this is also true for finding an optimal correlated equilibrium.
It has been shown that finding a Nash equilibrium in such a sparse game is PPAD-hard, and that there does not exist a fully polynomial-time approximation scheme unless PPAD is in P.[6] In symmetric games all players are identical, so in evaluating the utility of a combination of strategies, all that matters is how many of the
In a symmetric game with 2 strategies there always exists a pure Nash equilibrium – although a symmetric pure Nash equilibrium may not exist.
[9] Finding a correlated equilibrium in symmetric games may be done in polynomial time.
[2] In anonymous games, players have different utilities but do not distinguish between other players (for instance, having to choose between "go to cinema" and "go to bar" while caring only how crowded will each place be, not who'll they meet there).
In such a game a player's utility again depends on how many of his peers choose which strategy, and his own, so
[8] An optimal correlated equilibrium of an anonymous game may be found in polynomial time.
[2] When the number of strategies is 2, there is a known PTAS for finding an ε-approximate Nash equilibrium.
The number of utilities values required to represent such a game is
[11] The problem of finding a Nash equilibrium in a polymatrix game is PPAD-complete.
[5] Moreover, the problem of finding a constant approximate Nash equilibrium in a polymatrix game is also PPAD-complete.
[12] Finding a correlated equilibrium of a polymatrix game can be done in polynomial time.
Checking if a pure Nash equilibrium exists is a strongly NP-complete problem.
There exists an open source Python library[15] for simulating competitive polymatrix games.
Computing the value of a 2-player zero-sum circuit game is an EXP-complete problem,[17] and approximating the value of such a game up to a multiplicative factor is known to be in PSPACE.
[19] Many other types of succinct game exist (many having to do with allocation of resources).
Below is a table of some known complexity results for finding certain classes of equilibria in several game representations.