Top Qs
Timeline
Chat
Perspective
Graphical game theory
From Wikipedia, the free encyclopedia
Remove ads
Remove ads
In game theory, the graphical form or graphical game is an alternate compact representation of strategic interactions that efficiently models situations where players' outcomes depend only on a subset of other players.[1] First formalized by Michael Kearns, Michael Littman, and Satinder Singh in 2001, this approach complements traditional representations such as the normal form and extensive form by leveraging concepts from graph theory to achieve more concise game descriptions.
In a graphical game representation, players are depicted as nodes in a graph, with edges connecting players whose decisions directly affect each other. Each player's utility function depends only on their own strategy and the strategies of their immediate neighbors in the graph, rather than on all players' actions. This framework is particularly valuable for modeling social network interactions, economic networks, and localized competitive scenarios where players primarily respond to those in their immediate vicinity.
The graphical approach offers significant advantages when representing large games with limited interaction patterns, as it can exponentially reduce the amount of information needed to fully describe the game. This compact representation facilitates more efficient computational analysis for complex multi-agent systems across fields such as artificial intelligence, economics, and network science.
Remove ads
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 dependent 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.
Remove ads
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.
Remove ads
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.
References
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads