## 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 → … |