S l A M J . A P P I . MATH.
Vol. 26, No 3, May 1974
NUCLEOLUSES OF COMPOUND SIMPLE GAMES*
NIMROD MEGIDDOt
Absh.act. The nucleolus is a unique solut~onconcept for a cooperative game. It belongs to the
kernel of the game. Given m games over disjoint sets of players and an m-player game, one defines a
compound game over the union of the nt disjoint sets. These m games are the components and the
above twplayer game is called the quotlent.
The nucleolus of the compound game is a combination of the nucleoluses of the components. i.e..
the payoffs In the components are proportional to the payoffs in the compound. The combinat~on
depends on the quotlent game and on the two highest levels of excesses with respect to the nucleoluses
of the components. This combination is the solution of a problem of the same nature as that of the
nucleolus.
i
i
I
1
I
I
,
I
-1
1. Introduction. The nucleolus of a cooperative game was defined by D.
Schmeidler in [lo]. It is a solution concept for a characteristic function game
which consists of a unique point. As a point of the kernel of the game (see [2])
the nucleolus reflects strength relations between players and symmetry properties
of the characteristic function.
Compound simple games were defined by L. S. Shapley in [I I]. Shapley
proved in [12], [13], [14] (also proved by G. Owen in [9]) that von NeumannMorgenstern solutions of the component games compose in a natural manner
which results in a solution of the compound game. Kernels have a very similar
property (see [ 5 ] ) .
The nucleolus of the product of simple games was characterized in [4]. In
most of the cases (when the maximum excesses with respect to the nucleoluses
of the component games are distinct) the nucleolus of the product coincides with
the nucleolus of the component the maximum excess of which is the least. In this
case the players in the other components get zero. When the maximum excesses
in the components are not distinct the nucleolus ofthe product is a convex combination of the components' nucleoluses.
In this paper we generalize the results of [4]. A compound simple game is a
tensor composition (see [9]) with simple components. In view of the results
presented here, the computation of the nucleolus of a decomposable game (with
simple components) is easier than that of a prime one. It is equivalent to the
computation of the components' nucleoluses plus a similar computation in the
quotient game.
2. Definitions. A charucteristic function game is a pair r = ( N ; u) where
N = j 1, . . . , n ) is a nonempty finite set (whose elements are the players) and u
is a real-valued function defined over the subsets of N (the coalitions in the game).
A simple game is a characteristic function game l- = ( N ; u ) where for every
S c N either v(S) = 1 or v(S) = 0. Those coalitions that have a unit value are
called winning coalitions. The set of the winning coalitions is denoted by H and
the game is represented also by = ( N ; % ). We always assume N E % . A game
* Received by the editors September
6 . 1972. and in revised form February 23. 1973.
t Department of Mathematics. The Hebrew U n ~ v e r s ~ of
t y Jerusalem. Jerusalem, Israel
NUCLEOLUSES OF COMPOUND SIMPLE GAMES
That means
(3.4)
e(S,, V) 2 . . . 2 e(S2,, v),
(3.5)
e(Tl, y)
Let i, (1
l . . . 2 e(T2n,y).
5 i, 5 2") be the first index of unequal excesses :
e(Sio,V) <
(3.61
4 T 0 ,Y),
i < io * e(S,, V) = e(T,, y).
(3.7)
We shall prove that for every i < i,,
e(Si, v)
(3.8)
=
e(Si, y) .
First,
@,, 1 , V)> e(S,,, V )
(3.9)
-
(otherwise (3.5) and (3.7) contradict (3.6)). Let i* (1 5 i* 5 2") be defined by
(3.10)
e(Si*,V ) f 6
,Y)
and
Without loss of generality we assume that for every i > i*,
(3.12)
e(S,.,
and for every i < i*, Si =
i* - 1., . Suppose
V) =
e(S,, v)
* e(Si*,y) 2 e(Si,y)
T . It can be easily seen that i*
(3.13)
i,. We sha.11 prove that
< i,.
i*
Statements (3.7), (3.10) and (3.13) imply
Statements (3.9) and (3.13) imply
(3.15)
e(Sit,v) > e(S,,, v ) .
There exists c > 0 such that the imputation z
i > i* (see (3.12))
e(Si*,z ) = (1
=
Also, (3.11) implies
and (3.14) implies
-
c)e(Si*,v)
e(Si,z )
=
(1
-
c)v
+ ~y satislies for every
+ ee(Si*,y)
610
NIMROD MEGIDDO
Statements (3.16H3.18) imply that B(z) precedes 0 ( v ) in the lexicographical
order on R2" in contradiction to the assumption that v is the nucleolus. Thus,
i* = i, and (3.8) is proved. Relation (3.1)follows from (3.6) and (3.8).
The nucleolus was defined to be an imputation whose excesses vector is a
lexicographical minimum. In order to characterize the nucleolus of a compound
game we would like to define here a general lexicographical problem.
PROBLEM
3.2. Given a set of m affine functionals over R".
we denote by a ( x ) an m-tuple whose components are the numbers u,(x),
; = 1, . . . , m, arranged in decreasing order. Given a convex polytope X c Rn,
our problem is to find x, E X such that u ( x o ) is minimal in the lexicographical
order on R m in the set ja(x) :x E X 1 .
Rernark 3.3. One possible way to solve an n-dimensional lexicographical
problem with m functionals is by solving at most min (m, n) linear problems
(see [I]). The first one is: Minimize t subject to the constraints
Suppose X , is the set of the solutions to the kth problem and A , is the set of indices
i such that a i ( x )is not constant in X,. The ( k
1)th problem is: Minimize t subject
to
+
(3.22)
ai(x) 5 t ,
(3.23)
EX,.
~EA,,
In view of this method, a lexicographical problem may be simplified as
follows. Denote
Suppose a,(,is a linear combination of a,, , . . . , U i p and
a,,(x) 5 min {u,,(x):j
= 1,
. . . , p)
for every x E X. Then a,, may be omitted without affecting the solution. Our
last claim follows from the fact that, throughout the computation, in every problem,
k, either a&) is constant in X , or the constraint a,,(x) 5 t may be omitted (see
(3.25)).
DEFINITION
3.4. Let .Y' c 2" be any collection of coalitions in a game
r =(N;V).
(i) The nuclrolus with respect to 9 is defined to be the set of the solutions of
the lexicographical problem over X ( T ) with the functionals e(S,x ) , S E .Y. We
denote this set by ./l;,(T).
(ii) .if is called a nucleo-suficient collection if . l.&(T) coincides with the
nucleolus. b'(T) = . A ; N ( T )of r. That means that throughout the computation of
the nucleolus, one may be restricted to constraints corresponding to the coalitions
in 9.
NUCLEOLUSES OF COMPOUND SIMPLE GAMES
LEMMA3.5. Let I-
( N ;v) be a monotonic game und denote
.H,(r)= { S c N : ( 3E S )(v(S \ { i } )< v ( S ) ) ) ,
(3.26)
(3.27)
=
.#,(I-)
= { S c N : ( V T c S)(IS \ TI
2 2 * v(T)< v(S))),
Then .&(T) is a nucleo-sufficient collection in T.
Proof: A coalition S has property I if there are S 1 , . . . , S, E .&(I') such that
Si c S, z?(Si)= v(S),i = 1, . . . , k, and the characteristic vector of S, f , is a linear
combination of the characteristic vectors zSzof S i , i = 1, . . . , k. We shall prove
that every coalition S has property I. This is certainly true for the I-player
coalitions (see (3.29)). Let S consist of more than one player and assume, by induction, that every T 5 S has property I . If S E &(I-) then S has property I , so let
us assume that S $ .#(T). If S 6&',(r), then for every i E S,
and X S is a linear combination of the vectors xS\('), i E S (recall that there are at
least two players in S ) .
If S $ &,(I-) then there exist i,j E S (i # j) such that
Thus, there always exist
Also, X S is a linear combination of XS\'ii, XS\{Ji and XS\'i9j\
coalitions S , , . . . , S, such that Si c S, v(Si) = v(S),Sihas property I, i = 1, . . . , k,
and is a linear combination of x S 1 , . . . , x S k . It follows that S has property I. In
view of Remark 3.3, since every coalition S has property I , it follows that d ( T ) is a
nucleo-sufficient collection in T.
LEMMA3.6. Let r = ( N ; % ') be u monotonic simple gume with no veto pluyers
and denote
Then % * is u nucleo-suficient collection.
Proof. It is easily verified that
Using arguments similar to those of Lemma 3.5, we can prove that
(3.34)
~ ~ =( 4ir*(r)
r )
);1
(see Definition 3.4). Since d ( T ) =
U
Y4
it is sufficient to prove that .II is a
**,
6 12
NIMROD MEGIDDO
nucleo-sufficient collection, i.e.,
For every player i there is a winning coalition S such that i $ S. Also, S U {if is
winning because of the monotonicity. If { i ) is not winning, then for every x E X ( r ) ,
Moreover, x{'' is a linear combination of x S and XSu(i' and therefore e ( { i ) x, ) may
be omitted throughout the computation of the nucleolus (see Remark 3.3). Thus,
(3.35)is proved.
4. The nucleolus of a simple committee-game. In this section we prove that
the nucleolus of a simple committee-game is the barycentric projection of the
nucleolus of the grand game on this committee. Thus, strength relations between
the members of the committee, as reflected in the nucleolus, are the same in the
committee-game and in the grand game.
We shall use the notation
(4.1)
9 ( x ) = { a i : a i ( x2
) aj(x),B= 1 , . . . , m ) ,
x
EX
,
when dealing with Problem 3.2.
LEMMA
4.1. If' x E X 1 ( r )(using the notation of Remark 3.3 in the problem of
computing the nucleolus), where = ( N : LI) is a monotonic game, then for every
i E N there is S E 9 ( x ) such that i E S.
Proof: The proof is immediate in case x i = 0. If x i > 0 and' i # U { S : S E 9 ( x ) ) ,
then 0 4 9 ( x ) ( N4 @ x ) , e ( 0 ,x ) = e ( N ,x ) ) .For E > 0 small enough we can define
an imputation y,
such that for every S E G'(x),
and
This 1s a contradiction to our assumption that x E X l ( T ) .
LEMMA
4.2. Let = ( N ;v ) be a rrzonotonic game and Tc = ( C ; Yk;) a simple
C E %c.
comrn~ttee-gameof r. If x E X 1(1-), then there exists S E 9 ( x )such that S
Proof. The proof is ~mmediateif x(C) = 0. If I E C and x , > 0, let S E 9 ( x )such
thati~S(seeLemma4,1).IfS
n C$%,,then
and, thus, S 4 g(x)-a contradiction !
We consider 9 ( X ) also as a set of coalitions; no confusion may be caused since there is a one-toone correspondence between coalitions and their excesses.
613
NUCLEOLUSES OF COMPOUND SIMPLE GAMES
DEFINITION
4.3. Given a monotonic game r = ( N ; v), a simple committeegame rc = (C; q;)and an imputation x such that x(C) # 0, we denote
1
-max{v(CUT)-x(T):TcN\C)
(4.6)
w'"'(B)
ifB~%,,
=
max {v(T) - x(T) : T
ifB$W;.
c N \C)
We call rp)= (C ; w'")) the modification of Tc with respect to x. We shall show that
this modification, which does not depend on xi for i E C (but depends on x(C)),
does not affect the nucleolus of the committee-game if x E X l ( r ) . We use the
notation e',"'(S, y),
etc. when these expressions refer to the game r p ) .
Let us denote
o(T) = min {O,(x):x E X ( r ) ) ,
(4.7)
for any B E %; and
for any B $ %,.
LEMMA
4.4. Let r = ( N ; v) be a monotonic game and
such that x(C) # 0, then
committee-game of r. If x E X l(r)
r,
=
(C; V,) a simple
(4.10)
4 r (4
c >
= w(x)
o
(see Definition 4.3 and (4.7134.9)).
Proof. First, it follows from Definition 4.3 that
wy 2 1
(4.11)
N\C, then v(T U C) - x(T) = x(C)).Let Y E X(Tc) such that
} 1 - o(Tc)
min {y(B):B E ~ G =
and let 2 E X ( r ) such that
(if T
=
It follows from Lemma 4.2 that
Q1(Z)= max (e(S, 2 ) : s
=
c
N , S fl C E %
);
max {v(C U T) - x(T): T c N \C)
-
x(C) . min {y(B):B E %),
Since x(C). w t ) is also an excess with respect to 2 (see Definition 4.3) it follows that
Since for every z E X(rC),
(4.15)
min ( z ( B ) :B E Wk) S 1 - o(r,),
614
NIMROD MEGIDDO
it follows from (4.14H4.15) that
(4.16)
8',-'(z) = max {ev'(S,z) : S E 7%c J
so that
(4.17)
a(TF)) = \v(:)
-
(1 - a(l-0) 2
wp'.
Remark 4.5. Since o(T,) < I it follows from (4.14) that
> ,+,g).
(4.18)
w 1( ~ )
Thus, the winning coalitions in T, have (in the modified committee-game) a value
which is still greater than that of the losing coalitions. Moreover, it also follows that
~(r',"))
2 g(rc).
(4.19)
LEMMA4.6. Let r = ( N ; c) be u monotonic gunw und let T, = ( C ; f4,) be u
simple committee-gume with no veto players. Under these conditions, for ecery
i E C there is S E Y4& such that i $ S and S E 2',"'(y),for ecery y E X ,(Iy',"').
Proof: (a) Suppose, per absurdum, that i E C and y E X ,(I-?)) such that for
every S E fb;, S E C&(Cx)(y)implies i E S. Since i is not a veto player, there exists
such that i $ So. Thus, So $5$'(y) and, therefore, for every
So E
s H;. C ~ O ~ ) ,
$c
n
(4.20)
e',")(S,y) > e',")(S,, y) .
It thus follows that for every S E 7%; fl 9(Cx'(y)there i s i $ S ( j # i) such that yj > 0.
Let E be such that 0 < E < min jyj:j # i, yj # 0 ) and define y* by
(4.21 )
J ~ T=
I
y,
-
c
0
I
if1 # i a n d j , # 0 ,
if y,
-
y*(N\[ij)
if/
=
=
0,
i.
It follows that for every S 6 9FX)(y),
(4.22)
ey'(S, y*) < eF'(S. y ) .
If E is small enough, then $4, n 9',"'(y*) c Yb, fl Lic,"'(y)in contradiction to the
assumption that j E X ,(r:')).
We have proved that for every I E C and y E X,(r:")
there is S E Y%( fl f/F1(j)such that r E S.
(b) The existence of S was proved for every y E X,(Tp'). Particularly, that is
true for every y In the set
It can be inferred from Lemma 3.1 that y E XT and z E X I imply V',"'(y) c 'l',"'(z)
and, therefore, S E %?'(z) for every z E X ,(r',")).
LEMMA
4.7. Let = (N ; v) be a monotonicgame and let r, = (C ; 7%;) be u simple
committee-game. l f ' x E X l ( r ) is such that x(C) > 0 then the nucleolus o f r , coincides
with the nucleolus of'
'", 'r with respect to X(Tc).
Proof: (a) If there are veto players in T,, then o(F,) = 0 and (4.14) implies
wy' - 1 2 wg'. Thus, for every y E X(r,) and S E ' U i , ey'(S, y ) 2 wg) and the
respective lexicographical problems differ by a constant.
NUCLEOLUSES OF COMPOUND SIMPLE GAMES
615
(b) Assume that there are no veto players in T,. According to Definition 4.3
U
and (3.29), .&(TF') = ?A(T,) =
Y4 ,*. It can be seen that
to the nucleolus of I",'-l
(see Lemma 3.5). Suppose {i) $ W, and S E W i is such that
i $ S and y E X l ( r F ) )implies S E IlrF'(y) (see Lemma 4.6). Under these conditions,
for every j. E X l ( r F ) )(according to Lemmas 4.4 and 4.6)
Since %(i' = ZSu(i' - x ~it, follows, in view of (4.24), that the constraint eF)({i),jl)5 t
may be omitted from the problem of the nucleolus of T',") (see Remark 3.3). The
collection fb ',* is thus nucleo-sufficient in T',"'. That implies that the nuclei problems
in the games r',")
and TC have the same solution.
THEOREM
4.8. Let T = ( N ; v) be a monotonic game and let Tc = (C; %), be a
simple committee-game of I-. If' v is the nucleolus of' r and v(C) # 0, then BCv is the
nucleolus qf' r,.
Proof: The nucleolus belongs to the kernel. In a simple game with veto players
the nucleolus is the unique point in the kernel [3, Thm. 4.11. Thus, if there are veto
players in T,, then our theorem follows from the compounding theorem with
respect to the kernel (see [5, Thm. 6.11).
Let us assume that T, is free of veto players. Let vC denote the nucleolus of T,. ;
it is the nucleolus of Tv) too (Lemma 4.7). Let .uc = B,v and suppose, per
absurdum, that 's # vC. Let
Hp'(xc) = (ep)(T1, x'), . . . , ey)(~,~'I,xC)).
(4.26)
Let i, be defined by
(4.27)
e?'(Sio, vC) < e?'(TT;, , x'),
Without loss of generality we assume that
(see Lemma 3.1). Define an imputation y by
For every B c C,
1
max (r(B U T, v ) : T c N'\C),
(4.31)
ep)(B,vC) =
(4.32)
1
e',"'(B, xC) = -max
v(C)
-
v(C)
{e(B U T, y): T c N\\C)
616
NIMROD MEGIDDO
Let R, ,R, c N'\C be coalitions such that
(4.34)
e(R2 U C , v)
-
max {e(T U C, v): T c N'\C).
If Sio$ I, we denote Sio U R, by S*, and if SioE W;, Sio U R2 is denoted by S*
For every R c N'\C and i, if Si E %, then
and if Si $ Wc, then
Particularly (see Definition 4.3 and (4.33)44.34)),
(4.37)
e(S*,y)
=
v(C) . ep)(Si,, vC) .
Therefore, for every i 2 i, and R c N \ C ,
(4.38)
e(S*, Y) 2 e(Si U R , Y).
Analogously, if IT;, $ $4, denote T* =
U R,. For every i 2 i, and R c N'\C,
(4.39)
e(T*, v)
=
To U
R , and if 17;,
E
#& denote T* = IT;,
v(C).~p'(T,,x~
2) ~ ( 7 U
; R,xC).
It follows from (4.27), (4.37) and (4.39) that
(4.40)
e(S*, y) < e(T*, v).
Also, (4.28H4.29) imply for every i < i, and R c N\C,
(4.41)
e(Si U R, y) = e(T U R, v).
It can be verified that (4.38)-(4.41) mean that 8(y) precedes Q(v) in the lexicographical order on R," in contradiction to our assumption that v is the nucleolus
of l-.
Example 4.9. The nucleolus oj'the sum of two simple games. Let ri = (Ni; W1),
i = l,2, be two monotonic simple games such that N , n N, = @. The sum
r, @ r, is defined to be the game I- = ( N ; W ) where N = N, U N, and
W = { S C N : S ~ N , E % ' ~ O ~ S ~ N , E % ' ~ ] . T ~ ~ ~ ~ O ~ U C ~ ~ , O ~ , = ( N ; W
where YV' = {S c N : S' n N, E -,W1 and S f l N, E I%.,)
was investigated and its
nucleolus was characterized in [4]. Let r = ( N ; YV) be the sum r = I-, @ T,.
We shall prove that for every x E X,(T),
(4.42)
max {e(S,x):S€
= max{e(S,x):S~
#"$.
Suppose, per absurdum, that for example,
max { e ( ~x):
, S E W 1 )> max {e(S, x):S E W-,}.
(4.43)
Thus,
B,(x) = max j e ( S , x ) : S ~W ) .
(4.44)
= m a x [ m a x ( e ( S , x ) : ~ N l ~ W 1 ) , m a x { e ( S , x ) :n
S N,E W 2 ) ]
(cont.)
n
NUCLEOLUSES OF COMPOUND SIMPLE GAMES
=
max {e(S, x ) : S E Y4").
If x ( N l ) # 0 let x' = B,,x and if x ( N l ) = 0 let x 1 be any point in X l ( I - , ) .Also,
let x 2 = B N 2 x(it follows from (4.43) that x ( N 2 ) # 0 ) . Regard xi, i = 1,2, as an
imputation in by means of adding zeros for the players who do not belong to N i .
Thus,
r
+
(4.45)
x = x(N1)x1 x(N,)x~.
There is e > 0 such that the imputation
satisfies (4.43) and, consequently, (4.44).Since for every y E X , ( T , ) ,
min { ~ ( S ) : S%E" } > 0
(4.47)
it follows that
in contradiction to our assumption that x E X l ( r ) . Thus, (4.42) is proved. Let
v', i = 1,2, denote the nucleolus of T i . According to Theorem 4.8 the nucleolus of
r has the form
where 0 5 a 5 I. It follows from (4.42) that
min { v l ( S ) : S s% '}
e
a = --
min
(4.50)
{v'(s):s
E%")
+ min { v 2 ( S ) : SE ~
1
-
-
2
)
~
Qi(vl)
This means that the computation of the nucleolus is equivalent to the computation
of the nucleoluses of the summands. The coefficient cr is a by-product of this
computation.
5. The nucleolus of a compound game. According to the preceding section the
nucleolus of a simple committee-game is the barycentric projection of the nucleolus
of the grand game on that committee. In a compound game with simple components the set of players, N , is a union of disjoint committees. Thus, the nucleolus
of the compound game is a convex combination of the nucleoluses of the component games (the nucleolus of a component game is changed to an imputation in the
grand game by adding zeros). This combination depends only on the two highest
levels of excesses in the components' nucleoluses. It is a solution of a lexicographical problem.
Let T be a monotonic compound game, T = T O I T , ,. . . , r,], where Ti
= ( N , ; q " ) , i = 1, . . . , m, are simple games over pairwise disjoint sets and'
T o = ( M ; u ) , M = { I , . . . , m } . Let videnote the nucleolus of T i , i = l , . . . , r n ,
and let v denote the nucleolus of r. According to Theorem 4.8 there are ai2 0,
618
NIMROD MEGIDDO
i = 1, . . . , m, such that
1
tli
=
u ( M ) = v ( N ) and
By the *-notation an imputation in a committee-game is changed to an imputation
in the grand game (by adding zeros). The problem is to compute the coefficients
a,, i = 1, . . . , m. For every component game Ti, i = 1, . . . , m, let us denote the
payoffs to the winning coalitions, in the nucleolus vi, by
The payoffs to the losing coalitions will be denoted by
0
(5.3)
For every T
c
(5.4)
< A(;) < . . . < ~
=
11 '
M denote
J ( T ) = { j = ( j , , . . . ,j , ) : ( V i ~T)(O 5 ji 2 k,)
( V i $ T)(O 5 ji 2 li)}.
For every T c M and ,j E J ( T ) let
BE X(~O)>
(5.5)
( i )
a(T:j)(p) =
u ( T )-
be an affine functional such that for every
x
ieT
w!'pi -
x i!)pi.
i$l'
ASSERTION
5.1. The combination a = ( a , , . . . , am)(see(5.1)) is the solution of'
the lexicogruphical problem with the functionals a(T;j)( T c M , j~ J ( T ) ) and the
polytope X(T,).
The proof follows from the fact that for every ,4 E X ( T O )the values u ' ~ : J ' ( / ~ )
are the excesses with respect to the imputation P , v l *
...
bmvm*.
The number of functionals in the above problem can be decreased considerably. First, let us denote for every T c M ,
+
+
ASSERTION
5.2. The set { ~ ( ~ ; T
j )c
: M , j E J , ( T ) } is suficient (in the sense
Dejinition 3.4) to the lexicographical problewl presented in Assertion 5.1.
Proof. For every T c M and j E J ( T ) denote
of
Let e,, k = 1, . . . , m, denote the m-tuple in which (e,)i = 6,; (Kronecker delta).
Since (0, e l , e,, . . . , em}is an affine basis of Rm it follows that the linear functional
b(T;j)is an affine combination of b(T;O)
and b(T:ek',
k = 1, . . . , m. For every k such
that j, = 0 the coefficient of b(T;'k)in this combination must be equal to zero. Thus,
is a linear combination of b(T:O)
for every T c M and j E J ( T ) the functional b(T;J)
and b(T:'k),k = 1 , . . . , m, j, # 0. Moreover, for every /3 E X(T,),
That implies that the set of functionals a(T:i)such that j E J , ( T ) suffices.
Remark 5.3. If there are veto players in T i ,then there is only one level of payoffs
to winning coalitions in the nucleolus of T i . Thus, k, = 0 , o$)= 1 and for every
NUCLEOLIJSES OF COMPOUND SIMPLE GAMES
619
j~ J , ( T ) (where i~ T), j i = 0. We shall show that it can also be assumed (i.e.,
J , ( T ) may be reduced furthermore) that for every i, if there are no veto players in
Ti and if i $ T then for e v e r y j J1(T),,ji
~
= 0.
We denote
J*(T) = { j E J , ( T ):For every k E T such that there are veto players
in T,,j, = 0, and for every k $ T such that there
(5.91
are no veto players in T,, j, = 0 ) .
ASSERTION
5.4. The set ( d T ; j )T: c M ,j E J*(T)) is suficient to the solution of'
the lexicographical problewl presented in Assertion 5.1.
Proyf It can be easily verified that at the first stage of the solution (see Remark
3.3) it is sufficient to use only the functionals of the form
To see that, note that
for every j E J ( T ) and /3 E X(T,),
Suppose k $ T c M and T, is a game with no veto players. Let p E X I . According
to Lemma 4.1 there exists T* c M such that k E T* and T* E 9 ( B ) (see (4.1)). Let
1 E N , be a player such that v'; = i?).
Since 1 is not a veto player, there is B E -IFk
such that 1 $ B and B E 9 ( v k ) (see the proof of Lemma 4.6). Clearly, vk(B)= (0;)and
may, therefore, be omitted at the
also vk(B U (1)) = (I):~). The functional
following stages. The last claim follows from the fact that for every P E X I ,
and b(T:'k)(see (5.7))is a linear combination of b'T*:"k),
b(T*:O'
and b(T;O)
(see Remark
(3.3).
To conclude, the combination cc which determines the nucleolus is the solution
of the following problem.
Problem 5.5. Let To = ( M ; u) be an m-player game. Let d = ( d l , . . . , dm)be
an n2-tuple of nonnegative integers and let oOand w 1 be two m-tuples such that
0 < w p < o , ! 5 1 , i = l;..,m.Forevery T c M a n d p ~ X ( r ~ ) l e t
For every k E T such that d, = 0 let
and for every k $ T such that d, # 0 let
By LITo, wO,o l , dl we denote the lexicographical problem with functionals f"T'
and g'T:k) (where T c M and either k E T and d, = 0, or k 6 T and d, # 0).
The results are summed in the following theorem.
THEOREM
5.6. Let T = To[Tl, . . . , Tm]be a monotonic compound game with
simple components (see (2.1)).Let vi be the nucleolus of' Ti and let di be the number of'
620
NIMROD MEGIDDO
veto players in Ti, i
1, . . . , m. Let
=
(5.15)
wo = min { vi(B):B E W'i),
i
=
1, . . . , m,
min {vi(B):B E %Q.i,
v'(B) > up),
i = 1, . . . , m, d i = O ,
(for i such that di # 0 set w! = 1)
(5.16)
w!
=
Under these conditions the nucleolus of' T is
where ci = ( a , , . . . , urn)is the solution oj'the problem LITO,o O ,w', dl (Problem 5.5).
Example 5.7. Let l- = M , [ M , @ M , , M , @ M , , M , [ M , , M , , M , ] ] ( M , is
the 3-person majority game) and let us compute the nucleolus of this 21-player
game. According to our theorem we find by symmetry considerations that the
nucleoluses of M , 63 M , , M , @ M , and M , [ M , , M , , M , ] are, respectively,
I
)
()
,6,6,6,6r6
and ( 14 , 19 , 91 , 4I , 19 , 91 , 51 , 9I , 91 ) .The minimal payoffs to
winning coalitions (in the nucleoluses in the games are, respectively, 5, $. The
lexicographical problem is solved in one stage and the solution is (+, $, f). Thus,
the nucleolus of l- is
. A, A,:,;,:,;
S,
Example 5.8. There are two generalizations of(2.1).L. S. Shapley (see [13, p. 401)
suggested
(5.19)
"(s)= 1 1 ( -
l)IR\TI~(T).
min {wi(S
n Ni):i
ER)
K c M T c K
and G. Owen (see [9]) defined
Our results do not hold for these generalizations. Let T = (N ; v) be a 3-player game
such that 412) = v(13) = $, v(123) = 1 and v(S) = 0 for any other S c (1,2,3).
The nucleolus of the generalized
The nucleolus of r consists of the point
6, b, i ) .
product r @ T (using either (5.19) or (5.20)) consists of the point (b, b, i,
Obviously, this point cannot be presented as
(i,4,a).
REFERENCES
[I] A. KOPELOWITZ,Computation of'the kernels of simple games and the nucleolus of n-penon game.s,
Res. Memo. 31, Research Program in Game Theory and Mathematical Economics, Dept.
of Mathematics, The Hebrew University of Jerusalem, Jerusalem, 1967.
[2] M. MASCHLER
AND B. PELEG,A characterization, existence proof and dimension bounds for the
kernel o f a game, Pacific J . Math., 18 (1966), pp. 289-328.
---, The structure ofthr kernel of u cooperatior game, this Journal, 15 (1967), pp. 569-604.
[3]
[4] N. MEGIDDO.
The kernel and the nzcdeolus qf'aproduct of simple games. Israel J . Math., 9 (1971).
pp. 210- 221.
NUCLEOLUSES OF COMPOUND SIMPLE GAMES
[5] ---,
62 1
Kernels of compoundgames with simple components, Pacific J. Math., to appear.
Tensor decomposition of cooperative games, Res. Memo. 71, Research Program in Game
Theory and Mathematical Economics. The Hebrew University of Jerusalem, Jerusalem,
1972.
Nucleolusesofcompoundsimplegames.I : Thenucleolusof thesun, Res. Memo. 76, Research
[q ,
Program in Game Theory and Mathematical Economics, The Hebrew University of Jerusalem, Jerusalem, 1972.
Nucleoluses of compound simple jiumes. II: General compounds with simple components,
[8]
Res. Memo. 77, Research Program in Game Theory and Mathematical Economics, The
Hebrew University of Jerusalem, Jerusalem, 1972.
[9] G. OWEN,The tensor composition ofnon-negative games, Advances in Game Theory, M. Dresher,
L. S. Shapley and A. W. Tucker, eds., Annals of Mathematics Studies, No. 52, Princeton
University Press. Princeton, 1964, pp. 307-327.
The nucleolus of a characteristic,function game, this Journal, 17 (1969), pp. 1 163[lo] D. SCHMEIDLER,
1170.
Simplegames: An outline ofthe descriptive theory, Behavioral Sci., 7 (1962), pp. 59[I I] L. S. SHAPLEY,
66.
[I?]
C'ompound simple p t n r s . I : Solutions ofsums andproducts. RM-3192. The R A N D Corporation, Santa Monica. Calif.. 1962.
[I 31 -,
Compound simple games. 11: Some general composition theorems, RM-3643, The R A N D
Corporation, Santa Monica, Calif., 1963.
, Solutions of compoundsimplegames, Advances in Game Theory, M. Dresher, L. S. Shapley
~ 1 4 1and A. W. Tucker, eds., Annals of Mathematics Studies, No. 52, Princeton University Press,
Princeton, 1964, pp. 267-305.
[15] ,
Compound simple games. 111: On committees, RM-5438-PR, The R A N D Corporation.
1967 (also in New Methods of Thought and Procedure, F. Zwycky and A. Wilson, eds.,
Springer, New York, 1968).
[q
----,
.