Graphical game theory

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.

## Formal definition

[edit]

A graphical game is represented by a graph  G {\displaystyle G} , in which each player is represented by a node, and there is an edge between two nodes  i {\displaystyle i} and  j {\displaystyle j} iff their utility functions are dependent on the strategy which the other player will choose. Each node  i {\displaystyle i} in  G {\displaystyle G} has a function  u i : { 1 … m } d i + 1 → R {\displaystyle u_{i}:\\{1\ldots m\\}^{d_{i}+1}\rightarrow \mathbb {R} } , where  d i {\displaystyle d_{i}} is the degree of vertex  i {\displaystyle i} .  u i {\displaystyle u_{i}} specifies the utility of player  i {\displaystyle i} as a function of his strategy as well as those of his neighbors.

## The size of the game's representation

[edit]

For a general  n {\displaystyle n} players game, in which each player has  m {\displaystyle m} possible strategies, the size of a normal form representation would be  O ( m n ) {\displaystyle O(m^{n})} . The size of the graphical representation for this game is  O ( m d ) {\displaystyle O(m^{d})} where  d {\displaystyle d} is the maximal node degree in the graph. If  d ≪ n {\displaystyle d\ll n} , then the graphical game representation is much smaller.

## An example

[edit]

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  n {\displaystyle n} functions (tables) of size  m 2 {\displaystyle m^{2}} . So, the total size of the input will be  n m 2 {\displaystyle nm^{2}} .

## Nash equilibrium

[edit]

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

[edit]

* 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".

* v
* t
* e

Game theory

* Glossary
* Game theorists
* Games

Traditional game theory

| Definitions|

* Asynchrony
* Bayesian regret
* Best response
* Bounded rationality
* Cheap talk
* Coalition
* Complete contract
* Complete information
* Complete mixing
* Confrontation analysis
* Conjectural variation
* Contingent cooperator
* Coopetition
* Cooperative game theory
* Dynamic inconsistency
* Escalation of commitment
* Farsightedness
* Game semantics
* Hierarchy of beliefs
* Imperfect information
* Incomplete information
* Information set
* Move by nature
* Mutual knowledge
* Non-cooperative game theory
* Non-credible threat
* Outcome
* Perfect information
* Perfect recall
* Ply
* Preference
* Rationality
* Sequential game
* Simultaneous action selection
* Spite
* Strategic complements
* Strategic dominance
* Strategic form
* Strategic interaction
* Strategic move
* Strategy
* Subgame
* Succinct game
* Topological game
* Tragedy of the commons
* Uncorrelated asymmetry

|

Equilibrium
concepts|

* Backward induction
* Bayes correlated equilibrium
* Bayesian efficiency
* Bayesian game
* Bayesian Nash equilibrium
* Berge equilibrium
* Bertrand–Edgeworth model
* Coalition-proof Nash equilibrium
* Core
* Correlated equilibrium
* Cursed equilibrium
* Edgeworth price cycle
* Epsilon-equilibrium
* Gibbs equilibrium
* Incomplete contracts
* Inequity aversion
* Individual rationality
* Iterated elimination of dominated strategies
* Markov perfect equilibrium
* Mertens-stable equilibrium
* Nash equilibrium
* Open-loop model
* Pareto efficiency
* Payoff dominance
* Perfect Bayesian equilibrium
* Price of anarchy
* Program equilibrium
* Proper equilibrium
* Quantal response equilibrium
* Quasi-perfect equilibrium
* Rational agent
* Rationalizability
* Rationalizable strategy
* Satisfaction equilibrium
* Self-confirming equilibrium
* Sequential equilibrium
* Shapley value
* Strong Nash equilibrium
* Subgame perfect equilibrium
* Trembling hand equilibrium

Strategies|

* Appeasement
* Bid shading
* Cheap talk
* Collusion
* Commitment device
* De-escalation
* Deterrence
* Escalation
* Fictitious play
* Focal point
* Grim trigger
* Hobbesian trap
* Markov strategy
* Max-dominated strategy
* Mixed strategy
* Pure strategy
* Tit for tat
* Win–stay, lose–switch

Games|

