Shapley's Axiomatics for Lexicographic Cooperative Games

Published Online August 2015 in MECS DOI: 10.5815/ijmecs.2015.08.01

Analogically to the classical cooperative game theory in lexicographic cooperative games the main basic model represents a lexicographic noncooperative game [1,2,3,4,5,6]. The players’ cooperative behaviors in condition of a noncooperative game are studied. In noncooperative games players independently and simultaneously choose their strategies without telling each other about it. These games are called noncooperative where the players get guaranteed payoffs (utilities). In cooperative games the players can enrol in coalitions and each member can discuss about choosing their strategies consistently. At the same time the players from coalition sum their payoffs and then they distribute them. For a certain class of cooperative games players’ utilities have a transferring feature. Payoffs are measured by the same scale and they can transfer from one player to another without loosing and limitation.

Let discuss a classical noncooperative game

Г =        (1)

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

H.: ПX = X ^ R1 - i G N is player’s real- i e N valued payoff (utility) function. The player tries to maximize this function. It means, that Г game is finite, i.e. the players’ sets of pure strategies are finite. In Г game the players choose their strategies x e X, i e N and get the situation x = (Xj,x2,...,xn) e X. In each X e X situation the players’ payoff’s function H\(X), i e N are defined. Let discuss Г game’s modification using the following rule:    suppose, that

H = (H1,H2,...,H™) is i e N player’s payoff’s vector-function, for every i e N vector H; has identical measurement m and their comparison on the

X = П X set of the situations happens lexicographicaly, ie N

or criteria in payoff’s vector-function are strictly ranking. We call such game a lexicographic noncooperative game with m measurement and we note it in the following way

Г L =< N ,{ X i } i e N ,{ H i } i e N >  = ( Г 1 ,..., Г m ).   (2)

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

• 1)     a_x >  b ; 2) a_x = b_x , a^ >  b₂ ;...; m )

a l = ^b 1 , . . . , a m - 1 = ^bm - 1 , a m >  ^bm         ⁽³⁾

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

In the process of transferring from Г L = ( Г ¹,..., Г ^m ) game to the lexicographic cooperative game there are some difficulties they are analyzed by the author and it is related to the characterising function and the existence of the payoffs distribution, C -core and Neumann-Morgenstern’s solutions [7, 8].

The article is dedicated to Shapley’s axiomatic approach for lexicographic cooperative games [9]. It has been revealed that in contrast to the principles’ of C -core and Neumann-Morgenstern’s solutions, Shapley’s axiomatics principle is similar to the case of a classical one discussed by Shapley’s axiomatics principle. In detail, axiomatics discussed by Shapley for classical games are sufficient with payoff’s corresponding with distribution in lexicographic cooperative games. Besides, we are having a very interesting case – a classical principle identically is spread over the component of a lexicographic game for scalar games.

Let discuss n player’s m dimensional lexicographic noncooperative game

Г ^L =< N ,{ X₁}_ie N ,{ H i } , _e N >        (4)

and for any T C N , T ^ 0 coalition note

H T ( X ) = ^ H i ( X ) , X G X .       (5)

i g T

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

Note by X_T set of mixed strategies of T C N coalition. Let discuss a lexicographic antagonistic game Г L for T C N coalition, where T and N \ T are the players and H_T is the function of a payoff.

Let discuss such Г L games, where exists a lexicographic maxi min max min HT (XT, XN\T), T c N.    (6)

X T    X N \ T

The real vector-function v = ( v ¹,..., v m ) ^T is called a lexicographic noncooperative Г L game’s characterising function or m dimensional lexicographic cooperative game, if it satisfies L - super additive conditions: if T , 5 C N and T П S = 0 , then for v game’s value is fulfilled v(T U S ) >  L v(T ) + v ( S ). Note that v ¹

scalar game’s additive comes out from v game’s L - super additive and v ² or any other scalar v ³ ,..., v^m games could not be additive.

