Computing Sequential Equilibria for Two-Player Games

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Department of Computer Science
  • Teoretisk naturvidenskab
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.
Original languageEnglish
Title of host publicationProceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
Number of pages10
PublisherAssociation for Computing Machinery
Publication year2006
Edition1
Pages107-116
ISBN (print)ISBN:0-89871-605-5
Publication statusPublished - 2006
EventSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, Florida
Duration: 22 Jan 200624 Jan 2006
Conference number: 17

Conference

ConferenceSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
Nummer17
ByMiami, Florida
Periode22/01/200624/01/2006

See relations at Aarhus University Citationformats

ID: 653538