Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Adding Secure Communication Mechanism to Existing Distributed Applications by means of AOP Read chapter Read first chapter

2013 | OriginalPaper | Chapter

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

Authors : Nona Helmi, Gelareh Veisi

Published in: Ubiquitous Information Technologies and Applications

Publisher: Springer Netherlands

Log in

Activate our intelligent search to find suitable subject content or patents.

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Multi-Level Dynamic Key Management for Scalable Wireless Sensor Networks with UAV
next chapter Study on Analysis Android Applications for Smartwork
Literature
1.
Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic Game Theory. Cambridge University Press, Cambridge (2007)
2.
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.
Papadimitriu, C.: Algorithms, games and the internet. In: ACM Symposium on Theory of Computing, pp. 794–753 (2001)
4.
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.
Papadimitriou, C.H., Roughgarden, T.: Computing correlated equilibria in multi-player games. J. ACM 55(3) (2008)
6.
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.
McKelvey, R.D., McLennan, A.M.: Gambit: Software tools for game theory. In: Version 0.97.1.5 (2004)
8.
Lemke, C.E., Howson, T.: Equilibrium points of bimatrix games. J. Soc. Ind. Appl. Math. 12, 413–423 (1964)
9.
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.
Rosenmuller, J.: On a generalization of the Lemke- Howson algorithm to noncooperative N- person games. SIAM J. Appl. Math. 1, 73–79 (1971)MathSciNetCrossRef
11.
12.
Thie, P.R.: An Introduction to Linear Programming and Game Theory. Wiley, New York (1988)
13.
Wiegand, R.P.: An analysis of cooperative coevolutionary algorithms. PhD Thesis, George Mason University (2003)
14.
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.
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.
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.
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.
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.
Seredynski, F., Zomaya, A.Y., Bouvry, P.: Function optimization with coevolutionary algorithms. In: International Intelligent Information Processing and Web mining Conference (2003)
20.
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.
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.
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.
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.
Mahfoud, S.W.: Simple analytical models of genetic algorithms for multimodal function optimization. University of Illinois, IlliGAL Report No 93001 (1993)
25.
Mahfoud, S.W.: Niching methods for genetic algorithms PhD. Dissertation, Department of Computer Science, University of Illinois (1995)
Metadata
Title
A Multi-Modal Coevolutionary Algorithm for Finding All Nash Equilibria of a Multi-Player Normal Form Game
Authors
Nona Helmi
Gelareh Veisi
Copyright Year
2013
Publisher
Springer Netherlands
Book
Ubiquitous Information Technologies and Applications

Print ISBN: 978-94-007-5856-8

Electronic ISBN: 978-94-007-5857-5

Copyright Year: 2013

DOI
https://doi.org/10.1007/978-94-007-5857-5_3