Graphical game theory

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

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\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[edit]

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[edit]

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 nm^{2}.

Nash equilibrium[edit]

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.

Further reading[edit]

  • Michael Kearns (2007) "Graphical Games". In Algorithmic Game Theory, N. Nisan, T. Roughgarden, E. Tardos and V. Vazirani, editors, Cambridge University Press, September, 2007.
  • Michael Kearns, Michael L. Littman and Satinder Singh (2001) "Graphical Models for Game Theory".