Computing equilibria for two-person games
In: Handbook of Game Theory with Economic Applications
AbstractThis 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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
This chapter was published in:
This item is provided by Elsevier in its series Handbook of Game Theory with Economic Applications with number 3-45.
Contact details of provider:
Web page: http://www.elsevier.com/wps/find/bookseriesdescription.cws_home/BS_HE/description
Find related papers by JEL classification:
- C - Mathematical and Quantitative Methods
You can help add them by filling out this form.
CitEc Project, subscribe to its RSS feed for this item.
This item has more than 25 citations. To prevent cluttering this page, these citations are listed on a separate page. reading list or among the top items on IDEAS.Access and download statisticsgeneral information about how to correct material in RePEc.
If references are entirely missing, you can add them using this form.