In the lexicographic cooperative v = ( v ¹,..., v m ) T game m dimensional n vector’s consequence X = ( X _ч, X .₂,..., X .„) is called the payoffs’ distribution, where the following conditions are fulfilled:

• 1.    Individual rationality – X . ≽ ^L v ( i ) for every

• 2.    Collective rationality - ^^_X .. = _v ( _N ). i = 1

i G N ;

If each X . vector is formulated by ( x ,..., x ) ^T vector-column, then in v = ( v ¹,..., v m ) ^T game the distribution X = ( X _ч, X .₂,..., X .„) has the form of a matrix

' X11    X12    ...

X = x 21   x 22   ...   x 2 n .(7)

.             .         ....

Y YY кXm 1   xm2   ...

As we have already stated above Shapley’s axiomatics is defined for classical cooperative games and get the vector of payoff’s distribution. For the lexicographic cooperative v = ( v¹,..., v m ) ^T game such kind of approach gives us the payoff’s matrix of distribution.

• II.    Related Work

Discussing this problem is very important and it is caused by several different circumstances. The problem is that Shapley’s vector (value) and its result Shapley Shubik’s index are discussed as the principle of a fair distribution. It is used in different branches of economics, in the market competitive conditions, in the distribution of input and stocks, logistics, network systems and etc.

How to make the individual get he reasonable and practical profit between the fourth party logistics is still a question for further researches. By using Shapley value the weight of each enterprise is analyzed [10]. It is shown that, Shapley value model is relatively rational, practical and necessary mechanism in the fourth party logistics. The development of cooperative strategies between exporting countries have been taken place by the logistic rationalization [11]. The annual gain’s distribution is formulated by the concepts of a cooperative game theory. From several methods of gain’s distribution Shapley value is being used.

Traditional network optimization focuses on a single control objective in a network populated by obedient users and limited dispersion of information. However, most of today’s networks are large scale with lack of access to centralized information, consist of users with diverse requirements, and are subject to dynamic changes. These factors naturally motivate a new distributed control paradigm, where the network infrastructure is kept simple and the network control functions are delegated to individual agents that make their decisions independently (“selfishly").The interaction of multiple independent decision-makers necessitates the use of game theory [12]. Network games represent the new direction in Game theory.

Networked Control System (NCS) is a synthetic application that combines control science, computer science and network technology. Networked control systems (NCSs) have been gaining popularity with their high potential in widespread applications and becoming realizable with the rapid developments in computer, communication and control technologies. This paper reviews the development history of the NCS, and point out the field of farther researches [13].

The Shapley value—probably the most important normative payoff division scheme in coalition games. This approach has a variety of real-world applications (including social and organisational networks, biological networks and communication networks), its computational properties have not been widely studied. To date, the only practicable approach to compute Shapley value-based centrality has been via Monte Carlo simulations that are computationally expensive and not guaranteed to give an exact answer. Against this background, this paper presents the first study of the computational aspects of the Shapley value for network centrality’s [14].

It is shown that if the distribution of profits is enforced at a global level, then there exist profit-sharing mechanisms derived from the coalition games concept of Shapley value and its extensions that will encourage these selfish ISPs who seek to maximize their own profits to converge to a Nash equilibrium [15].

An easy and an efficient transmission pricing scheme using Shapley value method and power flow tracing method to allocate usage andcost of the transmission system in a deregulated environment is proposed. By comparing both the methods it is found that for a large power system allocation of usage and cost to users is difficult by using Shapley value method due to increase in number of coalitions [16].

In the paper [17] a new centrality metric for social network is introduced. An appropriate cooperative game is proposed and then presented efficient approximate algorithm to compute Shapley value of this game in order to rank the nodes based on the gatekeeper centrality.

Shapley Shubik’s index is used in voting. It plays a great role in politics [18]. Namely, for the definition of polling station’s measure, what station’s support is more necessary for choosing the wanted candidate. In the Parliament or in other representative branch party’s (player’s) vote’s number is not the accurate index of its influence. By means of Shapley’s vector the index of player’s is defined, as the average number of those coalitions, where its participation provides winning, and without it the coalition looses.

Hence, Game Theory as a branch of Mathematics and Computer Science. It helps us to solve the different problems of everyday life. The question is: why only mathematics helps us to solve the above stated problems. Because, the nature is innately mathematical and she speaks to us in mathematics. We should only listen to her. Therefore, any science that describes the nature is completely dependent on mathematics. Mathematics plays a great role and it is the essential instrument for many aspects of different sciences [19].

At the same time Game Theory is one of the largest part of the information culture. Therefore it has a great influence on modern education. In the article [20] the influence of educational, professionalism and activity pecularites has been studied on the formation of the personal information culture pecularities.

There are many learning methodologies that have been adopted down the years. One of them is Problem Based Learning (PBL). PBL is an approach, in which the learners first encounter the problem, followed by a systematic, student-centered inquiry process. In general, games and simulations provide rich learning environment for the students [21].

In game theory the most practical problems is multicriteria. All problems stated above is reasonable to establish in case of multi criteria. If we order these criteria with strict preference then in the interaction conditions we will have lexicographic cooperative games and Shapley matrix principle will be used.

• III.    Shapley’S Axiomatics for a Lexicographic Game

As well as in the case of classical cooperative games, in v = ( v ¹ ,..., v^m ) ^T game S ⊂ N coalition is called v game’s carrier, if we are having the following equality v ( K ) = v ( K П S ) for every coalition K c N , but we call i ∈ N player a stupid, if

v ( K \ { i }) = v ( K ), i ∈ K ⊂ N , (8) or

v(K U {i}) = v(K) + v(i), if i t K c N. (9)

Let π be any permutation of a set N , or π is a function π : N → N , that will correspond with this element i ∈ N by π ( i ) ∈ N meaning. π K denote permutation of K coalition: π K = { π ( i ) | i ∈ K }, and π v is a game that comes from v , if we change all K by π K . If u and v are cooperative games, then w = u + v note a cooperative game, its meaning is

w(K ) = u ( K ) + v ( K ),   K c N . For any c >  0

number cv defines a game, its meaning for any K c N is equal to cv ( K ).

Definition 1. Let call a lexicographic cooperative v = ( v 1 ,...,v m ) ^T game’s Shalley’s m x n matrix ф( v ), that consists of m dimensional vector-columns

Ф . 1 ( v ), Ф . ₂ ( v ),..., Ф . n ( v ),            (10)

where

Ф. j (v) = (Ф,, (v),..., Фm,j (v))T , j = 1,...,n and satisfies the following axioms [22]:

• 1)    Carrier’s - if S is a v game’s carrier, then 2 . S Ф ( v ) =X ^S )•

• 2)    Simmetry’s - if П is any permutation more than for any i . N we have Ф^) ( n v ) = Ф ._; ( v ).

• 3)    Linearity’s - for any two u and v game Ф . ( u + v ) = Ф . ( u ) + Ф ._; ( v ).

Definition 2. Suppose Ф function corresponds with v game by 1)_3) axioms Ф ( v ) matrix. Then the estimation of Ф ( v ) is called v = ( v 1 ,..., v m ) ^T game’s meaning or Shapley’s matrix.

What do above mentioned axioms mean? The axiom 1) says, that the players from carrier S coalition distribute v ( S ) common payoff. At the same time, for any i player, who is stupid gets Ф ._; ( v ) = O. The axiom 2) demands that the game’s meaning could not be depended on the players’ names. 3) According to the axiom, it is fair to believe that if the players are participating in two games (the sum will be understood as N players simultaneous participation in u and v games), then their payoffs could be added in separate games.

• IV.    Shapley’S Matrix of Payoffs’ Distributions

Suppose v p ( p = 1,..., m ) is a defined scalar function on the subsets of N = {1,2,..., n } set and l p = (0,...,1,...,0) ^T is a basic vector in R^m space, which component is 1 by number p .

