A program to find all pure Nash equilibria in games with n-players and m-strategies: the Nash Equilibria Finder – NEFinder

Renan Henrique Cavicchioli Sugiyama; Alexandre Bevilacqua Leoneti

doi:10.1590/1806-9649-2021v28e5640

Artigo Original

A program to find all pure Nash equilibria in games with n-players and m-strategies: the Nash Equilibria Finder – NEFinder

Renan Henrique Cavicchioli Sugiyama; Alexandre Bevilacqua Leoneti

http://dx.doi.org/10.1590/1806-9649-2021v28e5640 Gest. Prod., vol.28, n3, e5640, 2021

PDF

SciELO

Downloads: 2

Abstract

Abstract:: Nash equilibrium is an important concept for studying human behavior in group decision making process. Given the complexity of finding Nash equilibria, computational tools are necessary to find them. Several programs were developed for this task. However, available programs are either not comprehensive or might be of difficult installation and handling, creating a “barrier of entry” to non-specialists. The aims of this research are twofold: (i) firstly, it was to identify and to discuss about the available programs for finding Nash equilibria; and (ii) secondly, based on the theoretical proprieties of a Nash equilibrium, to develop a program capable of finding all pure Nash equilibria in games with “n” players and “m” strategies (“n” and “m” being finite numbers) as a Macro tool for Microsoft Excel®. It is expected that the program can contributed to the area of Operations Research by providing a new tool that facilitate the use of game theory concepts within group decision-making problem-solving scenarios enabling practical applications using a widespread software.

Keywords

Group decision-making, Game theory, Nash equilibrium, Software

Referências

Angeloni, M. T. (2003). Elementos intervenientes na tomada de decisão. Ciência da Informação, 32(1), 17-22. http://dx.doi.org/10.1590/S0100-19652003000100002.

Dickhaut, J., & Kaplan, T. (1993). A program for finding Nash equilibria. The Mathematica Journal, 1, 87-93.

Egesdal, M., Jordana, A. G., Prause, M., Savani, R., & Stengel, B. V. (2014). Game Theory Explorer. Retrieved in 2014, October 15, from http://www.gametheoryexplorer.org/

Echenique, F. (2007). Finding all equilibria in games of strategic complements. Journal of Economic Theory, 135(1), 514-532. http://dx.doi.org/10.1016/j.jet.2006.06.001.

Fylstra, D., Lasdon, L., Watson, J., & Waren, A. (1998). Design and use of the Microsoft Excel Solver. Interfaces, 28(5), 29-55. http://dx.doi.org/10.1287/inte.28.5.29.

Game Theory Society. (2019). Retrieved in 2014, October 15, from http://www.gametheorysociety.org/

Garey, M. R., & Johnson, D. S. (1977). Computers and intractability: A guide to the theory of NP-completeness. The Freeman

Govindan, S., & Wilson, R. (2003). A global Newton method to compute Nash equilibria. Journal of Economic Theory, 110(1), 65-86. http://dx.doi.org/10.1016/S0022-0531(03)00005-X.

Govindan, S., & Wilson, R. (2004). Computing Nash equilibria by iterated polymatrix approximation. Journal of Economic Dynamics and Control, 28(7), 1229-1241. http://dx.doi.org/10.1016/S0165-1889(03)00108-8.

Herings, P. J. J., & Peeters, R. J. (2001). A differentiable homotopy to compute Nash equilibria of n-person games. Economic Theory, 18(1), 159-185. http://dx.doi.org/10.1007/PL00004129.

Krawczyk, J., & Zuccollo, J. (2006). NIRA-3: An improved MATLAB package for finding Nash equilibria in infinite games. Victoria University of Wellington.

Knight, V. A., & Campbell, J. (2018). Nashpy: A Python library for the computation of Nash equilibria. Journal Open Source Software, 3(30), 904. http://dx.doi.org/10.21105/joss.00904.

Lemke, C., & Howson, J. Jr (1964). Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics, 12(2), 413-423. http://dx.doi.org/10.1137/0112033.

Luce, R. D., & Raiffa, H. (1957). Games and decisions: Introduction and critical survey. New York: Wiley.

McKelvey, R. D., McLennan, A. M., & Turocy, T. L. (2006). Gambit: Software tools for game theory. Dover Publications.

Langlois, J. P. (2005) An introduction to Game Theory Using the GamePlan Software. Retrieved in 2014, October 15, from https://www.researchgate.net/profile/Jean-Pierre_Langlois/publication/238098439_An_Introduction_to_Game_Theory_Using_the_GamePlan_Software/links/02e7e52d5a9cc8d3ac000000.pdf

Myerson, R. (1996). John Nash’s Contribution to Economics. Games and Economic Behavior, 14(2), 287-295. http://dx.doi.org/10.1006/game.1996.0053.

Nisan, N., Roughgarden, T., Tardos, E., & Vazirani, V. V. (2007). Algorithmic game theory (vol. 1). Cambridge: Cambridge University Press. http://dx.doi.org/10.1017/CBO9780511800481.

Osborne, M. J., & Rubinstein, A. (1994). A course in game theory. Cambridge: MIT press.

Parsons, S., & Wooldridge, M. (2002). Game theory and decision theory in multi-agent systems. Autonomous Agents and Multi-Agent Systems, 5(3), 243-254. http://dx.doi.org/10.1023/A:1015575522401.

Porter, R., Nudelman, E., & Shoham, Y. (2008). Simple search methods for finding a Nash equilibrium. Games and Economic Behavior, 63(2), 642-662. http://dx.doi.org/10.1016/j.geb.2006.03.015.

Sanfey, A. G. (2007). Social decision-making: insights from game theory and neuroscience. Science, 318(5850), 598-602. http://dx.doi.org/10.1126/science.1142996. PMid:17962552.

Spaniel, W. (2014). Game theory 101: the complete textbook. CreateSpace.

A program to find all pure Nash equilibria in games with n-players and m-strategies: the Nash Equilibria Finder – NEFinder

Renan Henrique Cavicchioli Sugiyama; Alexandre Bevilacqua Leoneti

Abstract

Keywords

Referências

Links

Compartilhar

Gest. Prod.