A Sampling-Based Approach to Computing Equilibria in Succinct Extensive-Form Games

Miroslav Dudik, Geoffrey Gordon
Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, PMLR R7:151-160, 2009.

Abstract

A central task of artificial intelligence is the design of artificial agents that act towards specified goals in partially observed environments. Since such environments frequently include interaction over time with other agents with their own goals, reasoning about such interaction relies on sequential game-theoretic models such as extensive-form games or some of their succinct representations such as multi-agent influence diagrams. The current algorithms for calculating equilibria either work with inefficient representations, possibly doubly exponential inthe number of time steps, or place strong assumptions on the game structure. In this paper,we propose a sampling-based approach, which calculates extensive-form correlated equilibria with small representations without placing such strong assumptions. Thus, it is practical in situations where the previous approaches would fail. In addition, our algorithm allows control over characteristics of the target equilibrium, e.g., we can ask for an equilibrium with high social welfare. Our approach is based on a multiplicativeweight update algorithm analogous to AdaBoost, and Markov chain Monte Carlo sampling. We prove convergence guarantees and explore the utility of our approach on several moderately sized multi-player games.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR7-dudik09a, title = {A Sampling-Based Approach to Computing Equilibria in Succinct Extensive-Form Games}, author = {Dudik, Miroslav and Gordon, Geoffrey}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {151--160}, 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/dudik09a/dudik09a.pdf}, url = {https://proceedings.mlr.press/r7/dudik09a.html}, abstract = {A central task of artificial intelligence is the design of artificial agents that act towards specified goals in partially observed environments. Since such environments frequently include interaction over time with other agents with their own goals, reasoning about such interaction relies on sequential game-theoretic models such as extensive-form games or some of their succinct representations such as multi-agent influence diagrams. The current algorithms for calculating equilibria either work with inefficient representations, possibly doubly exponential inthe number of time steps, or place strong assumptions on the game structure. In this paper,we propose a sampling-based approach, which calculates extensive-form correlated equilibria with small representations without placing such strong assumptions. Thus, it is practical in situations where the previous approaches would fail. In addition, our algorithm allows control over characteristics of the target equilibrium, e.g., we can ask for an equilibrium with high social welfare. Our approach is based on a multiplicativeweight update algorithm analogous to AdaBoost, and Markov chain Monte Carlo sampling. We prove convergence guarantees and explore the utility of our approach on several moderately sized multi-player games.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T A Sampling-Based Approach to Computing Equilibria in Succinct Extensive-Form Games %A Miroslav Dudik %A Geoffrey Gordon %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-dudik09a %I PMLR %P 151--160 %U https://proceedings.mlr.press/r7/dudik09a.html %V R7 %X A central task of artificial intelligence is the design of artificial agents that act towards specified goals in partially observed environments. Since such environments frequently include interaction over time with other agents with their own goals, reasoning about such interaction relies on sequential game-theoretic models such as extensive-form games or some of their succinct representations such as multi-agent influence diagrams. The current algorithms for calculating equilibria either work with inefficient representations, possibly doubly exponential inthe number of time steps, or place strong assumptions on the game structure. In this paper,we propose a sampling-based approach, which calculates extensive-form correlated equilibria with small representations without placing such strong assumptions. Thus, it is practical in situations where the previous approaches would fail. In addition, our algorithm allows control over characteristics of the target equilibrium, e.g., we can ask for an equilibrium with high social welfare. Our approach is based on a multiplicativeweight update algorithm analogous to AdaBoost, and Markov chain Monte Carlo sampling. We prove convergence guarantees and explore the utility of our approach on several moderately sized multi-player games. %Z Reissued by PMLR on 04 October 2026.
APA
Dudik, M. & Gordon, G.. (2009). A Sampling-Based Approach to Computing Equilibria in Succinct Extensive-Form Games. Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R7:151-160 Available from https://proceedings.mlr.press/r7/dudik09a.html. Reissued by PMLR on 04 October 2026.

Related Material