This file is part of IDEAS, which uses RePEc data


[ Papers | Articles | Software | Books | Chapters | Authors | Institutions | JEL Classification | NEP reports | Search | New papers by email | Author registration | Rankings | Volunteers | FAQ | Blog | Help! ]

Hard-to-Solve Bimatrix Games

Author info | Abstract | Publisher info | Download info | Related research | Statistics
Author Info
Rahul Savani
Bernhard Stengel

Additional information is available for the following registered author(s):

Abstract

The Lemke-Howson algorithm is the classical method for finding one Nash equilibrium of a bimatrix game. This paper presents a class of square bimatrix games for which this algorithm takes, even in the best case, an exponential number of steps in the dimension d of the game. Using polytope theory, the games are constructed using pairs of dual cyclic polytopes with 2d suitably labeled facets in d-space. The construction is extended to nonsquare games where, in addition to exponentially long Lemke-Howson computations, finding an equilibrium by support enumeration takes on average exponential time. Copyright The Econometric Society 2006.

Download Info
To download:

If you experience problems downloading a file, check if you have the proper application to view it first. Information about this may be contained in the File-Format links below. 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.

File URL: http://hdl.handle.net/10.1111/j.1468-0262.2006.00667.x
File Format: text/html
File Function: link to full text
Download Restriction: Access to full text is restricted to subscribers.

As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.

Publisher Info
Article provided by Econometric Society in its journal Econometrica.

Volume (Year): 74 (2006)
Issue (Month): 2 (03)
Pages: 397-429
Download reference. The following formats are available: HTML (with abstract), plain text (with abstract), BibTeX, RIS (EndNote, RefMan, ProCite), ReDIF
Handle: RePEc:ecm:emetrp:v:74:y:2006:i:2:p:397-429

Contact details of provider:
Phone: 1 212 998 3820
Fax: 1 212 995 4487
Email:
Web page: http://www.econometricsociety.org/
More information through EDIRC

Order Information:
Email:
Web: http://www.blackwellpublishing.com/memb.asp?ref=0012-9682

For technical questions regarding this item, or to correct its listing, contact: (Christopher F. Baum).

Related research
Keywords:

Cited by:
(explanations, Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.)

  1. Takuya Masuzawa, 2008. "Computing the cores of strategic games with punishment–dominance relations," International Journal of Game Theory, Springer, vol. 37(2), pages 185-201, June. [Downloadable!] (restricted)
  2. Andrew McLennan & Rabee Tourky, 2008. "Imitation Games and Computation," Discussion Papers Series 359, School of Economics, University of Queensland, Australia. [Downloadable!]
  3. Govindan, Srihari & Wilson, Robert B., 2007. "A Decomposition Algorithm for N-Player Games," Research Papers 1967, Stanford University, Graduate School of Business. [Downloadable!]
    Other versions:
Statistics
Access and download statistics

Did you know? You too can volunteer for RePEc, for example by editing a NEP report.

This page was last updated on 2009-12-8.

This information is provided to you by IDEAS at the Department of Economics, College of Liberal Arts and Sciences, University of Connecticut using RePEc data on a server sponsored by the Society for Economic Dynamics.