Computing Sequential Equilibria for Two-Player Games

TY - GEN

T1 - Computing Sequential Equilibria for Two-Player Games

AU - Miltersen, Peter Bro

AU - Sørensen, Troels Bjerre

N1 - Conference code: 17

PY - 2006

Y1 - 2006

N2 - Koller, Megiddo and von Stengel showed how to efficiently compute minimax strategies for two-player extensive-form zero-sum games with imperfect information but perfect recall using linear programming and avoiding conversion to normal form. Koller and Pfeffer pointed out that the strategies obtained by the algorithm are not necessarily sequentially rational and that this deficiency is often problematic for the practical applications. We show how to remove this deficiency by modifying the linear programs constructed by Koller, Megiddo and von Stengel so that pairs of strategies forming a sequential equilibrium are computed. In particular, we show that a sequential equilibrium for a two-player zero-sum game with imperfect information but perfect recall can be found in polynomial time. In addition, the equilibrium we find is normal-form perfect. Our technique generalizes to general-sum games, yielding an algorithm for such games which is likely to be prove practical, even though it is not polynomial-time.

AB - Koller, Megiddo and von Stengel showed how to efficiently compute minimax strategies for two-player extensive-form zero-sum games with imperfect information but perfect recall using linear programming and avoiding conversion to normal form. Koller and Pfeffer pointed out that the strategies obtained by the algorithm are not necessarily sequentially rational and that this deficiency is often problematic for the practical applications. We show how to remove this deficiency by modifying the linear programs constructed by Koller, Megiddo and von Stengel so that pairs of strategies forming a sequential equilibrium are computed. In particular, we show that a sequential equilibrium for a two-player zero-sum game with imperfect information but perfect recall can be found in polynomial time. In addition, the equilibrium we find is normal-form perfect. Our technique generalizes to general-sum games, yielding an algorithm for such games which is likely to be prove practical, even though it is not polynomial-time.

M3 - Article in proceedings

SN - ISBN:0-89871-605-5

SP - 107

EP - 116

BT - Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms

PB - Association for Computing Machinery

T2 - Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 22 January 2006 through 24 January 2006

ER -