The Optimal Principle of Stable Solutions in Lexicographic Cooperative Games

Published Online March 2014 in MECS DOI: 10.5815/ijmecs.2014.03.02

Game theory is a branch of modern mathematic and decision making theory. 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.

In that case when we construct a mathematical model of conflict and define principle of optimality, or a principle of making optimal decision, we get a mathematical problem that should be solved by mathematical methods.

In classical game theory the main basic model of a conflict is a no cooperative game that is defined by a system

*Corresponding author.

where N = {1,2,..., n} is a set of players, X. is i e N player’s set of mixed strategies,

Hi : П X.= X i e N

^ R ¹

is i e N player’s real-valued payoff (utility) function, he tries to maximize it. In Г game players choose their strategies simultaneously and independently they do not inform each other about it. This way we get a situation x = ( x _t, x ₂,..., x_n ) e X , where x. e N , i e N . Therefore Г game is called noncooperative. Here players’ strategic behaviours are studied or such strategies by using them they get this or that kind of guaranteed payoffs (utilities). Thus, the problem is to find such x * e X situation, that by the given principle of optimality, will be a solution of a multicriterion max( H ₁( x ),..., H_m ( x )) p ^ro bl ^em [1] ^. x

In a classical theory of cooperative games players’ cooperative behaviours are studied in conditions of Г game. Players can enrol in coalitions and each member of a coalition can discuss about choosing their strategies in accord. In addition to this in coalition players can combine – sum their payoffs and then imputate. Moreover, players’ utilities have got a transferring property, or payoffs are measured by unital scale, and they can transfer from one player to another without loosing and limitation.

In order to describe such games a characteristic function of Г game is used. It is called a real-valued function v ( S ) , that corresponding any number to any S c N coalition. v ( S ) is a maximal guaranteed summary payoff of the members of S coalition independently from other N \ S players’ behaviours. This means that v ( 0 )=0. Formally classical cooperative game is called a couple <  N , v > , where N = {1,2,..., n } is a set of players, but v :2 ^N ^ R ¹ - is a characteristic function. It has got two properties:

• 1)    v ( 0 )=0;

and

• 2)    super-additivity - v(T и S ) >   v ( T ) + v ( S ),  if

T , S c N and T о S = 0 .

For a simplification we call v a cooperative game.

A cooperative ^v game’s aim is an imputation of ^{v ( N )} maximal guaranteed common payoff among the players:

Let us suppose that in Г game each i e N player’s payoff function is given by preference, by means of strictly ranked m criteria, or

H i = ( H i , H i

_Hm ₎

vector-function is defined by X set of situations and the comparison of their meanings is taken place by ≽ and L

^ lexicographic relations. In this case ^Г game is called a lexicographic noncooperative game [2,3,4,5,6,7, 8,9] and note by ^Г L -

Г ^L =< N ,{ X^N ,{ H J _{i e} N > .       (3)

• II.    Lexicographic cooperative game and its c- CORE ’ S STRUCTURE

We discuss such Г ^L games, where there exists lexicographic maximin, or v ( S ), S c N . It is obvious, that v is a m -dimensional vector-function: v : 2 ^N ^ R m Therefore we call a lexicographic cooperative game such vector-function v and it fulfills the following conditions: 1) v ( 0 ) = 0; 2)

v ( T и S ) >  ^L v ( T ) + v ( S ) , T , S c N , T о S = 0

• [11] . The second condition is a lexicographically- L -super-additivity property.

Let write a lexicographic cooperative game v by means of scalar functions v = ( v 1 , v ²,..., v m ) ^T . In such games a imputation is called m -dimensional n vector’s consequence X = ( X _ч, X ,₂,..., X .„), we write it a form of matrix.

x11    xi2    ...   xi n x 21   X 22   ...   x 2 n

If we define Г L game’s characteristic function (a lexicographic cooperative game) analogically to the classical cooperative game, there will be additional difficulties connected to the existence of a characteristic function, imputation, C-core and e.t.c [10,11].

The presented article is dedicated to the problem of the existence of Neumann-Morgenstern’s solutions in lexicographic games. The obtained main results are given in the II and the III sections. In the II section the main definitions are given related to lexicographic cooperative game v = ( v 1 , v ² ,..., v m ) ^T In such game the imputation of the payoff are presented by the form of a matrix. In lexicographic cooperative games the existence of Neumann-Morgenstern’ s solutions is related to the existence of C-core C ( v ) . Therefore C-core of a lexicographic cooperative game’s v is defined and the conditions are proved, whereas the set of imputation is C-core (Theorem 1). Perhaps C-core C ( v ) will be an empty set (Example 1). Its structure in certain conditions is established (Theorem 2). In the III section Neumann-Morgenstern’s solution NM ( v ) is defined as a set of a stable imputation. Theorem 3 is proved that gives the sufficient conditions for the existing nonempty set of the stable solutions NM ( v ) in a lexicographic cooperative game and it can be coincided to C-core C ( v ) . By theorem 4 the necessary conditions of the existence of the stable solutions is proved. The proved theorems 3 and 4 give us the opportunity to establish its form in the case of their existence. Section IV is conclusion of research.

For n

X X.i i=1

X . i ≽

V x m 1    x m 2    ... x mn J

which fulfills the

following conditions

= v ( N ) — a condition of collective racionality;

^L v ( i ) , V i e N - a condition of individual

rationality.

It is obvious that according to ^v = ^{( v} , ^v ,

...,

mT is

^L -super-additive it follows that a cooperative v a super-additive function. But for functions

1 game is

v ²,

...

, v^m

such analogical property does not fulfill. Below we will

discuss separately a vector-function ^{( v ,} *

...,

mT v ) defined

on a set of coalition and note it by v . Therefore we write v = ( v 1 ,v * ) ^T

Also, note a set of imputation in v = ( v 1 , v *) ^T game

by E ( v ) , and the projection of this set on E ( v ¹ ) set note

by Pr( E ( v ) l E ( v ¹ )). At the same time note that

X X .- = X ( S ) We say that an imputation X dominates

i e S

Y imputation in coalition S c N and we write X ^ Y ,

S

if X., ^ L Y., , Vi e S and XX4  L ^ v(S) or ieS

X ( S ) L <  v ( S ) . Let note the condition X ._ ^ ^L Y ._,

V i e S by X_s ^ L Y _s . We say that an imputation X

dominates Y imputation, if there exists a coalition S c N for which X ^ у . In this case we write X ^ Y .

S

As well as in a classical cooperative game, in a lexicographic cooperative v game ideal variant also would be finding such kind of imputation, that would be belonged to C-core and would dominate over all other imputation. J.von Neumann and O. Morgenstern defined the solutions of a cooperative game as subsets of a set of imputations, they perform a ideal role of imputations. Let introduce a concept of such solution for a lexicographic cooperative game and establish some of its properties.

At first, define v = ( v 1 , v * ) ^T game’s C-core and show that conditions C-core’s imputations must by satisfied.

Definition 1. The set of all undominated imputations for a game _v = ( _v 1 , _v * ) ^T is called C-core let note it by

C ( v ) .

Theorem 1. C ( v ) is a set of X imputations for which X ( S ) ^ L v ( S ) , S c N .

Proof. If for any ^X imputation and ^{S c N} coalition

^{X ( S )} ≽     ^{v ( S )} , then from Y ^S it follows that

Y        ^L X         Y ( S )   ^L      v ( S )

^S ^        ^S and      '     < ^{v 7}  . Herewith

X(S)≽Lv(S), therefore from preferences YS ^  XS it follows that X(S)  ≽      Y(S)  , that contradicts

> X

^{Y S} domination.

Thus, it is proved that if ^{X ( S} ) >  ^{v ( S} ) for all ^{S c N} , then X imputation’s domination is not possible. On the contrary if ^X for any ^{S c N} coalition fulfills an inequality ^{X ( S} ) L ^ ^{v ( S} ) , than v ( S ) + v ( N \ S ) ^L_< v ( N ) = X ( S ) + X ( N \ S ) L ^ v ( S ) ₊ ^{X ( N} \ ^S ) and thus X ( N \ S ) ^ ^L v ( N \ S ) .

From v function’s L -super-additivity property it follows from the last inequality that i e N \ S players’ set, for which X .. ^ L v ( i ), is nonempty. For example for i₀ e N \ S player X > ^L v ( i ₀) Define the vector £ = ( ^ ,..., £_m ) by an equality.

Then X_ч >  L v ( i ) for i e N and

E Y.i = E (X: + —)+(X.. - £)+E X.i = i e N          i e S            | S |

E X. , = v (N),(8)

i e N or Y = (Y.j,..., Y.n) is an imputation in v game.

For i e S from £ ^ ^L О condition we get

Y. = X. + £ ^ LX.

i            i |S| and also

Y (S) = E (X .i + £) = X (S) + £ L > v (S) i eSI

Thus, it is proved that if for any S c N coalition X ( S ) L ^ v ( S ) , then X 6 C ( v ). The theorem is proved.

It follows from the theorem that if C ( v ) ^ 0, then C ( v ¹) ^ 0 . The following example shows that from C ( v ¹) ^ 0 does not follow C ( v ) ^ 0.

Example 1. Let discuss three players’ lexicographic cooperative game v = ( v *, v ²) ^T , where:

v 2(1) = v 42) = v 43) = 3, v1 (12) = v 1(13) = v423) = 2, v1 (123) = 1;

