The Library
Enumeration of Nash equilibria for two-player games
Tools
Avis, David, Rosenberg, Gabriel D., Savani, Rahul and von Stengel, Bernhard (2010) Enumeration of Nash equilibria for two-player games. Economic Theory, Vol.42 (No.1). pp. 9-37. doi:10.1007/s00199-009-0449-x ISSN 0938-2259.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/s00199-009-0449-x
Abstract
This paper describes algorithms for finding all Nash equilibria of a two-player game in strategic form. We present two algorithms that extend earlier work. Our presentation is self-contained, and explains the two methods in a unified framework using faces of best-response polyhedra. The first method lrsnash is based on the known vertex enumeration program lrs, for "lexicographic reverse search". It enumerates the vertices of only one best-response polytope, and the vertices of the complementary faces that correspond to these vertices (if they are not empty) in the other polytope. The second method is a modification of the known EEE algorithm, for "enumeration of extreme equilibria". We also describe a second, as yet not implemented, variant that is space efficient. We discuss details of implementations of lrsnash and EEE, and report on computational experiments that compare the two algorithms, which show that both have their strengths and weaknesses.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | H Social Sciences > HC Economic History and Conditions | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | Economic Theory | ||||
Publisher: | Springer | ||||
ISSN: | 0938-2259 | ||||
Official Date: | January 2010 | ||||
Dates: |
|
||||
Volume: | Vol.42 | ||||
Number: | No.1 | ||||
Number of Pages: | 29 | ||||
Page Range: | pp. 9-37 | ||||
DOI: | 10.1007/s00199-009-0449-x | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |