Graphical game theory: Difference between revisions

Revision as of 10:46, 3 February 2015

Latest revision as of 18:50, 16 July 2025

(7 intermediate revisions by 7 users not shown)

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.

In [[game theory]], the '''graphical form''' or '''graphical game''' is an [[Succinct game|alternate compact representation]] of strategic interactions that efficiently models situations where players' outcomes depend only on a subset of other players.<ref name=":02">{{cite conference |last1=Kearns |first1=Michael |last2=Littman |first2=Michael L. |last3=Singh |first3=Satinder |date=2 August 2001 |year= |title=Graphical Models for Game Theory |url=https://dl.acm.org/doi/10.5555/2074022.2074054 |conference=Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence |pages=253–260}}</ref> First formalized by [[Michael Kearns (computer scientist)|Michael Kearns]], [[Michael Littman]], and Satinder Singh in 2001, this approach complements traditional representations such as the [[Normal-form game|normal form]] and [[Extensive-form game|extensive form]] by leveraging concepts from [[graph theory]] to achieve more concise game descriptions.

In a graphical game representation, players are depicted as [[Vertex (graph theory)|nodes]] in a [[Graph (discrete mathematics)|graph]], with [[Edge (graph theory)|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 system|multi-agent systems]] across fields such as [[artificial intelligence]], [[economics]], and [[network science]].

==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 dependeddependent 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==

Line 20 ⟶ 24:

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==

== Further reading ==

{{Reflist}}

* Michael Kearns (2007) "[http://www.cis.upenn.edu/~mkearns/papers/agt-kearns.pdf Graphical Games]". In {{Cite 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]".

{{Game theory}}

[[Category:Game theory]]

[[Category:Graph theory]]