Top

Published in:

2016 | OriginalPaper | Chapter

Search of Nash Equilibrium in Quadratic n-person Game

Author : Ilya Minarchenko

Published in: Discrete Optimization and Operations Research

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

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.

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 On the Existence of Immigration Proof Partition into Countries in Multidimensional Space

next chapter 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

Title: Search of Nash Equilibrium in Quadratic n-person Game
Author: Ilya Minarchenko
Publisher: Springer International Publishing
Book: Discrete Optimization and Operations Research
Print ISBN: 978-3-319-44913-5

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

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

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner