Foundations of Lexicographic Cooperative Game Theory

Published Online April 2013 in MECS DOI: 10.5815/ijmecs.2013.03.03

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

Г =< N,{Xi^N,{Ht}ieN > system,where N = {1,2,..., n} is a set of players’, Xt is i e N player’s set of mixed strategies,

H: П Xi= X ^ R1 i e N is i e N player’s real-valued payoff function, it tries to maximize the function. It means that, Г game is finite i.e. the players’ sets of pure strategies are finite. In Г game players choose their strategies independently xt e X, i e N and we get   a situation

X = ( X j , X ₂,..., x_n ) e X . Players payoff functions H ( X ), i e N are defined for every X e X .

In Г game players simultaneously     and independently choose their strategies so that they don’t inform each other about it. Therefore Г game is called a noncooperative or noncoalition. Players strategic behaviours 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 , that will be multicriteria    max(H (x),...,H (x))    problem

x solution.

About classical cooperative games, we can say that players’ cooperative behaviors are studied in Г game’s condition. Here players can enrol in coalition and each member of a coalition can negotiate with the rest for choosing their strategies consistently. At the same time players can sum up their payoffs and then they will imputate them. In the definition of a classical cooperative game we mean that players payoffs have transferring property or payoffs are measured by a unique scalar, and they can transfer from one player to another without limitation.

Formally, a classical cooperative game is called a couple <  N , V >  ,where N = {1,2,..., n } is a set of players, and V : 2 N ^ R ¹ is a real-valued function, that is defined on N every subset, also it means that V ( 0 )=0. A subset S c N is called a coalition and V function is Г game’s characteristic function. Therefore in cooperative <  N , V >  game the imputation will be appeared by n - vector’s real components.

Let us denote that in

Г =< N,{Xi }ie N ,{Hi}ie N > gameHi = (H‘, Hi2,..., Him) is a vector-function of i e N player’s payoff, for every i e N vector H has the same dimensional m and on the set of situations X =   Xt i eN

their comparison holds

lexicographically. We call such game a lexicographic noncooperative (noncoalition) game with dimensional m and we note it in the following way

ГL =< N,{X,},gN,{Hi}^N  >   (Г1,...,Гm)

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, = b, ,..., a  , =b ,, a > b

• 1       1 ,       ^,     m - 1       m - 1^, m       m

and a >  L b if a ^ L b or a = b .

L     ***

In Г game a situation X = ( x_x ,..., X_n ) G X is called an equilibrium if for any i = 1,..., n fulfills H i ( x ) >  L H i ( X ||_; X_x ) for every X_; G X_t .

• P. Fishburn [1] defined a lexicographic matrix game and its equilibrium situation in the mixed strategies. He gave an example of such kind of game and showed that an equilibrium situation does not exist in mixed strategies. It is shown by him, that there exists a game where the first player has not got a maximin strategy, and the second – a minimax strategy; there exists a game, where the first player has a maximin strategy, the second has a minimax strategy, but they are different.

• V. Podinovski [2] defined a lexicographic finite antagonistic game and explored the problems about the existence of an equilibrium situation in a lexicographic matrix game.Lexicographic noncooperative games with the existence of conditions of an equilibrium situation is studied by G. Beltadze [3,4,5,6,7].

In the process of studying lexicographic cooperative games there exists some problems connected to the existence of a characteristic function and imputation. The existence of C-core in lexicographic cooperative games are studied by G. Beltadze [8]. In the given article we discuss the foundations of lexicographic cooperative games, that is necessary for studying the principles of optimality. We show some differences and similarities in the process of studying them to classical cooperative games. The main part of the paper is studied in the II-V sections. In the second section of the article a lexicographic noncooperative ГL game’s characteristic function is discussed and the fairness of its properties is shown. In the third section a lexicographic cooperative game is discussed,          as          players’ lexicographically    defined    super additive m dimensional vector function v = (v 1,v2,...,vm)T on N = {1,2,...,n}set’s subsets. In     a     lexicographic     cooperative     game

• 1  2     mT

v = (v ,v ,...,v ) a concept of imputation is introduced that is given by means of a m x n dimensional X matrix. The theorem is proved that gives us a full description of E(v) set of v game’s imputations. In the fourth section a domination of imputations, cooperative games’ isomorphism and lexicographical essential cooperative game are defined. In the fifth section we introduce the definitions of two cooperative games’ strategic equivalence, normalization of a lexicographic cooperative game in (0,1) and it is proved that a lexicographic essential cooperative game is strategically equivalent in (0,1) to a normalised cooperative game.

• II.    LEXICOGRAPHIC NONCOOPERATIVE GAME’S CHARACTERISTIC FUNCTION

Let Г L =< N ,{ X^ n ,{ H i } i _e n >  be a lexicographic noncooperative game, for n player’s and m dimension. For any T C N , T ^ 0 coalition note that

Ht (X) = £ Hi (X), X G X iGT

If T = 0 , then suppose, that H_T ( X ) = O for any X i G X_t .

Let define every sets of T C N coalition mixed strategies by X .

For T C N coalition let consider a lexicographic antagonistic game Г L , where T and N \ T are the players and a function payoff is H _T .

We consider such Г ^L games, where exists a lexicographic maximin

v(T) = max min  HT (XT, XNxr), T c N

^XT ^G X T ^XN \ T ^{G X}N \ T

Definition 2.1. Let v ( T ) vector-function call a lexicographic noncooperative Г ^L game’s characteristic function.

Some main properties of scalar noncooperative games’ characteristic functions are maintained in a lexicographic case. Particularly, such kind of property is superadditivity.

Theorem 2.1. If T , S C N and T П S = 0 , then v(T О S ) >  ^L v(T ) + v ( S ) . Such function is called L — superadditival.

Proof. Analogically to the famous result that exists in a classical cooperative game theory we can write the following relations:

v (T) + v (S) = max min HT (XT, XN Nr) +

^XT ^G X T ^XN \ T ^{G X}N \ T

max min  HS (XS , XN \ S ) =

XS G X S XN\ S GXN\ S max (min H (X ,X ) + min H (X ,X ))

X_T X X,    _{Y                         v}

^{T   S      X}N \ T                            ^XN \ S

L <  max ( min H_T ( X_T , X _xs x X_s )

X T ^{X X}S ^XN \ T \ S

+ min ^H S ^{( X} S , ^X T ^{X X} N \ S \ T ))

X N \ T \ S

< max⁽ min H T _u s ⁽ X T _u s , X N₄ t _u s ) ) = v(T ° S ) .