v 2(1) = v 2(2) = v 2(3) = 0, v2 (12) = v2 (13) = v2 (23) = 1, v2(123) = 1.

As v and v super-additive therefore v = ( v 1 , v²)

is L - super-additive.

v 1                                       X¹ = ( 1 , 1 , 1 )

v game has got the only imputation         ^{3 3 3}

.

Therefore each X imputation in v game has got a form

L

£ = min{ X ,_io - v ( i ₀), v ( S ) - X ( S )} ,     (6)

then £ ^ ^L О and note

X =

к x1

Y. i = 1

X ., + — , i e S ⁱ | S | ^,

X . i - ^£ , i = i о

X _ч , i 6 S , i ^ i₀ .

x

\

x 3 J

,

⎟

where ( x , x , x ) is an imputation in v ² .

By using 1 theorem the imputation X e C ( v ) then and only then, when ( x , x ₂, x ₃) e C ( v ²) . Herewith C ( v ²) = 0 , thus C ( v ) = 0 .

Let establish the ^{C ( v )} core’s structure of ^{C ( v )} game. Therefore suppose that C ( ^v ) + ⁰ and ^S is an arbitrary set of coalitions. We introduce the following notes:

D ⁰( S ) = { X ¹

e E ( v 1 )

X 4 S ) = v 4 S ), S eS

X 4 S ) >  v 4 S ), S tS

D 1 ( S ) = { X * | £ X * = v * ( N ), X * ( S ) >  L i e N

v * ( S ), S eS } .

Theorem 2. If in v = ( v ¹, v ²) ^T game C ( v ¹) + 0 , then

C ( v ) = J D ⁰( S ) x D 1 ( S ) .         (13)

S

Proof. It is obvious that

J D ⁰( S ) = C ( v 1 ).                  (14)

S

Therefore it is sufficient to check that if X ¹ e D ⁰( S )

for any S , then

X ¹( X *   ■ ^C ( v )■

= D 1 ( S ) .

By virtue of the theorem 1 the condition

X =

< X ¹)

X * 7

^e C ^{( v} )

is equal to inequality

X ( S ) >  L v ( S ) for every S c N .     (17)

It is obvious, that if S t S , then X 1 ( S ) >  L v 1 ( S ) and thus X ( S ) >  L v ( S ). If S e S , then X ¹ ( S ) = v ¹ ( S ) and the condition X ( S ) ≽ ^L v ( S ) is equal to the inequality X * ( S ) >  L v * ( S ), i.e. X * e D 1 (S).

• III.    Neumann-morgenstern’S solution of a LEXICOGRAPHIC COOPERATIVE GAME ’ S

