The Stability of Equilibrium Situation in Lexicographic Strategic Games

Published Online December 2016 in MECS DOI: 10.5815/ijmecs.2016.12.06

Game theory is a branch of modern mathematics and decision making theory [1,2,3,4,5]. Its aim is to study conflict situations, where players' interests are collided. Mostly we see such situations in every field of human activities and that is why it is often used. A mathematical model of conflict situation is called a game.Thus, game theory is a mathematical decision theory in conflict situations. Such game’s main task is not to describe a conflict, but the solutions by making compromise decisions [6].

In classical game theory the main basic model is a noncooperative game that is defined by

Г=         (1)

system, where N = {1,2,..., n } is a set of players’, its set of pure strategies we note by x = { x 1,..., x p } and such kind of strategies set of situations - by

X = П Xi. Hi : X = П Xi > R1 - i e N (2) i e N ie N is player’s real-valued payoff (utility) function. In Г =< N, {Xt }ieN, {Hi }ieN > game Xi is i e N player’s        set        of        mixed strategies,

H : X = ПX ^ R1 is i e N player’s payoff e N function, it tries to maximize the function. It means that, Г and Г game is finite i.e. the players’ sets of pure strategies are finite.

In Г and Г game players choose their strategies independently   x; e X, i e N and we get a situation X = (Xx, x2,..., Xn ) e X. Players payoff functions H (X), i e N are defined for every x e X.

In Г and Г game players simultaneously and independently choose their strategies so that they don’t inform each other about it. Therefore Г and Г game is called noncooperative or noncoalition. Player’s strategic behaviors are studied in such games, with the help of such strategies they get this or that kind of guaranteed payoffs (utilities). Hence, the task is to find such kind of situation    x* e X,    which are multicriteria max(H (x),..., H (x)) task solution [7]. x

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 Γ game the main principle of optimality is Nash equilibrium situation. For its determination let’s indicate

x-i =(x1,..., xi-1, xi+1,..., xn), x=(xi,x-i),     (3)

where i ∈ N, x ∈ X and x ∈ X .

Definition 1.1. The situation x ^* ∈ X is called Nash equilibrium situation in Γ game if for ∀ i ∈ N and ∀ x ∈ X is fulfilled H ( x ^*) ≥ H ( x , x ^* ), where

i ∈ N, x ∈ X and xi ∈ Xi .

Nash equilibrium situation is the only steady and reliable situation for agreement on collective action. Such situation is characterized by the following features: In situation given by any party by unilateral change of its strategy this state should not be improved. It means that none of the participant is able to increase its own payoff if other players acting rationally will correctly estimate their strategies. Consequently, of the principle of Nash equilibrium in noncooperative games there are available the various equilibrium situations. This principle of optimality and Pareto optimality principle the first is the strategic principle, and the second - is a compromised one, they are the main principles of optimality in all fields. Thus, Game Theory considers the independent mechanisms which lead us to “a good equilibrium” to rationally solve the tasks of the collective interrelations. Realizing the corresponding actions the players receive finally the utilities (payoffs). The aim of the players is to choose the optimal strategies by which they receive an optimal utility.

Definite generalization of classical noncooperative games is the lexicographic noncooperative games [8,9,10,11,12,13,14,15].

Let’s discuss Γ game’s modification using the following rule: suppose, that H = (H1 ,H2 ,..., Hm )  is i ∈ N player’s payoff’s vector-function, for every i ∈ N vector H has identical measurement m and their comparison on the

X = ∏ X i i ∈ N

set of the situations

happens lexicographically, or criteria in payoff’s vectorfunction are strictly ranking. We call such game lexicographic noncooperative game with m measurementand we note it in the following way

ΓL =≡(Γ1,...,Γm). (4)

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

• 1)    a > b ; 2) a = b , a > b ; . . . ; m ) a ₁ = b ₁ , . . . , a_{m - 1} = b_{m - 1} , a_m > b_m (5)

and

a > Lb, if a ^ L b or a = b .

