Graphical game theory

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 depended on the strategy which the other player will choose. Each node i in G has a function u i : { 1 … m } d i + 1 → 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 ≪ 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 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 n m 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.