Name
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. 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. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1145/1109557.1109570 | SODA |
Keywords | Field | DocType |
two-player extensive-form zero-sum game,imperfect information,perfect recall,two-player game,linear program,minimax strategy,linear programming,von stengel,sequential equilibrium,two-player zero-sum game,practical application,computing sequential equilibrium,normal form,polynomial time,independent set,zero sum game | Sequential equilibrium,Discrete mathematics,Minimax,Combinatorics,Computer science,Independent set,Linear programming,Perfect information,Time complexity | Conference |
ISBN | Citations | PageRank |
0-89871-605-5 | 23 | 2.24 |
References | Authors | |
7 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Bro Miltersen | 1 | 1146 | 94.49 |
| Troels Bjerre Sørensen | 2 | 181 | 18.08 |