Definition 1.2. The situation x ^* ∈ X is called Nash equilibrium situation in Γ ^L game if for ∀ i ∈ N and ∀ x ∈ X is fulfilled

Hi(x*) ≽L Hi(xi,x-*i), (6)

where i ∈ N, x ∈ X and x ∈ X .

Let’s note a set of equilibrium situationsin Γ ^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 ) = = ∅ .

Note 1.1. By 1.1 and 1.2 definitions weak nonstrict Nash equilibrium is given in classical Γ and corresponding in lexicographic Γ ^L games. In these games strict (strong) Nash equilibrium is defined corresponding to >  and >  L inequalities. In strategic game the usage of Nash strong equilibrium and lexicographic preferences are studied in [16].

In general, in classical noncooperative (strategic) game a problem of stability of Nash equilibrium situation concerns the small changes of functions of the players’ winning and it is essential for solution of the game. It is interesting to review the same problem for the lexicographic noncooperative games but here the main complexity is that, as we have already mentioned, not in every finite lexicographic noncooperative games there does not exist any Nash equilibrium situation neither in pure nor in mixed strategies.

In this work we shall review the lexicographic noncooperative games having the continuous vectorfunctions of winning which are defined on the Decart product of the metric compact sets of strategies and for them we introduce: the definition of stable lexicographic equilibrium noncooperative game, the definition of weak non lexicographic equilibrium situation and definition of its stability in pure strategies. It is approved that the space of lexicographically noncooperative games is finite by the set of weak nonstrict nonempty lexicographic equilibrium situations. The conditions of stability of weak non-severe equilibrium noncooperative game and the conditions of stability of weak equilibrium situation have been shown. The compromised lexicographic set and its stability has been defined in the weak sense.

• II .    Basic Definitions

Let’s bring several known definitions and the result which are connected with the multiform mapping, with their continuity and upper and lower semicontinuity.

Let’s admit that Χ and Υ are the typological spaces, and C ( Υ ) is the family of all nonempty subsets of Υ space. Let’s undermine that F : Χ → C ( Υ ) is a multi-image mapping.

Definition 2.1. The F : Χ → C ( Υ ) multi-image mapping is called alower semicontinuityin x ∈ Χ point if the any space of Υ is such open for U set for which the intersectionof U and F ( x ) sets is not empty, there exists such an area V , of x point that for each x ∈ V point the intersection of F ( x ) and U set is as well nonempty.

Definition 2.1¹. The multi-image mapping of F : Χ → C ( Υ ) is called a lower semicontinuity in x ∈ Χ pointif for each sequence of ( x , x ,...), points of X space which is converging to x point and for each y ∈ F ( x ) point is available for each n = 1,2,... y n ∈ F ( x n ).

It is known that for Χ and Υ topological spaces which satisfy the first axiom of countability, the definitions 2.1 and 2. 1¹ are equivalent to each other.

Definition 2.2. The F : Χ → C ( Υ ) multi-image mapping is called the upper semicontinuity in x ∈ Χ point if for any open U set of Υ space which comprises F ( x ) there exists such an V ( x ), of x point which comprises the F ( x ) as well.

Definition 2.3. The F : Χ → C ( Υ ) multi-image mapping is called the upper semicompact in x ∈ Χ point if from the x → x , n → ∞ , x ∈ X , y → F ( x ) conditions it follows that from the sequence of ( y , y ,...) points it can be distinguished such a subsequence ( y , y ,...), which is converging to y ∈ Y point and at the same tine y ∈ F ( x ).

Definition 2.3¹. The F : Χ → C ( Υ ) multi-image mapping is called a semicompact from the top in F : Χ → C ( Υ ) point if mapping of F is an upper semicontinouty in x point and the F ( x ) set is compact.

If Χ space satisfies the first axiom of countability and Υ space satisfies the second axiom of countability than the definitions 2.3 and 2.3¹ are equal to each other.

