Graphical games Graphical games are games in which the utilities of each player depends on the actions of very few other players. If 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 ns^{d+1}, which, for a small 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. Finding a correlated equilibrium of a polymatrix game can be done in polynomial time. Same as two-player zero-sum games, polymatrix zero-sum games have
mixed Nash equilibria that can be computed in polynomial time and those equilibria coincide with
correlated equilibria. But some other properties of two-player zero-sum games do not generalize. Notably, players
need 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 for simulating competitive polymatrix games. Polymatrix games which have coordination games on their edges are
potential games and can be solved using a potential function method.
Circuit games The most flexible of way of representing a succinct game is by representing each player by a polynomial-time bounded
Turing machine, which takes as its input the actions of all players and outputs the player's utility. Such a Turing machine is equivalent to a
Boolean circuit, and it is this representation, known as
circuit games, that we will consider. Computing the value of a 2-player
zero-sum circuit game is an
EXP-complete problem, and approximating the value of such a game up to a multiplicative factor is known to be in
PSPACE. Determining whether a pure Nash equilibrium exists is a \Sigma_2^{\rm P}-complete problem (see
Polynomial hierarchy).
Other representations Many other types of succinct game exist (many having to do with allocation of resources). Examples include
congestion games,
network congestion games,
scheduling games,
local effect games,
facility location games,
action-graph games,
hypergraphical games and more. ==Summary of complexities of finding equilibria==