Definition 2. A subset R c E ( v ) of v game’s imputation is called Neumann-Morgenstern’s solution if any its two imputations do not dominate each other (internal stability) and for any Y t R imputation there will be found such imputation as X e R , that X ^ Y

(external stability) for v game. Let note such solution R by NM ( v ) = R .

The set NM ( v ) = R is a stable subset of E ( _v ) set of imputation and therefore let call it a set of stable imputation of a lexicographic cooperative game analogically to the classical cooperative games [12, p. 235].

Neumann-Morgenstern’s solutions of a cooperative game is not possible to be used into practice. The concept of this solution has got a philosophic sense, that was explored by N.N. Vorob’ev: “it is a certain norm of a stable behaviour which is characteristic for a given social structure” [13]. Mathematics is universally accepted as mother of all science and it is in nature and in every fabric of life [14]. Game theory is a field of a modern mathematics which studies the norms of a human being’s behavior in the process of economic, social, political and everyday relationships. Therefore, if we take Neumann-Morgenstern’s norm of behavior in a game, then the payoffs imputation characterises player’s practical skills. Therefore this concept will be spread by using it in the case of a lexicographic game, because in such games we are having situations in the case of strictly ranked criterion. Some other applications of lexicographic games are studied in [15,16] articles.

First of all note that if   NM ( v ) = R , then

Pr( R l E ( v ¹ )) may not be existed NM ( v ¹ ).

Because of this it is interesting to put a question, if there exists or not R = NM ( v ),   for which

Pr( R l E ( v 1 )) = NM ( v 1 ) and what such kind of solutions sufficient conditions for their existence are like?

Let start the discussion of this problem with the very simple case, when v ¹ game’s C-core C ( v ¹ ) is NM ( v ¹ ). It follows that we can indicate the conditions, when in the process of their fulfilling C ( v ) = NM ( v ) , where v = ( v 1 , v *) ^T .

Let

X ¹ = ( X 11 ,X 12 ,..., X 1 n ) e E ( v ¹) , X *( S ) = ^ _X]. = ^{v 1( S} )                      ⁽¹⁸⁾

j e S and note

S ⁰( X 1 ) = { S c N I X 1 ( S ) = v 1 ( S )}     (19)

C T⁰ = { S ⁰( X 1 ) I X ¹ e C ( v 1 )} .

It is obvious that N e S ⁰( X 1 ) for V X ¹ e E ( v 1 ).

Theorem 3. Let   C ( v 1 ) = NM ( v 1 )  and for any

X ¹ e C ( v 1 )

J { S I S eS⁰( X 1 ) , S ^ N } ^ N .     (20)

Then C ( - ) # 0 and ^C ( v ) = NM ( v ) .

Proof. For X⁰ e ст ⁰ note

E(X0)={X1 e C(v 1)!50(X 1) = X0}.

It is obvious that

C (v 1) = U E (X0).(22)

00 X ест

Let note

2*

,      game’s imputation by X

*

_X *₌

^x 21

V x m 1

^x 2 n

x mn )

Let define the set

E ₂ ( X ⁰) ={ X * 1 X * ( 5 ) >  L v * ( 5 ), 5 eX ⁰ ,     (24)

X * ( N ) = v * ( N )} .

Let show that the set

R = U E i ( X ⁰) x E 2 ( X ⁰)         (25)

X ест is R = C(v) = NM(v) . For this it is sufficient to show that it fulfills an inclusion R c C(v) and R ’s condition of its external stability.

Let X e R . Then there exists such X ⁰ e ст ⁰ that

( X ¹ ) where X ¹ e E ( X ⁰) and X * e E ₂ ( X ⁰). If

X  V X * J ’

5 eX0 then X 1(5) = v 1(5) and x*(5) > L v*(5), where X♦(5) = 2 X.. Here with x 1(N) = v 1(N) , ie 5

