Simple search methods for finding a Nash equilibrium
We present two simple search methods for computing a sample Nash equilibrium in a normal-form game: one for 2-player games and one for n-player games. Both algorithms bias the search towards supports that are small and balanced, and employ a backtracking procedure to efficiently explore these supports. Making use of a new comprehensive testbed, we test these algorithms on many classes of games, and show that they perform well against the state of the art--the Lemke-Howson algorithm for 2-player games, and Simplicial Subdivision and Govindan-Wilson for n-player games.
If 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.
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.
References listed on IDEAS
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.:
- Rinott, Yosef & Scarsini, Marco, 2000.
"On the Number of Pure Strategy Nash Equilibria in Random Games,"
Games and Economic Behavior,
Elsevier, vol. 33(2), pages 274-293, November.
- Marco Scarsini & Yosef Rinott, 2000. "On the number of pure strategy Nash equilibria in random games," Post-Print hal-00540207, HAL.
- C. E. Lemke, 1965. "Bimatrix Equilibrium Points and Mathematical Programming," Management Science, INFORMS, vol. 11(7), pages 681-689, May.
- Talman, A.J.J. & van der Laan, G. & Van der Heyden, L., 1987. "Variable dimension algorithms for solving the nonlinear complementarity problem on a product of unit simplices using general labelling," Other publications TiSEM fbe9ae2f-e01d-4eef-944c-6, Tilburg University, School of Economics and Management.
- 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.
- Gilboa, Itzhak & Zemel, Eitan, 1989. "Nash and correlated equilibria: Some complexity considerations," Games and Economic Behavior, Elsevier, vol. 1(1), pages 80-93, March.
- Itzhak Gilboa & Eitan Zemel, 1988. "Nash and Correlated Equilibria: Some Complexity Considerations," Discussion Papers 777, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
- Itzhak Gilboa & Eitan Zemel, 1989. "Nash and Correlated Equilibria: Some Complexity Considerations," Post-Print hal-00753241, HAL.
- McLennan, Andrew & Berg, Johannes, 2005. "Asymptotic expected number of Nash equilibria of two-player normal form games," Games and Economic Behavior, Elsevier, vol. 51(2), pages 264-295, May.
- Govindan, Srihari & Wilson, Robert, 2003. "A global Newton method to compute Nash equilibria," Journal of Economic Theory, Elsevier, vol. 110(1), pages 65-86, May.
- McKelvey, Richard D. & McLennan, Andrew, 1997. "The Maximal Number of Regular Totally Mixed Nash Equilibria," Journal of Economic Theory, Elsevier, vol. 72(2), pages 411-425, February.
- McKelvey, Richard D. & McLennan, Andrew, 1994. "The Maximal Number of Regular Totally Mixed Nash Equilibria," Working Papers 865, California Institute of Technology, Division of the Humanities and Social Sciences.
- McKelvey, R.D. & McLennan, A., 1994. "The Maximal Number of Regular Totaly Mixed Nash Equilibria," Papers 272, Minnesota - Center for Economic Research.
- McKelvey, Richard D. & McLennan, Andrew, 1996. "Computation of equilibria in finite games," Handbook of Computational Economics,in: H. M. Amman & D. A. Kendrick & J. Rust (ed.), Handbook of Computational Economics, edition 1, volume 1, chapter 2, pages 87-142 Elsevier.
- Kohlberg, Elon & Mertens, Jean-Francois, 1986. "On the Strategic Stability of Equilibria," Econometrica, Econometric Society, vol. 54(5), pages 1003-1037, September.
- KOHLBERG, Elon & MERTENS, Jean-François, "undated". "On the strategic stability of equilibria," CORE Discussion Papers RP 716, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
- E. Kohlberg & J.-F. Mertens, 1998. "On the Strategic Stability of Equilibria," Levine's Working Paper Archive 445, David K. Levine.