Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
An Efficient Optimal-Equilibrium Algorithm for Two-player Game Trees
Michael Littman, Nishkam Ravi, Arjun Talwar, Martin Zinkevich
Two-player complete-information game trees are perhaps the simplest possible setting for studying general-sum games and the computational problem of finding equilibria. These games admit a simple bottom-up algorithm for finding subgame perfect Nash equilibria efficiently. However, such an algorithm can fail to identify optimal equilibria, such as those that maximize social welfare. The reason is that, counterintuitively, probabilistic action choices are sometimes needed to achieve maximum payoffs. We provide a novel polynomial-time algorithm for this problem that explicitly reasons about stochastic decisions and demonstrate its use in an example card game.
Pages: 298-305
PS Link:
PDF Link: /papers/06/p298-littman.pdf
AUTHOR = "Michael Littman and Nishkam Ravi and Arjun Talwar and Martin Zinkevich",
TITLE = "An Efficient Optimal-Equilibrium Algorithm for Two-player Game Trees",
BOOKTITLE = "Proceedings of the Twenty-Second Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-06)",
ADDRESS = "Arlington, Virginia",
YEAR = "2006",
PAGES = "298--305"

hosted by DSL   •   site info   •   help