Temporal Action-Graph Games: A New Representation for Dynamic Games

Albert Xin Jiang, Kevin Leyton-Brown, Avi Pfeffer
Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, PMLR R7:268-276, 2009.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR7-jiang09a, title = {Temporal Action-Graph Games: A New Representation for Dynamic Games}, author = {Jiang, Albert Xin and Leyton-Brown, Kevin and Pfeffer, Avi}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {268--276}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/jiang09a/jiang09a.pdf}, url = {https://proceedings.mlr.press/r7/jiang09a.html}, abstract = {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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Temporal Action-Graph Games: A New Representation for Dynamic Games %A Albert Xin Jiang %A Kevin Leyton-Brown %A Avi Pfeffer %B Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2009 %E Jeff Bilmes %E Andrew Y. Ng %F pmlr-vR7-jiang09a %I PMLR %P 268--276 %U https://proceedings.mlr.press/r7/jiang09a.html %V R7 %X 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. %Z Reissued by PMLR on 04 October 2026.
APA
Jiang, A.X., Leyton-Brown, K. & Pfeffer, A.. (2009). Temporal Action-Graph Games: A New Representation for Dynamic Games. Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R7:268-276 Available from https://proceedings.mlr.press/r7/jiang09a.html. Reissued by PMLR on 04 October 2026.

Related Material