Kernels of compound games with simple components

PACIFIC JOURNAL OF MATHEMATICS
Vol. 50, No. 2, 1974
KERNELS OF COMPOUND GAMES WITH SIMPLE
COMPONENTS
The kernel is a solution concept for a cooperative game.
It reflects symmetry properties of the characteristic function
and desirability relations over the set of the players. Given
m games over disjoint sets of players and a n m-person game,one defines a compound game over the union of the m disjoint
sets. These m games are the components and the above rnperson game is called the quotient. The quotient may be
treated as a game played by representatives of the component
games.
The kernel of the compound game is characterized fully.
The compound kernel is, in fact, a composition of the components' kernels by means of a distinguished subset of the
imputation space of the quotient game. This subset depends
also on the number of veto players in each component.
An effective formula for the compound kernel is given for
compound simple games. This formula enables short cuts in
the computations leading to the kernel of a decomposable
game. The results are applied to compound majority games
and a complete description of their kernels is given.
The kernel of a characteristic function game
was defined by M. Davis and M. Maschler in [2] and i t is related to
the theory of bargaining sets. M. Maschler and B. Peleg ([4, 51)
presented many interesting properties of the kernel. The kernel reflects
strength relations between players and symmetry properties of the
characteristic function.
Compound simple games were defined by L. S. Shapley in [ll].
I n this paper we deal with compound games which are not necessarily
simple, but their components are simple (see [13; p. 291). The decomposability of games was investigated by Shapley in [IS] and by the
present author in [ 7 ] .
This paper aims a t describing the kernel of a compound game in
terms of the quotient game and the kernels of the components. In
fact, we introduce a subset of the imputations space of the quotient
game which determines the structure of the kernel of the compound
game. The kernels of the components are composed according to a
formula which depends on that subset and generate the compound
kernel. The formula is shown to be effective for computation and i t
can be simplified when the quotient game is also simple.
L. S. Shapley ( [ U , 13, 141) and G . Owen ([9]) proved that vonNeumann-Morgenstern solutions of the component games compose in
1. Introduction.
532
NIMROD MEGIDDO
a natural manner which results in a solution of the compound game.
B. Peleg gave a characterization of the kernel of another kind of
composition for games ( [ l o ] ) . The nucleolus of a compound game was
characterized in [ 8 ] . The kernel of a product of simple games was
characterized in [ 6 ] . This paper generalizes the results of [6] with
respect to the kernel.
2. Preliminaries. A characteristic function game is a pair r =
(N; v), where N is a nonempty finite set ( N = {I,..., n ) ) and v is a
real-valued function defined over the subsets of N. The elements of
N are the players and the subsets of N are the coalitions.
If for every coalition S either v(S) = 0 or v(S) = 1 then we call
the game a simple game. Those coalitions that have a unit value are
called winning coalitions. The set of the winning coalitions is denoted
by W and the game is represented also by (N,W ) . We always
assume 0 4: 7 and N E %
A game is said to be monotonic if for every pair of coalitions S, T.
A 1-normalized game is a game ( N ; v) such that
A 1-0-normalized game is a 1-normalized game ( N ; v ) such that
We assume that always
A player i E N is called dummy if for every coalition S
Notice that if i is a dummy then according to (2.4)
A player i in a simple game ?
, = (N; W ) is called veto player if i E S
for every S E 2Z
= (Ni;
7Ki),
A compound game is defined as follows. Let r%
i = 1, ., m, be m simple games over disjoint sets of players. Let
T o= ( M ; u ) be an m-player characteristic function game (M = (1,
,
m}). The compound game r = r,[rl,
. . ., rm]
is defined over the set
N = Nl U
U Nm and its characteristic function v is defined by
.-
..
..
KERNELS O F COMPOUND GAMES WITH SIMPLE COMPONENTS
533
.
quotient and TI, . ., r, are the components. Thus, a coalition in the compound game has the value (in the quotient) of the
set of those components in which i t has enough players to form a
winning coalition (in that game). The concept of a compound game
contains as particular cases the product and the sum of simple games.
The product of two simple games r , , rzis defined by
r, is the
and their sum is defined by
(2.9)
rle r2= B; [ r l , r21
where B, and B; are defined by
An imputation in an n-player game
real numbers x = (x,, . . ., x,) such that
r = ( N ; v)
in an n-tuple of
and
The set of the imputations is denoted by Z ( r ) . A pseudo-imputation
is an n-tuple of nonnegative numbers x = (x,, . ., x,) that satisfies
(2.13). A weak imputation is defined by (2.12) and
The set of the weak imputations will be denoted by g ( r ) .
coalition S we denote
For every
and call e(S, x) the excess of S with respect to x. The maximum
surplus of a player i against another player j with respect to x is
defined by
(2.17)
sij(x) = Max {e(S, x): S c N, i E S, j 4: S ) .
The kernel (for the grand coalition) of a game r = ( N ; v) is defined
to be the set Z ( r )of all the imputations x E Z(r)such that for
every pair of distinct players i, j E N, xj > v({j}) implies
534
NIMROD MEGIDDO
Equivalently, x belongs to the kernel of the game if and only if for
every pair of distinct players i, j
The kernel is nonempty whenever E(r)
is nonempty (see [2]) and for
monotonic games in 1-0-normalization (2.19) may be changed to
(see [5; Corollary 3.91). The pseudo-kernel1 of a game is the set of all
the pseudo-imputations x such that for every pair of distinct players
Let a transformation T from ETinto ETbe defined by
Tx
=
Ax
+b
+6
(c, x)
where A is a linear transformation of E' into itself, b and c are
r-dimensional vectors and 6 is a real number. We assume that if c
is the zero vector then 6 # 0. Any transformation of this type will
be called a projective transformation of ET. Note that it is not defined
6 = 0); this set may be empty though.
for x in N(T) = {y: (c, y)
Convexity is preserved by projective transformations, i.e., if T i s a
projective transformation of ETand if P c ETis such that T is defined
for every x i n conv P then
+
T(conv P)
(2.23)
=
conv T(P)
.
An s-variable transformation T from Xi=, El ( E l = E T ,i = 1, . . -,S)
into ETis called a multi-projective transformation if for every i, i = 1,
. . ., S, and fixed x', . . ., %<-I , xi-' , . . , xs in Er the transformation
Ti:E' ETdefined by
4
is a projective transformation of E'. If Pic E:, i = 1, . . ., s, are sets
such that the multi-projective transformation T is defined for every
(xl, . ., x8)E conv PI x . . x conv P, then
(2.25)
T(conv PI x
3. Basic lemmas.
(3-1)
.. x
conv P,)
=
conv T(P, x
. . x P,).
We assume that for every player i E N in ( N ; v)
v({i}) = 0
.
A11 the statements in this paper hold for the pseudo-kernel of a game which is not
necessarily 1-0-normalized. We do not use explicitly the normalization assumption. The
reader is referred to [5; p. 5731 for a clearification of this point.
KERNELS OF COMPOUND GAMES WITH SIMPLE COMPONENTS
535
Notice that if i e Nk is a player who do not satisfy (3.1) in the compound game then {i}€ T kand therefore either the kernel of rkis
empty, or it consists of a unique point where i gets a unit payoff
and the other players in rk get zero. O u r compound games are
assumed to be monotonic and dummy-free. We also assume that for
every component game rk= ( N k ;T k ) , k = 1, ., m, Nk e T kand
0 4 T k .It is left to the reader to verify that our assumptions imply
that the component games are also monotonic and dummy-free.
.
LEMMA
3.1.
Denote
Let 7C be the kernel of a simple game
r = ( N ;W ) .
.
p(x) = min { x ( S ) :S e V ) ( x e Z(I'))
(3.2)
There exist convex polyhedra K,, . ., KT such that X = UL, Ki a n d
such that p(x) i s linear in each Ki, i = 1,
r.
. . a ,
Proof. x ( r )is a finite union of convex polyhedra (see [I; Q 31).
The required polyhedra are the nonempty intersections of the form
Pi n H, where
(3.3)
Hs = { x e En:x ( S ) 2 x ( T ) for every T E W } ( S E. gr)
and Piare the polyhedra assured by 111.
For every player i and x e 2 ( r )let us denote
(3.4)
gi(x) = Max {e(S, x): i E S c N }
(3.5)
hi(x) = Max {e(S, x): i 4S c N }
.
LEMMA
3.2. Let I' = (N;v) be a monotonic game satisfying (3.1).
I f x e Z ( r ) t h e n f o r every i e N
( a n d therefore gi(x) = s(x) = Max {e(S, x): S C N ) - see (3.4)-(3.5)).
Proof.
( xE
Since for every pair of distinct players i, j s J x ) = sji(x)
X(r)),it follows that
gi(x) = Max {e(S, x): i E S c N }
= Max [Max {e(S, x): i E S 5 N } , 0]
= Max [Max {sii(x):j E N, j # i),0]
= Max [Max {sji(x):j e N, j f i),01
= Max [Max e(S, x): i 4 S, 0 f S c N ) , 0]
= Max {e(S, x): i g S c N }
= hi(x)
.
NIMROD MEGIDDO
536
If i, j are two distinct players in ( N ; v ) we denote
(3-8)
Z j= { S C N ~ E Sj @
, S)
and if the game is simple, (N; Y T ) , denote
xj=wnxj.
(3.9)
Also,
(3.10)
aij(x)= Max {e(S, x): i 4 S f j
(3.11)
b,,(x)
=
Max {e(S, x): i E S f j
e S, 0 # S c N }
E S,
( x E $(r))
S c N ) ( x E g(r))
.
Given an imputation x E Z ( r )in a compound game
(see (2.7))
denote by p a weak imputation in
r = (N; v)
we
where
Ft$,
sit(x), g:(x),
We will write ek(S,x), sk(x)(see Lemma 3.2), Yi;,
h:(x), aFj(x),b&(x),where these expressions refer to the game rk,k = 0 ,
1, -,m. Note that
LEMMA3.4. Let r = (N;v ) be a compound game, let x E Z(r)
and let ifj E N k be two distinct players belonging to the same component
k = 1, --.,m.
game rk,
( i ) If j i s not a veto player in rkthen
(3.15)
+ sikj(x) - sk(x),hi@) - xi] .
sij(x) = Max [gi(p)
( i i ) If j i s a veto player in
r, then
Proof. ( i ) If j is not a veto players in rkthen there exists a
coalition S E W ksuch that j 4 S . Thus, S U {i)E 2P3. Considering
the compound game, we find that
(3.17)
sij(x) = Max {e(S, x): S E Z j }
= Max [Max {e(S, x): S E Sj,
S n N k E W k ,}
Max {e(S, x): S E A,,
S fl N k 4 Wk)l
= Max [Max { u ( T )- p(T\{k)): k E c M } - min { x ( S ) :S
Ti;}
E
9
Max { u ( T )- p ( T ) : k 4 T c M ) - xi]
= Max [Max {eO(T,
p): k E T c M ) + p k - m i n { x ( S ) : S E
Max {eO(T,p): k 4 T c M ) - xi]
= Max [gO,(p)f s$(x) - sk(x),
- xi] .
vi?}
,
KERNELS O F COMPOUND GAMES WITH SIMPLE COMPONENTS
( i i ) If j is a veto player in
(3.18)
r, then
7YiS=
(a
537
and
sii(x) = Max {e(S,x): S E Z j ,S n N, @ W k )
= Max {eO(T,p): k @ T c M } - xi
= hi@) - xi .
LEMMA3.5. Let r = (N;v ) be a compound game, let x E Z ( r )
and let i E N,, j E N, be two players belonging to distinct component
games r,, r,,1 2 k < 1 5 m.
( i ) I f j i s not a veto player in r, then
( i i ) I f j i s a veto player in
r, then
The proof is similar to that of Lemma 3.4.
LEMMA
3.6. Let r = (N;v ) be a compound game and let x E Z ( r ) .
For every k , k = 1, . ., m,
Proof. Assume that p,[x] = 0 and let S o E W ksuch that x(So)= 0.
Clearly, for all i, j such that S oE
stj(x) = 1. Hence
xj
Assume that x ( N k ) > 0 and let j~ N, such that x j > 0. j @ So and
therefore j is not a veto player. Let i E So. According to Lemma 3.4,
+
(3.23)
sij(x) = Max [gO,(p) $(x)
= Max [ g ; ( ~ ) h, u ) ]
= sO(p).
-
sk(x),
-
xi]
On the other hand,
It follows that sij(x) > sji(x) in contradiction to our assumption that
x E X((r).The other direction of (3.21) is immediate.
NIMROD MEGIDDO
538
Let r = (N;v ) be a compound
Z(r). F o r every k, k = 1, ., m,
LEMMA3.7.
x
E
Proof.
..
game a n d
let
If pk = 0 then for every T c M
= eO(T,p)
.
It follows that
gOk(~)= so@) = 4%)
.
(3.27)
Suppose pk
>0
and let i E Nk such that xi
>0
and
g f ( x ) = sk(x) .
(3.28)
Thus,
(3.29)
gi(x) = Max [g",(El, h",(El
If i is not a veto player in
(3.30)
-
xi]
.
rkthen
+
hi(%)= Max [ g " , ~ ) h:(x) - sk(x),hOk(~l)I
In this case it follows from Lemma 3.2 and (3.29)-(3.30) that
and this is equivalent to (3.25). If i is a veto player then
(3.32)
hdx) = h",~)
In this case (3.31) follows from Lemma 3.2, (3.29), and (3.32).
REMARK3.8. If i is a veto player in
Lemma 3.2, (3.29), and (3.32) that
r, then
it follows from
4. On the kernel of a component game. The barycentric projection of an imputation x E E(r)
on a coalition S such that x ( S ) > 0
will be denoted (see [13;p. 61) by B,x and defined to be an I S I-tuple
B,x = [(B,x),],, ,where for every i E S
(4.1)
Xi
(B,X)~
=-
x(S) '
Notice that if r is a compound game and r, = (N,; rk)
is a component game of r then B N k x is a pseudo-imputation in
or even an
imputation if (3.1) is satisfied in rk.
rk
KERNELS O F COMPOUND GAMES WITH SIMPLE COMPONENTS
539
THEOREM
4.1. Let r = (N;v) be a compound game a n d let x E S ( r )
be a n imputation such that for every k, k = 1, ., m,
Under these conditions, if x(Nk) > 0 a n d
players then
rkis
a game with veto
if a n d only if for every pair of distinct players i, j
E
N,
Proof. The kernel of a simple game with veto players consists
of a unique point in which the veto players share equally while the
others get zero ( [ 5 ; Theorem 4.11).
( a ) Suppose B,,x € x ( r k ) and let i, j be two distinct players
If both of them are veto players then (see Lemma 3.4)
in .
and since xi = xj i t follows that sij(x) = sji(x). If j is a veto player
but i is not, then (notice that s$(x) = sk(x) since all the winning
coalitions in r, have the same excess 1 - x(Nk))
According to (4.5) (it holds when i is not a veto player) and the fact
that xi = 0, i t follows that
Considering (4.2) i t follows that sij(x) 5 sji(x). If j is not a veto player
(4.4) follows from the fact that xj = 0.
( b ) Suppose (4.4) is true for every pair of distinct players i, j.
(4.5)-(4.6) hold for every pair of veto players. According to (4.4)
xi = xj. Suppose, per absurdum, that there is j E Nk, who is not a
veto player, such that xj > 0. Let i be a veto player in r,. (4.4)
implies sij(x) 5 sji(x). Thus, according to Lemma 3.4 and (4.2)
and hence
NIMROD MEGIDDO
540
This means that j belongs to every winning coalition having a maximal
excess ((4.10) holds for each veto player i). Thus, a coalition S that
has a maximal excess contains all the veto players and all the other
players of positive payoff. Therefore,
I t follows that all the winning coalitions have the same excess in
contradiction t o (4.10). This contradiction proves t h a t each player j
who is not a veto player gets zero and therefore BNkxbelongs to the
kernel.
THEOREM4.2. Let r = (N, v) be a compound game and let
x E Z(r)be a n imputation satisfying (4.2). Under these conditions,
if rkis free of veto players and x(Nk) > 0 then
if a n d only if for every p a i r of distinct players i, j~ Nk
Proof.
Let i, j be any two distinct players in
rkand
denote
It follows from (4.2) (note that s(x) = sO(p))that
Using Lemma 3.4 we find that
(4.18)
+
s&) = Max [g0,(p) stj(x) - sk(x), hi@) - xi]
= &(p) - sk(x) Max [sikj(x), sk(x) - A - xi]
and it follows that
(4.19)
sij(x) = sji(x)
-
+
h
Max [sFj(0), sk(2) - A = Max [s;$(0), sk(2) - 2 - Zj]
.
Suppose (4.13) is satisfied for every pair of distinct players i, j
We will show that for every j E Nk ( j is not a veto player)
E Nk.
KERNELS OF COMPOUND GAMES WITH SIMPLE COMPONENTS
Indeed, if h5(2)
< g:,(2)
541
then there exists Sosuch that j E Soand
Let i e N,\So ((4.21) implies ek(So,2) > 0 and therefore So+ N,).
Clearly,
Since
(4.23)
Max [stj($), sk(2)-
-
= Max [sii(2), sk(3) -
2 - Zj]
it follows that
The last equality is true for every i 4 So so that x(So) = 1 in contradiction to (4.21). Thus, (4.20) is proved. Let Soc N, be a coalition
such that j @ Soand
Since for every i E N, (i
#
j)
ek(Sou {i), 3) 2 ek(So,2) - Zi = sk(9)- zi
(4.26)
it follows that
Analogously,
It follows from (4.17), (4.19), and (4.27)-(4.28) that
C
and hence x E X ( r , ) . On the other hand, if 2 E X ( r , ) then (4.29) is
satisfied by every pair of distinct players i, j E N,. Lemma 3.2 implies
h5(2) = sk(2). Hence, there is Soc N, such that j @ So and sk(9)=
ek(S,, 2) = hjk(2). Thus,
(4.30)
sikj(2) 1 ek(SoU {i}, 2) 1 ek(So,2)
-
Zi
=
sk(2)- 2i
.
In a similar way we can show that (4.28) holds. (4.13) follows from
(4.17), (4.19), (4.28), and (4.30).
5. The dependence on the quotient game. In the preceding
section we proved that the barycentric projection of a point in the
compound kernel on any component must belong to the kernel of that
component (or to the pseudo-kernel if (3.1) is not satisfied in the com-
NIMROD MEGIDDO
542
ponent game). Moreover, if the barycentric projection of an imputation
in the compound game is in the kernel of the component then the
imputation must satisfy the kernel condition ((2.21)) for every pair of
distinct players in that component. To complete the characterization
of the kernel of the compound game we have to show how the components' kernels should be composed in order to obtain the compound
kernel.
The compound kernel depends on the quotient game by means of
a subset of its imputations space which is defined as follows.
DEFINITION5.1. Let r = ( M ; u) be a monotonic m-player game.
Let w = (w,, . ., w,) be a n m-tuple of nonnegative numbers. The
[weak] w-equalizing set [ g w ( r ) ] 9 " ( r ) of I' is defined to be the set of
all the [weak] imputations [y E &(r)] y E S ( r ) that satisfy the following three conditions:
( i ) For each i, i = 1,
m,
...,
.
(54
gdy) = S(Y)
( i i ) F o r every pair of distinct players i, j e M, if wi = 0 and
wj > 0 then
(iii) F o r every pair of distinct players i, j e M, if both wi
a n d wj > 0 then
>0
REMARK
5.2. The w-equalizing set for a monotonic game r = (N; v)
satisfying (3.1) is a generalization of the kernel. In fact
REMARK
5.3. 9w(I')[~w(r)] is a finite union of convex polytopes.
The number of linear inequalities which determine the w-equalizing
set is of the same order of magnitude of that number in the kernel.
When most of the wi-s are zeroes this number is smaller than the
respective number in the kernel. The computation of g W ( r
can
) be
carried out according to [I]. We conjecture that an algorithm based
on the "profile" idea can be built for e W ( r )(see [3, 41).
The w-equalizing set of a simple game is sufficient for determining
the weak w-equalizing set of that game:
LEMMA5.4.
If
r = ( M ; 2 2 ) is a monotonic simple game without
n
KERNELS O F COMPOUND GAMES WITH SIMPLE COMPONENTS
543
veto players t h e n
gw(r)
= {CYX
x :E L P ~ ( ~o )s, a 5 1) .
N
(5.5)
Proof. For every pair of distinct players i, j E M 2Yijf 0 . Hence
for every x E $(r)
(5.6)
sij(x) = Max {e(S, x): S E Sij}
= 1 - min { x ( S ) :S E S i j }
.
Similarly,
(5.7)
g,(x) = 1 - min { x ( S ) :i E S
(5.8)
s(x) = 1 - min { x ( S ) :S
Also, if there is S
(5.9)
E
E
%)
E %}
.
22 such that i, j B: S then
aij(x) = 1 - min { x ( S ) :i, j B: S E 22)
and otherwise
(5.10)
aij(x) = ~ ( x. )
An imputation x E S ( r )satisfies the conditions of Definition 5.1 if
and only if every multiplication of x by a satisfies them. This proves
(5.5).
EXAMPLE
5.5. Let M3 denote the 3-player majority game2. The
(0, 0, 0)-equalizing set for M3 and L P ( ' . ~ ~ ~ ' (are
M ~ as
) illustrated.
) Z ( M 3 )= {(1/3,113, 113)).
If w,, w,, w,> 0 then g W ( M 3 =
The w-equalizing set will be now used to characterize the dependence of the compound kernel of the quotient game.
LEMMA5.6. Let r = (N;v) be a monotonic compound game
satisfying3 (3.1). Let xk E Z ( r k a)n d let a,, k = 1, . ., m, be n o n M3 is a &player simple game in which a coalition wins if and only if i t consists of
a t least two players.
If (3.1) is not satisfied by the compound game or by a component then our claims
remain correct provided the "kernel" is replaced by the "pseudo-kernel".
NIMROD MEGIDDO
544
negative numbers such that C;1"=,
a k = u(M) = v(N). Let xk*e Z ( r )
where x:* = x: for i e Nk and x? = 0 otherwise. Let w, denote the
akxk*. Under these connumber of veto players i n r,. Let x = C;1"=,
ditions
Proof.
..-,m)
According to Lemma 3.2, for each player i E Nk (k
=
1,
( a ) If x E Z ( r ) then Lemma 3.7 implies condition (i) (see Definition 5.1).
( b ) We prove the necessity of condition (ii). Assume that w,= 0
and w, > 0, 1 5 k < 1 5 m. Let i e N, and let j E N, be a veto player
in .
Since xkE Z ( r k ) and x1E Z ( r , ) , it follows from (5.12) and
Lemma 3.5 that
and
Note that (5.13)-(5.14) hold even if x e Z ( r ) and (5.14) is independent
of j being a veto player. If x E Z ( T ) i t follows from condition (i)
(we have proved its necessity) and (5.14) that
Suppose x(Nk) = 0.
For every T c M
(see (3.26)). Thus, taking the maximum over the coalitions T such
that k, 1 @ T,
It follows from (5.13) and (5.17) that
Since sij(x) = sii(x) condition (ii) follows from (5.15) and (5.18). Assume
KERNELS O F COMPOUND GAMES WITH SIMPLE COMPONENTS
545
x(Nk) > 0. Choose i e Nk so that xi > 0. Thus,
Since sii(x) = sji(x) it follows from (5.13) and (5.15) that
and condition (ii) follows from (5.19)-(5.20).
( c) We prove the necessity of condition (iii). Assume wk, w, > 0
( I 5 k < 1 5 m) and let i e Nk and j e N, be veto players in their
component games. According to [5; Theorem 4.11
Lemma 3.5 and (5.12) imply
and, symmetrically,
The last two equalities are independent of x belonging to the kernel.
If x E Z ( r ) then sij(x) = sji(x) and condition (iii) follows from (5.22)(5.23).
( d ) Assume that ~ [ xE] "(To) and let us prove that x e Z ( r ) .
Condition (i), together with Theorems 4.1-4.2, imply for every pair of
distinct players i, j G N, (k = 1, . m)
5
a ,
Let i E Nk and j e N, (1 k < I 5 m). If i and j are veto players in
their components then (5.22)-(5.23) hold and condition (iii) implies
sij(x) = sji(x). If j is a veto player and i is not a veto player then
(5.13)-(5.14) hold and conditions (i) and (ii) imply sij(x) = sji(x) = sO(p).
If both i and j are not veto players then (5.14) and the symmetric
equality,
imply, according to condition (i), that sij(x) = sji(x) = sO(p). Thus, (5.24)
holds for all the pairs of distinct players i, j e N. Hence x E X ( r ) .
6. The kernel of the compound game. The results of the
preceding sections lead to the main theorem of this article, a theorem
NIMROD MEGIDDO
546
that determines the structure of the kernel of a compound game. This
theorem, which is interesting in itself, enables shortcuts in the computations leading to the kernel of a decomposable game.
.
THEOREM
6.1. L e t r = I',[r,,
., r,] be a monotonic d u m m y free compound game w i t h simple component games TI, . , r,. A s s u m e
that every component that consists of more t h a n one player i s in
1-0-normalization4 (NkE 7Tkand for i E Nk {i}4. W k ) . Let wk denote
Under these
the n u m b e r of veto players in rkand w = (w,, ., w,).
conditions x E SY ( r ) belongs to the kernel, X ( T ) , i f and o n l y i f for
every k , k = 1, ., m, such that x(Nk)> 0 B,,x E c X ( r k ) a n d the weak
i m p u t a t i o n p[x] belongs to the weak w-equalizing set, 2 " ( r 0 ) , of the
quotient game To.
.
.
Proof. ( a ) Suppose x E X ( r ) . Lemma 3.7 assures that the
conditions of Theorems 4.1-4.2 are satisfied. From these theorems it
follows that for every k such that x(Nk) > 0 B XE X ) . Since for
every x e Z ( r )
(for the *-notation refer to Lemma 5.6; if x(Nk) = 0 for a certain k
we define BNkxto be any point in Z ( r k ) - a n y h o w it is multiplied by
zero) it follows from Lemma 5.6 that p[x] E +"(To).
( b ) Suppose x E Z ( r ) is an imputation satisfying our conditions.
Lemma 5.6 implies that x E 3if(r).
COROLLARY
6.2.
Under the conditions of Theorem 6.1
Proof. Suppose x E X ( r ) . For every k E M such that x(Nk)> 0
let xk = BNkxand let = p[x]. For k E M such that x(Nk) = 0 let xk
be any point in the kernel z ( r k ) . According to Theorem 6.1
xke Z f ( r k ) for every k E M and ,i2 E +(r0).
The minimum payoff to
a winning coalition is positive for every point in the kernel of a simple
game (see 16; Lemma 3.71). Thus, pk[xk*]> 0 and
.
-
The normalization assumption may be dropped and the theorem is true for the
pseudo-kernel instead of the kernel (see Lemma 5.6).
KERNELS OF COMPOUND GAMES WITH SIMPLE COMPONENTS
547
According to (6.1)
and that proves that Z ( r )is obtained in the right-hand side of
(6.2). Let x belong to the right-hand side of (6.2). Thus, x E S ( r )
and there exist xkE X ( r k ) , k = 1,
m, and ,G E ~ W ( P ,such
)
that
(6.4) is satisfied. Necessarily, for every k such that x(Nk) > 0 xk =
B,,x and for all the k E M
.
- 0 ,
and hence p[x] E Gw(I',).
Theorem 6.1 implies x E 3?(r).
Corollary 6.2 shows how the kernel of the compound game is
obtained from the kernels of the components and the weak w-equalizing set for the quotient game. The next theorem shows how the
kernel is obtained if we are restricted to vertices of certain polyhedra
generating the components' kernels and to the vertices of the weak
w-equalizing set.
THEOREM6.3. Assume the conditions of Theorem 6.1. Let
m,
m, where Kjk, j = 1, -..,sk,k = 1,
Z r ( r k ) = U%kl
Kjk, k = 1,
are ,convex polyhedra i n which pk[x] is a linear function of x (see
Lemma 3.1). Let s w ( r o )= Ug"=,
Kj where K:, j = 1, . . , so, are convex
polyhedra. Under these conditions
. . a ,
p E vert K:o,x' E vert K;;,
Proof.
by
Define a mapping V :
i = 1,
5"(To)x =(TI)
x
. . ., mi .
. .x
3T(r,)
--t
E"
According to Corollary 6.2
If 15 jk 5 sk, k = 0, 1, - - -,m, then the restriction of ?F to the set
K,", x Kll x . . x Kj", is defined everywhere and i t is a multi-projective
NIMROD MEGIDDO
548
.
transformation since p,[xk*] is linear in K&, k = 1, . -,m. Thus, Y
is convexity-preserving in this domain (see (2.25)) and therefore,
YIK,Oox
(6.9)
-. x K c ] = conv Y[vert Kj0 x . . . x vert Krm]
= conv {Y(P, xl,
-,xm):9 E vert K,Oo,
x i e v e r t Kji, i = 1,
m) .
To complete the proof of the present theorem, notice that
In case To is a simple game without veto players the kernel of
the compound game can be presented using 9 " ( r 0 ) instead of 2 " ( r 0 ) .
This will be done by an appropriate modification in the definition of
the mapping V. Moreover, in this case the intersction with Z(r)
can be omitted.
THEOREM6.4. Under the conditions of Theorem 6.1, assume that
, s,
To i s a simple game without veto players. L e t Kjk, j = 1,
k = 1, ., m, be a s in Theorem 6.3. Let 9"(To) = UitlKO
j where KjO,
j = 1, . ., so, are convex polyhedra. Under these conditions
..
zqr)
u .. u conv {c, Pk/~k[x~*]p*:
8 7n
80
=
j,=1
j,=1
(6.11)
9 E vert K;",
k=1
C
Pi/~i[x~*l
i=1
xi E vert Kji, 1 S i 5 m
1.
Proof. Since To is a simple game without veto players, it follows
from Lemma 5.4 that 9 E 3"(To) if and only if P/P(M) E .9"(To). It
follows that all the vertices of Sw(I',) except the origin are vertices
of T w ( r 0 ) . Anyhow, the origin contributes nothing to (6.6) so that
i t can be omitted from vert Kjo (see (6.6)) and we may write kFw(r,)
instead of 3 " ( T 0 ) . Moreover, instead of intersecting with Z ( r ) in the
right-hand side of (6.6), we can obtain exact imputations by normalization, i.e., by defining
REMARK6.5. If 1,
. ., 1 are
the veto players in To then either
KERNELS OF COMPOUND GAMES WITH SIMPLE COMPONENTS
549
(in case 1 = m), or
(in case 1 2 I < m) where h
r is a monotonic simple game without veto
players. The kernel of r ; [ r , + , , . ., r,] can be computed according to
Theorem 6.4. Given the kernels of the components, the kernel of the
product is very easy to compute (see [6; Theorem 3.11). The set of
vertices of a polyhedron in the kernel of a product is the union of sets
of vertices of polyhedra in the kernels of the components.
EXAMPLE
6.6. Let r, be a monotonic simple game in which all
the 3-player coalitions except {I, 2, 3) and {4, 5, 6) win. It is left to
the reader to verify that the kernel of r, is the line segment [(1/3,
113, 113, 0, 0, O), (0, 0, 0, 113, 113, 1/3)]. Denote
Thus,
(6.16)
p(xm)= min {xa(S):S E W }=
12 - a
2
-
if
-15 a S 1 .
2 -
p(2) is a linear function of 2 in K, [(1/3, 113, 113, 0, 0, O), (116, 116,
116, 116, 116, 1/6)] and in Kz = [(O, 0, 0, 113, 113, 1/3), (116, 116, 116, 116,
1 6 1 / 6 1 Consider the kernel of the game r,,= r,@ r,. The quotient game is ({I, 2); {I}, {2), {I, 2)). There are no veto players in r,.
The (0,0)-equalizing set for the quotient game consists of a unique
point - (112, 112). A vertex of X ( r , , ) is a combination of vertices of
the polyhedra that generate Z ( r , ) . The combination is determined
by (6.12). For instance, if x' = (113, 113, 113, 0, 0, 0) and x2 = (116, 116,
116, 116, 116, 116) then, since, necessarily, ,i? = (112, 1/2), x = T(9, x', x" =
( I / , 5 5 0 0 0 1/15, 1/15 1/15, 1/15, 1/15 1/15) Because of the
symmetry, each imputation x in Z ( r , , ) can be represented by a
quadruple (al; a,; a,; a,) where a, = x, = x, = x,, a, = x, = x, = x, etc.
The kernel of r,,consists of the following four quadrangles, presented
by their vertices. (a) AEFO (b) BEHO (c) CGFO (d) DGHO, where
A = (116; 0; 116; O), B = (116; 0; 0; 1/6), C = (0; 116; 116; O), D = (0; 116;
0; 1/6), E = (115; 0; 1/15; 1/15), F = (1115; 1/15; 115; O), G = (0; 115;
1/15; 1/15), H = (1115; 1/15; 0; 1/5), and 0 = (1112; 1/12; 1/12; 1/12).
EXAMPLE
6.7. Let
be a kplayer monotonic simple game whose
minimal winning coalitions are (1, 31, (2, 31, {I,41, {2, 4).
is the
X(n)
NIMROD MEGIDDO
line segment [(1/2, 112, 0, O), (0, 0, 112, 1/2)] (notice that C ] = Bt @ B,*;
see (2.11)). The function p(x) is constant over X([7)
(p(x) = 112).
Consider the kernel of the 10-player game r = M,[n, M,, M,] (see
Example 5.5). X ( M 3 ) consists of the unique point (113, 113, 113).
9CO.O.O) (M,) was shown to consist of three line segments having a
KERNELS OF COMPOUND GAMES WITH SIMPLE COMPONENTS
551
common vertex. Let x1 = (112, 112, 0, 0) E X ( a ) , x2 = x3 = (113, 113,
113) and ,2 = (112, 0, 1/21E 9(0-0,0"(M,).It can be verified that Y(,2, x',
xq x3) = (2/7,2/7,0,0,0,0,0,1/7,1/7,1/7).
Running over all the possible
combinations we find that X ( r ) consists of the two quadrangles (a)
A B E F (b) C D E F and the triangle (c) GEF, where A = (217; 0; 117; O),
B = (0; 217; 117; O), C = 217; 0; 0; 1/7), D = (0; 217; 0; 1/7), E = (115; 0;
1/10; 1/10), F = (0; 115; 1/10; 1/10) and G = (0; 0; 116; 116).
7. Kernels of compound majority games. A majority game
is an n-player simple game M,,, in which a coalition wins if and only
if it consists of a t least k players. In this section we apply the results
of the preceding one to games of the form
where m = n o and 0
LEMMA7.1.
< k , < n,,
i
=
0, 1,
..., m.
Let x E S(M,,,) and denote
9= {S: (V T c N)(e(S, x) 2 e(T, x))) .
(7.2)
Under these conditions if S, T E 9 and i, j E (S U T)\(S n T) then
X, = Xj.
Proof.
Assume i E S\T and j E T\S. Thus,
and therefore
(7.4)
Similarly,
xj 5 x i .
(7.5)
If i, j E S \ T let I E T\S (if S I T then, clearly, xi = xj = 0) and according to what we have proved in (7.4) and (7.5) xi = x, = xi.
LEMMA^.^. L e t x a n d 9 b e a s i n L e m m a 7 . 1 .
Spthen xi = xj.
and i, j E U;=, SJ
n;=l
IfSl,...,S,~=9
Proof. ( a ) Assume that there is p, 15 p 5 r , such that i , j $ S,.
If there is q such that i, j E S, then i, j E (S, U S,)\(S, n S,) and we
can apply Lemma 7.1. If there is no such q let s be such that i E S,
and let t be such that j~ St and Lemma 7.1 can be applied again.
( b ) Suppose that for every p, p = 1, - - ., r, either i e S, or j e S,.
Let p be such that i G S, (and therefore j E S,) and let q be such that
NIMROD MEGIDDO
552
j @ S,.
Thus, i, j E (S, U S,)\(S,
LEMMA7.3.
S,,
n S,) and Lemma 7.1 can be applied.
If i E U;=, S,\
n;=,S,
..., S, are as i n the preceding
Proof.
(7.5).
n;,,
and j E
S, where x, 9,
Lemma, then xi L Xj.
Let T E 3 be such that i & T (clearly, j E T) and apply
REMARK
7.4. An imputation x E Z(Mn,,) belongs to 9(o~~...O)(M,,k)
if and only if Us,, S = N, where -9 i s defined by (7.2) (see Definition 5.1 condition (i)).
THEOREM7.5. Let x € Z ( M n , , ) . XE&PO(M~,,)if and only if
there is S c N such that IS1 = k - 1 and for every ZES and i, j @ S
Xi = X j 2 Xi.
Proof. ( a ) Assume that there is a coalition S as specified in the
theorem. In this case all the k-player coalitions T containing S have
the same payoff. Thus, this collection of coalitions is exactly 9 and
since it covers N it follows that x E &iP"'M,,k) (Remark 7.4).
,S.
( b ) Assume, conversely, that x E g0(M,,,). Let g =
According to Lemmas 7.2-7.3 and Remark 7.4, for every I E 3 and
..
The maximum excess is achieved in a k-player
2 , j @ S xi = xj 2 x,.
coalition. Since S is an intersection of a collection of k-player coalitions covering N (k < n) it follows that I I 5 k - l. Obviously, every
(k - 1)-player coalition containing satisfies the condition concerning
1, i, and j.
ns,
-
COROLLARY7.6. Denote by as ( S c N) an. imputation such that
a; = 111 S I for i E S and a: = 0 for i @ S. Then
(7.6)
90(Mn,,) =
U
conv {aT:T 3 S)
.
(*-?+1)
)
and denote by MS the set of all the
Proof. Let s E (% - +
imputations x such that for every I & S and i, j E S xi = xj 2 x,.
,, XTaT.
( a ) Let XT 2 0, T IS be such that C,,,xT = 1. Let x = C
Then
and therefore x E J&.
We have, thus, proved that MS3 conv {aT:
KERNELS OF COMPOUND GAMES WITH SIMPLE COMPONENTS
553
T 2 S}.
( b ) Let x E Ms. Without loss of generality assume that S =
{k, k + 1, -,n} and the players are arranged so that x, 5 x2 5 . I
xk-, 5 xk = . = x,. Since Cg, xi = 1 it follows that x, 5 11% and
for every i
.
..
..
Let T, = N and for every i, i = 1, ., k - 1, Ti+1= Ti\{i}. Let a, = nx,
and for every i , i = 2 ,
k - 1, a i = (n - i + l).(xi-xi-,).
Then
ai 2 0, i = 1,
k - 1, and
...,
. . a ,
Define a, = 1 - ZL' ai and y = Ct,criaTi. Also, for every j, j = 1,
., n , let j* = min (j,k). Then
.
, k} c
Hence, y = x. We have proved that x E conv {aTi:i = 1,
conv {aT:TI>S } . Thus, Ss= conv {aT:T 3 S } . According to Theorem
Ms (I N\S I = k - 1) and this completes the
7.5 9O(MmPk)
= USE
proof.
Let r be the game defined in (7.1). For every S c M (S + 0 )denote
by bS an imputation in r such that for every i E N, (1 = 1,. ., m)
.
THEOREM
7.7.
(7.11)
Let
r
x ( r )=
be the game defined i n (7.1).
Then
(J conv {bT: T 3 S } .
s~(m-i'~+l)
Proof. Because of the symmetry, X(M,,,) consists of a unique
point - (lln, . , 11%). The minimum payoff to a winning coalition
is therefore kjn. According to Corollary 7.8 9O(M,,,,,) is the union
of the polyhedra Ss(Sc M, I S I = rn - ko - 1) whose vertices are
aT,T 2 S. The combination of the components' kernels defined by
aT, T c M, (see (6.12)) is the imputation x E Z ( r ) where for every
i~ N, (1 = 1, . - - m)
,
NIMROD MEGIDDO
It follows from Theorem 6.4 that Z ( r )is the union of the polyhedra
Qs (Sc M, I S I = m - k , + 1) whose vertices are the bi"-s (T 3 S).
Acknowledgment. The author is indebted to Professor Michael
Maschler of the Hebrew University of Jerusalem for his helpful advices
and suggestions.
1. R. J. Aumann, B. Peleg, and D. Rabinowitz, A method for computing the kernel of
n-person games, Mathematics of Computation, 19 (1965), 531-551.
2. M. Davis and M. Maschler, T h e kernel of a cooperative game, Naval Research Logistics
Quarterly, 12 (1965), 223-259.
3. A. Kopelowitz, Computation of the kernels of simple games and of the nucleolus of
n-person games, Research Program in Game Theory and Mathematical Economics,
Research Memorandum No. 31, Department of Mathematics, The Hebrew University of
Jerusalem, Jerusalem, 1967.
4. M. Maschler and B. Peleg, A characterization, existelzce proof and dimension bounds
for the kernel of a game, Pacific J. Math., 18 (1966), 289-328.
The structure of the kernel of a cooperative game, SIAM J. Appl. Math.,
5. -,
15 (1967), 569-604.
6. N. Megiddo, The kernel and the nucleolus of a product of simple games, Israel J.
Math., 9 (1971), 210-221.
, Tensor decomposition, of cooperative games, Research Program in Game
7. Theory and Mathematical Economics, Research Memorandum No. 71, Department of
Mathematics, The Hebrew University of Jerusalem, Jerusalem, 1972. (To appear in SIAM
J. Appl. Math.)
Nucleoluses of compound simple games, SIAM J. Appl. Math., 26 (1974).
8. -,
9. G. Owen, T h e Tensor Composition of Nonnegative 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), 307-327.
10. B. Peleg, The kernel of the composition of characteristic function games, Israel
J. Math., 3 (1965), 127-138.
11. L. S. Shapley, Simple Games: A n Outline of the Descriptive Theory, Behavioral
Science, 7 (1962), 59-66 (also The RAND Corporation, P-2277, April, 11961).
, Compound Simple Games I : Solutions of S u m s and Products, The RAND
12. Corporation, RM-3192, June, 1962.
13. -,
Compound Simple Games 11: Some General Composition Theorems, The
RAND Corporation, RM-3643, July, 1963.
tions of Compound Simple Games, Advances in Game Theory, M.
14. -,Solu
Dresher,
L. S. Shapley, and A. W. Tucker, eds., Annals of Mathematics Studies, No. 52, Princeton
University Press, Princeton, (1964), 267-305.
KERNELS OF COMPOUND GAMES WITH SIMPLE COMPONENTS
555
15. , Compound Simple Games 111: On Committees, The RAND Corporation,
RM-5438-PR, October, 1967 (also in "New Methods of Thought and Procedure", ed. by
F. Zwycky and A. Wilson, Springer, New York, 1968).
Received September 28, 1972 and in revised form March 20, 1973.