Graphical Models for Game Theory

By Michael Kearns, Michael L. Littman, Satinder Singh. Conference on Uncertainty in Artificial Intelligence, 2001

711 citations recorded by the source corpus.

We introduce a compact graph-theoretic representation for multi-party game theory. Our main result is a provably correct and efficient algorithm for computing approximate Nash equilibria in one-stage games represented by trees or sparse graphs.

Subfields: Artificial Intelligence, Management Science and Operations Research, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/1e6f2b06416eb3e2df0c73c90e1bb3f81627a32a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Statistical and Nonlinear Physics

Citations in the corpus

Computing the optimal strategy to commit to (2006, methodology): “We can also study the computation of optimal strategies to commit to in other(1) concise representations of normal-form games—for example, in graphical games [10] or local-effect/action graph games [14, 1].”
The complexity of computing a Nash equilibrium (2006, background): “But our game has a special structure (called a graphical game, see [16]): The players are vertices of a graph (essentially the data flow graph of F ), and the utility of each player depends only on the actions of its neighbors.”
The complexity of computing a Nash equilibrium (2009, background): “But our game has a special structure (called a graphical game , see Kearns et al. 15 ): The players are vertices of a graph (essentially the data flow graph of F ), and the utility of each player depends only on the actions of its neighbors.”
Computing correlated equilibria in multi-player games (2005, background): “In a graphical game G [14], input z describes an undirected graph N (where N(p) is the set of neighbors of p, including p) and, for each p a game Gp, explicitly represented, with players in N(p).”
Playing large games using simple strategies (2003, neutral): “…(Section 3) is that if the players are allowed to communicate and sign treaties then there are constant support strategies which approximate the payo.s that each player gets in an equilibrium (in fact there are constant support strategies that approximate the payo.s of any pair of strategies).”
Hierarchical multi-agent reinforcement learning (2001, methodology): “The previous work established algorithms for computing Nash equilibria in one-stage games, including efficient algorithms for computing approximate [ 16 ] and exact [23] Nash equilibria in tree-structured games, and convergent heuristics for computing Nash equilibria in general graphs [26, 41].”
Dynamic fictitious play, dynamic gradient play, and distributed convergence to Nash equilibria (2005, background): “DAGP automatically respect any underlying “graph” structure in that a player only monitors the empirical frequencies of opponent players that enter into the utility function, e.g., [ 30 ]”
Multi-agent differential graphical games (2011, background): “Graphical games have been studied in the computational intelligence community [13], [14], [29].”
A polynomial-time nash equilibrium algorithm for repeated games (2003, methodology): “…other contexts in which we are applying the ideas in this paper, such as computing equilibria in repeated Markovgames (Littman 2001) and n-player games expressed in a graphical notation (Kearns et al. 2001), and using reinforcement learning to issue and recognize threats (Littman and Stone 2001).”
Settling the Complexity of Two-Player Nash Equilibrium (2006, background): “They continued to reduce the zero point problem to the problem of finding an approximate Nash equilibrium in a degree-3 graphical game ( graphical games were first proposed in [14]), and further to the four-player Nash equilibrium problem by a recent result of Goldberg and Papadimitriou [11].”
Diffusion, Strategic Interaction, and Social Structure (2011, methodology): “The first model that explicitly examines games played on a network is the model of “graphical games” as introduced by Kearns, Littman, and Singh (2001), and analyzed by Kakade, Kearns, Langford, and Ortiz (2003), among others.”
Methods for empirical game-theoretic analysis (extended abstract) (2006, background): “The recent surge in interest among AI researchers in game theory has led to numerous advances in game modeling (Gal & Pfeffer 2004; Kearns, Littman, & Singh 2001; Koller & Milch 2003; Leyton-Brown & Tennenholtz 2003) and solution techniques (Gilpin & Sandholm 2006; Porter, Nudelman, & Shoham 2004)”
Predicting human behavior in unrepeated, simultaneous-move games (2013, background): “An open problem for future work is finding a way to address this computational problem by representing the games compactly (e.g., Kearns et al., 2001; Koller and Milch, 2001; Jiang et al., 2011), such that expected utility can be computed efficiently over even a very large action space. validation:…”
Exploiting Agent and Type Independence in Collaborative Graphical Bayesian Games (2011, background): “CGSGs are also similar tographical games(Kearns et al., 2001; Kearns, 2007; Soni et al., 2007).”