Succinct game
Succinct game
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 <math>n</math> players, each facing <math>s</math> strategies, requires listing <math>ns^n</math> 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 Finding a correlated equilibrium of a polymatrix game can be done in polynomial time.
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. 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,
}}