Equilibrium Refinements for Multi-Agent Influence Diagrams: Theory and Practice

• URL: http://arxiv.org/abs/2102.05008v1
• Date: Tue, 9 Feb 2021 18:20:50 GMT
• Title: Equilibrium Refinements for Multi-Agent Influence Diagrams: Theory and Practice
• Authors: Lewis Hammond, James Fox, Tom Everitt, Alessandro Abate, Michael Wooldridge
• Abstract summary: Multi-agent influence diagrams (MAIDs) are a popular form of graphical model that, for certain classes of games, have been shown to offer key complexity and explainability advantages over traditional extensive form game (EFG) representations. We extend previous work on MAIDs by introducing the concept of a MAID subgame, as well as subgame perfect and hand perfect equilibrium refinements.
• Score: 62.58588499193303
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-agent influence diagrams (MAIDs) are a popular form of graphical model that, for certain classes of games, have been shown to offer key complexity and explainability advantages over traditional extensive form game (EFG) representations. In this paper, we extend previous work on MAIDs by introducing the concept of a MAID subgame, as well as subgame perfect and trembling hand perfect equilibrium refinements. We then prove several equivalence results between MAIDs and EFGs. Finally, we describe an open source implementation for reasoning about MAIDs and computing their equilibria.

Related papers

• Balanced Multi-Relational Graph Clustering [5.531383184058319]
  Multi-relational graph clustering has demonstrated remarkable success in uncovering underlying patterns in complex networks. Our empirical study finds the pervasive presence of imbalance in real-world graphs, which is in principle contradictory to the motivation of alignment. We propose Balanced Multi-Relational Graph Clustering (BMGC), comprising unsupervised dominant view mining and dual signals guided representation learning.
  arXiv  Detail & Related papers  (2024-07-23T22:11:13Z)
• Relational Learning in Pre-Trained Models: A Theory from Hypergraph Recovery Perspective [60.64922606733441]
  We introduce a mathematical model that formalizes relational learning as hypergraph recovery to study pre-training of Foundation Models (FMs) In our framework, the world is represented as a hypergraph, with data abstracted as random samples from hyperedges. We theoretically examine the feasibility of a Pre-Trained Model (PTM) to recover this hypergraph and analyze the data efficiency in a minimax near-optimal style.
  arXiv  Detail & Related papers  (2024-06-17T06:20:39Z)
• Cantor: Inspiring Multimodal Chain-of-Thought of MLLM [83.6663322930814]
  We argue that converging visual context acquisition and logical reasoning is pivotal for tackling visual reasoning tasks. We propose an innovative multimodal CoT framework, termed Cantor, characterized by a perception-decision architecture. Our experiments demonstrate the efficacy of the proposed framework, showing significant improvements in multimodal CoT performance.
  arXiv  Detail & Related papers  (2024-04-24T17:59:48Z)
• On Imperfect Recall in Multi-Agent Influence Diagrams [57.21088266396761]
  Multi-agent influence diagrams (MAIDs) are a popular game-theoretic model based on Bayesian networks. We show how to solve MAIDs with forgetful and absent-minded agents using mixed policies and two types of correlated equilibrium. We also describe applications of MAIDs to Markov games and team situations, where imperfect recall is often unavoidable.
  arXiv  Detail & Related papers  (2023-07-11T07:08:34Z)
• Understanding Masked Autoencoders via Hierarchical Latent Variable Models [109.35382136147349]
  Masked autoencoder (MAE) has recently achieved prominent success in a variety of vision tasks. Despite the emergence of intriguing empirical observations on MAE, a theoretically principled understanding is still lacking.
  arXiv  Detail & Related papers  (2023-06-08T03:00:10Z)
• Mean Field Games on Weighted and Directed Graphs via Colored Digraphons [26.405495663998828]
  Graphon mean field games (GMFGs) provide a scalable and mathematically well-founded approach to learning problems. Our paper introduces colored digraphon mean field games (CDMFGs) which allow for weighted and directed links between agents.
  arXiv  Detail & Related papers  (2022-09-08T15:45:20Z)
• Scaling up Mean Field Games with Online Mirror Descent [55.36153467919289]
  We address scaling up equilibrium computation in Mean Field Games (MFGs) using Online Mirror Descent (OMD) We show that continuous-time OMD provably converges to a Nash equilibrium under a natural and well-motivated set of monotonicity assumptions. A thorough experimental investigation on various single and multi-population MFGs shows that OMD outperforms traditional algorithms such as Fictitious Play (FP)
  arXiv  Detail & Related papers  (2021-02-28T21:28:36Z)
• Large-Scale Multi-Agent Deep FBSDEs [28.525065041507982]
  We present a framework for finding Markovian Nash Equilibria in multi-agent games using fictitious play. We showcase superior performance of our framework over the state-of-the-art deep fictitious play algorithm. We also demonstrate the applicability of our framework in robotics on a belief space autonomous racing problem.
  arXiv  Detail & Related papers  (2020-11-21T23:00:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.