The problem of nding a Nash equilibrium in polymatrix game of three players (hexamatrix game) is considered. For the equivalent nonconvex optimization problem an issue of local search is investigated. First, we study the special local search method (SLSM), based on the linearization of the original problem with respect to basic nonconvexity. Then the new local search procedure is elaborated. This procedure uses the bilinear structure of the objective function and is based on the consecutive solving of auxiliary linear programs. At the end of the paper the results of comparative computational simulation for two local search methods are presented and analyzed.
As known, the e cient numerical methods for solving problems of Game Theory is
the important issue of the contemporary mathematical optimization [
The new nonconvex optimization approach to numerical nding of Nash equilibria
in bimatrix games, based on Mills theorem [
Copyright c by the paper's authors. Copying permitted for private and academic purposes. In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org
The reduced problem belongs to the class of nonconvex optimization problems with
functions of A.D. Alexandrov, since it is easy to show that a bilinear function can be
represented as the di erence of two convex functions [
According to GST, one of the key elements of global search algorithms in the reduced
problems is specialized local search methods, taking into account the structure of the
problem under investigation [
In this paper two local search methods for hexamatrix games are studied. The
rst method employs the d.c. structure of the problem in question and applies the
linearization of the problem with respect to the basic nonconvexity [
Consider the following hexamatrix game with mixed strategies
F1(x; y; z) , hx; A1y + A2zi " max; x 2 Sm ; 9
x >> F2(x; y; z) , hy; B1x + B2zi " max; y 2 Sn ; =
y F3(x; y; z) , hz; C1x + C2yi " max; z 2 Sl ; >;> z where Sp = fu = (u1; : : : ; up)T 2 IRp ui 0; p = m; n; l: De nition 1. a) The triple (x ; y ; z ) 2 Sm
Sl satisfying the inequalities p X ui = 1g; i=1
Sn v1 = v1(x ; y ; z ) , F1(x ; y ; z ) v2 = v2(x ; y ; z ) , F2(x ; y ; z ) v3 = v3(x ; y ; z ) , F3(x ; y ; z )
F1(x; y ; z ) 8x 2 Sm ; 9
= F2(x ; y; z ) 8y 2 Sn ; F3(x ; y ; z) 8z 2 Sl ; will be henceforth called a Nash equilibrium point in the game 3 = (A; B; C) (A = (A1; A2), B = (B1; B2), C = (C1; C2)). Herewith, the strategies x , y , and z will be called the equilibrium strategies.
b) The numbers v1 , v2 , and v3 will be called the payo s of players 1, 2, and 3, respectively, at the equilibrium point (x ; y ; z ).
c) Denote the set of all Nash equilibrium points of the game 3 = (A; B; C) by N E = N E( 3) = N E( (A; B; C)).
It is well known that in the case of the game 3 = (A; B; C) due to Nash's
Theorem [
From the viewpoint of a real numerical search the following de nition of approximate Nash equilibrium point is appropriated. De nition 2. The triple (x0; y0; z0) 2 Sm Sn
Sl =: S satisfying the inequalities will be called an "-Nash equilibrium point for the game 3 ((x0; y0; z0) 2 N E( 3; ")).
Further consider the following optimization problem (
, (x; y; z; ; ; )):
( ) , hx; A1y + A2zi + hy; B1x + B2zi+
+hz; C1x + C2yi " max ;
2 D , f(x; y; z; ; ; ) 2 IRm+n+l+3 j x 2 Sm; y 2 Sn; z 2 Sl ; >
A1y + A2z em; B1x + B2z en; C1x + C2y elg ; >;
9
>
>
=
(P)
where ep = (1; 1; :::; 1) 2 IRp; p = m; n; l:
Lemma 1. [
Thus, the seeking for a Nash equilibrium can be carried out by approximate solving
Problem (P). To this end, we propose to use the Global Search Theory mentioned
above [
The reminder of the paper will be devoted to the rst stage of the approach.
Local Search Method for D.C. Formulation of Problem (P ) It can be readily seen that the objective function of Problem (P) (which is the special kind of quadratic functions with bilinear structure) is a d.c. function, since it can be represented as a di erence of two convex functions, for example, in the following way: (x; y; z; ; ; ) = h0(x; y; z) g0(x; y; z; ; ; ) ;
1 h0(x; y; z) = 4 kx + A1yk2 + kx + A2zk2+ +kB1x + yk2 + ky + B2zk2 + kC1x + zk2 + kC2y + zk2 ;
1 g0( ) = 4 kx A1yk2 + kx A2zk2 + ky B1xk2 + ky +kC1x zk2 + kC2y zk2 + + + :
B2zk2+ >> > > > > ; 9 > > > > > > = (1) (2) Besides, one can show that these functions are convex on (x; y; z) and , respectively.
Thus, the rst method of local search, which can be suggested here, is the Special
Local Search Method (SLSM) for d.c. programming [
In terms of Problem (P) the scheme of the SLSM can be written in the following way. Let 0 = (x0; y0; z0; 0; 0; 0) 2 D be a starting point. Further if one has the point s 2 D (at a current iteration), then the next point s+1 2 D is an approximate solution of the linearized (at the point s 2 D) problem: s( ) , g0( ) + has; xi + hbs; yi + hcs; zi # min; 2 D ; (PL( s)) where where as , bs , cs , [2xs + A1ys + (B1xs + ys)B1 + A2zs + (C1xs + zs)C1] ; [2ys + B1xs + (xs + A1ys)A1 + B2zs + (C1ys + zs)C2] ; [2zs + C1xs + (xs + A2zs)A2 + C2ys + (ys + B2zs)B2] :
1 s > 0; s = 0; 1; 2; :::; X s
+1 ; s=0 be given. Then the next iteration s+1 2 D is constructed to satisfy the following inequality:
The convergence theorem will be presented here in terms of Problem (P). Note that
the objective function of Problem (P) is bounded below due to Theorem 1 and Nash's
Theorem.
Theorem 2. [
b) If the function h0( ) is strongly convex, then we have lim k s s+1k = 0. s!1 c) Any limit point ^ of the sequence f sg generated by the SLSM is a solution of the linearized problem (PL(^)).
The point ^ be called a critical (with respect to the SLSM) point to Problem (P).
The resulting critical point will also satisfy classical rst order stationarity condition
[
In the implementation of the SLSM the following inequality can be used as a
stopping criterion:
s( s)
where > 0 is the given accuracy. If s =2 then point s will be -critical point to
Problem (P) with respect to the SLSM [
"Mountain Climbing" Procedure
The second idea of a local search in Problem (P) nds its roots in the "mountain
climbing" procedure, which is proposed by H. Konno [
Similar idea of a local search have previously demonstrated its e ciency in bimatrix
games [
In order to describe the method, consider the following LP problems: f (v;w)(x; ) , hx; (A1 + B1T )v + (A2 + C1T )wi 1
(x; ) 2 X(v; w; ) , f(x; ) j x 2 Sm;
B1x en B2w; C1x el C2vg ; f (u;w)(y; ) , hy; (B1 + A1T )u + (B2 + C2T )wi 2
(y; ) 2 Y (u; w; ) , f(y; ) j y 2 Sn;
A1y em A2w; C2y el C1ug ; f (u;v)(z; ) , hz; (C1 + A2T )u + (C2 + B2T )vi 3
(z; ) 2 Z(u; v; ) , f(z; ) j z 2 Sl; A2z em A1v; B2z en B1ug : " m(x;ax) ; 9>= " m(y;ax) ; 9>= " m(z;ax) ; 9>= > ; > ; > ; Here (u; v; w; ; ; ) 2 D is a feasible solution to Problem (P). (LPx(v; w; )) (LPy(u; w; )) (LPz(u; v; ))
It is easy to see that these problems will be feasible and bounded due to the boundedness from above of the function ( ) on the set D by Lemma 1.
Let (x0; y0; z0; 0; 0; 0) 2 D be a starting point. For example, one can use the barycenters of standard simplexes as follows: xi0 = 1 1
; i = 1; :::; m; yj0 = ; j = 1; :::; n; m n 0 = max(A1y0 + A2z0)i; i
1 zt0 = ; t = 1; :::; l ;
l 0 = max(B1x0 + B2z0)j ;
j 0 = max(C1x0 + C2y0)t :
t Y Z -procedure (4) Step 0. Set s := 1, ys := y0, zs := z0, s := 0.
Step 1. Using an LP technique, nd a s=3-solution (xs+1; s+1) to Problem (LPx(ys; zs; s)), so that the following inequality holds: f1s(xs+1; s+1) + s=3 := f (ys;zs)(xs+1; s+1) + s=3 ,
1 = hxs+1; (A1 + B1T )ys + (A2 + C1T )zsi s+1 + s=3 sup ff1s(x; ) j (x; ) 2 X(ys; zs; s)g : (x; )
Step 2. Find a s=3-solution (ys+1; s+1) to Problem (LPy(xs+1; zs; s)), so that the following inequality takes place: f2s(ys+1; s+1) + s=3 := f (xs+1;zs)(ys+1; s+1) + s=3 ,
2 = hys+1; (B1 + A1T )xs+1 + (B2 + C2T )zsi s+1 + s=3 sup ff2s(y; ) j (y; ) 2 Y (xs+1; zs; s)g : (y; )
Step 3. Find a s=3-solution (zs+1; s+1) (LPz(xs+1; ys+1; s+1)), so that the following inequality holds: to
Problem f3s(zs+1; s+1) + s=3 := f (xs+1;ys+1)(zs+1; s+1) + s=3 ,
3 = hzs+1; (C1 + A2T )xs+1 + (C2 + B2T )ys+1i s+1 + s=3 sup ff3s(z; ) j (z; ) 2 Z(xs+1; ys+1; s+1)g : (z; ) Step 4. Set s := s + 1, and loop to Step 1.
Note that the whole point (x0; y0; z0; 0; 0; 0) is not required to start the Y Z procedure, only the part (y0; z0; 0) is su cient.
The following convergence result of the local search method described above takes place. 1 Theorem 3. Suppose, s > 0; s = 0; 1; 2; : : : ; P s < +1. Then the sequence of s=0 vectors s , (xs; ys; zs; s; s; s), produced by the Y Z -procedure, converges to the point ^ , (x^; y^; z^; ^; ^; ^), which satis es the following inequalities: (^) (x; y^; z^; ^; ; ^) 8(x; ) 2 X(y^; z^; ^) ; (^) (^) (x^; y; z^; ^; ^; ) 8(y; ) 2 Y (x^; z^; ^) ; (x^; y^; z; ; ^; ^) 8(z; ) 2 Z(x^; y^; ^) :
Note, here we present the convergence result for sequence f sg, in contrast to the
theorem from [
It can be readily seen, that this concept of a critical point to Problem (P) is due to the structure of the proposed local search method. Moreover, the structure of the Y Z -procedure suggests using the following inequalities as the stopping criterion: f1s(xs+1; s+1)
f1s(xs; s) f2s(ys+1; s+1) f3s(zs+1; s+1) f2s(ys; s) f3s(zs; s) 3 3 3 ; ; ; where > 0 is the given accuracy.
Note that summing three inequalities (8){(10), the conventional for classical numerical methods criterion s+1 s is obtained. Wherein usage of the system (8){(10) instead of this inequality agrees with the goal of the local search ( nding a critical point which is a partial global solution to Problem (P) with respect to three pairs of variables).
It can be shown that when at the iteration s of the Y Z -procedure the system (8){ (10) is ful lled, we obtain an approximate critical point to Problem (P) in the sense of De nition 3.
Now let us move on to a description of a numerical experiment. 5
The both local search methods have been implemented with the help of MATLAB 7.11
R2010b [
Test hexamatrix games were randomly generated by the relevant subroutines of MATLAB by the following rules. Pseudorandom elements of matrices A1, A2, B1, B2, C1, and C2 have an uniform distribution and were choosing with the accuracy 10 3 from the interval ] 10; 10[, when minfm; n; lg 10, and from the interval ] minfm; n; lg; minfm; n; lg[, when minfm; n; lg > 10. (6) (7) (8) (9) (10)
The starting point for both methods was chosen according to the formula (4). The accuracy of the stopping criteria was = 10 3.
Firstly, let us present the results of the SLSM testing on the problem series of dimension (m + n + l) from (5 + 5 + 5) up to (50 + 50 + 50), that speci ed in Table 1. There was 1000, 100, and 10 problems in each series depending on the dimension of the problems (see Table 1).
In addition, the following notations have been used in Table 1: QP is the total number of convex quadratic problems solved in course of the SLSM, T stands for the total CPU time for all problems of series (in seconds); 0avg is the average value of the objective function of Problem (P) at the starting point; ^avg is the average value of the function at the obtained approximately critical point; ^avg is the worst value of the function at critical points; F ailed is the number of problems where an approximate critical point has not been obtained.
Note that in several problems an approximate critical point has not been obtained because the maximum number of iterations 100(m+n+l) has been attained. As a whole, this variant of the SLSM shows itself very slow and ine cient. It can be explained by the bad properties of the Hessian of Problem (PL( s)) at each iteration of the method. In particular, function h0( ) is not strongly convex (see Theorem 2). In order to improve these properties let us consider another regularized d.c. representation of the function : ( ) = h1( ) g1( ) ; where h1( ) = h0(x; y; z) + k k2; g1( ) = g0( ) + k k 2 with a regularizing parameter > 0 and Euclidean norm.
Thus, the functions h1( ) and g1( ) are strongly convex with respect to variable , and in accordance with convex optimization theory, the convergence of numerical methods for solving Problem (PL( s)) is going to be faster.
The results of the regularized SLSM testing, where = 10(m + n + l) are presented in Table 2 with the same notations.
It can be readily seen that the second variant of the SLSM nds a critical point much faster than the SLSM with d.c. representation (1){(2). Especially it appears for problems of high dimensions. For example, for problems with (40 + 40 + 40) dimension the time rate is more than 150 times less. Moreover, only for one problem an approximate point has not been obtained because the threshold number of iterations 10(m + n + l) was overcome.
On the other hand, the values ^avg and ^worst obtained by regularized SLSM are
farther from the global value 0 than for the rst variant of the method. At the same
time, the main goal of the local search stage according to the Global Search Theory
is the obtaining a critical point (point with "good" properties, see (5){(7)) as fast as
possible, because in course of a global search it is necessary to carry out a local search
many times [
Now let us pass to the testing of the Y Z -procedure and its comparison with the SLSM. The Y Z -procedure shows promising e ciency during the preliminary computational simulation, therefore the series of test problems were increased for each dimension. In Table 3 the results of applying the Y Z -procedure to the problem series from (5 + 5 + 5) up to (200 + 200 + 200) dimension are presented. There was 10000, 1000, 100 and 10 problems in each series. In Table 3 the notation LP instead of the notation QP has been used, because the auxiliary problems within the Y Z -procedure are linear programs. All the other notations are the same as before.
Further, in Table 4 the results of testing the regularized SLSM with = maxfm; n; lg(m+ n + l) is presented. Such a value of regularizing parameter was chosen for ensuring the diagonal predominance in the matrix of quadratic problem (PL( s)), which was built by the random matrices A1, A2, B1, B2, C1, and C2.
First of all, it is worth to emphasize the advantage of the Y Z -procedure concerning the speed of nding a critical points in random generated hexamatrix games. This advantage increases from 1.8 times for the problems of (5+5+5) dimension up to approximately 20 times for the problems of (125+125+125) and (200+200+200) dimension. Therefore, the Y Z -procedure is much more faster than the regularized SLSM especially for problems of high dimension.
As for ^avg and ^worst values for the Y Z -procedure they are considerably closer to 0 than for the regularized SLSM and even they are comparable with the corresponding values for the SLSM with the d.c. representation (1){(2) (see Table 1). In particular, note that the average values of the objective function at critical points provided the Y Z -procedure are not far from its global value.
So one can see that the reliability of the Y Z -procedure is superior than this one for the regularized SLSM (only 1 failed problem for all series versus 4 problems, respectively).
To sum up, based on the results of computational simulation, we can conclude that for the purpose of a local search, within global search algorithms, the using of the Y Z -procedure is more preferable. 6
In the paper the problem of nding a Nash equilibrium in hexamatrix games was considered. For the equivalent nonconvex optimization problem an issue of a local search was investigated. We studied two local search methods which are based on di erent ideas. First, we describe the special local search method (SLSM), based on the linearization of the original problem in d.c. form with respect to basic nonconvexity. Then the new local search procedure (so called the Y Z -procedure) was elaborated. This procedure is based on the consecutive solving of auxiliary linear programs and uses the bilinear structure of the objective function.
The results of comparative computational simulation for two local search methods certi ed the advantage of the Y Z -procedure with respect to the SLSM from the perspective of using them within the global search procedures, intended for a seeking a Nash equilibria in hexamatrix games.
Acknowledgments. This work is carried out under nancial support of Russian Science Foundation (project no. 15-11-20015).