X * ( N ) = v * ( N ). Then X e E ( v ) and X ( 5 ) >  L v ( 5 ). If 5 £X° , then X 1 ( 5 ) >  v 1 ( 5 ) and as X 1 ( N ) = v 1 ( N ), X * ( N) = v * ( N ), therefore we write X ( 5 ) >  ^L v ( 5 ).

Thus for X e R and 5 c N it fulfills the following enequality X ( S ) ≽ ^L v ( S ) and hence we write R C C ( v ) .

Let prove R ’s external stability. Let

( У¹ ^

^Y =    * e E ( v )

V Y )

and Y £ R.  Let discuss the following cases:  1)

Y ¹ £ C ( v 1 ), 2) Y ¹ e C ( v 1 ).

In the first 1) case let us external stability of C ( v ¹ ) , as providing that C ( v 1 ) = NM ( v 1 ) . Because of this there exists such imputation   X ¹ e C ( v ¹) and coalition

5 ₀ c N , that X ¹ ^ Y ¹  or X 1 ( 5 ₀ ) = v 1 ( 5 ₀ ) and

S 0

X 1 >  Y 1 . Here

S ₀       S ₀

X *= 2 x 1 j and Y 1₀= Z У i j .      (27)

j e 5 0                       j e 5 0

In the given case we can consider that, a coalition S is minimal with its members or there does not exist such coalition 5, c 5 _n that X ¹ ^ Y ¹ .

1         0                 _{S 1}

Let denote X * in the following way. For i e 5₀ choose X * in the way that X * ( 5 ₀ ) = v * ( 5 ₀ ) . As the coalition 5 ₀ is minimal, for which X ¹ ^ Y ¹, for every S 0

coalition 5 eX⁰( X 1 ) the following condition will be fulfilled 5 \ 5 ₀ ^ 0 .

Therefore for i e U { 5 1 5 e X ⁰ ( X 1 )} \ 5 ₀ player we can choose X ^* so that the following conditions will be fulfilled

2 X .* >  L v *( 5 ) , 5 eX ⁰( X 1 ) .     (28)

i e 5

By virtue of (20) for i e N\U{515 eX0(X 1),5 ^ N}   (29)

we can choose X ^* so

that 2 X * = v * ( N ) . i e N

It is obvious, that X * belongs to E ₂ (X⁰) . From the condition X ¹ e E , ( X ⁰) it follows that

X =

( X ¹ )

V X * J

e E 1 ( X ⁰) x E 2 ( X ⁰)

and X is an imputation from R. According to the given conditions   X 1(50) = v1(50),      X *(50) = v *( 50),

X 1 >  Y 1

S ₀       S ₀

it follows that X dominates

Y =

( Y ¹ )

Y * V Y

)

imputation in S coalition.

In the second 2) case Y =

Y * V Y

and Y ¹ e C ( v ¹). Let

suppose that 2 ⁰ = 2 ⁰( X 1 ) . As Y £ R , therefore the following condition Y * £ E ₂ ( 2 ⁰) must be fulfilled and thus there exists such coalition S_o e 2 ⁰ that

v * ( S _o) ^ L Y * ( S_o ). Let consider that S _o is a minimal set among the sets that have the same properties.

For every i e J {S l S e 20 (X 1)} player’s let increase components of Y * , we get elements of X * , for them the .i.

following relations will be fulfilled

• X.* ^ i'*, i e So,(31)

Z X * = v *( So),(32)

i ^{e S} 0

ZX* > Lv*(s), S e20.33)

i e S

Let choose for i e N \ J { S l S e2 ⁰} players’ the components of X * , finally we get X * = ( X * ,..., X * ) , that fulfills (31),   (32),  (33)  and the  condition

Z X * = v * ( N ) . Then X * £ E ₂( 2 °) and i e N

Theorem 4. Let R = NM ( v ) for v = ( v 1 , v * ) ^T game. If R ¹ = Pr( R l E ( v * )) and R ¹ * C ( v * ). then for any X ¹ e R ¹ \ C ( v 1 ) we have the following equality.

J{SlS e 2-(X 1),S * N} = N.(37)

Proof. Let suppose that for any X ¹ e R ¹ \ C ( v ¹)