lemma 1. If a lexicographic cooperative game v has a form _v = _v ^p l_p , then for each mapping Ф : v ^ Ф ( v ), that will be satisfied the above mentioned axioms the following equality must be fulfilled

Ф ( v ) = I p -Ф ( v^p ).              (11)

Proof. Suppose Ф ( v ) matrix has the following form

<Ф1Д   . .   Ф1,п Ф( v) = .. Ф p ,1   . ..    . Ф .   Ф p,n ,           (12) .. Ф , Vй m ,1   . ..    . Ф .       m, n ^ where Фу / = Фу z(v). By 1) axiom v = (v 1,..., vm )T game’s for any coalition S fulfills the following consequence

• 0,     j * p

У Ф .( v ) =                        (13)

• ²   j , ^{l lJ}  1 v^p ( S ),   j = p .

For any system of real numbers

• 2 1 , ..., 2 p _ 1 , 2 p + 1 ,..., 2 m

let discuss the following vector-function

• * ( v^p ) = ( Ф p ,1 + E 2 j Ф j_Л ,..., Ф p , n + j * ^p                          (14)

2 ² j ^Ф j , n ) =^Ф p v^p ) + 2 2 ^Ф j . ( v^p )■ j * p                       j * p

For ^ function Shapley’s every axioms are fulfilled. It is clear that if S is v ^p game’s carrier, then S will be also v game’s carrier. Therefore from (13) we write

* S ( v p ) = 2 ф p, ( v p ) + 2 2 j 2 Ф j, ( v p ) = v p ( S ).

• l.    S                 j * pl

The condition у ( n v p ) = * ( v p ) comes out from 2) axiom:

T, (nvp) = (v,|l)(n1.p),..., * ,n)<^vp)), where

• *„ , , n v^p ) =ф ,„ . ( n v p ) + 2 2 , Ф,„ , ) ( n v^p )

„           j’p(17)

= Ф „( v p ) + 2 2 , Ф» ( v p ) = * l ( v p ).

j * p

* function’s linearity’s condition

^ ( u^p + v^p ) = ^ ( u p ) + ^ ( v^p )       (18)

is a result of the 3)-rd axiom.

Hence, for classical games according to Shapley’s main theorem ^ ( v^p ) vector is defined identically and represents Shapley’s vector in v^p game:

y ( v ) = ф ( v^p ) = ( Ф 1 ( v ).., ф n ( v )),     (19)

i.e.

Ф l ( v ) = ф „ ( v ) + 2 j _M ( v ).      (20)

j * p

Because of the numbers Д ,..., ^ 1, ^ +р.-, ^ are arbitrary, the equality could be fulfilled only in the following conditions

m

Ф ( v ) = £ ф ( l p v^p ),            (25)

p = 1

and by the lemma 1 we write

m

Ф ( v ) = 2 l p Ф ( v^p ),            (26)

p = 1

so the theorem is proved.

Note by s several players’ in S coalition - s = | S |. Then on the strength of this theorem for the lexicographic cooperative v = ( v 1 ,..., v m ) ^T game’s Ф ( v ) matrix vector-line we have

Ф p,i (v ) = 2 ⁽ s ^1)!( n s ^)! ( v^p ( S ) - S c N ,         n !

i e S

— v^p ( S \{ i }),

Ф ,,l ( v ^p ) =

0, \ф i ( v ^p ),

j * p j = p ,

p = 1,...,m and

where l = 1,..., n.

Therefore

Г^фи ( v ) )

.

	Г 0    .	.   .     0 >
Ф ( v ) =	.. Ф 1    .	..   . ■  . Ф .	= l p -Ф( vp ),	(22)

⁰ J

Ф . , ( v ) =

.

.

1^Ф m , i ⁽ v ) J

= 2

S c N , i e S

( s - 1)!( n - s )!

( v 1 ( S ) - v 1 ( S \{ i }) )

n !

this proof was demanded.

Lemma 1 gives us the opportunity to prove the main result.

