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.
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.
A graphical game is represented by a graph
iff their utility functions are dependent on the strategy which the other player will choose.
specifies the utility of player
as a function of his strategy as well as those of his neighbors.
possible strategies, the size of a normal form representation would be
The size of the graphical representation for this game is
is the maximal node degree in the graph.
, then the graphical game representation is much smaller.
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
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.