EXTENSIONS OF COALITION

GAMES UDC 519.8

S. K. Polumienko

We consider a class of multilevel coalition games', with each game formed as the union of traditional cooperative and coalition games. Between-level interactions are described by a sequence of such games with different sets of reward functions.

Complex structured application domains and systems whose evolution is described by parameters representing inconsistency and/or conflict among the individual elements and subsystems are commonly analyzed using game-theoretical methods that do not reflect the full complexity of possible interdependences and the multilevel structure of these systems. The classes of coalition and cooperative games and multilevel coalitionless games have been studied in detail, and research is progressing on the subject of multilevel cooperative gaines [1, 2]. These studies, however, are still fairly disjointed, which restricts their applicability to real environmental and economic systems, to optimization problems and decision making methods, and to many other applications associated with optimal control of the national economy. The purpose of this study is to define and analyze multilevel coalition games as an apparatus for modeling of complex systems and solution of the corresponding optimization problems. MULTILEVEL COALITION GAMES We write the game in the general form [31

ro =

<~, ~, {s;(}K%, ~, ~ {~,(};(%n ),

where l is the set of players, -~a is the set (complex) of coalitions of action, K, S is the set of situations, , _ ~

SK

(1)

IS the set of coalition strategies of coalition

[-I S K, R'in is the complex of coalitions of interests, {HK} is the set of payoff functions. KE..~ a

The game (1) in its most general form is solvable in the following cases: a) realization games [4]:

{HK}Ke~Q' Qd, QS, Q, {cK}K~Q),

(2)

where 1 is the set of players, ~Qd, ~Qs, ~Q are respectively the complexes corresponding to distributional, strategic, and complete realizations, ~o = { K : K C ~Q, U K = i} {OK} is the set of coalition strings forming the game realizations; KEffQ

b) coalition ganqes [5[:

r/< = (I, ~, {s~}~, ~, {h,~}~:~),

(3)

where ff is some combination of coalitions from ~-----~a=Rin and U K = I;

Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 107-115, January-February, 1992. Original article submitted September 17, 1990. 1060-0396/9212801-0091512.50 ©1992 Plenum Publishing Corporation

91

c) cooperative nonstrategic games [6]

r~ <~,, {a(~}~%), =

(4)

where {G(K)} are the functions of subsets (measures) on ~inwhich express the coalition payoff. Using (2)-(4), we define the game

r = (r~, rc>

(5)

with payoff functions in the situation

~(g,~)+

H~(~)+ a(K).

In this game, FQ is called the strategic componentand Fc the cooperativecomponent. We will examine the propertiesof this game. The payofffunction HK of the coalition K is definedas the sum of the payoff functions of the participating players [5]. The situation g* is called acceptable [5] for the coalition I~ with respect to the coalition K if for any sK E SK, SI~\K E SI~\K,

H~ (s* IIsm~) ~< ~ (s* IIs,<), where S K and SI~\K are respectively the sets of coalition strategies of the coalitions K and I(\K. Acceptability of a situation implies that in the face of the pure coalition strategy of the player from K, the players from I<\K should preferably maintain their initial mode of action. Let SObe some mapping of ~ to :~., i.e., the set of coalition pairs (I(, K), where K E ~, K E ~ and I( tj saIT( _c ~. The situation ~* is called so-stable [5] if for any K E R it is acceptable for I( with respect to soI(. Let [5] ~ = ~n ~ ~n-~ ~ .-. ~ ~ ~ ,~o = 0 be an arbitrary normal series of R of the game (3), T i the extreme skeleton of ~ which corresponds to the normal subcomplex R¢_,, a n d Q~ = T~ \ t Ri_,[. Partition each of the sets Qi into pairwise no nintersecting sets of players Qi = Kil 1,3 Ki2 LI ... td Kir i and take the family of all subsets Kij , i = 1 ..... n, j = 1 ..... r i as ~. Let sa*K~l = 0 and sa*Ki,i C

U Kk/, and Kij k) so*Ki,i ~ ,,~ Kij ~ sa*Kij = ~ . k<~~.~<~i

The so*-stability of the mixed situation p, [5] implies that the inequalities

/-/r. (~t II(szqj, s,,,~¢i))<~/-/K¢i (~ IIs~,~i)

(6)

are satisfied for any Ki~ E~, ski I E Sr¢ i, s~.i<¢i E S~,Kt i. T H E O R E M 1 [5]. Every regular coalition game (3) has (mixed) so*-stable situations. These situations can be found among situations that are Markov with respect to the complex ~* (the image of the complex ~' under the mapping sa*). The game (4) is considered in [6]. The end game is the pair (N, v), where N is a finite set, v is a real-valued function on 2 N. The elements of N are called players, the elements of 2 N are called coalitions. Let/9 be a permutation of N, G N the space of functions v, x E E N the space of N-vectors on N. Define 6,v in G N by the equality (0.v)(S) = v(0S) and in E N by the equality (0.x)(i) -- x(0i). For i C G N, the null player of the game v is the element i on N such that v(S U {i}) = v(S) f o r a l l S C N. The value [6] on G N is the function SOc: GN '-> EN that satisfies the following conditions. Axiom 1. sac is linear. Axiom 2. For all v E G N and all permutations 0 of the set N, we have ~(O,v) = O(sav). Axiom 3. (sav)(N) = v(N). Axiom 4. If i is the null player v, then (sav)(i) = 0. T H E O R E M 2 [6]. On G N there exists one and only one value defined by the formula

(~) (0 = where3,s = IS I!( n -

92

]S] - l)!/n!, n = I NI.

~

Vs (v (s U {i})-- v(s)),

s c N \ { ~}

(7)

If ',/"~ is one of n! orders on N, then we denote by P ~ (7) is equivalent [6] to the expression (i) =

The vector ~ = (~'c,

~K),

where ~K

1

the set of players that precede i in the linear order J ? . Then

v s (v

u (i)) -

v

(8)

is considered as the optimality principle of the game

=

iF = (P•, It).

(9)

In this game, contrary to (5), the strategic component is coalition game (3), but with the same payoff functions {H(K, ")}Ke~ " LEMMA. Games defined by the coalition structure of game I"K with payoff functions {Ht<}I<~~ and {/J (K, ")}K~ respectively are affine equivalent. Proof is by simple substitution of {/t (K, ")}K~ in (6). Eliminating from (6) G(K), which by construction is independent of the set of situations, we obtain the same relationship for {HI<}K~~ • From the definition of the game (3), its coalition complex •~ is formed before the game starts. We thus define two stages of playing thegame (9): - construction of the coalition complex ~ = Ea in the framework of the cooperative component F c (solving this component, we remove from .~. -- Ea ) all coalitions and players that are indistinguishable with respect to some threshold ~'); lrl. - redistribution of the rewards in the framework of F K. Under these assumptions, we obtain the following corollary of the lemma. COROLLARY. Under the conditions of Theorems 1 and 2, the game (9) has a ~-optimal solution contained in rOe ({G (K)}Ke~i) × %
(10)

is identified with a two-level subsystem of the modeled complex system. Repeating the above construction and passing tYom level indices 2 and 1 to p and p - 1, we obtain the system Level

p:

PF--= (~i, Pg, PF, PSi, PG (i), PH i (Ps), Level

p ~

p -~ 1, Po),

1:

i1'F -----{~-llPa.... , ~ - l r np_l)~" np_l ~ It'-I I [,

P'--IF --/P-~I

s,-IS .

u-~

(11)

p-I

t

where v~ ~ {o~}i~l is some fixed scale of weights (importance measures) of the players that corresponds to level p. 93

Definition 1. The system (11) is called a general-form multilevel coalition game.

Let us define the relationships between the payoff functions in P+ IF and PF and the rules for which the game (11) is analyzed. By PKj we denote the set of coalitions of level p that participate in the formation of situations, i.e., to each situation ,+1~

~

~

nO ~"

Ps, Ps 6 [-I p s' corresponds a fictitious coalition PI~j, which in general is different from all the others. ~=1

Assume that on level p the coalition PI(j has the capital endowment pG0(pI(j). From its representative on level p + 1 the coalition receives (12) At the beginning of the game, PI(j has the capital endowment

"~ ('Kj) = "~ ('k j)+ "+'cg ('~;,) + ;-'~0' ('~,),

(13)

which is allocated to all the participating players. Since the game is essential, we should have [5]

(14)

I

First, the cooperative component of the game (9) is played. Let PG'(PKj) be the distribution received by the coalition PKj C PKi as a result of this game, We have [6]

'6' ('K~) := ~ '6' ¢i). iEPK]

(15)

Players indistinguishable with respect to some threshold ~" can be eliminated at this stage. The game continues as a strategic game with payoff functions {'Hr}Kc~. After playing both components of the game, the coalition PKj receives the reward

' ~ ('K j, Q = 'HKj (~ + '~ (K~), P6 (K j) = P6' (PKj) - - P6 ; - ~ (PKj) - - ' 6 '+~ ( ' K j),

' a '-~ ('Kj) = ~] '6 '-~ ( %

(16)

'Kj = 'K j,

iePKj

where PGp-I(pi) and PGp+I(PKj) respectively are the payments made by player Pi to his agents on level p - 1 and by the coalition PKj to its representative on level p + 1. Rule 1 (of. [2]). The distribution of the reward between levels p + 1, p and p, p - 1 is done independently in the framework of the two-level games 2FL(P+ tj, PI~j) and 2FL(Pj, P-lI(j). The players can change their capital endowments only before or after playing a party of the game between the given levels. Rule 2. The player P+ lj announces his strategy to the coalition PI~j and provides it with the capital required for the execution of the strategy for all s E P+LSj. By this rule, the player P+ lj knows the entire set of strategies of the players from PI~j, but he does not fix the choice of a specific situation g, which consists of the collection of level-p strategies and his own strategy realizing this collection. Rule 3. The players in coalitions of level p do not have information about the set of strategies of coalitions of level p+l. Rule 4. The endowment of level p with the capital P+ IG0P(PI~j) and its allocation to coalitions and players PI~j is done within the framework of the cooperative component of the game (9). Its solution defines the complex ~ in (3). Rule 5. The strategy of the player P+ lj is realized by the strategic component of the game (9).

94

In other words, a preliminary estimate is first obtained of the possibilities of pIT~jwith regard to the realization of the strategies P+~j and then these strategies are realized. Rule 6. The payments between levels are fixed. The game (11) will be considered subject to the system of rules 1-6. It is written as p = 1, po) = ( r L ,

=

p = a, po).

(17)

T H E O R E M 3. Under the conditions of Theorems 1 and 2, the game (11) has a ~-optimal solution. Proof In the game F L we identify two players: P+ lj and the fictitious player PKj. The first player uses the strategies P+ ISj and the second uses the entire set of situations PS realizing the strategies p+lj. Seeing that the payoff pI(j is generated as the payoff of all the participating elements in the framework of the game I' L, we define the payoff functions HI, HII in r' L. As in [7], let

VL (,,+1]) ___ VL (I) ----- max m i n H i (P+ls, Ps--), p+lsj p~ v a (PI(j) =

vL

(II) = max rain H n (P+Is, Ps'). pg P'~-Isj

(18)

With this definition, (18) is a game in the sense of [6]. By Theorem 2, we have

1 (v L (I, II)--v (q)LDL)(I) = -~-

L

(I)), (19)

1 (ePLVL) (II) = -2-(VL (II, I ) - - VL (II))

as the values for players I and II. By construction, VL(l, II) = VL(II, I). The function H n and the value (¢LVL)(II) define respectively the payoff and the minimum guaranteed payoff of level p in P L. We can thus assume that (¢,LVL)(II) = (¢cVc)(P/) = vc(P/) is the value of the game PcBy Theorem 2, we have for F c

1

(P~ U (0)-- vc0~/'~ )),

Z ((~GVC)(i) : (q)LVL) ( I I ) iEPl Let ~PL = (~Pl, ~PII), ~ c = (q)c 1 . . . . .

=

(CPcVc)(PI).

(20)

q)cp ) ' and let the values of the components of these vectors be defined by the 1

expressions (18)-(20). Identifying ~l! and ~c, we define the vector ~L¢ = (
95

these interests by the situations forming in the course of the game and at the end of the game (including the ~-optimal situation). Let PUI be the set of interests of players of level p formed as the union over all i E Pl of the vectors Pui of the individual interests Pui of the players i. We may take IPuil = mpi < mp~ over all i E Pl. Thus, the lPll x mpl matrix POI of player interests is associated to level p. For measurement and comparison of Pui, we use the simplest scale: to POt we associate the matrix of predicates Pp(Pl.TJI), which are true when the players Pi are satisfied by the realization of their interests at the end of the game, and the matrix of individual weights P3'i specified by the players on the sets of their interests. We introduce the utility function of the players that evaluates the satisfaction of their interests: mp l

(%),

"L, ( % ) = rrl = l

(21) mp i

O~y~l,

~

77

1.

m~J

Without changing the constructions, we may assume that the strategy set of the players Pi is the set of prestrategy vectors selected from a fixed set of subsets PSi, and s i E S is s i = (psf)3EBi, where/3i is an index set. in every organization, there is a group of decision makers whose strategies must be carried out by their subordinates. The players form coalitions of action, guided by the interests of these decision makers. In the game (11), P+ lj is such a decision maker. In addition to this player, we also identify the players h = hK, which by analogy with [2] will be called coalition centers. The player h is called a coalition center if one of the following conditions is satisfied: 1) u i = ui(uh) f o r a l l i E K , h E K C I, 2) s i = Si(Sh) or s i = si(PSh) for all i E K, h E K C I, 3) 1) and 2) are satisfied. Here u i, u h are the elements of the interest vectors of the players i and h, respectively; s i and si(PSh) are their strategies (prestrategies). We see that in case 3) the player p+lj is the unique center in R over the entire VRin O PI. The player Pi knows all the subsets PUh, PPSi/3 over all Ph and is capable of estimating in advance the change of his realized interests as a result of entering the coalition PKll. If the player simultaneously joins other coalitions PK/2. . . . . PK/n, then he naturally faces greater opportunities for satisfying his interests. This advance analysis of interests and strategies and their coordination with PUb, PSh leads each player to identify the subsets of i n t e r e s t s PUii a n d PUi K = PUh which are realized independently and by coalition strategies. The set PUiK also includes the interests that can be realized only in coalitions. In (21) we thus pass to the functions

.d epu

pd%vt4< N

(22)

=

The union

Ke~.r~eK

:

Ke~i n

is called the set of coalition interests. We assume that each player can establish a lower bound on the realizability of his interests Pfi within the coalition strategies. Let P~'I be the set of all such thresholds for all i E Pl. The players i E P~in can realize their interests and thus maximize the functions (22) only by coalition action: even if it is disadvantageous for some player to joint the coalitions, the realization of his interests depends on the coalition behavior.

96

Therefore, the individual players are also included in ; ~ n ' With this assumption, to each coalition K ~ ~P~in we associate the utility function (compare with [6, 8]) % (%).

¢.t<) =

(23)

iEPK

Similarly to (18), we define the function

v~t<(Put<) =

max PK

~LK (PuK),

min

(24)

K~P~in,K~t<=~

which is the maximum of (23) in the face of opposition from all other coalitions. For the function (24) we can define the cooperative game

ru = ( ~ ,

~U

%'

(25)

T H E O R E M 4. Under axioms 1-4, the game (25) has a unique value. Proof Clearly VLK(~) = 0. Following [5, 9], it suffices to establish superadditivity [8]:

vet<, (PuK,) + vL~" (Out<~)<~ vc~ ' u~_ (~u~ , Put<,) tbr K l n K 2 = ~ , Kl, K2 c P'~in. Indeed, we have

ULt
~--- max

KtUK~

PL t<,UKo (PuK, U Pu~%) =

rain

~EP~ in

,~N(K,UKp=o

--- max rain (PLK, (PUt<,)"}- °L t<, (°u,Q)

by (24). Now, by nonnegativity of (24), rain

KeP~in

(PLK, (PuK,) + °Lt<, (Put<~)) =

~C'O(t<~Ut
rain

PL (Put<) +

~n(t<,UK~>=~

rain

PL

P

Kn(KwKO=c

and sincei~ n (K l u K2) c_ I~ n K l andl~ n (K 1 U Ko)_ _c 1~ n Ko,_ I~ E o~}in, we have min PLK~ CuKt) + min "Lt<~ Cut
PLt<1 (Uut<) "-k

rain PLt<~ (PttK~)

for I~ E oR.!In Hence we obtain "

vc~lv,% (PUKIUK)~

max ( rain PLt<1 (PuK) + K1UK~ K (.)KI=0

+

rain PLs~ (Put<)) = vL~ ~ (PuK1)+ Vm'~.~ (PUK), ff f ~'~n ~n~,=~

Thus, (24) is a game in the sense of [6] (a characteristic function [8]) and tbr (25) there is a mapping ~'u which is the value of the game from (7). 97

Solving the game, the player finds (~PLVL)(Pi), which enters (23) and is expressed by (7). If (~LVL)(Pi) < P~'i, the player has every reason to exit the coalition. The reasons for the breala~p of coalitions can be expressed similarly. In the game (17), we measured the "consequences" by the quantities PGp-I(pi) and PGP+ I(PKj) passed to other levels, keeping the payments fixed (rule 6). We now use the functions {PLK}~:~in for this purpose. Assuming that the quantity PGA(PKj) = P+ IGP(PKj) - PGP + I(PKj) is allocated by the center p+lj for the realization of the interests of the coalition PKj and PG'5(PKj) includes the portion P+lGZX(P+ lj) of the player P+ lj for the realization of his individual interests, we obtain a contradictory situation for all the elements of level p, including P+ lj: there are no conflicts of interest among the players. We obtain a game f'u similar to (~-rL, I'C), defined for the functions (23) and the function P+1Lj. By Theorems 3 and 4, there exists a mapping ~LU, which is the value of this game. Here P Pu ---- ({"+'1} O P~in: ~+'UI hi U~in,

P~ { LK}t<~#+li~UP~i)n

(26)

and the quantities PG2~(PKj), P+IGA(p+lj) are defined by (17)-(18). Rule 6'. The scheme of payments between the levels of the game (17) is defined by the game (26). De[in#ion 2. The game = <'rL, re, rs,

p = 1, p,> = (r,., re, rs, ?u, p

=

1,

Po},

(27)

satisfying the rules 1-5, 6' is called a general-form extended multilevel coalition game. Ottr constructions prove the following theorem. T H E O R E M 5. Under the conditions of Theorems 1 and 2, the game (27) has a ,b-optimal solution, where • = (~, ~LU) ~- (~LC, ~°S, ~LU)" The games considered in this paper are used for modeling and optimization of organizations and environmentaleconomic systems (in particular, see [9]). LITERATURE CITED .

2. .

4. 5. 6. 7. .

9.

98

N. S. Kukushkin and V. V. Morozov, Theory of Non-Zero-Sum Games [in Russian], Izd. MGU, Moscow (1984). V. A. Gorelik and A. F. Kononenko, Game-Theoretical Models of Decision Making in Environmental-Economic Systems [in Russian], Radio i Svyaz', Moscow (1982). N. N. Vorob'ev, "State of the art in game theory," Usp. Mat. Nauk, 25, No. 2, 81-140 (1970). A. I. Kondrat'ev, Game-Theoretical Models in Classification Problems [in Russian], Nauka, Moscow (1986). N. N. Vorob'ev, "Coalition games," Teor. Veroyatn. Ee Primen., 12, No. 2, 71-85 (1967). R. J. Aumann and L. S. Shapley, Values for Nonatomic Games, Princeton Univ. Press, NJ (1974). A. I. Kondrat'ev, S. K. Polumienko, and A. A. Stognii, Construction of Structural Game-Theoretical Models of Complex Systems [in Russian], Preprint DVNTs Akad. Nauk SSSR, Vladivostok (1987). G. V. Dyubin and V. G. Suzdal', An Introduction to Applied Theory of Games [in Russian], Nauka, Moscow (1981). S. K. Polumienko, "Modeling and optimization of information support systems for scientific research," in: A. A. Stognii, (ed.), Computerization of Information Support for Scientific Research [in Russian], Naukova Dumka, Kiev (1990), pp. 39-72.