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
Contents
Graphical games
Graphical games are games in which the utilities of each player depends on the actions of very few other players. If
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
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.
Symmetric games
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. 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 AC0; 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=
Anonymous games
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
If the number of actions grows with the number of players, finding a pure Nash equilibrium in an anonymous game is NP-hard. An optimal correlated equilibrium of an anonymous game may be found in polynomial time. When the number of strategies is 2, there is a known PTAS for finding an ε-approximate Nash equilibrium.
Polymatrix games
In a polymatrix game (also known as a multimatrix 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
Polymatrix games always have at least one mixed Nash equilibrium. The problem of finding a Nash equilibrium in a polymatrix game is PPAD-complete. Finding a correlated equilibrium of a polymatrix game can be done in polynomial time.
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
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
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 and s 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.