Stochastic game with lexicographic payoffs

Published Online April 2018 in MECS DOI: 10.5815/ijmecs.2018.04.02

• I.    Introduction

  Stochastic game is a noncooperative repeated game with randomized revert of the situations. At first such kind of games for several players and for scalar payoffs was defined by L. Shapley in 1953 year [1]. Then in detail they are studied in [2]. Stochastic game is played by some stages. At the beginning of each stage a game is in a certain situation. Players choose their activities and gain payoffs. They depend on current situation and activities. After this the system moves into another situation by randomization. At the same time the probability of moving depends on a previous situation and players activities. This procedure is repeated by finite or nonfinite number. A player's general payoff is often defined as payoff's sum on each stage. For players' finite number, for finite sets of activities and situations, in the process of a replay game by finite number, Nash

equilibrium always exists in scalar stochastic games. A two players stochastic game is studied by A. Condon as a complexity of a simple gambling game [3]. N. Vieille showed that in two players' stochastic game for the finite set of players' activities and situations, if payoff's functions are the low limit of payoffs average meanings on finite step, there is always Nash approximate equilibrium for the majority number of players. The problem of the existence such equilibrium is still open [4].

Stochastic games are used in many fields: economics, computer sciences, in systems management and ets. The usage of stochastic games in economics is dedicated the article [5] from works [2]. In this parer consider a recent trend in the application of stochastic games to economics characterized by the use of the lattice-theoretic approach to capture the monotonic properties of Markovian equilibria. The topics covered are: 1) a general framework for discou-nted stochastic games with Lipschitz-continuous and monotone equilibrium strategies and values, 2) a model of capital accumulation, and 3) two classes of games with perfect information: strategic bequests and oligopoly with commitment. In [6] turn-based stochastic games on infinite graphs induced by game probabilistic lossy channel systems (GPLCS), the game version of probabilistic lossy channel systems (PLCS) are discussed. Games with Buchi (repeated reachability) objectives and almost-sure winning conditions. These games are pure memoryless determined and, under the assumption that the target set is regular, a symbolic representation of the set of winning states for each player can be effectively constructed. Thus, turnbased stochastic games on GPLCS are decidable. In [7] two-person zero-sum stochastic games with finite state and action spaces are considered. The expected average payoff criterion is introduced. In the special case of single controller games it is shown that the optimal stationary policies and the value of the game can be obtained from the optimal solutions to a pair of dual programs. For multichain structures, a decomposition algorithm is given which produces such optimal stationary policies for both players. In the case of both players controlling the transitions, a generalized game is obtained, the solution of which gives the optimal policies. In [8] zero-sum stochastic games are studied. The importance of statio- nary strategies is demonstrated by showing that stationary strategies are better (in terms of the rewards they guarantee for a player, against any strategy of his opponent) than 1) pure strategies (even history-dependent ones), 2) strategies which may use only a finite number of different mixed actions in any state, and 3) strategies with finite recall. Examples are given to clarify the issues.

We hereby note that a lot of works are dedicated to the stochastic games in the case of scalar payoffs. They are available through the Internet, but stochastic games in the case of vector payoffs are not studied.

We can define stochastic games as general dynamic games private class. Let us define a general dynamic game.

Players' N set and X positions' set are given. Note by S ( x ) , i E N player's setof elementary situ-ations in

X E X position, and S ⁽ x ) = J П S/ x )

iEN set's elements call

elementary situations in x position. Every sequence of positions and elementary situations

x1,S(x1);x2,S(x2);...               (1)

is called a party.

At every set of the parties players' payoff H, i E N are given. Position x choosing is defined by transition function that is a general function for fixed x towards its other arguments, but for fixed party v V (x1)- v     V( xk-1)

x1,       ;... xk _1,

is probability distribution on X set.

From these definitions we get a stochastic game, if we consider the following: 1) let in general dynamic game X set is finite, and at the same time its one of the elements that we note by x , is called finite. We suppose that each set S(x0) consists of the only b strategy (game final). If in (2) we fix Xk_! = Xo, then transition function F will choose x ; 2) Consider that function F depends on only its last arguments -F = F (Xk_„ S(xk_1); Xk );  3) For every  (X, S(X))

