| Consider a game of three players, I,II and III, facing, respectively, the strategies,, and . Without further constraints, 3*23=24 utility values would be required to describe such a game. | |||||
| L, l | L, r | R, l | R, r | ||
|---|---|---|---|---|---|
| T | ,, | ,, | ,, | ,, | |
| B | ,, | ,, | ,, | ,, | |
| For each strategy profile, the utility of the first player is listed first, and is followed by the utilities of the second player and the third player . | |||||
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
n
s
nsn
| Say that each player's utility depends only on his own action and the action of one other player - for instance, I depends on II, II on III and III on I. Representing such a game would require only three 2x2 utility tables, containing in all only 12 utility values. |
d
nsd+1
d
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.
| When most of the utilities are 0, as below, it is easy to come up with a succinct representation. | |||||
| L, l | L, r | R, l | R, r | ||
|---|---|---|---|---|---|
| T | ,, | ,, | ,, | ,, | |
| B | ,, | ,, | ,, | ,, | |
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.
| Suppose all three players are identical (we'll color them all), and face the strategy set . Let #TP and #BP be the number of a player's peers who've chosen T and B, respectively. Describing this game requires only 6 utility values. |
n
s
s\tbinom{n+s-2}{s-1}
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=
O(logn/loglogn)
| If players were different but did not distinguish between other players we would need to list 18 utility values to represent the game - one table such as that given for "symmetric games" above for each player. |
sn\tbinom{n+s-2}{s-1}
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.
| If the game in question was a polymatrix game, describing it would require 24 utility values. For simplicity, let us examine only the utilities of player I (we would need two more such tables for each of the other players). If strategy profile (B,R,l) was chosen, player I's utility would be 9+8=17, player II's utility would be 1+2=3, and player III's utility would be 6+4=10. |
O(n2*s2)
Polymatrix games always have at least one mixed Nash equilibrium. The problem of finding a Nash equilibrium in a polymatrix game is PPAD-complete. Moreover, the problem of finding a constant approximate Nash equilibrium in a polymatrix game is also PPAD-complete.[1] Finding a correlated equilibrium of a polymatrix game can be done in polynomial time. 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 a strongly NP-complete problem.[2]
Competitive polymatrix games with only zero-sum interactions between players are a generalization of two-player zero-sum games. The Minimax theorem originally formulated for two-player games by von Neumann generalizes to zero-sum polymatrix games.[3] 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[4] for simulating competitive polymatrix games.
Polymatrix games which have coordination games on their edges are potential games [5] and can be solved using a potential function method.
| Let us now equate the players' various strategies with the Boolean values "0" and "1", and let X stand for player I's choice, Y for player II's choice and Z for player III's choice. Let us assign each player a circuit: Player I: X ∧ (Y ∨ Z) | --xor'd-->Player III: X ∨ YThese describe the utility table below. | ||||
|---|---|---|---|---|---|
| 0, 0 | 0, 1 | 1, 0 | 1, 1 | ||
| 0 | ,, | ,, | ,, | ,, | |
| 1 | ,, | ,, | ,, | ,, | |
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
| \rmP | |
| \Sigma | |
| 2 |
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.
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.
| Representation | Size (O(...)) | Pure NE | Mixed NE | CE | Optimal CE | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Normal form game | nsn | NP-complete | PPAD-complete | P | P | ||||||
| Graphical game | nsd+1 | NP-complete | PPAD-complete | P | NP-hard | ||||||
| Symmetric game | s\tbinom{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 | sn\tbinom{n+s-2}{s-1} | NP-hard | P | P | |||||||
| Polymatrix game | n2s2 | strongly NP-complete | PPAD-complete (polynomial for zero-sum polymatrix) | P | NP-hard | ||||||
| Circuit game |
| ||||||||||
| Congestion game | P | NP-hard |