We formulate the problem of nding 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 curvilinear algorithm which allows us to nd 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.
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 rm competitions at oligopoly markets where each rm maximizes its own pro t using the same price which depends on the sum of quantities produced by the rms. Existence of Nash equilibrium points have been proved in [11, 12]. In recent years, computational methods of game theory or equivalently, nding Nash equilibrium points in various games have been intensively studying in the literature [2, 3, 6{10, 13{17]. As usual, nding 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 ful ll 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 Curvilinear 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
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:
Dq = { u 2 Rq
q ∑ ui = 1; ui i=1
} 0; i = 1; : : : ; q : A mixed strategy for player 1 is a vector x = (x1; x2; : : : ; xm) 2 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) 2 Dn and z = (z1; z2; : : : ; zs) 2 Ds. Their expected payoffs are given by:
m n s f1(x; y; z) = ∑ ∑ ∑ aijkxiyjzk; i=1 j=1 k=1 m n s f2(x; y; z) = ∑ ∑ ∑ bijkxiyjzk; i=1 j=1 k=1 m n s f3(x; y; z) = ∑ ∑ ∑ cijkxiyjzk:
i=1 j=1 k=1 De nition 1. A triple of mixed strategies x 2 Dm; y 2 Dn; z 2 Ds; is a Nash equilibrium if 8< f1(x ; y ; z )
f2(x ; y ; z ) : f3(x ; y ; z ) f1(x; y ; z ); f2(x ; y; z ); f3(x ; y ; z); 8x 2 Dm; 8y 2 Dn; 8z 2 Ds: It is clear that f1(x ; y ; z ) = max f1(x; y ; z );
x2Dm f2(x ; y ; z ) = max f2(x ; y; z );
y2Dn f3(x ; y ; z ) = max f3(x ; y ; z):
z2Ds 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 8 ∑im=1 ∑sk=1 aijkxi yj zk
i=1 ∑∑∑jjjnnn===111 ∑sk=1 cijkxi yj zk
< ∑im=1 ∑sk=1 bijkxi yj zk
: ∑m
∑∑∑jjjnnn===111 ∑sk=1 cijkxi yj ; k = 1; 2; : : : ; s:
∑sk=1 aijkyj zk; i = 1; 2; : : : ; m;
∑sk=1 bijkxi zk; j = 1; 2; : : : ; n;
(
Proof. Necessity: Assume that (x ; y ; z ) is a Nash equilibrium. Then by de nition 1,
we have
m n s
∑ ∑ ∑ aijkxi yj zk
i=1 j=1 k=1
m n s
∑ ∑ ∑ aijkxi yj zk
i=1 j=1 k=1
m n s
∑ ∑ ∑ aijkxi yj zk
In the rst inequality (
i=1 xi = ∑jn=1 yj = ∑sk=1 zk = 1 we have f1(x ; y ; z )
f1(x; y ; z ); f2(x ; y ; z ) f3(x ; y ; z ) f2(x ; y; z ); f3(x ; y ; z); 8x 2 Dm; 8y 2 Dn; 8z 2 Ds; which shows that (x ; y ; z ) is a Nash equilibrium. The proof is complete.
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:
max (x;y;z;p;q;t)
m n s
F (x; y; z; p; q; t) = ∑ ∑ ∑(aijk + bijk + cijk)xiyj zk
i=1 j=1 k=1
p
q
t
(
m n s f1(x; y; z) = ∑ ∑ ∑ aijkxiyj zk i=1 j=1 k=1
p;
n s
∑ ∑ aijkyj zk
j=1 k=1
m s
∑ ∑ bijkxizk
i=1 k=1
m n
∑ ∑ cijkxiyj
i=1 j=1
m
∑ xi = 1;
i=1
n
∑ yj = 1;
j=1
s
∑ zk = 1;
k=1
xi
yj
zk
p;
q;
t;
0;
0;
0;
i = 1; : : : ; m;
j = 1; : : : ; n;
k = 1; : : : ; s;
i = 1; : : : ; m;
j = 1; : : : ; n;
k = 1; : : : ; s:
(
m n s
F (x; y; z; p; q; t) = ∑ ∑ ∑(aijk + bijk + cijk)xiyjzk
i=1 j=1 k=1
p q t
0
for all x 2 Dm; y 2 Dn and z 2 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 (
Sufficiency: Now we have to show reverse, namely, that any solution of problem
(
m n s
F (x; y; z; p; q; t) = ∑ ∑ ∑ [aijk + bijk + cijk] xiyjzk
i=1 j=1 k=1
p q t
0:
(
m n s F (x; y; z; p; q; t) = (∑ ∑ ∑ aijkxiyjzk i=1 j=1 k=1 m n s + (∑ ∑ ∑ bijkxiyjzk i=1 j=1 k=1 m n s + (∑ ∑ ∑ cijkxiyjzk i=1 j=1 k=1 p) + q) + t) = 0: 8 ∑im=1 ∑sk=1 aijkxiyjzk = p;
i=1 ∑∑∑jjjnnn===111 ∑sk=1 cijkxiyjzk = t:
< ∑im=1 ∑sk=1 bijkxiyjzk = q;
: ∑m
(
i=1 ∑∑∑jjjnnn===111 ∑sk=1 cijkxiyjzk < ∑im=1 ∑sk=1 bijkxiyjzk : ∑m ∑∑jnm=1 ∑sk=1 aijkyjzk; i = 1; : : : ; m;
i=1 ∑sk=1 bijkxizk; j = 1; : : : ; n; ∑im=1 ∑jn=1 cijkxiyj; k = 1; : : : ; s: Now taking into account the above results, by Theorem 1 we conclude that (x; y; z) is a Nash equilibrium point which completes the proof. 2
In order to solve problem (
q2(x); if q(x) > 0: Thus, we have the following box-constrained optimization problem: f^(x) = f (x) + 2 ∑ g^i(x) + i 2 ∑ q^j(x) ! min;
j X X = {x 2 Rnjxi 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], [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 nding some local minimums we increase it for searching another local minimum.
The proposed algorithm starts from some initial point x1 2 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 2 X { initial (start) point; K > 0 { iterations count;
Output: Global minimum point x and f = f (x ); 1 for k 2 f k 1 to K do f (xk); 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 (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 ags: -O2 -DNDEBUG
Three problems of type (
2x1y1 3x1y2 + 2x2y1 + 2x2y2 >> x1 + x2 > >>> y1 + y2 > >>> z1 + z2 >>:>>>> zx11 00;; zx22 00;; py1 0;0;q y2 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.
Problem 4. We have considered competitions of 3 companies sharing the bread market of city Ulaanbataar where each company maximizes own pro t depending on its manufacturing strategies. The problem was formulated as the three-person game with pro t matrices A = faijkg, B = fbijkg, C = fcijkg, 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: 8 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 rst 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 pro ts were 65, 160 and 53 respectively.
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 optimization problem. Based on generalization of Mills's theorem [10] (1960), we derive a sufficient condition for Nash equilibrium points for the game. To nd the equilibrium 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.
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.