couple let us introduce payoffs H ( x , S ^{( x )}) and in (1) party the payoff note the following way X H , ( X . , S ⁽ x k ) ).

k

The latter is the main principle of a stochastic game's construction. At the same time we use the definition of a stochastic antagonistic game from book [9] and according to this we define a stochas-tic matrix game with m -dimensional vector pay-offs, their criteria are strictly ranked, or we define a lexicographic stochastic matrix game. We will study the problem of Nash equilibrium existence with both common standard, and for nonstandard conceptions

Let define m -dimensional lexicographic strate-gic game and Nash equilibrium in it.

Let us denote that in

Г =< N,{Xi}^N,{H.KN >      (3)

game H = (H 11, H 2,.., H™ ) is a vector-function of i E N player’s payoff, for every i E N vector H has the same m -dimensional and on the set of situa-tions

X = П X their comparison holds lexicographi-cally.

i e N

We call such game a lexicographic noncoopera-tive (noncoalition) game with m - dimensional and we note it in the following way

ГL =< N,{X}eN,{HiLN >= (Г1,...,Гm). (4)

For two a = ( a 1 ,..., a m ) and b = ( b 1 ,..., b_m ) vectors lexicographic preference a ^ L b means that it fulfills one of the following m conditions:

• 1)    a_x >  b_x ; 2) a_x = b_x , a ₂ >  b₂ ; . . . ; m ) ^a i = ^b 1 , . . . , ^a m - 1 = b m - 1 , ^a m >  ^b m and ^a >  L^{b if} a ^ L b or a = b .

By means of Game Theory the main exclusivity of modelling of strategic conflict is finding of J. Nash equilibrium (equilibrium, stable, steady) situation on the basis of analysis of the model of corresponding game. Consequently, in Г ^L game the main principle of optimality is Nash equilibrium situation. For its determination let’s indicate

X _ i = ( X 1 ,.

^X _i - 1 , ^X i + 1 ,.

^X n ), ^X = ^{( X} i , ^X - i ),

where

i E N, x e X and X E Xt.

Definition 1.1. The situation x * e X is called Nash equilibrium situation in Г ^L game if for V i E N and V X_x E X_x is fulfilled H ( X * ) >  ^L H ( X_x , X * ), where i E N , x e X and x E X .

Let’s note a set of equilibrium situation Г ^L games standard mixed extension by ^ ( Г ^L ). In such kind of games the main problem is that in every Г ^L game there doesn’t exist the equilibrium situation or maybe this set will be empty - < г ( Г ^L ) =0 [10 -19].

Definition 1.2. m -dimensional lexicographic matrix stochastic Г L game is called a set of p lexicographic game elements or positions Г = ( Г 1 ,..., Г " ), j = 1,..., p . Each lexicographic game's element is described by p_k x q_k matrix, their elements have the following form:

p k,1         k,m           k,1         k,m              kl

⁽ b y ,..., b y  ) = ⁽ a y , ,..., a y ) + E Ч_У^ 1 , (5)

i = 1

where

p qj > 0 and 0 < E qk < 1.       (6)

i = 1

Hence, according to the (5) definition, if in position of p lexicographic game the first player will choose i strategy and the second - j strategy, then the first player's payoff will be equal (bk,1,..., bk,m) vector and by qj (l = 1,...,P) probability transfer will be taken p place on l lexicographic position, 1 -E qj >0 pro-i=1

bability the process of a game will be stopped. On the (5) basic the game may be returned in one of the previous situation, by virtue of (6) probability that the party will go on infinitely is equal to 0.

Defiition 1.3. The first player's strategy represents p -vectors     totality     {xkn = (xy,n,..., xjn )}     every j = 1,...,p and every such positive n number, that fulfills the conditions pk xyn > 0, E xj=1.          (7)

i = 1

A x ^kn strategy is called a stationary, if for every k vectors x ^kn do not depend on n number.

Also, the second player's strategy is called q vectors totality { y ^kn = ( y ^y , ⁿ ,..., y ^y _t ⁿ )}, for which y^j >  0 and q_k

E kn y , = 1.

j = 1