J{SlS e2(X 1),S * N} * N(38)

and say that X =

( X 1

V X *

e R .

As X ¹ £ C ( v 1 ) therefore there exists such coalition S _o c N that

X 1(S0) < v 1(S0).(39)

According to (38) there exists a player i , who does not belong to any S * N coalition from 2 - ( X * ) family or if S * N and X 1 ( S ) <  v 1 ( S ), then i ₀ ^ S .

Let take such Y ^* that

X =

( X * ]

V X 7

e R .

Herewith in v game X ^ Y . The theorem is proved.

S 0

It is necessary to mention that, the proved theorem gives sufficient conditions for the existence of

v = ( v 1 , v ²,..., v m ) ^T

game’s core-solution,

for this

purpose we use limitations only for v game. In addition to this the theorem’s provement gives us the possibility to show such kind of solutions

R = J E * ( 2 °) x E 2 ( 2 ⁰),          (35)

00 2 ea

where E (2⁰) and E ₂ ( 2 ⁰) sets have already been defined above.

We now consider a general case when v ¹ game’s C-core is not its solution - C ( v 1 ) * NM ( v 1 ). Below we will show that 3 theorem condition’s opposite condition is a necessary condition for the existence of NM ( v ) solution.

For X ¹ e E ( v * ) imputation let note

2^- ( X * ) = { S c N l X 1 ( S ) <  v 1 ( S )} .     (36)

Y .i ^ ^LX . i , i e S 0 ,             (40)

Y,. = X„ i e N \ S 0 , i * i 0 ,       (41)

Y. * = v ' ( N ) - Z Y. '.            (42)

i * i 0

(X ¹ ^

Let check up that y = I     I is an imputation in

V Y * J v = (v 1, v*)T game. For i0 e So according to (40) and individual rational property of X imputation we write Y.,. ^L X.,. > L v(i). If i e N \ So and i * i0, then from (41) it follows that Y* = X*. Therefore Y.. = X.. > L v(i).

Finally, for i = i₀ we have i ₀ ^ 2^- ( X 1 ), therefore

x * _io >  ^v *⁽ i 0 ) ^and

Y . i ₀

^xx ¹ *

V Y . i 0 7

^ L v ( i 0 ) .

Thus for every i e N we have Y ._; >  L v ( i ). Condition (42) denotes that

Y *( N) = £ Y * = v *( N ) ,         (44)

therefore Y ( N ) = v ( N ) . Thus, Y is v = ( v 1 , v * ) T game’s imputation.

• (3 9) and (40) mean that Y ^ X . Hence, Y £ R , as in

S ₀

the oposite situation the internal stability will be violated. This means that, there exists an imputation.

Z =

< Z ¹ )

7 * к Z 7

e R ,

that dominates Y in any S coalition:

Z ^ Y =

S 1

X* к1  7

.

It is obvious that Z 1 = X 1 as if Z 1 >  X 1 then S 1          S 1                 S 1          S 1

Z >  X and again R internal stability will be violated.

S ₁

Then, namely from Z ^ Y condition we get that

S 1

Z 4 S ) <  v V S ) and thus X ¹( S ) <  v ¹( S )   or

S 1 eS - ( X ^L) .

It is clear that Z _o ^ S j. According to the definition of Y imputation and (40), (41), (42) conditions we write Y„ >  L X, . Therefore from Z ^ Y it follows that

• ^S 1                ^S 1                                      _{S 1}

Z ^ X . But as Z e R and X e R , we again get a

S 1

contradiction with internal stability. The theorem is proved.

• IV. Conclusion

In the process of defining a lexicographic cooperative game and discussing its principles of optimality, some difficulties are put forward, connected to the existence of a characteristic function, imputation, C-core. The more so, such difficulties were expected in lexicographic cooperative games, connected to the definition of Neumann-Morgenstern’s solutions and its existence. In the proved theorems there are necessary and sufficient conditions of the existence of Neumann-Morgenstern’s solutions. The proved theorems gives us the opportunity to establish its form in the case of their existence.