In algorithmic game theory, a succinct game or a succinctly representable game is a game which may be represented in a size much smaller than its normal form representation. Without placing constraints on player utilities, describing a game of ${\displaystyle n}$ players, each facing ${\displaystyle s}$ strategies, requires listing ${\displaystyle ns^{n}}$ utility values. 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 (a formal definition, describing succinct games as a computational problem, is given by Papadimitriou & Roughgarden 2008).

Graphical games are games in which the utilities of each player depends on the actions of very few other players. If ${\displaystyle d}$ 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 ${\displaystyle ns^{d+1}}$, which, for a small ${\displaystyle d}$ is a considerable improvement.

It has been shown that any normal form game is reducible to a graphical game with all degrees bounded by three and with two strategies for each player. Unlike normal form games, the problem of finding a pure Nash equilibrium in graphical games (if one exists) is NP-complete. The problem of finding a (possibly mixed) Nash equilibrium in a graphical game is PPAD-complete. 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.

Sparse games are those where most of the utilities are zero. Graphical games may be seen as a special case of sparse games.

For a two player game, a sparse game may be defined as a game in which each row and column of the two payoff (utility) matrices has at most a constant number of non-zero entries. 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.

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 ${\displaystyle n}$ players play each of the ${\displaystyle s}$ strategies. Thus, describing such a game requires giving only ${\displaystyle s{\tbinom {n+s-2}{s-1}}}$ utility values.

In a symmetric game with 2 strategies there always exists a pure Nash equilibrium – although a symmetric pure Nash equilibrium may not exist. The problem of finding a pure Nash equilibrium in a symmetric game (with possibly more than two players) with a constant number of actions is in AC⁰; however, when the number of actions grows with the number of players (even linearly) the problem is NP-complete. In any symmetric game there exists a symmetric equilibrium. Given a symmetric game of n players facing k strategies, a symmetric equilibrium may be found in polynomial time if k=${\displaystyle O(\log n/\log \log n)}$. Finding a correlated equilibrium in symmetric games may be done in polynomial time.

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 ${\displaystyle sn{\tbinom {n+s-2}{s-1}}}$ utility values are required.