Note 1. According to the definition, the number x ^kn is the probability of choosing its pure strategy i on the n step in Г position done by the first player. We will discuss a case, when players choose stationary strategies, or they always use one and the same elementary strategies when Г will be played.

For a couple of strategies in scalar stochastic game the first player's payoff is a vector V = ( V ₁' ,..., V 1 ), and in lexicographic stochastic matrix game payoff or the value of the game will be given by matrix

V =

' ( > 1 .   ...   , v " ) '

.              ...     .

(v *    ...   ,v ")

V ⁽ p ,          , p ) /

Stochastic games is one of the most complex tendency in Dynamic games. In scalar stochastic matrix games even in the case of Nash equilibrium existence, for its finding it is necessary tu use special algorithms. But in stochastic games in case of ranking vectors payoffs or in lexicographic matrix stochastic game the problem is getting worse and worse. At first the existence of equilibrium must be established and then such kind of situation must be found, this is the most difficult procedure. Therefore in the given paper we formally study these problems for two players' an tagonistic variant but their concrete realization is the subject of future.

In the second part of the paper o lexicographic stochastic game is given from Г^ , j = 1,..., p position of p lexicographic game and with the help of it Г₄^ affine game will be constructed. If in affine Г game will be the solution on any positive interval, then on any positive interval of this section the set of Гц^ game's equilibrium is described. The sufficient condition of the given affine game's value is proved (Theorem 2.3) and hence the sufficient conditions of the given stochastic matrix game's existence value is also proved.

In the third part of the paper the question of the existence of equilibrium in lexicogrsphic stochastic matrix game is studied with the help of nonstandard analysis, therefore the concept of a lexicographic probabilistics mixed strategy is introduced and with the help of this lexocographic game's positions playing are taken place. In such strategies equilibrium situation's set's subsets are described (Theorem 3.1)

• II.    Equilibrium Situation In Lexicographic Stochastic Matrix Game

Let us discuss a lexicographic noncoalition game ГL = (Г1,..., Г" ) with payoff functions H = (H1,H2,...,H"),i e N. In this sort of game the problem of the existence Nash equilibrium will be studied by us, because of this H = (H', H2,..., H™) by certain scalar combina-tion of criteria vector-function on the basic of (depe-nding of scalar t e [0,1] parametric) affine game theory was constructed [10-12] and with the help of it the form of a set σ(ΓL ) Nash equilibrium that is given in the following way:

^ ( Г L ) = U  П ~ ( Г t ) ),         (9)

τ ∈ (0,1) t ∈ [0, τ ]

^where Γ ( t ) is Γ game's affine game.

f or vector ( b ¹ ,..., b ^m ) affine form is defined by the following way:

A ( b ¹,..., b^m ) = b ¹ + ( b ² - b ¹) t + ... +

+ ( b^m - b^{m - 1}) t^{m - 1},0 ≤ t ≤ 1.              ⁽¹⁰⁾

Let us note this form by A ( b ¹,..., b^m ) = b .

Theorem 2.1. Let us say

p

1         m         1         m            kl 1       m

( b ,..., b ) = ( a ,..., a ) + ∑ q_ij ( Γ _l -Γ _l ), (11)

l = 1

then

p

^b ( t ) ^{= a} ( t ) ⁺ ∑ ^q ij ^Γ l ,( t ) ^{,               (12)}

l = 1

where Γ is Γ position's affine game.

Proof. From (11) we get, that

p

(b1,...,bm)=(a1+∑qikjlΓl1,..., l=1

p

, a ^m + ∑ q i^kj^l Γ l^m ).              (13)

l = 1

It follows that:

A f ( b ¹,..., b^m ) =

p

