The Curvilinear Search Algorithm for Solving Three-Person Game Rentsen Enkhbat1 , Natsagdorj Tungalag1 , Alexander Gornov2 , and Anton Anikin2 1 National University of Mongolia renkhbat46@yahoo.com, n.tungalag@num.edu.mn, 2 Institute for System Dynamics and Control Theory, SB RAS, Russia gornov@icc.ru, anton.anikin@htower.ru Abstract. We formulate the problem of finding a Nash equilibrium point for the non-zero sum three-person game as a nonconvex optimization problem by generalizing Mills’s theorem [10]. For solving the problem, we propose the curvi- linear algorithm which allows us to find global solutions. The proposed algorithm was tested numerically on some examples as well as on 3 competitive companies which share the bread market of the city Ulaanbataar. Keywords: Game theory, optimality conditions, global optimization, the curvi- linear search algorithm Introduction It is well known that game theory plays an important role in economics, optimization and operations research. Game theory is found to be a powerful mathematical tool for modeling of firm competitions at oligopoly markets where each firm maximizes its own profit using the same price which depends on the sum of quantities produced by the firms. Existence of Nash equilibrium points have been proved in [11, 12]. In recent years, computational methods of game theory or equivalently, finding Nash equilibrium points in various games have been intensively studying in the literature [2, 3, 6–10, 13–17]. As usual, finding Nash equilibrium points in zero-sum games leads to linear programming while in non-zero sum game it requires solving nonconvex optimization problems. Global search for Nash equilibrium points have been mainly studied for polymatrix [5] and hexamatrix games by global optimization techniques [13–15]. But it seems to us that a little attention has been paid to computational aspects of non-zero sum three-person game. Aim of this paper is to fulfill this gap. The paper is organized as follows. Section 1 is devoted to formulation of non-zero sum three-person game in mixed strategies and its reduction to a nonconvex optimization. The Curvi- linear Search Algorithm has been considered in Section 2. Computational experiments has been examined in Section 3. 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 Curvilinear Search Algorithm for Solving Three-Person Game 575 1 Non-Zero Sum Three-person Game Consider the three-person game in mixed strategies with payoff matrices (A, B, C) for players 1,2 and 3. A = (aijk ), B = (bijk ), C = (cijk ), i = 1, . . . , m, j = 1, . . . , n, k = 1, . . . , s. Denote by Dq the set { } ∑ q Dq = u∈R q ui = 1, ui ≥ 0, i = 1, . . . , q . i=1 A mixed strategy for player 1 is a vector x = (x1 , x2 , . . . , xm ) ∈ Dm representing the probability that player 1 uses a strategy i. Similarly, the mixed strategies for players 2 and 3 are y = (y1 , y2 , . . . , yn ) ∈ Dn and z = (z1 , z2 , . . . , zs ) ∈ Ds . Their expected payoffs are given by: ∑m ∑n ∑s f1 (x, y, z) = aijk xi yj zk , i=1 j=1 k=1 ∑ m ∑ n ∑ s f2 (x, y, z) = bijk xi yj zk , i=1 j=1 k=1 ∑ m ∑ n ∑ s f3 (x, y, z) = cijk xi yj zk . i=1 j=1 k=1 Definition 1. A triple of mixed strategies x∗ ∈ Dm , y ∗ ∈ Dn , z ∗ ∈ Ds , is a Nash equilibrium if   f1 (x∗ , y ∗ , z ∗ ) ≥ f1 (x, y ∗ , z ∗ ), ∀x ∈ Dm , f2 (x∗ , y ∗ , z ∗ ) ≥ f2 (x∗ , y, z ∗ ), ∀y ∈ Dn ,  f3 (x∗ , y ∗ , z ∗ ) ≥ f3 (x∗ , y ∗ , z), ∀z ∈ Ds . It is clear that f1 (x∗ , y ∗ , z ∗ ) = max f1 (x, y ∗ , z ∗ ), x∈Dm f2 (x , y , z ) = max f2 (x∗ , y, z ∗ ), ∗ ∗ ∗ y∈Dn f3 (x∗ , y ∗ , z ∗ ) = max f3 (x∗ , y ∗ , z). z∈Ds For further purpose, it is useful to formulate the following statement. Theorem 1. A triple strategy (x∗ , y ∗ , z ∗ ) is a Nash equilibrium if and only if  ∑m ∑n ∑s ∗ ∗ ∗ ∑n ∑s ∗ ∗  ∑i=1 ∑j=1 ∑k=1 aijk xi yj zk ≥ ∑j=1 ∑k=1 aijk yj zk , i = 1, 2, . . . , m, m n s ∗ ∗ ∗ n s ∗ ∗ j=1 ∑k=1 bijk xi yj zk ≥ ∑j=1 ∑k=1 bijk xi zk , j = 1, 2, . . . , n, (1)  ∑i=1 m ∑n s ∗ ∗ ∗ n s ∗ ∗ i=1 j=1 k=1 cijk xi yj zk ≥ j=1 k=1 cijk xi yj , k = 1, 2, . . . , s. 576 Rentsen Enkhbat et al. Proof. Necessity: Assume that (x∗ , y ∗ , z ∗ ) is a Nash equilibrium. Then by definition 1, we have ∑m ∑ n ∑s ∑ n ∑ s ∗ ∗ ∗ aijk xi yj zk ≥ aijk xi yj∗ zk∗ , ∀x ∈ Dm , (2) i=1 j=1 k=1 j=1 k=1 m ∑ ∑ n ∑ s ∑ m ∑ s aijk x∗i yj∗ zk∗ ≥ aijk x∗i yj zk∗ , ∀y ∈ Dn , (3) i=1 j=1 k=1 i=1 k=1 ∑ m ∑ n ∑ s ∑ m ∑ n aijk x∗i yj∗ zk∗ ≥ aijk x∗i yj∗ zk , ∀z ∈ Ds . (4) i=1 j=1 k=1 i=1 j=1 In the first inequality (2), successively choose x = (0, 0, . . . , 1, . . . , 0) with 1 in each of the m spots, in (3) choose y = (0, 0, . . . , 1, . . . , 0) with 1 in each of the n spots, and in (4) choose z = (0, 0, . . . , 1, . . . , 0) with 1 in each of the s spots. We can easily see that ∑ n ∑ s f1 (x∗ , y ∗ , z ∗ ) ≥ aijk yj∗ zk∗ , i = 1, . . . , m, j=1 k=1 ∑ m ∑ s f2 (x∗ , y ∗ , z ∗ ) ≥ bijk x∗i zk∗ , j = 1, . . . , n, i=1 k=1 ∑ m ∑ n f3 (x∗ , y ∗ , z ∗ ) ≥ cijk x∗i yj∗ , k = 1, . . . , s. i=1 j=1 Sufficiency: Suppose that for a triple (x∗ , y ∗ , z ∗ ) ∈ Dm × Dn × Ds , conditions (1) are satisfied. We choose x ∈ Dm , y ∈ Dn and z ∈ Ds and multiply (1) by xi , yj and zk respectively. We obtain   ∑ m ∑m ∑n ∑ s ∑m ∑n ∑s xe  aijk x∗i yj∗ zk∗  ≥ aijk xi yj∗ zk∗ , e=1 i=1 j=1 k=1 i=1 j=1 k=1   ∑ n ∑m ∑ n ∑ s ∑ m ∑ n ∑ s ye  ∗ ∗ ∗  bijk xi yj zk ≥ bijk x∗i yj zk∗ , e=1 i=1 j=1 k=1 i=1 j=1 k=1   ∑ m ∑ m ∑ n ∑ s ∑ m ∑ n ∑ s ze  cijk x∗i yj∗ zk∗  ≥ cijk x∗i yj∗ zk . e=1 i=1 j=1 k=1 i=1 j=1 k=1 ∑m ∑n ∑s Taking into account that i=1 xi = j=1 yj = k=1 zk = 1 we have f1 (x∗ , y ∗ , z ∗ ) ≥ f1 (x, y ∗ , z ∗ ), ∀x ∈ Dm , f2 (x∗ , y ∗ , z ∗ ) ≥ f2 (x∗ , y, z ∗ ), ∀y ∈ Dn , ∗ ∗ ∗ ∗ ∗ f3 (x , y , z ) ≥ f3 (x , y , z), ∀z ∈ Ds , which shows that (x∗ , y ∗ , z ∗ ) is a Nash equilibrium. The proof is complete. The Curvilinear Search Algorithm for Solving Three-Person Game 577 Now we are ready to generalize Mills’s theorem [10] formulated originally for the bimatrix game of two players for three-person matrix game as follows. Theorem 2. A triple strategy (x∗ , y ∗ , z ∗ ) is a Nash equilibrium for the non-zero sum three-person game if and only if there exist scalars (p∗ , q ∗ , t∗ ) such that (x∗ , y ∗ , z ∗ , p∗ , q ∗ , t∗ ) is a solution to the following nonconvex optimization problem: ∑ m ∑ n ∑ s max F (x, y, z, p, q, t) = (aijk + bijk + cijk )xi yj zk − p − q − t (5) (x,y,z,p,q,t) i=1 j=1 k=1 subject to: ∑ n ∑ s aijk yj zk ≤ p, i = 1, . . . , m, (6) j=1 k=1 ∑ m ∑ s bijk xi zk ≤ q, j = 1, . . . , n, (7) i=1 k=1 ∑ m ∑ n cijk xi yj ≤ t, k = 1, . . . , s, (8) i=1 j=1 ∑ m xi = 1, xi ≥ 0, i = 1, . . . , m, i=1 ∑ n yj = 1, yj ≥ 0, j = 1, . . . , n, (9) j=1 ∑ s zk = 1, zk ≥ 0, k = 1, . . . , s. k=1 Proof. Necessity: Now suppose that (x∗ , y ∗ , z ∗ ) is a Nash equilibrium point. Choose scalars p∗ , q ∗ and t∗ as: p∗ = f1 (x∗ , y ∗ , z ∗ ), q ∗ = f2 (x∗ , y ∗ , z ∗ ), and t∗ = f3 (x∗ , y ∗ , z ∗ ). We show that (x∗ , y ∗ , z ∗ , p∗ , q ∗ , t∗ ) is a solution to problem (5)-(9). First, we show that (x∗ , y ∗ , z ∗ , p∗ , q ∗ , t∗ ) is a feasible point for problem (5). By Theorem 1, the equivalent characterization of a Nash equilibrium point, we have  ∑n ∑s  ∑j=1 ∑ k=1 aijk yj∗ zk∗ ≥ f1 (x∗ , y ∗ , z ∗ ), m s ∗ ∗ ∗ ∗ ∗ i=1 ∑k=1 bijk xi zk ≥ f2 (x , y , z ),  ∑m n ∗ ∗ ∗ ∗ ∗ i=1 j=1 cijk xi yj ≥ f3 (x , y , z ). The rest of the constraints are satisfied because of x ∈ Dm , y ∈ Dn and z ∈ Ds . It meant that (x∗ , y ∗ , z ∗ , p∗ , q ∗ , t∗ ) is a feasible point. Choose any x ∈ Dm , y ∈ Dn , z ∈ Ds and multiply (6)-(8) by xi , yj and zk respectively. If we have sum up these inequal- ities, we obtain ∑ m ∑ n ∑ s f1 (x, y, z) = aijk xi yj zk ≤ p, i=1 j=1 k=1 578 Rentsen Enkhbat et al. ∑ m ∑ n ∑ s f2 (x, y, z) = bijk xi yj zk ≤ q, i=1 j=1 k=1 ∑ m ∑ n ∑ s f3 (x, y, z) = cijk xi yj zk ≤ t. i=1 j=1 k=1 Hence, we get ∑ m ∑ n ∑ s F (x, y, z, p, q, t) = (aijk + bijk + cijk )xi yj zk − p − q − t ≤ 0 i=1 j=1 k=1 for all x ∈ Dm , y ∈ Dn and z ∈ Ds . But with p∗ = f1 (x∗ , y ∗ , z ∗ ), q ∗ = f2 (x∗ , y ∗ , z ∗ ), and t∗ = f3 (x∗ , y ∗ , z ∗ ), we have F (x∗ , y ∗ , z ∗ , p∗ , q ∗ , t∗ ) = 0. Hence, the point (x∗ , y ∗ , z ∗ , p∗ , q ∗ , t∗ ) is a solution to the problem (5)-(9). Sufficiency: Now we have to show reverse, namely, that any solution of problem (5)- (9) must be a Nash equilibrium point. Let (x̄, ȳ, z̄, p̄, q̄, t̄) be any solution of prob- lem (5)-(9). Let (x∗ , y ∗ , z ∗ ) be a Nash equilibrium point for the game, and set p∗ = f1 (x∗ , y ∗ , z ∗ ), q ∗ = f2 (x∗ , y ∗ , z ∗ ), and t∗ = f3 (x∗ , y ∗ , z ∗ ). We will show that (x̄, ȳ, z̄) must be a Nash equilibrium of the game. Since (x̄, ȳ, z̄, p̄, q̄, t̄) is a feasible point, we have ∑n ∑ s aijk ȳj z̄k ≤ p̄, i = 1, . . . , m, (10) j=1 k=1 ∑ m ∑ s bijk x̄i z̄k ≤ q̄, j = 1, . . . , n, (11) i=1 k=1 ∑ m ∑ n cijk x̄i ȳj ≤ t̄, k = 1, . . . , s. (12) i=1 j=1 Hence, we receive ∑ m ∑ n ∑ s aijk x̄i ȳj z̄k ≤ p̄, i=1 j=1 k=1 ∑ m ∑ n ∑ s bijk x̄i ȳj z̄k ≤ q̄, i=1 j=1 k=1 ∑ m ∑ n ∑ s cijk x̄i ȳj z̄k ≤ t̄. i=1 j=1 k=1 Adding these inequalities, we obtain ∑ m ∑ n ∑ s F (x̄, ȳ, z̄, p̄, q̄, t̄) = [aijk + bijk + cijk ] x̄i ȳj z̄k − p̄ − q̄ − t̄ ≤ 0. (13) i=1 j=1 k=1 The Curvilinear Search Algorithm for Solving Three-Person Game 579 We know that at a Nash equilibrium F (x∗ , y ∗ , z ∗ , p∗ , q ∗ , t∗ ) = 0. Since (x̄, ȳ, z̄, p̄, q̄, t̄) is also a solution, F (x̄, ȳ, z̄, p̄, q̄, t̄) be equal to zero: m ∑ ∑ n ∑ s F (x̄, ȳ, z̄, p̄, q̄, t̄) = ( aijk x̄i ȳj z̄k − p̄) + i=1 j=1 k=1 ∑m ∑ n ∑ s +( bijk x̄i ȳj z̄k − q̄) + (14) i=1 j=1 k=1 ∑m ∑ n ∑ s +( cijk x̄i ȳj z̄k − t̄) = 0. i=1 j=1 k=1 Consequently,  ∑m ∑n ∑s  ∑i=1 ∑j=1 ∑k=1 aijk x̄i ȳj z̄k = p̄, m n s j=1 ∑k=1 bijk x̄i ȳj z̄k = q̄,  ∑i=1 m ∑n s i=1 j=1 k=1 cijk x̄i ȳj z̄k = t̄. Since a point (x̄, ȳ, z̄, p̄, q̄, t̄) is feasible, we can write the constraints (10)-(12) as follows:  ∑m ∑n ∑s ∑n ∑s  ∑i=1 ∑j=1 ∑k=1 aijk x̄i ȳj z̄k ≤ ∑j=1 ∑ k=1 aijk ȳj z̄k , i = 1, . . . , m, m n s m s i=1 ∑j=1 ∑k=1 bijk x̄i ȳj z̄k ≤ ∑i=1 ∑k=1 bijk x̄i z̄k , j = 1, . . . , n,  ∑m n s m n i=1 j=1 k=1 cijk x̄i ȳj z̄ k ≤ i=1 j=1 c ijk x̄i ȳj , k = 1, . . . , s. Now taking into account the above results, by Theorem 1 we conclude that (x̄, ȳ, z̄) is a Nash equilibrium point which completes the proof. 2 The Curvilinear Global Search Algorithm In order to solve problem (5)-(9), we use curvilinear search algorithm introduced in [4]. This algorithm allows us to search for the minimum value of the function along the scanning domain curve. The algorithm was originally developed for solving box- constrained optimization problems, therefore, we convert our problem from the con- strained to unconstrained form using penalty function techniques. For each equality constraint g(x) = 0, we construct a simple penalty function ĝ(x) = g 2 (x). For each inequality constraint q(x) ≤ 0, we also construct the corresponding penalty function as follows: { 0, if q(x) ≤ 0, q̂(x) = q 2 (x), if q(x) > 0. Thus, we have the following box-constrained optimization problem: γ∑ γ∑ fˆ(x) = f (x) + ĝi (x) + q̂j (x) → min, 2 i 2 j X { } X = x ∈ Rn |xi ≤ xi ≤ xi , i = 1, ..., n . where γ is a penalty parameter, x and x - are upper and below bounds. For original x, y and z variables the constraint is the box [0, 1]; for p, q and t box constraints are [0, p], 580 Rentsen Enkhbat et al. [0, q] and [0, t]. Values of p, q and t are chosen from some intervals. An initial value of a penalty parameter γ is chosen not too large (something about 1000) and after finding some local minimums we increase it for searching another local minimum. The proposed algorithm starts from some initial point x1 ∈ X. At each k−th iteration the algorithm performs randomly “drop” of two auxiliary points x̃1 and x̃2 and generating a curve (parabola) which passes through all three points xk , x̃1 and x̃2 . Then we solve one-dimensional minimization problem along this curve. If a solution to this problem is better than xk , we use it as a new minimum point, otherwise, we start a new iteration from the previous point. Details are presented in Algorithm 1: Input: x1 ∈ X – initial (start) point; K > 0 – iterations count; Output: Global minimum point x∗ and f ∗ = f (x∗ ); 1 for k ← 1 to K do 2 f k ← f (xk ); 3 for i ← 1 to 2 do 4 generate stochastic point x̃i ∈ X; 5 if f (x̃i ) < f k then 6 xk+1 ← x̃i ; 7 go to the next iteration; 8 end 9 end 10 αk ← argmin f (x̂(α)), α∈[−1,1] 11 where ( ( ) ( ) ) 12 x̂(α) = ProjX α2 (x̃1 + x̃2 )/2 − xk + α/2 x̃2 − x̃1 + xk ; 13 ProjX (z) - projection of point z onto set X. 14 // note that x̂(−1) = x̂1 , x̂(1) = x̂2 , x̂(0) = xk 15 if f (x̂(αk )) < f k then 16 xk+1 = x̂(αk ); 17 else 18 xk+1 = xk ; 19 end 20 end 21 x∗ ← xk ; ∗ 22 f ← f (x ) k Algorithm 1: The Curvilinear Global Search 3 Computational Experiments The proposed method was implemented in C language and tested on compatibility with using the GNU Compiler Collection (GCC, versions: 4.8.4, 4.9.3, 5.2.1), clang The Curvilinear Search Algorithm for Solving Three-Person Game 581 (versions: 3.4.2, 3.5.2, 3.6.1, 3.7.0) and Intel C Compiler (ICC, version 15.0.3) on both GNU/Linux, Microsoft Windows and Mac OS X operating systems. The results of numerical experiments presented below were obtained on a personal computer with the following characteristics: – Ubuntu server 14.04, x86 64 – Intel Core i5-2500K, 16 Gb RAM – used compiler — gcc-5.2.1, build flags: -O2 -DNDEBUG Three problems of type (5)−(9) have been solved numerically for dimensions 2×2×2 (Problems 1–3) and 5 × 6 × 4 (Problem 4). In all cases, Nash equilibrium points were found successfully. These problems were: Problem 1. Let a111 = 2, a112 = 3, a121 = −1, a122 = 0, a211 = 1, a212 = −2, a221 = 4, a222 = 3, b111 = 1, b112 = 2, b121 = 0, b122 = −1, b211 = −1, b212 = 0, b221 = 2, b222 = 1, and c111 = 3, c112 = 2, c121 = 1, c122 = −3, c211 = 0, c212 = 2, c221 = −1, c222 = 2. Then problem (5)–(9) can be written as: F (x, y, z, p, q, t) = 6x1 y1 z1 + 7x1 y1 z2 − 4x1 y2 z2 + 5x2 y2 z1 + +6x2 y2 z2 − p − q − t → max .    2y1 z1 + 3y1 z2 − y2 z1 − p ≤ 0,     y z 1 1 − 2y z 1 2 + 4y z 2 1 + 3y z 2 2 − p ≤ 0,    1 1  x z + 2x z 1 2 − x z 2 1 − q ≤ 0,     −x z 1 2 + 2x z 2 1 + x z 2 2 − q ≤ 0,    1 1 3x y + x y 1 2 − x y 2 2 − t ≤ 0, 2x1 y1 − 3x1 y2 + 2x2 y1 + 2x2 y2 − t ≤ 0,     x1 + x2 = 1,     y 1 + y 2 = 1,     z1 + z2 = 1,     x 1 ≥ 0, x 2 ≥ 0, y 1 ≥ 0, y 2 ≥ 0,  z1 ≥ 0, z2 ≥ 0, p ≥ 0, q ≥ 0, t ≥ 0. Nash equilibrium points are: F∗ x∗ y∗ z∗ p q t 0 (0; 1) (0; 1) (0; 1) 3 1 2 0 (1; 0) (1; 0) (1; 0) 2 1 3 2.08 · 10−8 (0.5191; 0.4809) (0.5888; 0.4112) (0.5382; 0.4618) 1.2281 0.5 0.9327 3.37 · 10−8 (0.75; 0.25) (0.8333; 0.1667) (1.0; 0.0) 1.5 0.5 1.9583 Problem 2. Let a111 = 5, a112 = 3, a121 = 6, a122 = 7, a211 = 0, a212 = 8, a221 = 2, a222 = 1, b111 = 2, b112 = 4, b121 = −1, b122 = 0, b211 = 3, b212 = 5, b221 = 4, b222 = 9, and c111 = 2, c112 = 0, c121 = −4, c122 = −1, c211 = −2, c212 = 6, c221 = 8, c222 = 9. 582 Rentsen Enkhbat et al. Nash equilibrium points are: F∗ x∗ y∗ z∗ p q t 0 (1; 0) (1; 0) (1; 0) 5 2 2 2.6 · 10−8 (0.5; 0.5) (0.5454; 0.4545) (0; 1) 4.8181 4.5 3.4545 9.9 · 10−8 (0.8; 0.2) (1; 0) (0.5; 0.5) 4.0 3.2 1.2 Problem 3. Let a111 = 3, a112 = 2, a121 = 1, a122 = 5, a211 = 8, a212 = 4, a221 = 1, a222 = 3, b111 = 3, b112 = 2, b121 = 4, b122 = 0, b211 = 1, b212 = 8, b221 = 6, b222 = 6, and c111 = 3, c112 = 1, c121 = 9, c122 = 2, c211 = 4, c212 = 7, c221 = 2, c222 = 3. Nash equilibrium points are: F∗ x∗ y∗ z∗ pq t 0 (1; 0) (0; 1) (1; 0) 1 4 9 0 (0; 1) (1; 0) (0; 1) 4 8 7 0 (0.5; 0.5) (0; 1) (1; 0) 1 5 5.5 −1.33 · 10−15 (0.7; 0.3) (0; 1) (1; 0) 1 4.6 6.9 Problem 4. We have considered competitions of 3 companies sharing the bread mar- ket of city Ulaanbataar where each company maximizes own profit depending on its manufacturing strategies. The problem was formulated as the three-person game with profit matrices A = {aijk }, B = {bijk }, C = {cijk }, i = 1, 5, j = 1, 6, k = 1, 4. The matrix data can be downloaded from [1]. In this case the problem had 18 variables with 18 constraints. The solution of the problem found by the proposed algorithm was:  ∗   F = 0,     x∗ = (0, 0, 0, 0, 1),    y ∗ = (0, 0, 0, 0, 0, 1), z ∗ = (1, 0, 0, 0),     p∗ = 65,     q ∗ = 160,  ∗ t = 53. It means that first and second companies must follow their 5-th and 6-th production strategies while third company applies for its 1-st production strategy. Companies’s maximum profits were 65, 160 and 53 respectively. Conclusion We examine non-zero sum three-person matrix game from a view of point of global optimization. Finding a Nash equilibrium point of the game reduces to a global op- timization problem. Based on generalization of Mills’s theorem [10] (1960), we derive a sufficient condition for Nash equilibrium points for the game. To find the equilib- rium points we apply the curvilinear algorithm. The proposed algorithm found Nash equilibrium points in considered problems. The algorithm was tested also for solving a real-world problem which arises in Mongolian industry. The Curvilinear Search Algorithm for Solving Three-Person Game 583 Acknowledgements This work was partially supported by the research grants PROF2016-0070, P2016-1064 of National University of Mongolia and by the research grant 15-07-03827 of Russian Foundation for Basic Research. References 1. https://www.dropbox.com/s/137aaahvbniau9q/problem_4_data.txt 2. Batbileg, S., Enkhbat, R.: Global optimization approach to game theory. Journal of Mon- golian Mathematical Society 14, 2–11 (2010) 3. Dickhaut, J., Kaplan, T.: A program for finding nash equilibria. Mathematica J. (1), 87–93 (1991) 4. Gornov, A.Yu., Zarodnyuk, T.S.: Optimization, Simulation, and Control, chap. Tunneling Algorithm for Solving Nonconvex Optimal Control Problems, pp. 289–299. Springer New York (2013) 5. Howson, J.T.: Equilibria of polymatrix games. Management Sci. 18, 312–318 (1972) 6. Lemke, C.E., Howson, T.T.: Equilibrium points of bimatrix games. SIAM J. Appl. Math. 12, 413–423 (1961) 7. Mangasarian, O.L.: Equilibrium points in bimatrix games. J. Soc. Indust. Appl. Mathe- mat. 12, 778–780 (1964) 8. Mangasarian, O.L., Stone, H.: Two-person nonzero games and quadratic programming. J. Mathemat. Anal. Appl. (9), 348–355 (1964) 9. McKelvey, R.D., McLennan, A.: Computation of equilibria in finite games. In: Amman, H.M., Kendrick, D.A., Rust, J. (eds.) Handbook of Computational Economics, vol. 1, chap. 02, pp. 87–142. Elsevier, 1 edn. (1996) 10. Mills, H.: Equilibrium points in finite games. J. Soc. Indust. Appl. Mathemat. 8(2), 397– 402 (1960) 11. Nash, J.F.: Equilibrium points in n-person games. Proc. of the Nat. Acad. of Sci. USA 36, 48–49 (1950) 12. Nash, J.F.: Non-cooperative games. Annals of Mathematics 54(2), 286–295 (1951) 13. Orlov, A.V., Strekalovsky, A.S., Batbileg, S.: On computational search for nash equilib- rium in hexamatrix games. Optimization Letters 10(2), 369–381 (2014) 14. Strekalovsky, A.S., Enkhbat, R.: Polymatrix games and optimization problems. Automa- tion and Remote Control 75(4), 632–645 (2014) 15. Strekalovsky, A.S., Orlov, A.V.: Bimatrix Game and Bilinear Programming. Nauka (2007) 16. Vasilyev, I.L., Klimentova, K.B., Orlov, A.V.: A parallel search of equilibrium points in bimatrix games. Numerical methods and programming 8, 233–243 (2007) 17. Yanovskaya, E.B.: Equilibrium points in polymatrix games. Latvian Math. Col lect. 8, 381–384 (1968)