An Efficient Optimal-Equilibrium Algorithm for Two-player Game Trees

Understand

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.