Graphical game theory

In game theory, the graphical form or graphical game is an alternate compact representation of strategic interactions that efficiently models situations where players' outcomes depend only on a subset of other players. First formalized by Michael Kearns, Michael Littman, and Satinder Singh in 2001, this approach complements traditional representations such as the normal form and extensive form by leveraging concepts from graph theory to achieve more concise game descriptions.

In a graphical game representation, players are depicted as nodes in a graph, with edges connecting players whose decisions directly affect each other. Each player's utility function depends only on their own strategy and the strategies of their immediate neighbors in the graph, rather than on all players' actions. This framework is particularly valuable for modeling social network interactions, economic networks, and localized competitive scenarios where players primarily respond to those in their immediate vicinity.

The graphical approach offers significant advantages when representing large games with limited interaction patterns, as it can exponentially reduce the amount of information needed to fully describe the game. This compact representation facilitates more efficient computational analysis for complex multi-agent systems across fields such as artificial intelligence, economics, and network science.

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.

References

• Michael Kearns (2007) "Graphical Games". In Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.
• Michael Kearns, Michael L. Littman and Satinder Singh (2001) "Graphical Models for Game Theory".