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 (68)

• 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
• 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
• Graphical potential games
• Interdependent Defense Games: Modeling Interdependent Security under Deliberate Attacks
• Learning and Solving Many-Player Games through a Cluster-Based Representation
• Ranking Games that have Competitiveness-based Strategies
• CoCo Games: Graphical Game-Theoretic Swarm Control for Communication-Aware Coverage
• Learning Game Representations from Data Using Rationality Constraints
• Temporal Action-Graph Games: A New Representation for Dynamic Games
• Exploiting Structure in Cooperative Bayesian Games
• Solving Structured Hierarchical Games Using Differential Backward Induction
• Identifying reasoning patterns in games
• Paradoxes in Social Networks with Multiple Products
• Functional Dependence in Strategic Games
• Smooth markets: A basic mechanism for organizing gradient-based learners
• 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
• An Efficient Optimal-Equilibrium Algorithm for Two-player Game Trees
• Settling the Complexity of Computing Two-Player Nash Equilibria
• Graphical Potential Games
• Learning Quadratic Games on Networks
• Chaos of Learning Beyond Zero-sum and Coordination via Game Decompositions
• Computing Equilibria in Binary Networked Public Goods Games
• Graphical Games and Decomposition
• Functional Dependence in Strategic Games (extended abstract)
• The Truth Behind the Myth of the Folk Theorem
• Exchangeable Equilibria, Part I: Symmetric Bimatrix Games
• On the Complexity of Nash Equilibria of Action-Graph Games
• Preference Games and Personalized Equilibria, with Applications to Fractional BGP
• A Refined Study of the Complexity of Binary Networked Public Goods Games
• Altruism Design in Networked Public Goods Games
• The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions
• The Impact of Complex and Informed Adversarial Behavior in Graphical Coordination Games
• Boolean Observation Games
• Computing Best-Response Strategies in Infinite Games of Incomplete Information
• Correlated Equilibria for Approximate Variational Inference in MRFs
• Online Optimization in Games via Control Theory: Connecting Regret, Passivity and Poincaré Recurrence
• Prior Independent Equilibria and Linear Multi-dimensional Bayesian Games
• Comparing the notions of optimality in CP-nets, strategic games and soft constraints
• Multi-Scale Games: Representing and Solving Games on Networks with Group Structure
• Nash Equilibria in certain two-choice multi-player games played on the ladder graph
• Solving Graph-based Public Good Games with Tree Search and Imitation Learning
• Robustness of Nash Equilibria in Network Games
• Graphical One-Sided Markets
• A process algebraic form to represent extensive games
• Distributed Mechanism Design for Network Resource Allocation Problems
• Strategic Prediction with Latent Aggregative Games
• 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
• Knowledge Combination in Graphical Multiagent Model
• Bounding the Uncertainty of Graphical Games: The Complexity of Simple Requirements, Pareto and Strong Nash Equilibria
• Pure Nash Equilibria: Complete Characterization of Hard and Easy Graphical Games
• A Primer on Strategic Games
• If more than Analytical Modeling is Needed to Predict Real Agents' Strategic Interaction
• Polynomial Graphs With Applications To Graphical Games, Extensive-Form Games, and Games With Emergent Node Tree Structures