nach oben

Soft Computing

Erschienen in:

10.08.2020 | Methodologies and Application

An algorithm for finding approximate Nash equilibria in bimatrix games

verfasst von: Lunshan Gao

Erschienen in: Soft Computing | Ausgabe 2/2021

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

This paper describes an algorithm for calculating approximately mixed Nash equilibria (NE) in bimatrix games. The algorithm fuzzifies the strategies with normalized possibility distributions. The fuzzification takes advantage of the piecewise linearity of possibility distributions and transforms the NE problem of bimatrix games into a reduced form. The algorithm is guaranteed to find approximate NE in bimatrix games and ensures that the approximate NE is the saddle point of expected payoff functions in the reduced form. The algorithm provides a method of determining how close an approximate NE is to a solution during computation. Numerical results show that the new algorithm is approximately seven-time faster than the Lemke–Howson (LH) algorithm when the game size is 96, and the value of approximation deviation can be as small as 0.1.

Vorheriger Artikel Motion control of multiple humanoids using a hybridized prim’s algorithm-fuzzy controller

Nächster Artikel Design of new fractional order PI–fractional order PD cascade controller through dragonfly search algorithm for advanced load frequency control of power systems

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Bector CR, Chandra S (2005) Fuzzy mathematical programming and fuzzy matrix games. Springer, BerlinMATH

Bosse H, Byrka J, Markakis E (2010) New algorithms for approximate Nash equilibria in bimatrix games. Theor Comput Sci 411(1):164–173MathSciNetCrossRef

Campos L, Gonzalez A, Vila MA (1992) On the use of the ranking function approach to solve fuzzy matrix games in direct way. Fuzzy Set Syst 49:193–203MathSciNetCrossRef

Chen X, Deng X, Teng SH (2009) Setting the complexity of coomputing two-player Nash equilibria. J ACM 56(3):1–57CrossRef

Daskalakis C, Mehta A, Papadimitriou C (2009) A note on approximate Nash equilibria. Theor Comput Sci 410:1581–1588MathSciNetCrossRef

Dijkman JG, ven Haeringen H, DE Lange SJ (1983) Fuzzy numbers. J Math Anal Appl 92:301–341MathSciNetCrossRef

Downey R, Fellows MR (2013) Fundamentals of parameterized complexity. Springer, BerlinCrossRef

Dubois D, Prade H (2015) Practical methods for constructing possibility distributions. Int J Intell Syst 31(3):215–239CrossRef

Fearnley J, Goldberg PW, Savani R, Sorensen TB (2012) Approximate well-supported Nash equilibria below two-thirds. In: International symposium on algorithmic game theory, SAGT: algorithmic game theory, pp 108–119

Gao L (2017) The application of possibility distribution for solving standard quadratic optimization problems. Comput Inf Sci. https://doi.org/10.5539/cis.v10n3p60CrossRef

Gao L (2012) The discussion of applications of the fuzzy average to matrix game theory. In: The proceeding of CCECE2012

Gao L (1999) The fuzzy arithmetic mean. Fuzzy Sets Syst 107:335–348MathSciNetCrossRef

Kacher F, Larbanib M (2006) Solution concept for a non-cooperative game with fuzzy parameters. Int Game Theory Rev 8:489–498MathSciNetCrossRef

Kaufmann A, Gupta MM (1998) Fuzzy mathematical models in engineering and management science. Elsevier, AmsterdamMATH

Kontogiannis SC, Spirakis PG (2007) Efficient algorithms for constant well supported approximate equilibria in bimatrix games. In: Proceeding of ICALP, pp 595-606

Larbani M (2009) Non cooperative fuzzy games in normal form: a survey. Fuzzy Sets Syst 160:3184–3210MathSciNetCrossRef

Li C, Zhang Q (2011) Nash equilibrium strategy for fuzzy non-cooperative games. Fuzzy Sets Syst 176:46–55MathSciNetCrossRef

Li DF (2016) Linear programming models and methods of matrix games with payoffs of triangular fuzzy numbers, studies in fuzziniss and soft computing 328. Springer, BerlinCrossRef

Lipton RJ, Markakis E, Mehta A (2003) Playing large games using simple strategies. In: Proceeding of the fourth ACM conference on electronic commerce. New York, USA, pp 36–41

McKelvey RD, McLennan A (1996) Chapter 2, computation of equilibria in finite games. Handb Comput Econ 1:87–142CrossRef

McKelvey RD, McLennan A, Turocy TL (2014) Gambit: software tools for game theory. Version 16:1. http://www.gambit-project.org/

Nishizaki I, Sakawa M (2001) Fuzzy and multiobjective games for conflict resolution. Springer, BerlinCrossRef

Ortiz LE, Irfan MT (2017) Tractable algorithms for approximate Nash equilibria in generalized graphical Games with tree structure. In: The Proceeding of the thirty-first conference on artificial intelligence

Rubinstein A (2016) Settling the complexity of computing approximate two-player Nash equilibria. In: Proceeding of FOCS, pp 258–265

Vijay V, Chandra S, Bector CR (2005) Matrix games with fuzzy goals and fuzzy payoffs. Omega Int J Manag Sci 33:425–429CrossRef

Zadeh LA (1978) Fuzzy sets as a basis for a theory of possibility. Fuzzy Sets Syst 1:3–28MathSciNetCrossRef

Zimmermann H-J (2011) Fuzzy set theory and its application, 4th edn. Kluwer Academic Publishers, Berlin

Titel: An algorithm for finding approximate Nash equilibria in bimatrix games
verfasst von: Lunshan Gao
Publikationsdatum: 10.08.2020
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 2/2021
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-020-05213-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2021

Locally -complete and locally complete EMV-algebras

A novel statistical decimal pattern-based surface electromyogram signal classification method using tunable q-factor wavelet transform

Experimental investigation and comparative machine-learning prediction of compressive strength of recycled aggregate concrete

General type-2 fuzzy sliding mode control for motion balance adjusting of power-line inspection robot

Development of smart controller for demand side management in smart grid using reactive power optimization

Shadowed type 2 fuzzy-based Markov model to predict shortest path with optimized waiting time

Premium Partner