^X T о S X N \( T о S )

The theorem is proved.

Definition 2.2. We say that a lexicographic noncooperative Г ^L game’s V has a property of complementary, if for all T C N fulfills the following equality V ( T ) + V ( N \ T ) = O.

For a scalar zero-sum noncooperative game’s characteristic function a property of complementary always takes place. But for a lexicographic zero-sum noncooperative game a property of complementary maybe won’t fulfill.

Theorem 2.2. If a lexicographic zero-sum noncooperative game’s characteristic function fulfills the property of complementary, then every lexicographic matrix game Г L ( T C N ) has a solution.

Proof. Let T C N ,  ^ H = O and i e N

V(T) = -v(N \ T). Then max min H (X ,X )

X T   X N \ T

= - max min H_NXT ( X_NXT , X_T )

^XN \ T ^XT

= min max H ( X , X )

X N \ T X T

It means that the lexicographic matrix game Г L has a solution.

• III.    LEXICOGRAPHIC COOPERATIVE GAMES

Definition 3.1. We call a lexicographic cooperative game in a form of a characteristic function a couple <  N , V > , where N = {1,2,..., n} is players’ set, v -real vector-function on N subset and fulfills the following conditions:

v ( 0 )= O; V (T о S ) >  L v (T ) + v ( S ) , T , S c N , T n S = 0 .

Definition 3.2. If v ( N ) = v ( S ) + v ( N \ S ) for any S C N , then <  N , V >  is called a lexicographic cooperative game with a constant sum.

It is shown by J. von Neumann and O. Morgenstern that every superadditive scalar function v , where V ( 0 )=0, is a characteristic function of any zero-sum noncooperative game [9]. Analogical fact for L — superadditive function is proved.

