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. 4,5
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
Languages
Recent
Show all languages
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds # 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. This page was last edited on 17 July 2020, at 08:40