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. 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.

Original languageEnglish
Title of host publicationProc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'06)
Number of pages10
PublisherACM-SIAM
Publication year2006
Pages107-116
Publication statusPublished - 2006
EventACM-SIAM Symposium on Discrete Algorithms - , United States
Duration: 17 Dec 2010 → …
Conference number: 17

Conference

ConferenceACM-SIAM Symposium on Discrete Algorithms
Nummer17
LandUnited States
Periode17/12/2010 → …

    Research areas

  • equilibrium refinements, equilibrium computation, computational game theory

See relations at Aarhus University Citationformats

ID: 3688063