Graphical Models for Game Theory

Abstract

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.

Appears in Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence (UAI2001)

Cited by in corpus (77)

• Autonomous Agents Modelling Other Agents: A Comprehensive Survey and Open Problems
• A distributed primal-dual algorithm for computation of generalized Nash equilibria with shared affine coupling constraints via operator splitting methods
• Complexity Results about Nash Equilibria
• Distributed Constraint Optimization Problems and Applications: A Survey
• A Continuation Method for Nash Equilibria in Structured Games
• Predicting Human Behavior in Unrepeated, Simultaneous-Move Games
• Empirical Centroid Fictitious Play: An Approach For Distributed Learning In Multi-Agent Games
• Asymmetric Distributed Constraint Optimization Problems
• Networks of Influence Diagrams: A Formalism for Representing Agents' Beliefs and Decision-Making Processes
• A Distributed Nash Equilibrium Seeking in Networked Graphical Games
• Efficient Nash Computation in Large Population Games with Bounded Influence
• On Influence, Stable Behavior, and the Most Influential Individuals in Networks: A Game-Theoretic Approach
• Network games with dynamic players: Stabilization and output convergence to Nash equilibrium
• Fashion, Cooperation, and Social Interactions
• Learning the Structure and Parameters of Large-Population Graphical Games from Behavioral Data
• Interdependent Defense Games: Modeling Interdependent Security under Deliberate Attacks
• Graphical potential games
• Computer Science and Game Theory: A Brief Survey
• Learning and Solving Many-Player Games through a Cluster-Based Representation
• Computing Pure Nash Equilibria via Markov Random Fields
• Ranking Games that have Competitiveness-based Strategies
• CoCo Games: Graphical Game-Theoretic Swarm Control for Communication-Aware Coverage
• Temporal Action-Graph Games: A New Representation for Dynamic Games
• Learning Game Representations from Data Using Rationality Constraints
• Exploiting Structure in Cooperative Bayesian Games
• Identifying reasoning patterns in games
• Smooth markets: A basic mechanism for organizing gradient-based learners
• Solving Structured Hierarchical Games Using Differential Backward Induction
• Functional Dependence in Strategic Games
• Paradoxes in Social Networks with Multiple Products
• Learning Equilibria of Games via Payoff Queries
• Complexity Theory, Game Theory, and Economics: The Barbados Lectures
• FPTAS for Mixed-Strategy Nash Equilibria in Tree Graphical Games and Their Generalizations
• Settling the Complexity of Computing Two-Player Nash Equilibria
• Learning Quadratic Games on Networks
• An Efficient Optimal-Equilibrium Algorithm for Two-player Game Trees
• Graphical Potential Games
• Chaos of Learning Beyond Zero-sum and Coordination via Game Decompositions
• A Refined Study of the Complexity of Binary Networked Public Goods Games
• Preference Games and Personalized Equilibria, with Applications to Fractional BGP
• Functional Dependence in Strategic Games (extended abstract)
• Exchangeable Equilibria, Part I: Symmetric Bimatrix Games
• The Truth Behind the Myth of the Folk Theorem
• Graphical Games and Decomposition
• Polynomial-time Computation of Exact Correlated Equilibrium in Compact Games
• Exploiting Agent and Type Independence in Collaborative Graphical Bayesian Games
• On the Complexity of Nash Equilibria of Action-Graph Games
• Computing Equilibria in Binary Networked Public Goods Games
• Boolean Observation Games
• Altruism Design in Networked Public Goods Games
• The Impact of Complex and Informed Adversarial Behavior in Graphical Coordination Games
• Online Optimization in Games via Control Theory: Connecting Regret, Passivity and Poincaré Recurrence
• Prior Independent Equilibria and Linear Multi-dimensional Bayesian Games
• Correlated Equilibria for Approximate Variational Inference in MRFs
• Computing Best-Response Strategies in Infinite Games of Incomplete Information
• The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions
• The Impact of Tribalism on Social Welfare
• Hypergraphical Clustering Games of Mis-Coordination
• Computational Analysis of Perfect-Information Position Auctions
• Approximating Nash Equilibria in Tree Polymatrix Games
• Robustness of Nash Equilibria in Network Games
• Knowledge Combination in Graphical Multiagent Model
• Bounding the Uncertainty of Graphical Games: The Complexity of Simple Requirements, Pareto and Strong Nash Equilibria
• Comparing the notions of optimality in CP-nets, strategic games and soft constraints
• Nash Equilibria in certain two-choice multi-player games played on the ladder graph
• Pure Nash Equilibria: Complete Characterization of Hard and Easy Graphical Games
• Solving Graph-based Public Good Games with Tree Search and Imitation Learning
• A Primer on Strategic Games
• If more than Analytical Modeling is Needed to Predict Real Agents' Strategic Interaction
• Multi-Scale Games: Representing and Solving Games on Networks with Group Structure
• Polynomial Graphs With Applications To Graphical Games, Extensive-Form Games, and Games With Emergent Node Tree Structures
• A General Framework for Computing Optimal Correlated Equilibria in Compact Games
• Distributed Mechanism Design for Network Resource Allocation Problems
• A process algebraic form to represent extensive games
• Distributed iterated elimination of strictly dominated strategies
• Graphical One-Sided Markets
• Strategic Prediction with Latent Aggregative Games