Definition 2.4. The F : Χ → C ( Υ ) multi-image mapping is called the locked in x ∈ Χ point if for any y ∈ F ( x ) point there are the areas of x and y points correspondingly for V ( x ) and U ( y ), that from X G V ( X _o ) - results the F ( X ) П U ( J _o ) = ^ •

Definition 2.4¹. The F : Χ → C ( Υ ) multi-image mapping is called a locked in x ∈ Χ point if from the convergence of ( x , x ,...) sequence to x point results the convergence of ( y , y ,...) sequence to y point, simultaneously,   from y ∈ F ( x ) there results

yn ∈ F(x0).

If Χ and Υ spaces satisfy the first axiom of countability than the definitions 4 and 4¹ are equal and if Υ is of Hausdorff and locked than the _mappi_ng F : Χ → C ( Υ ) is semicompact from the top then and only then, when it is locked in x point.

Definition 2.5. The F : Χ → C ( Υ ) multi-image mapping is called the continuous in x ∈ Χ point if it is simultaneously lower and upper semicontinuity in x ∈ Χ point.

Definition 2.6. The F : Χ → C ( Υ ) transformation is called the continuous (correspondingly lower and upper semicontinuityon the Χ space), if it is such in each x point of X space.

Now let’s say that (X, d) - is a metric space and Φ ( Χ ) is a family of all locked subsets of this space. For Α , Β ∈ Φ ( Χ ) let’s indicate l ( Α , Β ) = max d ( x , Β ).

x ∈Α

It is known that

h(Α,Β)=max{l(Α,Β),l(Β,Α)},       (7)

is a metric on Φ ( Χ ) and it is called the function of Hausdorff h : Φ ( Χ ) × Φ ( Χ ) → [0, ∞ ), defined as a metric Hausdorff.

It is approved that if Χ is a complete metric space than Φ ( Χ ) is as well full (complete) metric space: if Χ is a compact metric space than the Φ ( Χ ) is a compact metric space as well [17].

Let’s indicate by K ( Χ ) the metric space of all compact subsets of Χ space on which is defined the h metric. If the X space is complete than K ( Χ ) space is complete as well: if X is a separable space than K ( Χ ) is as well separable.

• III.    The Main Part

Let’sdiscuss    m -dimensional lexicographic noncooperative games class Υ

Γ ^L ( H ) =< N ,{( X i , ρ i )} i ∈ N ,{ H i } i ∈ N >≡

≡ ( Γ ¹, Γ ²,..., Γ ^m ),                    (8)

where N = {1,2,..., n} is a set of players’, (Xi,ρi) -i ∈ N is a compact metric set of the player and Hi =(Hi1,...,Him) : X =∏X →Rm - is i∈N i ∈ N player’s real-valued continuous payoff (utility) function.

For noncooperative Γ ^L ( H ) games for Υ class with the spaces of fixed X ( i ∈ N ) strategies let’s introduce a distance by the following formula:

ρ ( Γ ^L ( H ), Γ ^L ( H )) = max|| H ( x ) - H ( x )||,   (9)

x ∈ X

Where

|| H ( x ) - H ( x ) || = max | H^k ( x ) - H^k ( x ) | . (10) i ∈ N ,1 ≤ k ≤ m      ^{i             i}

For situations   x , x ^' ∈ X let’s indicate as well

ρ ( x , x ^') = ∑ ρ _i ( x_i , x_i ^').

i ∈ N

Let’s indicate the set of equilibrium situations of lexicographic noncooperative Γ ^L ( H ) game by σ ( H ) .

Let’s indicate the following fact that characterizes the task of lexicographic maximum in contrast to the task of scalar maxima: in the lexicographic maximum of the continuous vector-function defined on the metric compact the set of points of lexicographic maximum is compact but at the sametime the set of equilibrium situations in lexicographic noncooperative game could not be a compact. Let’s prove this fact.

Let’s introduce the following definitions. The x ^* ∈ X point is called the point of nonstrict lexicographic maxima of the function

