Inalgorithmic game theory, asuccinct game or asuccinctly representable game is a game which may be represented in a size much smaller than itsnormal form representation. Without placing constraints on player utilities, describing a game of${\displaystyle n}$ players, each facing${\displaystyle s}$strategies, requires listing${\displaystyle n{s}^n}$ utility values. Even trivial algorithms are capable of finding aNash equilibrium in a timepolynomial in the length of such a large input. A succinct game is ofpolynomial type if in a game represented by a string of lengthn the number of players, as well as the number of strategies of each player, is bounded by a polynomial inn^[1] (a formal definition, describing succinct games as acomputational problem, is given by Papadimitriou & Roughgarden 2008^[2]).

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 theindegree of the game graph), the number of utility values needed to describe the game is${\displaystyle n{s}^{d+1}}$, which, for a small${\displaystyle d}$ is a considerable improvement.

It has been shown that any normal form game isreducible to a graphical game with all degrees bounded by three and with two strategies for each player.^[3] Unlike normal form games, the problem of finding a pure Nash equilibrium in graphical games (if one exists) isNP-complete.^[4] The problem of finding a (possibly mixed) Nash equilibrium in a graphical game isPPAD-complete.^[5] Finding acorrelated equilibrium of a graphical game can be done in polynomial time, and for a graph with a boundedtreewidth, this is also true for finding anoptimal correlated equilibrium.^[2]

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 fullypolynomial-time approximation scheme unless PPAD is inP.^[6]

Insymmetric 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(\genfrac{}{}{0ex}{}{n+s-2}{s-1})}$ utility values.

In a symmetric game with 2 strategies there always exists a pure Nash equilibrium – although asymmetric pure Nash equilibrium may not exist.^[7] 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 inAC⁰; however, when the number of actions grows with the number of players (even linearly) the problem is NP-complete.^[8] In any symmetric game there exists asymmetric equilibrium. Given a symmetric game ofn players facingk strategies, a symmetric equilibrium may be found in polynomial time if k=${\displaystyle O(\log n/\log \log n)}$.^[9] Finding a correlated equilibrium in symmetric games may be done in polynomial time.^[2]

Inanonymous 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(\genfrac{}{}{0ex}{}{n+s-2}{s-1})}$ utility values are required.

If the number of actions grows with the number of players, finding a pure Nash equilibrium in an anonymous game isNP-hard.^[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 knownPTAS for finding anε-approximate Nash equilibrium.^[10]

In apolymatrix game (also known as amultimatrix game), there is a utility matrix for every pair of players(i,j), denoting a component of player i's utility. Player i's final utility is the sum of all such components. The number of utilities values required to represent such a game is${\displaystyle O(n^2\ast s^2)}$.

Polymatrix games always have at least one mixed Nash equilibrium.^[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.^[2] Note that even if pairwise games played between players have pure Nash equilibria, the global interaction does not necessarily admit a pure Nash equilibrium (although a mixed Nash equilibrium must exist). Checking if a pure Nash equilibrium exists is astrongly NP-complete problem.^[13]

Competitive polymatrix games with only zero-sum interactions between players are a generalization of two-playerzero-sum games. TheMinimax theorem originally formulated for two-player games byvon Neumann generalizes to zero-sum polymatrix games.^[14] Same as two-player zero-sum games, polymatrix zero-sum games havemixed Nash equilibria that can be computed in polynomial time and those equilibria coincide withcorrelated equilibria. But some other properties of two-player zero-sum games do not generalize. Notably, playersneed not have a unique value of the game and equilibrium strategies are not max-min strategies in a sense that worst-case payoffs of players are not maximized when using an equilibrium strategy. There exists an open source Python library^[15] for simulating competitive polymatrix games.

Polymatrix games which have coordination games on their edges arepotential games^[16] and can be solved using a potential function method.

The most flexible of way of representing a succinct game is by representing each player by a polynomial-time boundedTuring machine, which takes as its input the actions of all players and outputs the player's utility. Such a Turing machine is equivalent to aBoolean circuit, and it is this representation, known ascircuit games, that we will consider.

Computing the value of a 2-playerzero-sum circuit game is anEXP-complete problem,^[17] and approximating the value of such a game up to a multiplicative factor is known to be inPSPACE.^[18] Determining whether a pure Nash equilibrium exists is a${\displaystyle {\mathrm{\Sigma }}_2^{\mathrm{P}}}$-complete problem (seePolynomial hierarchy).^[19]

Many other types of succinct game exist (many having to do with allocation of resources). Examples includecongestion games,network congestion games,scheduling games,local effect games,facility location games,action-graph games,hypergraphical games and more.

Below is a table of some known complexity results for finding certain classes of equilibria in several game representations. "NE" stands for "Nash equilibrium", and "CE" for "correlated equilibrium".n is the number of players ands is the number of strategies each player faces (we're assuming all players face the same number of strategies). In graphical games,d is the maximum indegree of the game graph. For references, see main article text.

Representation	Size (O(...))	Pure NE	Mixed NE	CE	Optimal CE
Normal form game	${\displaystyle n{s}^n}$	NP-complete	PPAD-complete	P	P
Graphical game	${\displaystyle n{s}^{d+1}}$	NP-complete	PPAD-complete	P	NP-hard
Symmetric game	${\displaystyle s(\genfrac{}{}{0ex}{}{n+s-2}{s-1})}$	NP-complete	The computation of symmetric Nash equilibrium is PPAD-hard for two players. The computation of non-symmetric Nash equilibrium for two players is NP-complete.	P	P
Anonymous game	${\displaystyle sn(\genfrac{}{}{0ex}{}{n+s-2}{s-1})}$	NP-hard		P	P
Polymatrix game	${\displaystyle n^2{s}^2}$	strongly NP-complete	PPAD-complete (polynomial for zero-sum polymatrix)	P	NP-hard
Circuit game		${\displaystyle {\mathrm{\Sigma }}_2^{\mathrm{P}}}$-complete
Congestion game		PLS-complete		P	NP-hard

• Algorithmic Game Theory: The Computational Complexity of Pure Nash

• Game theory game classes

• Articles with short description
• Short description is different from Wikidata