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 {\displaystyle n} players with m {\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. Read all..

Comments

You could also like

What people searched for

Explanation

[You can read the original article here], Licensed under CC-BY-SA.

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 players with 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 , in which each player is represented by a node, and there is an edge between two nodes and iff their utility functions are depended on the strategy which the other player will choose. Each node in has a function , where is the degree of vertex . specifies the utility of player as a function of his strategy as well as those of his neighbors.

The size of the game's representation

For a general players game, in which each player has possible strategies, the size of a normal form representation would be . The size of the graphical representation for this game is where is the maximal node degree in the graph. If , 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 functions (tables) of size . So, the total size of the input will be .

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

  • 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".
Read all..
© 2019 raptorfind.com. Imprint, All rights reserved.