(b1,...,bm)=(a1 +∑qklΓ1 +(a2 -a1 + l=1

p kl    2      1                mm

+∑qij (Γl -Γl )t+...+ (a -a + l=1

p

∑kl m     m-1   m-1     1      21

q (Γ - Γ ))t = a + (a - a )t + ... + l=1

m    m-1

( a - a ) t +

p kl 1       2      1                m      m-1

+∑qij (Γl +(Γl -Γl )t+...+(Γl -Γl  )t ) = l=1

^p = a ( t ) + ∑ q i ^k j ^l Γ l ,( t ) , l = 1

that means (12).

Hence, lexicographic stochastic matrix game is given from the Γ, k=1,..., p position of p lexico-graphic game and with the help of Γ   affine game will be constructed.

We call scalar Γ game the element of affine game.

Let us denote that there exists the solution of Γ game on t ∈ [0,t ],k = 1,..., p interval. Let us change in (12) affine game's Γ element with its meaning v (t),t ∈[0, t ] component and note vk(t) =val(Bk(t)), where B is p × q matrix {bk }, their elements are defined by equalities

p bij,(t) = aij,(t) + ∑qijvl(t), l=1

at the same time aikj,(t) =Af(aikj,1,...,aikj,m),t∈[0,t*],

t* = min{t1,..., tp}.

Let us also discuss     p × q     matrix

Q = { q^kl }, k , l = 1,..., p , that is formed by playing probabilities of the game's elements.

By A matrix of a payoff the set of solutions Γ game note σ ( Γ ( A )), in its every situation the value of the game is given by virtue of (8) matrix.

Theorem 2.2. If there exists the solutions Γ game on [0, t ^* ] interval, then inclusion takes place

p

^ ( Г ( A k ( t ) )) Q ^ ( Г ( Q ki )) £ ^ ( Г ( B k ( t ) )) (17)

on interval [0, t ] ⊆ [0, t ^*].

Proof. Let us say ( X ^k , Y K ) e с г ( Г ( A k ( t )), t e [0, t o ],    ( X C ^k , Y^ K ) e а ( Г (Q_H )),     l = 1,..., p .

Than can write inequalities:

X' A.(t) YkT < XkAk(t)YkT < XkAk(t) Y,

VXk, VYk, Vt e [0,t0],

X k Q k Y ^k T <  X^kQY ^k T <  X k Q ki Y k T ,

VXk, VYk, I = 1,..., p.(19)

Let us multiply both part of inequality (19) by vi ⁽ t ) ⁽ t ^{e [0}, t ₀ ^{] c [0}, t ^], ^l = 1,..., ^p ) and sum this kind of inequality together with (18) inequality, we get:

X k A k ( t ) Y k T + £ » i ( > ) X k Q ki Y^- k T <  X i A ( t , Y k T + = 1

2>(t)XkQHYkT

X^kBk(t)Y^kT< X^kBk(t)Y^kT< XX^kB_k(t)Y. (20)

It means that (X ,Y ) e ^(TCBk(t))  for every t e [0, t0] and inclusion (17) is proved.

Conclusion. On the basis of this theorem and from (9) equality of the set of equilibrium in lexicographic game we write:

• ^<7<Г< Bk )) = и  П^(Г< Bk (t))).   (21)

re(0,1) te[0,r]

^(Г(Ak(t)))Q^(Г(Qki))   0.     (22)

than there exists exactly only vector-function v(t) = (V1(t),..., Vp(t)) on the set [0,10] c [0, t*], that fulfills (14) and (15) equalities.

Proof. From the begining let us prove v(t) vectorfunction uniqueness. We admit a contradiction, let there exists two such kind of v(t) and u(t) vector-function on the set t e [0, t0] C [0,t*]. let us note max {max I vi(t) - ui(t) |} =| vk (t 1) - uk (t1)| (23) l       [0,t0 ]

and note that | V_k (t_x) — u_k (t_x) |= C > 0.

Let us define two affine B and B matrix with relations

p bk,(t)=aik,(t)+E qijvi(t), l=1                        (24)

p biku) = а» и) + yiqk'ui (t).

ij,(t)          ij,(t)                 ij l l =1

We get that

p

Ibi,_t« — b_lk(t,)I<Zqjlvi('.)—ui(t>)kc, (25) =1

kk according to this b^< b^+ C. Then it is obvi-ous, that the following inequality will be fulfilled

• ^val(Bk(t >) < ^val(Bk(t,>) ^{+ c}.       (26)

By v(t) vector-function fulfills (14) and (15) equalities, and u(t) vector-function fulfills analogical equalities. Therefore the following inequality will be fulfilled vk⁽t 1) < ^uk⁽t 1) ^{+ c},    that is contradictory to

| ^vk⁽t1) ^{— u}k⁽t1)^{|= c} > 0.

