Computing a quasi-perfect equilibrium of a two-player game

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Department of Computer Science
  • Teoretisk naturvidenskab
Refining an algorithm due to Koller, Megiddo and von Stengel, we show how to apply Lemke's algorithm for solving linear complementarity programs to compute a quasi-perfect equilibrium in behavior strategies of a given two-player extensive-form game of perfect recall. A quasi-perfect equilibrium is known to be sequential, and our algorithm thus resolves a conjecture of McKelvey and McLennan in the positive. A quasi-perfect equilibrium is also known to be normal-form perfect and our algorithm thus provides an alternative to an algorithm by von Stengel, van den Elzen and Talman. For the case of a zero-sum game, we devise variants of the algorithm that rely on linear programming rather than linear complementarity programming and use the simplex algorithm or other algorithms for linear programming rather than Lemke's algorithm. We argue that these latter algorithms are relevant for recent applications of equilibrium computation to artificial intelligence.
Original languageEnglish
JournalEconomic Theory
Volume42
Issue1
Pages (from-to)175-192
Number of pages18
ISSN0938-2259
DOIs
Publication statusPublished - 2010

Bibliographical note

From the issue entitled "Symposium on Computation of Nash Equilibria in Finite Games"

    Research areas

  • Equilibrium computation, quasi-perfect equilibrium

See relations at Aarhus University Citationformats

ID: 6197294