# Graphical Models for Game Theory

arXiv: https://arxiv.org/abs/1301.2281 · HTML: https://mlsanity.com/paper/1301.2281/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jan 2013.

## Built on by (most cited first, 21 of 21)

- [Pick Your Battles: Interaction Graphs as Population-Level Objectives for Strategic Diversity](https://mlsanity.com/paper/2110.04041/) (2021)
- [Multi-Player Zero-Sum Markov Games with Networked Separable Interactions](https://mlsanity.com/paper/2307.09470/) (2023)
- [Performative Reinforcement Learning with Linear Markov Decision Process](https://mlsanity.com/paper/2411.05234/) (2024)
- [Scalable Learning of Intrusion Responses through Recursive Decomposition](https://mlsanity.com/paper/2309.03292/) (2023)
- [Who Needs to Know? Minimal Knowledge for Optimal Coordination](https://mlsanity.com/paper/2306.09309/) (2023)
- [Fast Convergence of Optimistic Gradient Ascent in Network Zero-Sum Extensive Form Games](https://mlsanity.com/paper/2207.08426/) (2022)
- [Factorised Active Inference for Strategic Multi-Agent Interactions](https://mlsanity.com/paper/2411.07362/) (2024)
- [Computing Game Symmetries and Equilibria That Respect Them](https://mlsanity.com/paper/2501.08905/) (2025)
- [Online Optimization in Games via Control Theory: Connecting Regret, Passivity and Poincar'e Recurrence](https://mlsanity.com/paper/2106.04748/) (2021)
- [Guarantees for Self-Play in Multiplayer Games via Polymatrix Decomposability](https://mlsanity.com/paper/2310.11518/) (2023)
- [A Principle of Targeted Intervention for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2510.17697/) (2025)
- [CoCo Games: Graphical Game-Theoretic Swarm Control for Communication-Aware Coverage](https://mlsanity.com/paper/2111.04576/) (2021)
- [Altruism Design in Networked Public Goods Games](https://mlsanity.com/paper/2105.00505/) (2021)
- [Approximating Nash Equilibria in General-Sum Games via Meta-Learning](https://mlsanity.com/paper/2504.18868/) (2025)
- [Regret Minimization in Population Network Games: Vanishing Heterogeneity and Convergence to Equilibria](https://mlsanity.com/paper/2507.17183/) (2025)
- [Computing Equilibrium beyond Unilateral Deviation](https://mlsanity.com/paper/2604.28186/) (2026)
- [Solving Graph-based Public Good Games with Tree Search and Imitation Learning](https://mlsanity.com/paper/2106.06762/) (2021)
- [Approximating Nash Equilibrium in Random Graphical Games](https://mlsanity.com/paper/2112.03442/) (2021)
- [Boolean Observation Games](https://mlsanity.com/paper/2202.03637/) (2022)
- [Counting Markov Equivalent Directed Acyclic Graphs Consistent with Background Knowledge](https://mlsanity.com/paper/2206.06744/) (2022)
- [A Knowledge-Based Multi-Agent Framework for Security Control Recommendation](https://mlsanity.com/paper/2607.09954/) (2026)

## Abstract (arXiv)

In this work, we introduce graphical modelsfor multi-player game theory, and give powerful algorithms for computing their Nash equilibria in certain cases. An n-player game is given by an undirected graph on n nodes and a set of n local matrices. The interpretation is that the payoff to player i is determined entirely by the actions of player i and his neighbors in the graph, and thus the payoff matrix to player i is indexed only by these players. We thus view the global n-player game as being composed of interacting local games, each involving many fewer players. Each player's action may have global impact, but it occurs through the propagation of local influences.Our main technical result is an efficient algorithm for computing Nash equilibria when the underlying graph is a tree (or can be turned into a tree with few node mergings). The algorithm runs in time polynomial in the size of the representation (the graph and theassociated local game matrices), and comes in two related but distinct flavors. The first version involves an approximation step, and computes a representation of all approximate Nash equilibria (of which there may be an exponential number in general). The second version allows the exact computation of Nash equilibria at the expense of weakened complexity bounds. The algorithm requires only local message-passing between nodes (and thus can be implemented by the players themselves in a distributed manner). Despite an analogy to inference in Bayes nets that we develop, the analysis of our algorithm is more involved than that for the polytree algorithm in, owing partially to the fact that we must either compute, or select from, an exponential number of potential solutions. We discuss a number of extensions, such as the computation of equilibria with desirable global properties (e.g. maximizing global return), and directions for further research.