Temporal Action-Graph Games: A New Representation for Dynamic Games
This addresses the problem of efficiently representing and computing in dynamic games for researchers in game theory and AI, offering a novel method for compact encoding.
The paper introduces temporal action graph games (TAGG), a new graphical representation for dynamic games with imperfect information, showing it can be more compact than multiagent influence diagrams (MAID) for games with anonymity or context-specific utility independencies, and provides an algorithm that significantly improves on prior state of the art.
In this paper we introduce temporal action graph games (TAGGs), a novel graphical representation of imperfect-information extensive form games. We show that when a game involves anonymity or context-specific utility independencies, its encoding as a TAGG can be much more compact than its direct encoding as a multiagent influence diagram (MAID).We also show that TAGGs can be understood as indirect MAID encodings in which many deterministic chance nodes are introduced. We provide an algorithm for computing with TAGGs, and show both theoretically and empirically that our approach improves significantly on the previous state of the art.