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 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

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

Further reading

This article is issued from Wikipedia - version of the Thursday, December 10, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.