  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.