Let us prove the existence and define it inductively

• V⁰= (0,0,....,0)

p hk,r =ak  +У akl r—1

bij,(t)    aij,(t) ⁺^ qijvi   ⁽t ), r    1,²,...    ^(2/)

l=1

• vk⁺¹(t) = val(Bk(t)) = val{bk,r},t e[0,10].

First of all prove that the sequence {vr (t) = (vr (t),..., vp (t))} is uniformly convergent and then prove that its limit has got (14) and (15) properties. Let note

5 = max{^^q,}.           (28)

^k,¹,^j

Apparently 5< 1. Note that

Cr (t) = max|vk⁺¹( t) — vk( t )|, t e[0,10]. (29) k

From this we get C (t) < 5 • C_r_^t) and hence C_r (t) < 5r • C_o. Thus sequence {vr (t)} is Cauchy subsequence and because of this it must be sum-med up to towards any v(t) limit and at the same time uniformly.

Let note uk (t) = val(Bk (t)) = val{bk,(t)},     (30)

Where

p rebk,(t) = ak,(t) 'Iq^V,(t).         (31)

=1

As sequence {v^r (t)} is uniformly convergent on interval [0,t ], therefore we can choose r so big for any £ > 0 number, that for every k the follo-wing inequalities will be fulfilled.

| vk (t) - Vk (t) < £, | vk+1 (t) - Vk (t) |< £. (32)

From this it follows that for every k the following inequality will be fulfilled | V(t) — u_k (t) |< £. But as £ arbitrary, that is why the following equality must be fulfilled V(t) = U_k (t), t E [0, t₀ ]. The Theorem has been proved.

Let discuss without analysis 2-dimensional stocha-stic matrix game from the 3 element of a lexicog-raphic game.

Example 2.1.

((3,1) + Г3/2(1,0)

¹   ((4,8)         (2,1) + Г₂/2

_ ((0,5) + Г1/2  (3,2))

Г

2   ((4,4)          (0,1) J’ r = ((—1,2) + Г3/2(5,1)

• ²  ((2,10)          (0,5) + Г1/2

In the given game in the case of the equilibrium existence the value of the game will be by virtue of (8)

v —

' (v1, V2) ' v ( V 2,V 2) у

• III.    Usage of Nonstandard Analysis

In m -dimensional lexicographic stochastic matrix Г L game let us use a nonstandard analysis. Because of this ^{let us write down}Г and payoff vector-function H — (H¹, H²,..., Hm) the following way

Г L — (Г0, Г¹,.

Г ^m—1),

H — (H 0, H2,..., Hm—1) — {(a0, ai,.

am -1)},

i — 1,..., p; j — 1,..., q.

On a set of pure strategies m -dimensional probability distributions are given. In this case each Г^k

(k — 0,1,..., m — 1) criteria of ГL game corresponds to its probability distributions on sets of pure strategies. Besides, a lexicographic m -dimensional order relation is given on set of m -dimensional probability distri-bution. The given construction is made by the metho-dology of nonstandard analysis [20]. Therefore, the given mixed strategy is called a nonstandard mixed strategy, and a lexicographic game in such strategies is called a nonstandard mixed extension. An equilibrium situation in mixed strategies is defined in ГL game. The analyzed examples show that if in a lexicographic matrix game doesn’t exist a saddle point in standard mixed strategies then a saddle point maybe doesn’t exist in nonstandard mixed strategies. If in a lexicographic matrix game doesn’t exist a saddle point in standard mixed strategies then there can be existed a saddle point in nonstandard mixed strategies. Thus, lexicographic games’ nonstandard mixed distribution is a generalization of a standard mixed extension [17].

For conducting such analysis it is necessary to define vectors lexicographicp roduct operation by ® notation.

Let we have m - dimensional vectors a — (a0,..., am 1) and b — (b°,...,bm 1) we note

a ® b — (a0 b 0, a0 b1 + a1 b 0,

0 2.    1 1 1    2 0     0 m-1

, a b + a b + a b , a b +... + a b ) =

• 1                2

0 0       k 1— k V k 2— k          k m —1— k

— (a b , ^a b , /,a b ,., ^ a b ). (34)

k—0           k—0

It is obvious, that m -dimensional a ® b vec-tor’s components are the following form of one variable m -degree       a (t) — a⁰+ a¹1 +... + a™t^m        and

b(t) — b⁰+ b¹1 +... + bmtm coefficients of polynomials multiplication, only in difference with, that in the process of their multiplication m -degree polynomial can be conservated.

In the following lemma some essential properties of vectors lexicographic product is established.

Lemma 3.1. Lexicographic product’s ® operation defined by (33) has got the following properties:

• 1)    Commutativity - a ® b = b ® a;

• 2)    Associativity - (a ® b) ® c — a ® (b ® c) ;

• 3)    Distributivity of summation -

• (a + b) ® c — a ® c + b ® c;

• 4)    “Monotonicity in two cases:

• a)    Weak monotonicity. If а — (a0,...,am 1) E Rm and (a °,..., am 1) ^L ^ (b °,..., b^m 1) (a ^L ^ b) , then a ® a ^L ^ b ®a;

