On Imperfect Recall in Multi-Agent Influence Diagrams

Journal article

Multi-agent influence diagrams (MAIDs) are a popular game-theoretic model based on Bayesian networks. In some settings, MAIDs offer significant advantages over extensive-form game representations. Previous work on MAIDs has assumed that agents employ behavioural policies, which set independent conditional probability distributions over actions for each of their decisions. In settings with imperfect recall, however, a Nash equilibrium in behavioural policies may not exist. We overcome this by showing how to solve MAIDs with forgetful and absent-minded agents using mixed policies and two types of correlated equilibrium. We also analyse the computational complexity of key decision problems in MAIDs, and explore tractable cases. Finally, we describe applications of MAIDs to Markov games and team situations, where imperfect recall is often unavoidable.Comment: In Proceedings TARK 2023, arXiv:2307.0400

Authors: Fox, J; MacDermott, M; Hammond, L; Harrenstein, P; Abate, A

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Open Publishing Association
• Journal: Electronic Proceedings in Theoretical Computer Science
• Volume: 379
• Pages: 201-220
• Publication date: 2023-07-08
• DOI: 10.4204/eptcs.379.17
• ISSN: 2075-2180
• Language: English
• Keywords: Influence diagram; Decision tree; Mathematical economics; Set (abstract data type); Machine learning; Computer science; Recall; Repeated game; Nash equilibrium; Game theory; Extensive-form game; Artificial intelligence; Economics; Imperfect; Computer security; Psychology; Cognitive psychology; Bayesian game; Key (lock); Markov chain