Abstract
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. Their algorithm has been used by AI
researchers for constructing prescriptive strategies for concrete, often
fairly large games. 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.
We also describe an extension of our technique to general-sum
games which is likely to be prove practical, even though it is
not polynomial-time.
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. Their algorithm has been used by AI
researchers for constructing prescriptive strategies for concrete, often
fairly large games. 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.
We also describe an extension of our technique to general-sum
games which is likely to be prove practical, even though it is
not polynomial-time.
| Originalsprog | Engelsk |
|---|---|
| Titel | Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'06) |
| Antal sider | 10 |
| Forlag | ACM-SIAM |
| Publikationsdato | 2006 |
| Sider | 107-116 |
| Status | Udgivet - 2006 |
| Begivenhed | ACM-SIAM Symposium on Discrete Algorithms - , USA Varighed: 17 dec. 2010 → … Konferencens nummer: 17 |
Konference
| Konference | ACM-SIAM Symposium on Discrete Algorithms |
|---|---|
| Nummer | 17 |
| Land/Område | USA |
| Periode | 17/12/2010 → … |