DIMACS TR: 2006-14
An Efficient Optimal-Equilibrium Algorithm for Two-player Game Trees
Authors: Michael L. Littman, Nishkam Ravi, Arjun Talwar and 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.
Paper Available at:
DIMACS Home Page