To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
Show all languages
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.

Graphical game theory

From Wikipedia, the free encyclopedia

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".
This page was last edited on 17 July 2020, at 08:40
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.