Theorem 3.1. On N = {1,2,..., n } set’s subsets for every L — superadditive function v₀ we can construct n player’s lexicographic noncooperative game Г ^L , where every lexicographic antagonistic Г L ( T C N ) game will have a solution and its meaning will coincide v 0 ( T ) .

Note, that N = {1,2,..., n }     set’s subset’s

L — superadditive function V we can be presented by a

1  2      mT           1

form of a vector V = (V , V ,...,V )  , where V , v2 ,..., vm functions N subsets are definite scalar functions.

According to this fact that v function is

L — superadditive, V ¹ is superadditive too. V ² ,..., V m functions’ maybe won’t have analogical property.

Example 3.1. Let discuss a lexicographic cooperative game as a form of a characteristic function <  N , V >  , where N = {1,2,3} , and V = ( V 1 , V 2 ) T is given as the following form:

v ( 0 )= (0;0) ^T , v (1) = (3;2) ^T , v (2) = (2;1) ^T , v (3) = (1;2) ^T , v (1,2) = (6;2) ^T ,

v (1,3) = (4;3) ^T , v (2;3) = (4;1) ^T , v (1,2,3) = (8;2) ^T .

Here v2( 0 )=0, v2(1) = 2, v2(2) = 1 , v2(3) = 2 , v 2(1,2) = 2   , v 2(1,3) = 3   , v 2(2,3) = 1   , v 2(1,2,3) = 2.

It is obvious that v ² is not superadditive, because , for example v ² (1,2) < v ² (1) + v ² (2) .

i t is necessary to discuss a function ( v ² ,..., v^m ) ^T on

*

N subsets, that we note by v . Hence, sometimes we can write v function in the following way 1    * T

V = ( V , V ) .

Shortly we call L — superadditive function 1   2      mT       1  * T

V = (V ,V ,...,V )   = (V , V ) a lexicographic cooperative game by m dimension. Because of this, *

V function in general is not L — superadditive, that is why we can’t connect it to a lexicographic cooperative game.

Definition 3.3. In a lexicographic cooperative

V = ( V 1 , V ) T game we call imputation a sequence of m dimensional vectors X = ( X _q, X .₂,..., X ._n) , where fulfills the following conditions:

• 1.    Individual rationality - X .. >  L V ( г ) for i G N ;

• 2.    Collective rationality - ^ X .,. = V ( N ) .

i = 1

If we write every X . vectors      in

( x ,..., x ) ^T column vector form,  then in

• 1    * T

V = ( V , V ) game we can write the   imputation

X = ( X . 1 , X . 2 ,..., X . n ) in a		form of matrix .
X =	" X 11     X 1 2    ...     X 1 n " x 21     x 22    ...    x 2 n .             .         ...         .
	V X m 1    X m 2    ...   X mn 7

Let note the set of imputation in V = ( V 1 , V * ) T game by E ( v ) and a projection of E ( v ) set on the E ( v ¹ ) set of v ¹ games imputation   - by

Pr( E ( v ) | E ( v ¹)) .

Let observe that if the given notes X G E(V) , then X1 = (X[[,X[2,...,X]„) G E(V 1)  . Therefore the condition

E (v) c E (V 1) X R nX(m-1)

is correct, where R nX(m 1) is a set of matrices x21    ...

.         ...         .

Y .Y

V x m 1    ... ^X mn 7

Condition (1) means that

E ( v 1) ^ Pr( E ( v )|E ( v 1)).(2)

In fact here the exact equality takes plase.

Theorem 3.2. E ( V 1 ) = Pr( E ( V ) | E ( V 1 )) .

Proof. Let hold the argument according to m dimension of V = (V 1, V )T game’s. For m = 1 an equality is correct, because V1 = V . Suppose for any m > 1 and X1 = (Xjj,Xj2,...,Xjn) G E(V 1) . Let consider two cases:

• 1)    X_u >  V ¹ ( i ) for any i G N ;

• 2)    x_xi = V ¹ ( i ) for all i g N .

Let divide 1) case into two subgroups:

• 1    a ) x_u >  V ¹ ( i ) for all i G N ;

• 1    b ) {i g N | x_u = v 1 ( i )} ^ 0

and

