Skip to main content

2013 | OriginalPaper | Buchkapitel

A Multi-Modal Coevolutionary Algorithm for Finding All Nash Equilibria of a Multi-Player Normal Form Game

verfasst von : Nona Helmi, Gelareh Veisi

Erschienen in: Ubiquitous Information Technologies and Applications

Verlag: Springer Netherlands

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Nash’s theorem says that every game that has a finite strategic form has at least one Nash point. The problem of finding one Nash point is a well studied problem, and there exist a number of different methods for numerically computing a sample Nash equilibrium. But the problem of finding all equilibria has been addressed only recently. Literature review shows that many of the existing methods for detecting all equilibria are computationally intensive and error prone. In this paper we present a multi-modal coevolutionary algorithm that is able to detect all Nash points of a multi-player normal form game at the same time. We formulate the problem of solving a matrix game as a multi- modal optimization problem. Then a coevolutionary algorithm decomposes the problem and solves it in a parallel form. It associates one population to each player’s strategies. So various components of the problem will coevolve and better results may be produced at lower computational costs.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic Game Theory. Cambridge University Press, Cambridge (2007) Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic Game Theory. Cambridge University Press, Cambridge (2007)
2.
Zurück zum Zitat McKelvey, R.D., McLennan, A.: Computation of equilibria in finite games. In: Rust, J., Amman, H., Kendrick, D. (eds.) Handbook of Computational Economics, pp. 87–142. Elsevier, Amsterdam (1996) McKelvey, R.D., McLennan, A.: Computation of equilibria in finite games. In: Rust, J., Amman, H., Kendrick, D. (eds.) Handbook of Computational Economics, pp. 87–142. Elsevier, Amsterdam (1996)
3.
Zurück zum Zitat Papadimitriu, C.: Algorithms, games and the internet. In: ACM Symposium on Theory of Computing, pp. 794–753 (2001) Papadimitriu, C.: Algorithms, games and the internet. In: ACM Symposium on Theory of Computing, pp. 794–753 (2001)
4.
Zurück zum Zitat H′emon, S., Rougemont, M.D., Santha, M.: Approximate Nash equilibria for multi-player games. In: First International Symposium on Algorithmic Game Theory, pp. 267–278. Germany (2008) H′emon, S., Rougemont, M.D., Santha, M.: Approximate Nash equilibria for multi-player games. In: First International Symposium on Algorithmic Game Theory, pp. 267–278. Germany (2008)
5.
Zurück zum Zitat Papadimitriou, C.H., Roughgarden, T.: Computing correlated equilibria in multi-player games. J. ACM 55(3) (2008) Papadimitriou, C.H., Roughgarden, T.: Computing correlated equilibria in multi-player games. J. ACM 55(3) (2008)
6.
Zurück zum Zitat Nanduri, V., Das, T.K.: A reinforcement learning algorithm for obtaining Nash equilibrium of multi-player matrix games. IEEE Trans. Oper. Eng. 41, 158–167 (2009) Nanduri, V., Das, T.K.: A reinforcement learning algorithm for obtaining Nash equilibrium of multi-player matrix games. IEEE Trans. Oper. Eng. 41, 158–167 (2009)
7.
Zurück zum Zitat McKelvey, R.D., McLennan, A.M.: Gambit: Software tools for game theory. In: Version 0.97.1.5 (2004) McKelvey, R.D., McLennan, A.M.: Gambit: Software tools for game theory. In: Version 0.97.1.5 (2004)
8.
Zurück zum Zitat Lemke, C.E., Howson, T.: Equilibrium points of bimatrix games. J. Soc. Ind. Appl. Math. 12, 413–423 (1964) Lemke, C.E., Howson, T.: Equilibrium points of bimatrix games. J. Soc. Ind. Appl. Math. 12, 413–423 (1964)
9.
Zurück zum Zitat Sandholm, T., Gilpin, A., Conitzer, V.: Mixed-Integer Programming Methods for Finding Nash Equilibria. In: American Association for artificial intelligence, pp. 495–501 (2005) Sandholm, T., Gilpin, A., Conitzer, V.: Mixed-Integer Programming Methods for Finding Nash Equilibria. In: American Association for artificial intelligence, pp. 495–501 (2005)
10.
Zurück zum Zitat Rosenmuller, J.: On a generalization of the Lemke- Howson algorithm to noncooperative N- person games. SIAM J. Appl. Math. 1, 73–79 (1971)MathSciNetCrossRef Rosenmuller, J.: On a generalization of the Lemke- Howson algorithm to noncooperative N- person games. SIAM J. Appl. Math. 1, 73–79 (1971)MathSciNetCrossRef
12.
Zurück zum Zitat Thie, P.R.: An Introduction to Linear Programming and Game Theory. Wiley, New York (1988) Thie, P.R.: An Introduction to Linear Programming and Game Theory. Wiley, New York (1988)
13.
Zurück zum Zitat Wiegand, R.P.: An analysis of cooperative coevolutionary algorithms. PhD Thesis, George Mason University (2003) Wiegand, R.P.: An analysis of cooperative coevolutionary algorithms. PhD Thesis, George Mason University (2003)
14.
Zurück zum Zitat Pavlidis, N.G., Parsopoulos, K.E., Vrahatis, M.N.: Computing Nash equilibria through computational intelligence methods. J. Comput. Appl. Math. 175, 113–136 (2005)MathSciNetMATHCrossRef Pavlidis, N.G., Parsopoulos, K.E., Vrahatis, M.N.: Computing Nash equilibria through computational intelligence methods. J. Comput. Appl. Math. 175, 113–136 (2005)MathSciNetMATHCrossRef
15.
Zurück zum Zitat Lung, R., Dumitrescu, D.: An evolutionary model for solving multi-player non-cooperative games. In: Proceedings of the International Conference on Knowledge Engineering, pp. 209–216. Romania (2007) Lung, R., Dumitrescu, D.: An evolutionary model for solving multi-player non-cooperative games. In: Proceedings of the International Conference on Knowledge Engineering, pp. 209–216. Romania (2007)
16.
Zurück zum Zitat Amaral, W.M., Gomide, F.: A coevolutionary approach to solve fuzzy games. In: Bello, R., Felcon, R., Pedrycz, W., Kacprzyc, W. (eds.) Granular Computing: At the Junction of Fuzzy Sets and Rough Sets. Springer, Heidelberg (2007) Amaral, W.M., Gomide, F.: A coevolutionary approach to solve fuzzy games. In: Bello, R., Felcon, R., Pedrycz, W., Kacprzyc, W. (eds.) Granular Computing: At the Junction of Fuzzy Sets and Rough Sets. Springer, Heidelberg (2007)
17.
Zurück zum Zitat Potter, M.A., Jong, K.A.: A cooperative coevolutionary approach to function optimization. In: Proceedings of the Parallel Problem Solving form Nature Conference, pp. 249–257. Germany (1994) Potter, M.A., Jong, K.A.: A cooperative coevolutionary approach to function optimization. In: Proceedings of the Parallel Problem Solving form Nature Conference, pp. 249–257. Germany (1994)
18.
Zurück zum Zitat Tan, K.C., Yang, Y.J., Lee, T.H.: A distributed cooperative coevolutionary algorithm for multi-objective optimization. In: Proceedings of 2003 Congress on Evolutionary Computation, IEEE Press (2003) Tan, K.C., Yang, Y.J., Lee, T.H.: A distributed cooperative coevolutionary algorithm for multi-objective optimization. In: Proceedings of 2003 Congress on Evolutionary Computation, IEEE Press (2003)
19.
Zurück zum Zitat Seredynski, F., Zomaya, A.Y., Bouvry, P.: Function optimization with coevolutionary algorithms. In: International Intelligent Information Processing and Web mining Conference (2003) Seredynski, F., Zomaya, A.Y., Bouvry, P.: Function optimization with coevolutionary algorithms. In: International Intelligent Information Processing and Web mining Conference (2003)
20.
Zurück zum Zitat Sofge, D., Jung, K.D., Schultz, A.: A blended population approach to cooperative coevolution for decomposition of complex problems. In: Proceedings of Congress on Evolutionary Computation, IEEE (2002) Sofge, D., Jung, K.D., Schultz, A.: A blended population approach to cooperative coevolution for decomposition of complex problems. In: Proceedings of Congress on Evolutionary Computation, IEEE (2002)
21.
Zurück zum Zitat Deb, K., Saha, A.: Finding multiple solutions for multimodal optimization problems using a multi-objective evolutionary approach. In: Genetic and Evolutionary Computation Conference (2010, in press) Deb, K., Saha, A.: Finding multiple solutions for multimodal optimization problems using a multi-objective evolutionary approach. In: Genetic and Evolutionary Computation Conference (2010, in press)
22.
Zurück zum Zitat Harik, G.R.: Finding multimodal solutions using restricted tournament selection. In: Proceedings of the Sixth International Conference on Genetic Algorithms (ICGA), pp. 24–31 (1995) Harik, G.R.: Finding multimodal solutions using restricted tournament selection. In: Proceedings of the Sixth International Conference on Genetic Algorithms (ICGA), pp. 24–31 (1995)
23.
Zurück zum Zitat El Imrani, A., Bouroumi, A., Zine El Abidine, H., Limouri, M., Essaid, A.: A fuzzy clustering-based niching approach to multimodal function optimization. J. Cogn. Syst. Res. 1, 119–133 (2000)CrossRef El Imrani, A., Bouroumi, A., Zine El Abidine, H., Limouri, M., Essaid, A.: A fuzzy clustering-based niching approach to multimodal function optimization. J. Cogn. Syst. Res. 1, 119–133 (2000)CrossRef
24.
Zurück zum Zitat Mahfoud, S.W.: Simple analytical models of genetic algorithms for multimodal function optimization. University of Illinois, IlliGAL Report No 93001 (1993) Mahfoud, S.W.: Simple analytical models of genetic algorithms for multimodal function optimization. University of Illinois, IlliGAL Report No 93001 (1993)
25.
Zurück zum Zitat Mahfoud, S.W.: Niching methods for genetic algorithms PhD. Dissertation, Department of Computer Science, University of Illinois (1995) Mahfoud, S.W.: Niching methods for genetic algorithms PhD. Dissertation, Department of Computer Science, University of Illinois (1995)
Metadaten
Titel
A Multi-Modal Coevolutionary Algorithm for Finding All Nash Equilibria of a Multi-Player Normal Form Game
verfasst von
Nona Helmi
Gelareh Veisi
Copyright-Jahr
2013
Verlag
Springer Netherlands
DOI
https://doi.org/10.1007/978-94-007-5857-5_3

Neuer Inhalt