Graphical game theory explained
In game theory, the common ways to describe a game are the normal form and the extensive form. The graphical form is an alternate compact representation of a game using the interaction among participants.
Consider a game with
players with
strategies each. We will represent the players as nodes in a graph in which each player has a utility function that depends only on him and his neighbors. As the utility function depends on fewer other players, the graphical representation would be smaller.
Formal definition
A graphical game is represented by a graph
, in which each player is represented by a node, and there is an edge between two nodes
and
iff their utility functions are dependent on the strategy which the other player will choose. Each node
in
has a function
, where
is the degree of vertex
.
specifies the utility of player
as a function of his strategy as well as those of his neighbors.
The size of the game's representation
For a general
players game, in which each player has
possible strategies, the size of a normal form representation would be
. The size of the graphical representation for this game is
where
is the maximal node degree in the graph. If
, then the graphical game representation is much smaller.
An example
In case where each player's utility function depends only on one other player:
The maximal degree of the graph is 1, and the game can be described as
functions (tables) of size
. So, the total size of the input will be
.
Nash equilibrium
Finding Nash equilibrium in a game takes exponential time in the size of the representation. If the graphical representation of the game is a tree, we can find the equilibrium in polynomial time. In the general case, where the maximal degree of a node is 3 or more, the problem is NP-complete.
Further reading
