title: Graphical game theory
text: # 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 $n$ players with $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 $G$, in which each player is represented by a node, and there is an edge between two nodes $i$ and $j$ iff their utility functions are dependent on the strategy which the other player will choose. Each node $i$ in $G$ has a function $u_{i}:\{1\ldots m\}^{d_{i}+1}\rightarrow \mathbb {R}$, where $d_{i}$ is the degree of vertex $i$. $u_{i}$ specifies the utility of player $i$ as a function of his strategy as well as those of his neighbors.
  
  ## The size of the game's representation
  
  For a general $n$ players game, in which each player has $m$ possible strategies, the size of a normal form representation would be $O(m^{n})$. The size of the graphical representation for this game is $O(m^{d})$ where $d$ is the maximal node degree in the graph. If $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 $n$ functions (tables) of size $m^{2}$. So, the total size of the input will be $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.
  
  