* All-pay auction
* Battle of the sexes
* Nash bargaining game
* Bertrand competition
* Blotto game
* Centipede game
* Coordination game
* Cournot competition
* Deadlock
* Dictator game
* Trust game
* Diner's dilemma
* Dollar auction
* El Farol Bar problem
* Electronic mail game
* Gift-exchange game
* Guess 2/3 of the average
* Keynesian beauty contest
* Kuhn poker
* Lewis signaling game
* Matching pennies
* Obligationes
* Optional prisoner's dilemma
* Pirate game
* Prisoner's dilemma
* Public goods game
* Rendezvous problem
* Rock paper scissors
* Stackelberg competition
* Stag hunt
* Traveler's dilemma
* Ultimatum game
* Volunteer's dilemma
* War of attrition

Theorems|

* Arrow's impossibility theorem
* Aumann's agreement theorem
* Brouwer fixed-point theorem
* Competitive altruism
* Folk theorem
* Gibbard–Satterthwaite theorem
* Gibbs lemma
* Glicksberg's theorem
* Kakutani fixed-point theorem
* Kuhn's theorem
* One-shot deviation principle
* Prim–Read theory
* Rational ignorance
* Rational irrationality
* Sperner's lemma
* Zermelo's theorem

Subfields|

* Algorithmic game theory
* Behavioral game theory
* Behavioral strategy
* Compositional game theory
* Contract theory
* Drama theory
* Graphical game theory
* Heresthetic
* Mean-field game theory
* Negotiation theory
* Quantum game theory
* Social software

Key people|

* Albert W. Tucker
* Alvin E. Roth
* Amos Tversky
* Antoine Augustin Cournot
* Ariel Rubinstein
* David Gale
* David K. Levine
* David M. Kreps
* Donald B. Gillies
* Drew Fudenberg
* Eric Maskin
* Harold W. Kuhn
* Herbert Simon
* Herbert Scarf
* Hervé Moulin
* Jean Tirole
* Jean-François Mertens
* Jennifer Tour Chayes
* Ken Binmore
* Kenneth Arrow
* Leonid Hurwicz
* Lloyd Shapley
* Martin Shubik
* Melvin Dresher
* Merrill M. Flood
* Olga Bondareva
* Oskar Morgenstern
* Paul Milgrom
* Peyton Young
* Reinhard Selten
* Robert Aumann
* Robert Axelrod
* Robert B. Wilson
* Roger Myerson
* Samuel Bowles
* Suzanne Scotchmer
* Thomas Schelling
* William Vickrey

Combinatorial game theory

| Core
concepts|

* Combinatorial explosion
* Determinacy
* Disjunctive sum
* First-player and second-player win
* Game complexity
* Game tree
* Impartial game
* Misère
* Partisan game
* Solved game
* Sprague–Grundy theorem
* Strategy-stealing argument
* Zugzwang

|

Games|

* Chess
* Chomp
* Clobber
* Cram
* Domineering
* Hackenbush
* Nim
* Notakto
* Subtract a square
* Sylver coinage
* Toads and Frogs

Mathematical
tools|

* Mex
* Nimber
* On Numbers and Games
* Star
* Surreal number
* Winning Ways for Your Mathematical Plays

Search
algorithms|

* Alpha–beta pruning
* Expectiminimax
* Minimax
* Monte Carlo tree search
* Negamax
* Paranoid algorithm
* Principal variation search

Key people|

* Claude Shannon
* John Conway
* John von Neumann

Evolutionary game theory

| Core
concepts|

* Bishop–Cannings theorem
* Evolution and the Theory of Games
* Evolutionarily stable set
* Evolutionarily stable state
* Evolutionarily stable strategy
* Replicator equation
* Risk dominance
* Stochastically stable equilibrium
* Weak evolutionarily stable strategy

|

Games|

* Chicken
* Stag hunt

Applications|

* Cultural group selection
* Fisher's principle
* Mobbing
* Terminal investment hypothesis

Key people|

* John Maynard Smith
* Robert Axelrod

Mechanism design

| Core
concepts|

* Algorithmic mechanism design
* Bayesian-optimal mechanism
* Incentive compatibility
* Market design
* Monotonicity
* Participation constraint
* Revelation principle
* Strategyproofness
* Vickrey–Clarke–Groves mechanism

|

Theorems|

* Myerson–Satterthwaite theorem
* Revenue equivalence

Applications|

* Digital goods auction
* Knapsack auction
* Truthful cake-cutting

Other topics

* Bertrand paradox
* Chainstore paradox
* Computational complexity of games
* Helly metric
* Multi-agent system
* PPAD-complete

* Mathematics portal
* Commons
* WikiProject
* Category

1. ^ Kearns, Michael; Littman, Michael L.; Singh, Satinder (2 August 2001). Graphical Models for Game Theory. Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence. pp. 253–260.

*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template