{ i g N | x_u >  v 1 ( i )} ^ 0 .

Suppose we have 1 a ) case. Let take such x

( i = 1,..., n; k = 2,..., m ) numbers and make up a matrix

X • = и x21    . .. ..   X2n ' ..         . V Xm 1   . Y ..  Xmn 7 for fulfilling the following conditions

^^X_ki = V^k ( N ) , k = 2,..., m .

i = 1

Then a matrix

	" X 11	x 12
X =	X 21 .	x 22 .
	V X m 1	X о m 2

X 1 n
x 2 n		r X q
. X mn 7	=	V X • 7

will be an imputation in

n

1    * T

V = (V , V ) game. In fact, a rationality condition ^ X.x = V(N) comes out from (3) i=1

n and ^ X1i = V 1( N)

i = 1

conditions, and

individual

rationality inequalities X . ≽ ^L v ( i ) comes out from

1 a ) condition.

In 1 b ) case let define a matrix X ^* in the following way. Define

N 1 = ^{{i G} N | Xu = v ¹ ( i )}, I ^N 1 1 = ⁿ 1 ,

N 2 = ^{{i G N} | X 1 i >  V 1 ( i )},   | N 2 | = n 2 .

It is obvious, that here N C N = N , N A N = 0 . Let note

x2, = v2 (i) +1, if i g N1,

V 2(N) -Z V 2( i) - ni x2l=---------—----------, if i g N2.       (4)

n2

Let choose other elements in conditions:

*

X matrix from the

n

Z xkl = vk (N), k = 3, i=1

...

, m .

/

Let us show that the given X

V

X *)

matrix is an

Z V ¹( i ) = V ¹( S ) for every S C N . According to i G S

V ’s L — superadditivity we can make a conclusion, that v ^* ( S ) ≽ ^L Z V ( i ) for every S C N . Hence i G S

V is L — superadditive function on subsets of N set and its dimension is m — 1 . If we use permissibility of induction in v ^* game, we can write that E ( V 2 ) = Pr( E ( V ) | E ( V 2 )) . From here it follows that E ( V ) ^ 0 . Therefore let take a matrix

x21    ...   x2n

.        ...        .

Vxm 1   .••  xmn У

imputation in V = ( V 1 , V ) T game. For i G N ₂ the condition X_ч >  ^L V ( i ) comes out from x_u >  V ¹ ( i ) inequalities. For i G N 1 it fulfills that x_u = V ¹ ( i ) and x_2/ = V ² ( i ) + 1 >  V ² ( i ), from which follows that X . ≽ ^L v ( i ) . So, it fulfills a condition of an individual rationality for X .

from the sets of v game’s imputation. It is obvious that a matrix

' v 1(1)   v ‘(2)   ... v 1( n)2

^x 21      ^x 22     ...     ^X 2 n

V xm 1    xm2    ... xmn У

Let check up that it fulfills an equality n

Z X ч = V (N).  If we consider (5) and i=1

( X ]j, X j₂,..., X ]) G E ( V ¹) conditions, it is sufficient

1    *T gives us the imputation in V = (V , V ) game.

With the help of discussing all cases we have proved

that for any X1 = (X115X12,...,X1 и) G E(V1)

imputation

to check up the equality from (4):

Z x = V ²( N ) . It follows i = 1

X =

1 X • V X у

there exists a matrix X ^*   , where

1    *T is an imputation in V = (V , V ) game.

n

Z ^X 2 i = Z x 2 i ⁺ Z ^X 2 i = Z ^{( V 2 (} i ) ^{+ 1) +} i = 1          i g N         i g N ₂        i g N ₁

n

v 2( N) - ZV 2( i) - n1 i G N!

n

Z v2( i)+n 1 + v2( N) - ZV 2( i) - n1 = V2( N).

i G N !                                       i G N !

Now consider the 2) case. If   X_b = V ¹ ( i ) for all

n i G N , then it means that Zv 1( i) = v 1( N) .

i = 1

Function V = ( V ¹, V ) T is L — superadditive and

This is equal to the condition

E ( v 1) c Pr( E ( v) | E (v 1)) .