Theorem 1. There exists the only function Ф , that for each v = ( v 1 ,..., v^m ) ^T game Ф ( v ) matrix is corresponded and 1) - 3) axioms is satisfied. At the same time Ф ( v ) matrix vector-lines

(vm (S) - vm (S \{i}) J i = 1,..., n.

Example 1. Let find Shapley’s matrix for 2 dimensioned lexicographic cooperative game v = ( v *, v ²) ^T :

Ф p ,1 ,..., Ф p , n ( p = 1,..., m )          (23)

coincide v = (v 1,..., vm )T game’s vp component’s of shapley’s vector.

Proof. Write down v = ( v 1 ,..., v m ) ^T game by the form of the components of the sum

m v=2 lpvp.

p = 1

v (i ) = (0;0) ^T , i = 1,2,3, v (12) = (0;0,4), v (13) = = (0,2;0,1) ^T , v (23) = (0,2;0,3) ^T , v (123) = (1;1) ^T .

Solution. v = ( v *, v ²) T game L is super additive. Therefore acoording to the theorem it has Shapley’s matrix

^{Ф ( v} ) = ^{( Ф}ч ^{( v} ), ^Ф . 2^{( v} ), ^Ф . 3^{( v} )) =

By 3) axiom we get

:ф

^Ф 1,2

^Ф 2,2

^Ф 1,3 )

Ф

2,3 J

The first line’s elements of this matrix represents v ¹ game’s Shaplkey’s vector. This scalar cooperative game has got the following form

V1 (i) = 0, i = 1,2,3, V 1(12) = 0, V1 (13) = 0,2, v 1(23) = 0,2, v 1(123) = 1

and it is super additive. Let find its Shapley’s vector.

According to the (27) formula, for finding Ф 1, i ( v 1 ), i = 1,2,3 we have to discuss the meanings of the summand for such S coalition that consists i . Let name these coalition for every i :

i = 1, S 1 = {1}, S 2 = {1,2}, S 3 = {1,3}, S 4 = {1,2,3};

i = 2, S 1 = {2}, S 2 = {1,2}, S 3 = {2,3}, S 4 = {1,2,3};

i = 3, S 1 = {3}, S 2 = {1,3}, S 3 = {2,3}, S 4 = {1,2,3}.

After this we easily calculate (27) each summand.

Let calculate in detail only Ф, j ( V 1 ). we have

Ф,.( V 1 ) = ⁽¹ - ^{1)!(3 - 1)!} .( V 1 (1) - v 4 0 ))+

+ ⁽² - 1Ж3 - 2)! .( v 1 (12) - ^{v 1 (2))} +

⁺ (2 -¹)!(³ - ^2)! .( v ¹ (13) - v ¹ (3)) +

+ ^{(3 -} 1Ж3 ^{- 3)!} _ ( v i(123) - v ¹ (23)) =

= 2.0 + 1.0 + 1.0,2 + 1.0,8 = 0,3.     ⁽³⁰⁾

6      6      6,     6,      ,

We analogically get vector’s other two coordinates Ф 1,₂ ( V 1 ) = 0,3, Ф, ₃( V 1 ) = 0,4. We could find easily the third coordinate by calculating Ф₁₃( V 1 ) = 1 - (0,3 + 0,3) = 0,4. Hence V ¹ game’s Shapley’s vector is equal to

( Ф 1,1 ( v ¹), Ф 1,2 ( v ¹), Ф,з ( v ¹)) = (0,3;0,3;0,4).

Vector (Ф₂ Ф₂ Ф₂ ) represents a lexicographic cooperative game’s 2-nd component v ² ’s Shapley’s vector. The game v ² has the following form

V ² ( i ) = 0, i = 1,2,3; V 2 (12) = 0,4, v ² (13) = 0,1, v 2 (23) = 0,3, v 2 (23) = 1.

The game is super additive and its Shapley’s vector will be calculated analogically as in v ¹ game. We get

( Ф 2,1 ( V ²), Ф 2,2 ( V 2 ), Ф 2,3 ( V 2 )) =