• b)    Strict monotonicity.

Let         α = (α⁰,...,α^m-1 ) ∈R^m         and

(a °,..., am-1) > L (0,...,0).

If (a⁰,...,am 1)^L ^ (b0,...,b^m 1) and a⁰^0, then a ® a ^L ^ b ® a.

Let note that in the conditions of b) case the requirement of difference from first components’ xero is essential in (a⁰ ,..., a^m-1 ) vector.

Having applied Let use this apparatus in lexicographic stochastic game. Let us discuss a case when in the process of choosing (i, j) situation l -th lexicographic game's element is being played by lexicographic probability

(qi^kj^l,0,...,qi^kj^l,m-1),k=1,...,p.

In this case k -th game's element payoff matrix consists of the following elements:

_(bik_j,0_,...,bik_j,m-1_{) =(ai}k_j,10_,...,aik_j,m-1_{) +}

p(35)

∑kl,0       kl,m-1        0

(q_i^k_j^l,0,...,q_i^k_j^l,m-1)⊗(Γ_l⁰,...,Γ_l^m-1), l=1

where kl,0        kl,m-1

(q_ij  ,..., q_ij     ) ∈R₊,

p

∑ (qikjl,0,...,qikjl,m-1)<(1,...,1).

l=1

let change in (35) (Γ0,..., Γm-1) by its meaning component v = (v0 ,...,vm-1 ). According to the definition we have kl,0        kl,m -1         0

(qij, ,..., qij,    )⊗(vl ,..., vl)

kl,0 0    kl,0 1      kl,1 0

= (q_ij v_l ,q_ij v_l + q_ij v_l ,...,

_,qik_jl,0_vlm-1_+...+qik_jl,m-1_vl0_).

Because of this (35) will have the form

_(bik_j,0_,...,bik_j,m-1_)=(aik_j,0_,...,aik_j,m-1₎₊ ^p

∑kl,0 0        kl,0 m -1              kl,m -1 0

(q_ij v_l ,...,q_ij v_l    +...++q_ij     v_l ). ₍₃₈₎

l=1

Let discuss the following p × q matrices:

Ak ={(ai^kj^,0,..., ai^kj^,m-1)},

Bk ={(bi^kj^,0,...,bi^kj^,m-1)},        (39)

Qkl ={(qi^kj^l,0,..., qi^kj^l,m-1)}.

Analogically tu the theorem 2.2 the following theo-rem is proved.

Theorem 3.1. Inclusion is being taken place

^(HAk ))f^^(Г(Qki ® vi)) с ^(Г(Bk )). (40)

l =1

• IV.    Conclusion

Is some scalar stochastic antagonistic game Nash equilibrium may not be existed. We are having certain problems in lexicographic stochastic matrix games too -in all games equilibrium situation may not be existed. In lexicographic stochastic matrix Γ^L = (Γ¹,..., Γ^m) game the set of equilibrium situa-tions if it is empty is described by means of a set of equilibrium situation in relevant affine (scalar) game. At the same time for Γ^L = (Γ¹,...,Γ^m) game with the help of nonstandard analyses the players lexicographic probable mixed strategies are defined, by using them Γ¹,..., Γ^m games will be chosen. It is pos-sible that Γ^L game neither has got the solution in these strategies.