After taking this and (2) into the consideration we have an exact equality E ( V ¹) = Pr( E ( V ) | E ( V ¹)) and the theorem is proved. It is shown that in game V = ( V ¹, V ) T a set of imputation is nonempty.

Now prove a theorem that gives us a full caracterisation of E ( v ) set. Let note X ^* matrix’s columns by X . ( i = 1,..., n ) and for S C N discuss the following sets

ES(v 1) = {X1 = (Xu,...,X1 n) g E(v 1)

1 X1i > v 1(i), i ё S; Xh. = v 1(i), i g S},

particularly for it should be V(N) > L ZV(i) . Hence i g N

fulfilled the inequality v is unessential or

n

ES(v*)= {X' I £X', = v'(N), X" > L V"(О, i=1

i e S}.

It is obvious, that if S = 0 , then

n

ES(v")={X"I £X> v*(N)}.

i = 1

Theorem 3.3. If v = ( V 1 , V ) T is a lexicographic cooperative game, then

E (v) = U ES( v 1) x ES( v *).

S c N

Proof. It is obvious that

E ( v 1) = U ES( v 1).

S c N

Therefore, on the basis of sufficient to show that for any

the theorem 3.2 it is

X1 e Es'(V 1) a set

/

{X *|X =

V

X

X

*

e E(v)}

is equal to E ¹ ( v ¹ ) . Let X ¹

e E ® ( V ¹) , it means that

S = {i e N | xu

= V ¹ ( i )} .If X is any kind of

/

matrix, for which

X =

v

X

X

*

is an imputation in

V = (V1, V )T game, then Xч У L V(i) , i = 1,

...

, n .

As it fulfills an equality x_lz = v ¹ ( i ) for i e S , therefore X .y L V ( i ) for i e S .

*

On the other hand by the X definition £ X . = V ( N ) . These two relations mean that i e N

X e E 1(V ). Hence, when  X1 e E°(V 1)  the condition is proved

/

{X *|X =

V

X

X

*

e E(v)} c ES(v*).

Contrary inclusion is obvious, as from the following conditions X1 e E0( V 1) and X e E 1( v ) it

follows that the matrix X =

V

X

X

*

fulfills the

following conditions £ Xч = V(N), X.; > L V(i) , ieN i = 1,..., n . The theorem is proved.

IV. DOMINATION OF AN IMPUTATION

For the purpose of studying the principles of optimality in lexicogrsphic cooperative games, as well as in the theory of classical cooperative games, it is necessary to define the apparatus of domination on the set of imputation.

Definition 4.1. We say that from X , Y e E ( v ) imputations X dominates Y in S c N coalition, if

X у ^ L Y ._z, i e S                               (6)

and

£ X.z L < v(S).                              (7)

i e S

We write (6) condition in the following way Xs ^ L Y_s and (7) condition - X ( S ) ^L <  V ( S ) . If X dominates Y in S coalition then we write X >  Y .

S

We say that imputation X dominates an imputation Y , if there exists a coalition S c N , for which X >  Y . In this case we write X ^ Y .

S

Analogically to the scalar case, in a lexicographic cooperative V = ( V 1 , V ) T game domination does not exist in a coalition, that consists of one player or N players.

Truly, from X >  Y domination it follows that i

Y ч L ^ X ч L ≼ v ( i ) , that is against the condition of

X imputation’s individual rationality. From X ^ Y

N follows that Xу У L Yу for every i e N and from here

£ X. i У L £ Y.i= V(N), ieN           ieN that contradicts to the condition of   X collective rationality .

Definition 4.2. Let call    two lexicographic cooperative v and u games isomorphic, if there exists one-to-one correspondence ф between the sets of E(V) and E(u) imputations, that for X У Y domination it is sufficient and necessary ф(X) У Ф(Y) .

Definition 4.3. We call a cooperative V = ( V 1 ,..., V m ) T    game L — essential, if

V ( N ) У ^L £ v ( i ) . If V 1 ( N ) >  £ V 1 ( i ) or when a i e N                      i e N

game v ¹ is essential, then we call v game completely L — essential.

Theorem 4.1. Every L — essential lexicographic V = ( V 1 ,..., V m ) T game is isomorphic of a completely L — essential lexicographic game.

