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.

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}$ 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.

...
Wikipedia