IDEAS home Printed from
   My bibliography  Save this book chapter

Computing equilibria for two-person games

In: Handbook of Game Theory with Economic Applications


  • Von Stengel, Bernhard


This paper is a self-contained survey of algorithms for computing Nash equilibria of two-person games. The games may be given in strategic form or extensive form. The classical Lemke-Howson algorithm finds one equilibrium of a bimatrix game, and provides an elementary proof that a Nash equilibrium exists. It can be given a strong geometric intuition using graphs that show the subdivision of the players' mixed strategy sets into best-response regions. The Lemke-Howson algorithm is presented with these graphs, as well as algebraically in terms of complementary pivoting. Degenerate games require a refinement of the algorithm based on lexicographic perturbations. Commonly used definitions of degenerate games are shown as equivalent. The enumeration of all equilibria is expressed as the problem of finding matching vertices in pairs of polytopes. Algorithms for computing simply stable equilibria and perfect equilibria are explained. The computation of equilibria for extensive games is difficult for larger games since the reduced strategic form may be exponentially large compared to the game tree. If the players have perfect recall, the sequence form of the extensive game is a strategic description that is more suitable for computation. In the sequence form, pure strategies of a player are replaced by sequences of choices along a play in the game. The sequence form has the same size as the game tree, and can be used for computing equilibria with the same methods as the strategic form. The paper concludes with remarks on theoretical and practical issues of concern to these computational approaches.

Suggested Citation

  • Von Stengel, Bernhard, 2002. "Computing equilibria for two-person games," Handbook of Game Theory with Economic Applications,in: R.J. Aumann & S. Hart (ed.), Handbook of Game Theory with Economic Applications, edition 1, volume 3, chapter 45, pages 1723-1759 Elsevier.
  • Handle: RePEc:eee:gamchp:3-45

    Download full text from publisher

    File URL:
    Download Restriction: Full text for ScienceDirect subscribers only

    As the access to this document is restricted, you may want to search for a different version of it.

    More about this item

    JEL classification:

    • C - Mathematical and Quantitative Methods


    Access and download statistics


    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:gamchp:3-45. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Dana Niculescu). General contact details of provider: .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.