Graphical game theory

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 ${\displaystyle n}$ players with ${\displaystyle m}$ 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 ${\displaystyle G}$ , in which each player is represented by a node, and there is an edge between two nodes ${\displaystyle i}$  and ${\displaystyle j}$  ${\displaystyle iff}$  their utility functions are depended on the strategy which the other player will choose . Each node ${\displaystyle i}$  in ${\displaystyle G}$  has a function ${\displaystyle u_{i}:\{1\ldots m\}^{d_{i}+1}\rightarrow \mathbb {R} }$ , where ${\displaystyle d_{i}}$  is the degree of vertex ${\displaystyle i}$ . ${\displaystyle u_{i}}$  specifies the utility of player ${\displaystyle i}$  as a function of his strategy as well as those of his neighbors.

The size of the game's representation

For a general ${\displaystyle n}$  players game, in which each player has ${\displaystyle m}$  possible strategies, the size of a normal form representation would be ${\displaystyle O(m^{n})}$ . The size of the graphical representation for this game is ${\displaystyle O(m^{d})}$  where ${\displaystyle d}$  is the maximal node degree in the graph. If ${\displaystyle d\ll n}$ , 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 graphical form of the described game

The maximal degree of the graph is 1, and the game can be described as ${\displaystyle n}$  functions (tables) of size ${\displaystyle m^{2}}$ . So, the total size of the input will be ${\displaystyle nm^{2}}$ .

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.