nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Search of Nash Equilibrium in Quadratic n-person Game

verfasst von : Ilya Minarchenko

Erschienen in: Discrete Optimization and Operations Research

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

This paper is devoted to Nash equilibrium search in quadratic n-person game, where payoff function of each player is quadratic with respect to its strategic variable. Interactions between players are defined by corresponding bilinear terms in the payoffs. First, the statement is considered without any assumptions on payoffs’ concavity. We use Nikaido-Isoda approach in order to reduce Nash equilibrium problem to optimization problem with nonconvex implicitly defined objective function. We propose global search algorithm based on the linearization of implicit part of the objective by linear support minorants. This technique allows to determine numerically whether the game has no equilibria. Then payoffs are assumed to be concave with respect to its strategic variables, and we suggest d.c. decomposition of the objective, thus corresponding local search method is applicable. Computational results are provided in the paper. Local search method is compared with extragradient equilibrium search algorithm.

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 "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

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

Vorheriges Kapitel On the Existence of Immigration Proof Partition into Countries in Multidimensional Space

Nächstes Kapitel Convergence of Discrete Approximations of Stochastic Programming Problems with Probabilistic Criteria

Rosen, J.B.: Existence and uniqueness of equilibrium points for concave \(n\)-person games. Econometrica 33(3), 520–534 (1965)MathSciNetCrossRefMATH

Zukhovitskiy, S.I., Polyak, R.A., Primak, M.E.: Many-person convex games. Economica i Mat. Metody 7(6), 888–900 (1971). (in Russian)

Krawczyk, J., Uryasev, S.: Relaxation algorithms to find nash equilibria with economic applications. Environ. Model. Assess. 5, 63–73 (2000)CrossRef

Krawczyk, J.: Numerical solutions to coupled-constraint (or generalized nash) equilibrium problems. CMS 4, 183–204 (2007)MathSciNetCrossRefMATH

Strekalovskiy, A.S., Orlov, A.V.: Bimatrix Games and Bilinear Programming. FIZMATLIT, Moscow (2007) (in Russian)

Flam, S.D., Ruszczynski, A.: Finding normalized equilibrium in convex-concave games. Int. Game Theory Rev. 10(1), 37–51 (2008)MathSciNetCrossRefMATH

von Heusinger, A., Kanzow, C.: Relaxation methods for generalized nash equilibrium problems with inexact line search. J. Optim. Theory Appl. 143, 159–183 (2009)MathSciNetCrossRefMATH

Dreves, A., von Heusinger, A., Kanzow, C., Fukushima, M.: A globalized newton method for the computation of normalized nash equilibria. J. Glob. Optim. 56, 327–340 (2013)MathSciNetCrossRefMATH

Antipin, A.S.: Equilibrium programming: gradient methods. Autom. Remote Control 58(8), 1337–1347 (1997)MathSciNetMATH

10.

Schiro, D.A., Pang, J.-S., Shanbhag, U.V.: On the solution of affine generalized nash equilibrium problems with shared constraints by Lemke’s Method. Math. Program., Ser. A. 142, 1–46 (2013)

11.

Dreves, A.: Finding all solutions of affine generalized nash equilibrium problems with one-dimensional strategy sets. Math. Meth. Oper. Res. 80, 139–159 (2014)MathSciNetCrossRefMATH

12.

Antipin, A.S.: Gradient and Extragradient Approaches in Bilinear Equilibrium Programming. Dorodnitsyn Computing Center RAS, Moscow (2002). (in Russian)

13.

Kakutani, S.: A generalization of Brouwer’s fixed point theorem. Duke Math. J. 8, 457–458 (1941)MathSciNetCrossRefMATH

14.

Minarchenko, I.M.: Support function method in bilinear two-person game. Bull. Tambov State Univ. 20(5), 1312–1316 (2015). (in Russian)

15.

Garg, J., Jiang, A.X., Mehta, R.: Bilinear games: polynomial time algorithms for rank based subclasses. In: Chen, N., Elkind, E., Koutsoupias, E. (eds.) Internet and Network Economics. LNCS, vol. 7090, pp. 399–407. Springer, Heidelberg (2011)CrossRef

16.

Nikaido, H., Isoda, K.: Note on noncooperative convex games. Pac. J. Math. 5(5), 807–815 (1955)MathSciNetCrossRefMATH

17.

Mills, H.: Equilibrium points in finite games. J. Soc. Ind. Appl. Math. 8(2), 397–402 (1960)MathSciNetCrossRefMATH

18.

Mangasarian, O.L.: Equilibrium points of bimatrix games. J. Soc. Ind. Appl. Math. 12, 778–780 (1964)MathSciNetCrossRefMATH

19.

Strekalovskiy, A.S., Enkhbat, R.: Polymatrix games and optimization problems. Autom. Remote Control 75(4), 632–645 (2014)MathSciNetCrossRefMATH

20.

Cavazutti, E., Flam, S.D.: Evolution to selected Nash equilibria. In: Giannessi, F. (ed.) Nonsmooth Optimization Methods and Applications, pp. 30–41. Gordon and Breach, London (1992)

21.

The General Algebraic Modeling System. http://www.gams.com

22.

Bulatov, V.P.: Numerical methods for solving the multiextremal problems connected with the inverse mathematical programming problems. J. Glob. Optim. 12, 405–413 (1998)MathSciNetCrossRefMATH

23.

Khamisov, O.V.: A Global Optimization Approach to Solving Equilibrium Programming Problems. Series on Computers and Operations Research 1: Optimization and Optimal Control, pp. 155–164 (2003)

24.

Monderer, D., Shapley, L.S.: Potential games. Games Econ. Behav. 14, 124–143 (1996)MathSciNetCrossRefMATH

25.

Khamisov, O.V., Minarchenko, I.M.: Local search in bilinear two-person game. Bull. Siberian State Aerosp. Univ. 17(1), 91–96 (2016)

26.

Strekalovskiy, A.S.: On local search in d.c. optimization problems. Appl. Math. Comput. 255, 73–83 (2015)MathSciNet

Titel: Search of Nash Equilibrium in Quadratic n-person Game
verfasst von: Ilya Minarchenko
Verlag: Springer International Publishing
Buch: Discrete Optimization and Operations Research
Print ISBN: 978-3-319-44913-5

Electronic ISBN: 978-3-319-44914-2

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-44914-2_40

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 "Technik"

Springer Professional "Wirtschaft"

Premium Partner