Proof. The provement is obvious when

v 1( N )> 2 V '(i).

i e N

u = ( u 1 , u 2 ,..., u m ) T games are said to be strategic equivalent, if there exist such positive numbers k, ..... k and vectors ( c 1, ..., c m ) , I e N , that for all 1 mii

S C N we have

If 2 V 1(i ) = V 1(N) , then by ieN

theorem 3.3 in game

1    * T

V = ( V , V ) an imputation has the following form

X =

X 0

V X *

X* e E(v*).

where  X 1 = (V 1(1),..., V 1( n ))  and

It is clear that transformation ф : E ( V ) ^ E ( V )

X =

( X.

V X

0

- *

^ X

is one-to-one. By theorem 3.3 it is a transformation on

E(v*). In for i e S

v game the condition

X ^ Y means that

X1 •

V X. i 7

>

L

УУ’1* 1

VY.i 7

and 2

i e S V

fv x1i

L

As y1i

x .* 7

≼

Уv 1( $) 1

VV ■( S))

.

= Xu = V1 (i) and 2 V1 (i) = V1 (S) , we ieS

get an equivalent condition

X*, ► LV,. 2X• L < V*(S),

i e S

or in V game ф ( X ) >  ф ( Y ) . The theorem is proved.

This theorem shows that in the process of studying every points connected to the lexicographic domination of the imputation is sufficient to be limited by a completely L -essential cooperative game.

( v 1( S),..., Vm (S)) T =  (k 1 u 1( S),..., kmum (S)) T +

2 (cl,..., cm)T.

i e S

Definition 5.2. A lexicographic cooperative game V = ( V 1 , V ²,..., V^m ) ^T is said to be in (0,1) normalized if     V ( i ) = (0,...,0) T for all i e N and

v ( N) = (1,...,1) T.

1  2     mT

Theorem 5.1. If in V = ( V , V ,..., V ) game v ¹ ,..., v^m games are essential, or

v(N) > 2vj (i), j = 1,..., m , i e N then V = (V 1,V2,...,Vm)T is strategic equivalent in (0,1) of normalized lexicographic cooperative u game.

Proof. Let find u = ( u 1 , u 2 ,..., u m ) T game with the help of unknown numbers k ... k and vectors 1 ,, m

( c ¹ ,..., c ^m ) , i e N in the following form:

u(i) = (k 1V 1(i),..., kmVm (i))T +   (c1,...,cm )T =

(0,...,0)T, i e N,u (N) = ( k 1 v *( N),..., kmVm (N)) T +

2 (c1,..., cm ) T = (1,...,1) T.

i e N

From here we write the systems of equalities:

kjvj( i)+ ci =0 ' kjv(N) + 2 ci = 1, i e N

i e N; j = 1,..., m .

• V. COOPERATIVE GAME’S NORMALIZATION

Sometimes it is necessary to compare each other different cooperative game’s meanings in one and the same coalition. For this we introduce a concept of a lexicographic cooperative game’s normalization. Let define a lexicographic cooperative game’s strategic equivalence in advance.

Definition 5.1. For N = {1,2,..., n }   players’

• 1  2     mT

V = (V ,V ,...,V )                                and

From these systems we get

J   VJ( N) — 2 Vj( i)

i e N

c_i ^j

vj(i)

2 vj (i) — v'( N)’ ieN

j = 1,...’m ; i e N.

Herewith k ^ , j = 1,..., m and ( c 1 ,..., c m ) , i G N is defined identically. The theorem is proved

• VI. CONCLUSION

A lexicographic cooperative game is defined as a cooperative game with vector-functions of a finite dimension’s payoffs. A vector’s coordinates are ranked by decreasing. In such cooperative games some principles of optimality of a scalar cooperative games maybe will not be fulfilled. Basic foundations of lexicographic cooperative games are offered.

• [9]    J. von Neuman, O. Morgenstern, “Theory of Games and Economic Behavior”, Prinston University Press, 1944.

  
  
  

MR. Guram N. Beltadze is a full Professor,     mathematician     at

Informatics and Control Systems Faculty. He finished Tbilisi State University. He got a postgraduate education in the Academy of Sciences of the USSR in St.-Petersburg. His