H = ( H ¹,..., H^m ) : X → R^m       (11)

if for each y е X or x ^ y or x ~ y . And the situation x ^* = ( x ^*,..., x ^*) ∈ X is an equilibrium situation in Γ ^L ( H ) game if for i ∈ N x ^* is a point of nonstrict lexicographic maxima on X fixed for x ^* ,..., x ^* , x ^* ,..., x ^* strategies.

For the continuous H = (H1 ,...,Hm)  function defined on metric compact X set let’s indicate the set of points of its nonstrict lexicographic maxima L by ArgmaxH . Let’s consider the compact set X

A = Arg max H ¹. If A set is not one-pointthan on 1 _X                   1

A set let’s consider the function H ² and the compact set A = Arg max H ² ⊂ A . In case if A set is not x ∈ A ₁

one-point  than  let’s consider the compact set

A = Arg max H ³ ⊂ A and etc. The received 3              _{A 2}              2

consequence of compact sets A ⊃ A ⊃ ... are finite, their intersection is nonempty and compact. It is a set L

Arg max H .

X

The validity of the second evidence is the consequence of the fact that the lexicographic inequality might be violated while going beyond the limit. E.g., for any positive ε >  0 number there occurs the lexicographic inequality (1,2) ^ L (1 — S ,3 + S ). If we go beyond the limit in this inequality when ε → 0, we receive that (1,2) ^ ^L (1,3), which is inequitable.

In scalar case, in conditions of compactness of continuous function of winning sets of strategies both the set of equilibrium situations and that of solutions of the task of maxima are compact.

Let’s consider the subspace Υ¹ of Υ space of noncooperative Γ ^L ( H ) games which comprises of such games the set of equilibrium situations of which is σ ( H ) ≠ ∅ .

Definition 3.1. Equilibrium situation x ^* ∈ σ ( H ) of noncooperative lexicographic Γ ^L ( H ) ∈ Υ¹ game is called the stable if for each ε >  0 number there is found such a δ >  0 number that if for Γ ^L ( H ) ∈ Υ¹ game the distance ρ ( Γ ^L ( H ), Γ ^L ( H )) <  δ , then in Γ ^L ( H )

game there is searched out an equilibrium situation x ^' , for which ρ ( x ^*, x ^') <  ε .

Definition 3.2. The Γ ^L ( H ) ∈ Υ game is called stable if its all equilibrium situations are stable.

Let’s indicate the set of stable equilibrium situations of Γ ^L ( H ) game by σ ^* ( H ) .

Let’s consider a new multi-image mapping σ : Υ¹ → X , which acts in the form of σ ( Γ ^L ( H )) = σ ( H ).

It has appeared that in comparison to the case of scalar functions of the players‘ winning this transformation is not semi continuous from the top. This circumstance together with the fact of incompetence of above indicated σ(H) is the reason of various complexities which are originated while using of lexicographic optimality and the notions of equilibrium for the lexicographic noncooperative games.

Let’s effect the demonstration of indicated by the example. For this let’s indicate by C^m all continuous set of H : X → R^m set of vector-functions defined on X and simultaneously they are provided with the equal

L norm, then the mapping of ArgmaxH : Cm → X is XX not the upper semicontinuity.

Example 3.1 . In the role of X space let’s take [0,1] segment X = [0,1]. Let’s indicate

Hα1(x)=αx,Hα2(x)=1-x,Hα=(Hα1,Hα2), (12) α → 0.

Here α ∈[0,1] is a numeric parameter. It is easily L indicated that for each α≠ 0 ArgmaxH (x) = {1}. x∈X

Besides, when α = 0, then the limit of sequence of L

ArgmaxH (x) = {0} and x = {1} does not belong x∈X   0                 α

x∈X where X is a metric compact and H : X → Rm - is continuous vector-function let’s call a task of lexicographic optimization.

