Computing equilibria for two-person games

Bernhard von Stengel

Chapter 45 in Handbook of Game Theory with Economic Applications, 2002, vol. 3, pp 1723-1759 from Elsevier

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

JEL-codes: C (search for similar items in EconPapers)
Date: 2002
References: Add references at CitEc
Citations: View citations in EconPapers (54)

Downloads: (external link)
http://www.sciencedirect.com/science/article/B7P5P ... 20502692a90aa1f84523
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:gamchp:3-45

Access Statistics for this chapter

More chapters in Handbook of Game Theory with Economic Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().