- f 19 25 16 A                     ⁽³²⁾

= ( 60,60,60 )

Hence, v = ( v 1 , v ²) ^T game’s Shapley’s matrix is equal to

	f 0,3	0,3	0,4 A
Ф ( V ) =	19	25	16	.                (33)
	( 60	60	60 ,

Hence, in the lexicographic game the players’ common payoff V (123) = (1;1) ^T has been distributed: the vectors (0,3;19 60), (0,3;25 60) and (0,4;16 60) are the first, the second and the third player’s payoff part corresponding with V = ( V 1 , V ²) ^T game. At the same time by the definition of a lexicographic preference the most part gets the third player, fewer than this the second and the fewest the third:

(0,4;16/60) ^ L (0,3;25/60) > ^L (0,3;19/60).

Example 2. Let find Shapley’s matrix for a 1    2T lexicographic cooperative game V = (V , V )  .

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

Solution. This game L is super additive, where v ² is a game:

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

It is not super additive ( V 2 (12) <  V ²(1) + V 2 (2)). From L -super additive V = ( V 1 , V 2 ) ^T by the theorem there exists Shapley’s matrix, analogically it has the form to the previous example

( ^Ф ...    Фи  ^Ф ,.3

(Ф 2,1    Ф 2,2    Ф 2,3

Its first line’s elements represent v1 game’s v 1( 0)=0, v 1(1) = 3, v 1(2) = 2,, v 1(3) = 1, v 1(12) = 6, v 1(13) = 4, v 1(23) = 4, v 1(123) = 8

Shapley’s vector’s components

( Ф 1,1 ( v 1 ), Ф^( v 1 ), Ф 1,3 ( v 1 )),          (36)

and the 2-nd line’s elements give us v ² game’s Shapley’s vector - (Ф_2t( v ²),Ф_{2 2}( v ²),Ф_{2 3}( v ²)). Let calculate them.

According to the (27) formula and the previous solution we write:

Hence, v ¹ game’s Shapley’s vector is equal to

(Фц (v1), Ф1,2 (v1), Ф1,3 (v1)) = (3,5;3;1,5).(3 8)

For v ² game the same (27) formula gives:

Ф2,1 (v2) = 2; Ф2,2(v2) = 1,5; Ф2,3(v2) = 0,5

and Hence v ² game’s Shapley vector is

(Ф 2,1 (v2), Ф 2,2 (v2), Ф 2,3 (v2)) = (2;1,5;0,5)(40)

and v = (v1,v2)T game’s Shapley’s matrix has the following form

Ф ( v )

( 3,5   3   1,5 )

( 2   1,5  0,5 J

For lexicographic cooperative games by discussing Shapley’s axiomatics we get some significant position. Namely, the last example shows us that from v = ( v 1 , v 2 ) T game’s L -super additive, where v ² scalar cooperative game is not super additive, Shapley’s matrix anyway gives us a fair distribution of common payoffs:

Ф 1,1 ( v ¹) + Ф 1,2 ( v ¹) + Ф 1,3 ( v ¹) = 3,5 + 3 + 1,5 = 8 = = v 4123),

Ф₂,1 ( v ²) + Ф₂,₂ ( v ²) + Ф₂,3 ( v ²) = 2 + 1,5 + 0,5 = 4 = = v 2 (123).

• V. Conclusion

Generally it should be mentioned that for lexicographic cooperative games v = ( v 1 , v ²,..., v m ) T differ from the optimal principles ( C -core and Neumann-Morgenstern’s solutions) discussed by us previously, only Shapley’s principle is spread on v game’s each v ¹ ,..., v^m component simultaneously and seperately, nevertheless from v ²,..., v^m scalar games any of them or every could not be super additive. The difference is in the case of a scalar cooperative game Shapley’s axiomatics gives us the vector of payoffs’ distribution, but in the case of a lexicographic cooperative game it is given by the form of a matrix. The given result – Shapley matrix principle could be used in all those problems, where Shapley vector is used, if the problem will be put by using ranking criteria.