Definition 3.3. Let’s call the weak nonstrict lexicographic maxima of ( X , H ) task to x ^* ∈ X point for which there exists a sequence limit of { H } functions when α → α , which by the norm is convergent to H 0 H α → H α and exists the sequence of points L

xα ∈ Arg max Hα is convergent to x* - x → x* , x∈X

when α → α .

L

Let’s indicate by wargmax H the point of weak x∈X nonstrict lexicographic maxima of (X,H) task.

Let’s call the value of weak nonstrict lexicographic maxima of ( X , H ) task in x point to such y point for which there exists such sequences of { x } points and { H } functions that when α → α , there will be fulfilled x → x and H → H conditions, as well α              α      α ₀

there exists such a sequence of {y } points for which y → y, where  y is the value of nonstrict lexicographic maxima of H function in x point. Let’s indicate the set of all such magnitudes by L

vwargmax H.

x ∈ X

From the definition follows the validity of the following Lemma.

Lemma 3.1. The mappings

W:Cm →K(X), V:Cm→K(Rm),    (13)

which act by the following rules

L

W(H) = warg max H, x∈X                 (14)

L

V(H) = vwarg max H, x∈ X is the upper semicontinuity.

Now let’s go on to the lexicographic noncooperative games.

Let’s indicate locking of C graphic of σ : Υ¹ → K ( X ) mapping by C and locking of C graphic ofmapping v : Υ¹ → K ( R^m ) which Γ ^L ( H ) game will correspond to the set of magnitudes of H function in its points of equilibrium let’s indicate by C v .

Definition 3.4. The weak nonstrict lexicographic equilibrium situation of the Γ ^L ( H ) game is called the point of image mapping of σ : Υ¹ → K ( X ) (the graphic of this mapping is C ).

Definition 3.5. The magnitude of the function of winning in weak nonstrict lexicographic equilibrium situation of Γ ^L ( H ) game to the image mapping point of v :Υ¹ → K ( R^m ) (It’s graphic is C ).

Lemma 3.2. The space of Γ(H) games by weak nonempty set of weak nonstrict    lexicographic equilibrium situations is finite.

For proving of Lemma it is enough to check up the locking of Υ¹ subspace in finite Υ space. Let’s consider the sequence of games { Γ ^L ( H )}, which is convergent towards the Γ ^L ( H ) game, when k → ∞ . According to the condition of Lemma for each k = 1,2,... it takes place σ ( H ) ≠ ∅ . Let’s show that σ ( H ) ≠ ∅ .

We consider the sequence {x }. of weak nonstrict lexicographic equilibrium situations in ΓL (H ). In the force of compactness of X space if all situations there exists the convergent subsequence {x }. Let’s indicate its limit byx . So as the mapping σ : Υ1 → K(X) is the upper semicontinuity that is why a condition should be fulfilled, therefore, σ(H) ≠ ∅.

Definition 3.6. The x situation of weak nonstrict equilibrium in Γ ^L ( H ) game is called stable if for any ε >  0 number can be found such a number δ >  0, when for each Γ ^L ( H ) game the inequality will be fulfilled ρ ( Γ ^L ( H ), Γ ^L ( H )) <  δ , it will be possible to find such a situation x ∈ σ ( H ), for which it will be fulfilled the inequality ρ ( x , x ^') <  ε . Let’s call the Γ ^L ( H ) game a weak nonstrict lexicographically stable if all its weak nonstrict lexicographic equilibrium situation is stable.

Lemma 3.3. The lexicographic noncooperative Γ ^L ( H ) game is weakly nonstrict lexicographically stable then and only then when Γ ^L ( H ) is the point of continuity of σ mapping.

Proof. Necessity. Let’s say that the lexicographic game Γ ^L ( H ) ∈ Υ¹ is stable. So as the mapping σ is the upper semicontinuity it is necessary to check only its lower semicontinuity. According to the definition of stability of the equilibrium situation for each x ∈ σ ( H ) situation and for any ε >  0 it is possible to find such number δ ( ε , x ) >  0, that if the game Γ ^L ( H ) ∈ Υ¹ satisfies the inequality

ρ ( Γ ^L ( H ), Γ ^L ( H )) < δ ( ε , x ),        (15)

then there exists a situation of equilibrium x ^' , of Γ ^L ( H ) game for which ρ ( x , x ^') <  ε .

