Papyrus 53: Difference between revisions
Jump to navigation
Jump to search
en>Giftzwerg 88 No Oxy. papyrus |
→Images: the images aren't there anymore |
||
| Line 1: | Line 1: | ||
In [[game theory]], the common ways to describe a game are the [[normal-form game|normal form]] and the [[extensive-form game|extensive form]]. The graphical form is an alternate compact representation of a game using the interaction among participants. | |||
Consider a game with <math>n</math> players with <math>m</math> 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 <math>G</math>, in which each player is represented by a node, and there is an edge between two nodes <math>i</math> and <math>j</math> iff their utility functions are depended on the strategy which the other player will choose . Each node <math>i</math> in <math>G</math> has a function <math>u_{i}:\{1\ldots m\}^{d_{i}+1}\rightarrow\mathbb{R}</math>, where <math>d_i</math> is the degree of vertex <math>i</math>. <math>u_{i}</math> specifies the utility of player <math>i</math> as a function of his strategy as well as those of his neighbors. | |||
==The size of the game's representation== | |||
For a general <math>n</math> players game, in which each player has <math>m</math> possible strategies, the size of a normal form representation would be <math>O(m^{n})</math>. The size of the graphical representation for this game is <math>O(m^{d})</math> where <math>d</math> is the maximal node degree in the graph. If <math>d\ll n</math>, then the graphical game representation is much smaller. | |||
==An example== | |||
In case where each player's utility function depends only on one other player: | |||
<gallery> | |||
Image:GraphicalGameExample.png|The graphical form of the described game | |||
</gallery> | |||
The maximal degree of the graph is 1, and the game can be described as <math>n</math> functions (tables) of size <math>m^{2}</math>. So, the total size of the input will be <math>nm^{2}</math>. | |||
==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) "[http://www.cis.upenn.edu/~mkearns/papers/agt-kearns.pdf 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) "[http://www.cis.upenn.edu/~mkearns/papers/graphgames.pdf Graphical Models for Game Theory]". | |||
[[Category:Game theory]] | |||
Revision as of 00:04, 4 October 2013
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 graphical form of the described game
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 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".