Local search in quadratic two-person game

I. M. Minarchenko

The Bulletin of Irkutsk State University. Series Mathematics, Tome 18 (2016), pp. 60-73

Résumé

We consider a noncooperative two-person game in strategic form with quadratic players' loss functions. Loss function of every player is assumed to be strictly convex quadratic function with respect to own variable and linear with respect to another player's variable defining by corresponding bilinear term. Nash equilibrium problem for such a game is reduced to an equivalent minmax problem by Nikaido–Isoda approach. As the "inner" maximization problem does not admit analytical solution, the minmax problem is represented by the minimization problem of nonconvex implicitly defined function over the set of strategy profiles of the game. The "inner" maximization problem, which is turn out to be convex, is replaced by Lagrange dual problem. For the problem under consideration, it leads to d.c.-decomposition of the objective function. In other words, the objective is represented as a difference of two convex functions with implicit function that defines concave part of the decomposition. In this paper we propose a natural way to linearize concave term, and then iterative local search method for d.c.-functions is suggested to use. The main idea of this method is that the next point is chosen as a solution of auxiliary convex optimization problem where objective function is taken as initial objective with linearized concave term. Since the problem is nonconvex, we propose to use multistart of local search from randomly generated initial points. It is known, that minimum of the objective function is zero, and the set of the points bringing minimal value to the objective is coincide with the set of Nash equilibria of the game. Therefore one can easily verify whether stationary point obtained by local search is Nash equilibrium. In the paper we provide results of numerical testing of local search for d.c.-functions on the randomly generated problems and a comparison with some existing algorithms for computing Nash equilibria.

Détail

Keywords: Nash equilibrium, Nikaido–Isoda function, algorithms for computing Nash equilibria.
Mots-clés : d.c.-decomposition

Bibliographie

[1] Antipin A. S., Gradient and Extragradient Approaches in Bilinear Equilibrium Programming, Vychislitel'nyy Tsentr im. A. A. Dorodnitsyna RAN, M., 2002, 130 pp. (in Russian)

[2] Antipin A. S., “Equilibrium Programming: Gradient–Type Methods”, Avtomat. i Telemekh., 1997, no. 8, 125–137 (in Russian)

[3] Zukhovitskiy S. I., Polyak R. A., Primak M. E., “Many-Person Convex Games”, Economica i Mat. Metody, 7:6 (1971), 888–900 (in Russian)

[4] Strekalovskiy A. S., Orlov A. V., Bimatrix Games and Bilinear Programming, Fizmatlit, M., 2007, 224 pp. (in Russian)

[5] A. Dreves, “Finding All Solutions of Affine Generalized Nash Equilibrium Problems with One-dimensional Strategy Sets”, Math Meth Oper Res., 80 (2014), 139–159 | DOI | MR | Zbl

[6] S. D. Flam, A. Ruszczynski, “Finding Normalized Equilibrium in Convex-Concave Games”, International Game Theory Review, 10:1 (2008), 37–51 | DOI | MR | Zbl

[7] J. Garg, A. X. Jiang, R. Mehta, “Bilinear Games: Polynomial Time Algorithms for Rank Based Subclasses”, Internet and Network Economics, Lecture Notes in Computer Science, 7090, 2011, 399–407 | DOI

[8] A. von Heusinger, C. Kanzow, “Relaxation Methods for Generalized Nash Equilibrium Problems with Inexact Line Search”, J. Optim. Theory Appl., 143 (2009), 159–183 | DOI | MR | Zbl

[9] J. Krawczyk, “Numerical Solutions to Coupled-Constraint (or Generalized Nash) Equilibrium Problems”, CMS, 4 (2007), 183–204 | DOI | MR | Zbl

[10] J. Krawczyk, S. Uryasev, “Relaxation Algorithms to Find Nash Equilibria with Economic Applications”, Environmental Modeling and Assessment, 5 (2000), 63–73 | DOI

[11] O. L. Mangasarian, “Equilibrium Points of Bimatrix Games”, Journal of the Society for Industrial and Applied Mathematics, 12 (1964), 778–780 | DOI | MR | Zbl

[12] H. Mills, “Equilibrium Points in Finite Games”, Journal of the Society for Industrial and Applied Mathematics, 8:2 (1960), 397–402 | DOI | MR | Zbl

[13] H. Nikaido, K. Isoda, “Note on Noncooperative Convex Games”, Pacific Journal of Mathematics, 5:5 (1955), 807–815 | DOI | MR

[14] T. Quint, M. Shubik, “A Theorem on the Number of Nash Equilibriua in a Bimatrix Game”, International Journal of Game Theory, 26 (1997), 353–359 | DOI | MR | Zbl

[15] J. B. Rosen, “Existence and Uniqueness of Equilibrium Points for Concave N-Person Games”, Econometrica, 33:3 (1965), 520–534 | DOI | MR | Zbl

[16] D. A. Schiro, J.-S. Pang, U. V. Shanbhag, “On the Solution of Affine Generalized Nash Equilibrium Problems with Shared Constraints by Lemke's Method”, Math. Program., Ser. A, 142 (2013), 1–46 | DOI | MR | Zbl

[17] A. S. Strekalovskiy, R. Enkhbat, “Polymatrix Games and Optimization Problems”, Automation and Remote Control, 75:4 (2014), 632–645 | DOI | MR

[18] A. S. Strekalovsky, “On Local Search in D.C. Optimization Problems”, Applied Mathematics and Computation, 255 (2015), 73–83 | DOI | MR | Zbl