The lower semicontunuity of σ mapping indicates that for each ε >  0 number it can be found such δ ^' >  0 number that if ρ ( Γ ^L ( H ), Γ ^L ( H )) <  δ , then there will occur inclusion of σ ( H ) ⊂ U ( σ ( H ), ε ), where U ( σ ( H ), ε ) is the ε -area of σ ( H ). Now let’s indicate δ ^' = inf δ ( ε , x ).

x ∈ σ ( H )

The necessity will be proved if we show that δ' > 0. Let’s admit the contrary, let’s say δ' = 0. Let’s consider the sequence δ → 0, k → ∞ and the sequence of the situation of its corresponding equilibrium situations x(δ ), k → ∞. Let’s say x = lim x(δ ) is the k→∞ limiting point of this sequence. On the one hand x point is unstable equilibrium situation. And on other hand, in force of compactness of σ(H) set it should be fulfilled x ∈σ(ΓL (H)) and by it we received the opposite one.

Sufficiency. Let’s say that Γ ^L ( H ) game is a point of continuity of σ mapping. Then for each number ε >  0 in force of the lower semicontinuity of σ mapping there is possible to find such a δ >  0 number that what kind were the δ -area of game Γ ^L ( H )   in

U(ΓL (H),δ)  game  U(ΓL (H),δ)  for each equilibrium x ∈σ(H) situation it is possible to find such an equilibrium situation x' ∈σ(H'), for which ρ(x, x ) < ε. And this approves the stability of Γ L (H) game.

Lemma 3.4. Let’s say that X is a metric space and Y is a compact metric space F : X → K ( Y ) is the upper semicontinuity multi-image mapping. Then the set of points of interruption of F mapping is in Bera’s opinion (categoria en Bera) is the set of the first category (i.e. it can be represented nowhere in the form of countable unification of the firm subsets).

Proof see in [18].

The result 3.1. If X is a metric space than the set of points of interruption of F is everywhere dense in X space (i.e., the set of continuity points is in opinion of Bera is the set of the second category).

Proof see in [18].

Theorem 3.1. The set of weakly stable lexicographic noncooperative games everywhere is dense in Υ¹.

Proof directly results from the definition and from last two Lemmas.

Theorem 3.2. If in Γ ^L ( H ) game there exists the only weak equilibrium situation x , then it is a weak equilibrium stable situation and Γ ^L ( H ) game is stable.

Proof. Let’s take the number ε >  0. So as the mapping σ is the upper semicontinuity in x point that is why there should exist such an area V , of the game Γ ^L ( H ) that if Γ ^L ( H ^') ∈ V , then the inclusion of

σ ( Γ ^L ( H ^')) ⊂ U ( σ ( H ), ε ).        (16)

So as σ ( H ) = { x } comprises only one x point that is why it should be fulfilled σ ( H ) ⊂ U ( σ ( H ^'), ε ). Thus, the mapping σ is continuous.

• IV.    Conclusion

A classical strategic (the same noncooperative) game is a game with the scalar functions of winning. The set sof strategies are possible to be given in various images. Lexicographic noncooperative games are given by onedimensional vector-functions. Lexicographic games have been considered in this article when the sets of strategies are the metric spaces and consequently the vectorfunctions of winning are continuous. In classical games the Problem of Nash Equilibrium situation stability concerns the small changes of scalar functions of players’ winning which is essential for their solution. The same problem has been studied in the given article for the lexicographic games the complexity of which is caused by the situation that in such game the equilibrium situation can be not existed. The study of the issue caused introducing and using of many definitions. The given result - if in lexicographic strategic game there exists the only weak equilibrium situation, then it is a weak equilibrium stable situation and the game is stable.