Int. Journal of Game Theory, Vol. 8, Issue 3, page 133-164. Q Physica- Verlag, Vienna.

On Coalition Formation: A Game-Theoretical Approach 1 )

By P.P. Shenoy, Lawrence 2 )

Abstract: This paper deals with the question of coalition formation in n-person cooperative games.
Two abstract game models of coalition formation are proposed. We then study the core and the
dynamic solution of these abstract games. These models assume that there is a rule governing the
allocation of payoffs to each player in each coalition structure called a payoff solution concept.
The predictions of these models are characterized for the special case of games with side payments
using various .payoff solution concepts such as the individually rational payoffs, the core, the
Shapley value and the bargaining set Mti). Some modifications of these models are also discussed.

1. Introduction

The theory of n-person cooperative games is a mathematical theory of coalition

behavior. A fundamental problem posed in game theory is to determine what outcomes
are likely to occur if a game is played by "rational players". I.e. given an n-person co-
operative game, it is natural to inquire ( I ) what will be the final allocation of payoffs
to each of the players and (2) which of the possible coalitions can be expected to form.
These two aspects of coalition behavior are closely related. The final allocation o f pay-
offs to each of the players depend on the coalitions that finally form, and the coalitions
that finally form depend on the available payoffs to each player in each of these coali-
tions. Since the p u b l i c a t i o n i n 1944 of the monumental work Theory o f Games and
Economic Behavior by yon Neumann/Morgenstern [ 1944], most o f the research in
n-person game theory has been concerned explicitly with predicting players' p a y o f f
and only implicitly (if at all) with predicting which coalitions shall form. In this paper,
the primary emphasis is on the second aspect o f coalition behavior, namely the forma-
tion of coalitions. Two models of coalition formation are proposed based on the
theory of n-person games. As in most of game theory, our models are normative and
use only endogenous arguments, that is, only information contained in the characteris-
tic function is used.

1) This research was supported in part by the Office of Naval Research under Contract
N00014-75-C-0678 and the National Science Foundation under Grants MPS75-02024 and
MCS77-03984 at Cornell University and also by the United States Army under Contract
No. DAAG-29-75-C-0024 and the National Science Foundation under Grant No. MCS75-17385 A01
at the University of Wisconsin at Madison. The author is grateful to Professor William F. Lucas under
whose guidance the research was conducted and to Professor Louis J. Billera for many helpful dis-
cussions.
2) Prof. P.P. Shenoy, The School of Business, The University of Kansas, Lawrence, Kansas
66045, USA.
134 P.P. Shenoy

A brief review of abstract games and its solutions is presented in section 2. In Sec-
tion 3, two abstract game models of coalition formation are proposed. In one ap-
proach, payoff allocations and coalition structures are modeled as the outcomes of an
abstract game on which an appropriate domination relation is defined. In another ap-
proach, coalition structures alone are modeled as outcomes. In both cases, we study
the core and the dynamic solution of the abstract game. The two models are then
cempared. Section 4 deals with the representation of the models by means of digraphs.
In Section 5 - 8, the solutions of the abstract games are characterized for the special
case of games with side payments using various payoff solution concepts such as the
individually rational payoffs, the core, the Shapley value and the bargaining set M~i).
Finally in Section 9, we discuss possible modifications in the definition of the domina-
tion relation in the case where coalition structures alone are modeled as outcomes.

2. Abstract Games and their Solutions

An abstract game is a pair (X, dom) where X is an arbitrary set whose members are
called outcomes of the game, and dom is an arbitrary binary relation defined on X and
is called domination. An outcome x E X is said to be accessible from an outcome
y E X , denoted by x +-y ( o r y ~ x ) , if there exists outcomes Zo = x, zl . . . . . Zm. i,
z m = y , where m is a positive integer such that

x = z0 dom Z l dom z2 d o m . . , dom Zm.1 d o m z m = y . (2.1)

Also assume x +-x, i.e. an outcome is accessible from itself. Clearly the binary relation
accessible is reflexive and transitive. Two outcomes x and y which are accessible to
each other are said to communicate and we write this as x ~ y. Since the relation
accessible is transitive and reflexive, it follows that

Proposition 2.1. Communication is an equivalence relation.

We can now partition the set X into equivalence classes. TWo outcomes are in the
same equivalence class if they communicate with each other.
The set

Dom(x) = (y E X : x d o m y ) (2.2)

is called the dominion o f x . Also, we define the dominion of any subset A c X by

Dom(A) = U Dom(x). (2.3)

x~A

The core C [due to Gillies; Shapley, 1953] of an abstract game is defined to be the set
ofundominated outcomes. I.e.

C = X -- Dom(X). (2.4)

We can rewrite the definition of the core in terms of the relation accessible as follows.
 On Coalition Formation 135

C=(xEX :~yEX, y~x, wehavey~-x). (2.5)

I.e., in the terminology of Markov chains, the core is the set of all absorbing outcomes.
Note that each outcomes in the core (if nonempty) is an equivalence class by itself.
An elementary dynamic solution (elem. d-solution) of an abstract game is a set
S C X such that

if x E S, y E X -- S then y 4- x , (2.6)
and
ifx, y E S , thenx~yandy§ (2.7)

It can easily be shown that

Proposition 2.2. An elem. d-solution is an equivalence class.

The converse, however, is not always true. Condition (2.6) requires S to be (in the
terminology of Markov chains) a non-transient (recurrent, persistent) equivalence class.
The dynamic solution (d-solution) P of an abstract game is the union of all distinct
elem. d-solutions. I.e.

P = U {S C X : S is an elem. d-solution). (2.8)

We have the following easy result.

Proposition 2.3. For all abstract games, C C P.

It is clear that the dynamic solution always exists and is unique. However, it may
sometimes be empty. However, i f X is a finite set, we have the following two results.

Lemma 2.4. I f X is a finite set, thenP is the d-solution if and only i f P satisfies

Vx, y E P , y ~ x iffx~y. (2.9)

IfxEP, yEX--P, theny4x. (2.10)

And

IfyEX--P, then3xEP suchthatx+-y. (2.11)

Theorem 2.5. I f X is a finite set, then the d-solution is always nonempty.

For proofs of these assertions and for a behavioral interpretation of the dynamic
solution, see Shenoy [ 1977a]. The dynamic solution has also been defined independ.
ently by Kalai/Pazner/Schmeidler [ 1976].

3. The Models

We shall first introduce some notation and definitions. Let N = ~ 1 , . . . , n) denote

the set of players. Let F be an n-person cooperative game (with side payments, without
side payments or a game in partition function form). Let 2N denote the set of all sub-
136 P.P. Shenoy

sets (coalitions) of N and II denote the set of all partitions (coalition structures, c.s.)
of N. Let S : II ~ 2En be a payoff solution concept, where 2gn denotes the set of all
subsets of the n-dimensional Euclidean space E n. Intuitively, given that the players in
N align themselves into coalitions in the c.s. P E II, we interpret S (P) as the set of all
likely disbursements of payoffs to players in N. E.g. S may denote the individually
rational payoffs, the core, a vN - M stable set, the Shapley value, the bargaining set
M~i), the kernel, the nucleolus or any other payoff solution concept that indicates
disbursement of payoffs as solutions of an n-person cooperative game. For PE 11,
S (P) may be the empty set r (e.g. the core), or a single point in E n (e.g. the Shapley
value or the nucleolus) or a nonempty subset o f E n (e.g. the bargaining set M~i) or the
kernel). If S(P) = ~ (interpreting this fact as players unable to reach an agreement on
the disbursement of payoffs when they are aligned into coalitions in P), then we will
assume for simplicity of exposition that Pis not viable. Let 11 (S) denote the set of all
viable coalition structures with respect to the payoff solution concept (p.s.c.) S, i.e.
II(S) = (P e 11: S (P) ~: 0). (3.1)
Definition 3.1. A solution configuration with respect to p.s.c. ,q is a pair (x, P) such
thatx E S (P) and PE 11 (S).
A solution configuration w.r.t.p.s.c. S represents a possible outcome of the n-
person cooperative game where S represents any appropriate payoff solution concept.
Let SC (S) denote the set of all solution configurations w.r.t.p.s.c. S, i.e.
SC(S) = u IS(P) • {P}]. (3.2)
~n(S)
We now define a binary relation, domination, on the set SC(S) as follows:
Definition 3.2. Let (x, P1 ) and 0', P2) belong to SC(S). Then (x, P1 ) dominates
(Y, P2), denoted by (x, P1 ) dom(y, P2) iff

3 a nonempty R E P1 such that x i >Yi for all i E R . (3.3)

Intuitively, if (x, P1 ) dom(y, P2), then the players in some coalition R in c.s. P1
prefer P~ to P2. We require the players in subset R to be together in a coalition in c.s.
P~ so that there is no conflict of interest between these player's preference for P1 and
their allegiance to the other players in their coalition.
The dominance relation as defined above may be neither asymmetric nor transitive.
We now have an abstract game (SC(S),dom) where SC(S) is the set of outcomes and
dom is a binary relation on SC(S). For this abstract game, we look at the core and the
dynamic solution as defined in Section 2.

Definition 3.3. Let P be an n-person cooperative game 3) and S be a p.s.c. The core of
solution configurations w.r.t.p.s.c. S, denoted by Jo (S), is the core of the abstract
game (SC( S),dom).

Definition 3.4. Let [' be an n-person cooperative game and S be a p.s.c. The dynamic

3) In this section, r denotes an n-person cooperative game with side payments, without side
payments or a game in partition function form.
 On Coalition Formation 137

solution of solution configurations w.r.t.p.s.c. S, denoted by J1 (S), is the dynamic

solution of the abstract game (SC(S),dom).
From Proposition 2.3, we obtain the following result.

Proposition 3.1. Jo(S) c J1 (S).

The core of an abstract game is a very intuitive and plausible solution concept.
However, for some games and for certain p.s.c., Jo(S) may be an empty set. In such
cases, we can proceed to look at J1 (S) as a solution concept. If the p.s.c. S is such
that S(P) is a unique point inE n for each P E H(S) with II(S) :/: ~}, then the set SC(S)
is finite and nonempty. By appealing to Theorem 2.5, we conclude the following result.

Proposition 3.2. Let F be an n-person cooperative game and S be a p.s.c, such that
II(S) q: O and assume that S(P) is a unique point in E n for each P E II(S). Then
]1(S)=/= 0.
In another approach, we model just the set of all viable coalition structures H(S) as
the outcomes of an abstract game. A domination relation on 1](S) is defined as follows.
Definition 3.5. Let/91, P2 E II(S), • =/=R @ 2N and S be a p.s.c. Then/91 dominates
P2 via R w.r.t.p.s.c. S, denoted by/91 domR (S) P2, iff
R E PI (3.4)
and
for eachy E S(P2), 3 a n x E S(P1) such that xi >Yi V i E R . (3.5)

Intuitively, if/91 dOmR (S)/92, then the players in subset R prefer/9i to/92 because by
Condition (3.5), no matter how the players disburse the payoffs corresponding to c.s.
/92, each player in R will do better in c.s. PI. Condition (3.4) is imposed for the same
reasons Condition (3.3) is imposed in Definition 3.2.

Definition 3. 6. Let P1, P2 E II(S) and S be a p.s.c. P1 dominates P2 w.r.t. S, denoted

by P1 dom(S) P2, iff

3 a nonempty R C 2N such that /91 domR (S) P2- (3.6)

We.now have another abstract gamr dom(S)) where II(S) is the set of out-
comes and dom(S) is the binary relation on H(S). Once again we look at the core and
the dynamic solution of this abstract game.

Definition 3. 7. Let F be an n-person cooperative game and S be a p.s.c. The core of

coalition structures w.r.t.p.s.c. S, denoted by Ko(S), is the core of the abstract game
(H(S), dom(S)).

Definition 3.8. Let F be an n-person cooperative game and ._qbe a p.s.c. The dynamic
solution of coalition structures w.r.t.p.s.c. S, denoted by K1 (,_q),is the dynamic
solution of the abstract game (H(S), dom(S)).
Once again, by appealing to Proposition 2.3, we have:
138 P.P. Shenoy

Proposition 3.3. Ko(S) c K1 (S).

Also, since II(S) is always finite, we have:

Proposition 3.4. Kt ( S) =/=O.

The following results gives a comparison of the two models.

Theorem 3.5. Let P be an n-person cooperative game and S be a p.s.c. Then we have
Ko(S) D {PC Fl: (x, P)EJo(S)).

Proof: Let P I E ( P EII: (x, P) E Jo (S)}. Then 3 x E S (P1) such that (x, P1) is
undominated in SC(S) which implies that/91 is undominated (w.r.t. S) in 1I(S), i.e.,
Pl E Ko (S). []
Another consequence of the definitions of K0 (S) and 3"o(S) is as follows:

Theorem 3.6. Let P be an n-person cooperative game and S be a.p.s.c, such that
VPE IL S(P) is either a single point set inEn or an empty set. Then

Ko(S) = {P~rI: (x, P) elo(S)}

and
Jo(S) = {(s(v), v): V~Ko(S)}.
If J0 (S) q: 0, then the solution configuration model indicates both coalition struc-
tures and distribution of payoffs among the players as solution in Jo(S) whereas the
coalition structure model indicates only coalition structures as solutions in Ko (S). Also
by Theorem 3.5,Jo(S) indicates fewer (or at most an equal number of) coalition struc-
tures as solutions compared to Ko(S). However, if the p.s.c. S is such that for each
P EII, S(P) is either a single point in E n or an empty set, then the two models are
identical (expect in form) and indicate the same results.
Note that the stability of the core is much stronger than the stability of the dynamic
solution. Hence ifKo(S) (do(S)) is non-empty, we shall use Ko(S) (do(S)) as the
prediction of the coalition structure (solution configuration) model. We shall look at
K1 (S) (dl (S)) only ifKo(S) (Jo(S)) is an empty set.
In the next section, the c.s. model is represented by means of digraphs. The predic-
tions of this model, Ko(S) and Kl (S), are then described in graph theoretic terminol-
ogy. Subsequently, in sections 5, 6, 7 and 8, the predictions of the c.s. model and the
s.c. model w.r.t, various p.s.c.'s are studied for the special case of games with side
payments.

4. Representation by Digraphs

Since the number of coalition structures is finite, we can represent the abstract:
game (II(S), dom(S)) of a game on N by means of a directed graph (or digraph).
Given a payoff solution concept S, let D = D(S) be a digraph whose vertex set
 On CoalitionFormation 139

V(D) = II(S) and whose arc set A (/9) is given by

A(D) = ((P1 ,P2) e II(S) X I-I(S): Pt dom(S) P2}- (4.1)
We call such a digraph D the domination digraph of the abstract game (II(S), dom(S)).

Example 4.1. Let F be a 3-person game on (1,2,3). Let S be a p.s.c, defined as

follows:
Let 0 ~<a ~<b ~<c = d be real numbers such that c > a + b and

(0,0,0) if P = ((1}, (2}, (3))

(04,0) if P = {{1,2), (3))
S(P) = (O,0,b) if/9 = {{1,3), {2)}
{(O,x2, c--x2): a<~x2 <~c--b} if P = {{1), (2,3)) or ((1,2,3)).
To condense notation, we shall drop the braces around coalitions in coalition structures
and, for example, denote ((1), (2,3}) by (1) (23). Note that

(1) (23) dom(S) (1) (2) (3),

(1) (23) dom(S) (12) (3),
(1) (23) dom(S) (13) (2).

The domination graph of the game F is shown in Figure 4.1.

Let (P1, P2) EA(D). Then we say P, is adjacent to P2 and P2 is adjacentfrom
F1. The outdegree, od(P), for P E II(S) is the number of c.s.'s adjacent from it and the
indegree, id(P), for P E II(S) is the number adjacent to it. Then, in terms of this
terminology, the core of the abstract game (II(S), dom(S)) is given by

Ko(S) = {P e V(D): id(P) = 0). (4.2)

In Example 4.1, Ko(S) = {(1) (23), (123)).

(i) (2) (3)

(12) (3) @ (123)

( - ~ w (i) (23)

Fig. 4.1: The domination digraph of game in Example 4.1

140 P.P. Shenoy

The converse digraph D' of D has the same vertex set as D and the arc
(/91, P2) ~ A ( D ' ) r (P2, P1 ) E A ( D ) . Thus the converse of D is obtained by reversing
the direction of every arc in D. I f D = D ( S ) is the domination digraph of the abstract
game (II(S), dom(S)), then we call its converse D' = D ' ( S ) the transition digraph of
the abstract game (II(S), dom(S)). The transition digraph of the game in Example 4.1
is shown in Figure 4.2
(i)(2)(3)

Fig. 4.2: The transition digraph of the game in Example 4.1

To define the dynamic solution in terms of the transition graph, we need a few
basic definitions from graph theory [cf. Harary]. A (directed) walk in a digraph is an
alternating sequence of vertices and arcs/90, el, P1 . . . . . en, Pn in which each arc e i
is (Pi-1, Pi). A closed walk has the same first and last vertex. A p a t h is a walk in which
all vertices are distinct; a cycle is a nontrivial closed walk with all vertices distinct
(except the first and the last). If there is a path from P1 to P2, then P2 is said to be
accessible from P1. A digraph is strongly connected or strong if any two vertices are
mutually accessible. A strong component of a digraph is a maximal strong subgraph.
Let T1, 7'2, 9 9 9 T m be the strong components of D. The condensation D* of D
has the strong components of D as its vertices, with an arc from T i to T/whenever there
is at least one arc in D from a vertex of T i to a vertex of/~. (See Figure 4.3). It follows
from the maximality of strong components that the condensation D* of any graph D
has no cycles. Let D ' ( S ) be the transition graph of the abstract game (II(S), dom(S))
with strong components T1, 7/'2. . . . . T m .

D: ~ / T3
D* :
T2
T2
Fig. 4.3: A digraph and its condensation
 On Coalition Formation 141

Then the dynamic solution of the abstract game is given by

K I ( S ) = U {Ti: od(T/) = 0 in the condensatlonD }. (4.3)

In Example 4.1, KI (S) = {(I) (23), (123)}.

5. Solutions with Respect to the Individually Rational Payoffs

In the next four sections, we will characterize the solutions of the abstract games
for the special case of games with side payments using various payoff solutions con-
cepts.
A cooperative n-person game in characteristic function form with side payments
is a pair (N, v) where N = {1 . . . . . n} denotes the set of players (as stated before) and
v is a nonnegative real-valued function defined on the subsets of N which satisfies
v (0) = 0 and v ({i}) = 0 for 4) all i E N .
The individually rational payoffs (i.r.p.) corresponding to coalition structure
P = (P1 . . . . . Pm ) E 11 is the set

F(P) = {x EEn: i ~ D x i = V (6.) for all] = 1 . . . . . m

=j
and

x i >~v (i) for s ) all i EN}.

When P = (N), I((N)) is also referred to as the set of imputations. Since I(P) is non-
empty for all P E II, we have

11(/) = 11.

A game (N, v) is said to be superadditive if

RI n R2 = O, R1,R2 E 2N ~ v(R1) + v(R2 ) <- v(R1 U R 2 ) (5.1)

and strictly superadditive if strict inequality holds in Relation (5.1).
Define the worth of a coalition structure P in the game (N, v) by

(5.2)

Let

z = max w(P) (5.3)

P~H

4) This condition and the nonnegativity restriction on v causes no real loss of generality since
all the payoff solution concepts we consider are invariant under strategic equivalence.
s) To condense notation, we shorten expressions like v ({i, 1", k)) to v (i/k) and so on.
142 P.P. Shenoy

and define

I1z = {P ~ II: w(P) = z}. (5.4)

I f x E E n and R C N , let x(R) denote x r Then we have the following theorem.

i~R

Theorem 5.1. Let I" be an n-person cooperative game with side payments. Then
Ko(/) :~ ~. In particular, we have Ko(/) ~ IIz.

Proof. Let 191 = (PI,

1 P21 . . . . ,plm) E H z . Suppose 3 19 E II such that 19dom(/) p l , i.e.
m
3 R EP such that 19dora R (/) 191. Now we can write R = W (R n P~ ). P i c k y ~ i ( p l )
i=1
such that y (R n P~ ) = v (P~) if R n P~ ~ ~ for all i = 1, 2 . . . . . m. Since 19 dom R (/) 191,
3 x E I(19) s.t. x i > Y i for all i E R . I.e. v(R) = x ( R ) > y ( R ) = p.1 ~ - v ( P ~ ). Pick

19~ S II as follows. 192 = (R) U {P]: P~ n R ~ q~} u {P} - R: ~ n R =/=q)} Then

w(P 2) > w(191 ), a contradiction! This completes the proof. []
The following example will show that, in general, we cannot make a stronger
statement than in the theorem above.

Example 5.1. Let F be a 4-person game with

v(12) = v(34) = v(23) = 1, and v(R) = 0 for all other R C N .

Let Pl = (12) (34), 192 = (14) (23) and Pa = (1) (23) (4). W(Pl ) = 2,
w(P2) = w(193)= 1. But K o ( / ) = (Pl, P2,193}.
However, we do have the following.

Theorem 5.2. Let V be an n-person game with side payments such that (N) E Hz . Then
Ko (/) = IIz.

Proof: From Theorem 5.1 we need prove only Ko (/) C IIz. Let t91 E II such that
191 ~ Hz, i.e. w(191 ) < z. Then (N) dom(D P1. This is seen as follows. Let x E I(191 ).
Then x (N) = w(P1 ) < z. Define y so that Yi = xi + (z -- w(P1 ))/n for all i E N. Then
y E I ( { N } ) andYi > x i for all i E N . []

Corollary 5.3. Let V be a superadditive game. Then Ko(/) = IIz. Furthermore, if I~ is

strictly superadditive, then Ko(/) = {(At)}.

Proof." P superadditive =~ (iV) E IIz, and P strictly superadditive =~ IIz = {(N)). []

For the solution configurations model, no general existence result is possible as is
illustrated by the following example:

Example 5.2. Let F = (N, v) be a 3-person game with

v(12) = v(13) = v(23) = 2, v(123) = 2.5.

If can easily be shown that for this game Jo(/) = ~.

 On Coalition Formation 143

6. Solutions with Respect to the Core

Let (N, v) be a cooperative game with side payments. Then the core of the game
(N, v) corresponding to c.s. P E H is defined by
Co(P) = (x EI(P): x(R) >1v(R) for all R E 2N). (6.1)

The core corresponding to a particular c.s. may be empty. Hence in general II(Co) :~ H.
in fact, for some games the core corresponding to every c.s. may be empty, i.e.,
II (Co) = 0. A characterization of Ko (Co) and Jo (Co) is as follows.

Theorem 6.1. Let (N, v) be a cooperative game with side payments. Then,
Ko(Co) = II(Co) = (P: Co(P) @ 0).

Also

&(Co) = sc(co) = u [Co(p) x {p}].

Pen(co)

Proof: Let Pl, P2 E II(Co). Suppose Pl dOmR(CO) P2 for some R E Pl. LetyECo(P2).
Then 3x E Co(P1) s.t. x i >Yi for all i ER. I.e. x(R) > y ( R ) . But since R E P1,
x(R) = v(R). Hence y (R) < v (R) contradicting the fact that y E Co (P2)- The proof
of the second assertion is similar to the first. []
Corollary 6.2. Let (iV, v) be a cooperative game with side payments. Let S be a p.s.c.
such that, for all P c II, S(P) C I(P), and S(P) n Co(P) ~ 0 whenever Co(P) q= O.
Then Ko(Co) C Ko(S) and {P: (x, P) EJo(Co)) c (P: (x, P) EJo(S)).

In light of Theorem 6.1 we would like to characterize the coalition structures with
nonempty cores. The next two theorems along with a known characterization of
games with nonempty cores corresponding to the grand coalition N accomplish this
task.

Theorem 6.3. Let (N, v) be a cooperative game with side payments. If II(Co) :~ 0,
then I1(Co) = 11z.

Proof: Let Pl E II(Co), and suppose Pl ~ IIz. Then 3 P2 E H such that w(P2) > w(Pl ).
Let x E Co(P1 ). Then x(R) >~v(R) for all R C N which implies that
w(P1 ) = x(N) ~> w(P2) and this is a contradiction! Hence H(Co) C Hz.
Let Pl E IIz and assume P2 E II(Co) c Hz. Let x E Co(P2 ). Then x(R) >1v(R) for
all R C N. I f x (P) > v(P) for some P E Pl, then w(P2) = x(N) > w(Pl ), contradicting
the fact that Pl E IIz . Hence x (P) = v(P) for all P ~ Pl =~x E Co(P1 ) = Pl E 11(Co).
Therefore H (Co) D rlz. []

Corollary 6.4: Let (N, v) be a game with side payments. Then for all Pl, P2 E If(Co),
Co(Pl ) = Co(P2).
144 P.P. Shenoy

Corollary 6.5. Let (N, v) be a game with side payments. If there is a P E IIz such that
Co(P) = 0, then II(Co) = r

Given a game F = (N, v) define game Fz = (N, Vz) derived from I~ as follows.

z ifR=N
vz (R) = (6.2)
v(R) for all otherR C N

where z = max w(P).

Pen

When there is more than one game under discussion, we shall denote the sets
Co(P), II(Co) and 11z by Co(P, F), II(Co, r), and I]z (F), respectively.

Theorem 6.6. Let F = (N, v) be a game and I"z be as in Relation (6.2) Then if
Co(P, r) ~ 0, Co(P, r) = Co((N), rz).

Proof: From the definition of Fz it is clear that for P :/: (N) Co (P, F) = Co(P, Fz). From
Theorem 6.3 we obtain I1(Co, l-'z) = IIz (rz). Since (N) E 11z (Fz) , by Corollary 6.4,
Co(P, Fz) = Co ((N), Fz). Hence the theorem follows. []

Games with nonempty cores corresponding to the grand coalition have been
characterized by Bondareva [ 1962, 1963 ] and Shapley [ 1967]. For the sake to com-
pleteness we will repeat this characterization here.
A balanced set B is defined to be a collection of subsets R of N with the property
that there exist positive numbers 6R MR E B called weights, such that for each i E N
we have

~R = 1. (6.3)
(R E B :iER )

A game (N, v) is called balanced iff

Y, 8 R v(R) < v(N)

REB

holds for every balanced set with weights (6R)- The following theorem was proved by
Bondareva [1962, 1963] and Shapley [1967].

Theorem 6. 7. Let (N, v) be a game. Then Co((N)) 4:0 if and only if the game is
balanced.

Corollary 6.8. Let P = (N, v) be a game. Then II (Co, P) 4= 0 if and only if the game
(N, Vz) is balanced.

Proof: (Necessity): II(Co, F) 4:0 =' Co((N), (N, Vz)) 4:0 (by Theorem 6.6) = (N, Vz)
is balanced (by Theorem 6.7).
 On Coalition Formation 145

(Sufficiency): If Pz = (N, Vz) is balanced ~ Co((N), Fz) :~ 0 (by Theorem 6.7). If

(Ar) E IIz (P) then V = F z and we are finished.Otherwise 3 P E I I z (Fz) such that
P :/: (N). Then, Co(P, F) = Co(P, Fz) = Co((N), Fz) :/: 0. []
Thus we have completely characterized Ko(Co) and J0 (Co) for all games with side
payments.

Example 6.1. (A game with no solution. See Lucas [1968, t 969].) Let
N = (1,2,3,4,5,6,7,8,9,10) and v be given by
v(N) = 5, v(13579) = 4,
v(12) = v(34) = v(56) = v(78) = v(910) = 1,
v(3579) = v(1579) = v(1379) = 3,
v(357) = v(157) = v(137) = 2,
v(359) = v(159) = v(139) = 2,
v(1479) = v(3679) = v(5279) = 2, and

v(R) = 0 forallotherRCN.

In this game z = 5, 11z = fiN), P1 = (12) (34) (56) (78) (910)) and
Co((N)) = Co(P1 ) = (x: x(12) = x(34) = x(56) = x(78) = x(910) = 1, and
x(13579) f> 4). By Theorem 6.1,

Ko (Co) = ((N), Pl ),

and

Jo(Co) = Co((N)) X ((N), ;o~ ).

7. Solutions with Respect to the Shapley Value

Shapley [1953] defined a unique value satisfying three axioms for all n-person co-
operative games with side payments. It was assumed that the grand coalition would
form. Later, Aumann/Dreze [ 1974] generalized the axioms to define the Shapley value
for all coalition structures.
A permutation ct of N is a one-one function from N onto itself. For R E 2N, write
aR = {ai: i E R ) . If v is a game on N, define a game a * v on N by

(a * v) (R) = v(aR) for all R E 2N. (7.1)

Also, if v and u are games on N, define a game v + u on N by

(v + u) (R) = v (R) + u (R) for all R E 2N. (7.2)

Call a c.s. P = (PI . . . . . Pm) invariant under ~ if o ~ l = P/. for all ] = 1 . . . . . m. Player
i is null if v(R u (i)) = v(R) for all R E 2N. Let G N denote the set of all games with
side payments o n N . Since we assume that for all games with side payments, v(0) = 0
and v(i) = 0 V i E N , G N is a Euclidean space o f dimension 2 n -- (n + 1).
146 P.P. Shenoy

F i x N = (1 . . . . . n} and P = (PI . . . . ,Pm) E 11. The Shapley value corresponding

to c.s. P is a function e p from G N to E n i.e. a function that associates with each game
a payoff.vector satisfying the following axioms:

A.1 (Relative Efficiency): ~ p ( v ) (Pj) = v(P]) for a l l / = 1 . . . . . m.

A.2 (SymmetryJ: For all permutationsa of N u n d e r which P is invariant,

9 /) (~ * v) (R) = ~r,(v) (~R).

A.3 (Additivity): ~ p ( v + u) = ~p(v) + ~pp(u).

A.4 (NullPlayerAxiom}: I f / i s a null player, then ~p(v) (/) = 0.
When P = (N), the above axioms are equivalent to Shapley's axiom which specify a
unique value r = (~1 (v) . . . . . en (v)) given by

(~i(v) = ~P(N)(v)(0 = R cN
~ ( r - 1)n[[ (n - - r ) ! [ v ( R ) - - v ( R - (i))] (7.3)

where r = I R I, the cardinality of coalition R. For eachR E 2N, denote by v I R the

game on R defined for all T C R by

(v I R) (T) = v(T). (7.4)

Theorem 7.1. Fix N and F = (Pl . . . . , Pro)" Then there is a unique value ~ p and it is
given for a l l / = 1 . . . . . m and i E P / b y

( ~ p v ) (i) = (e~(pi)(v I P/)) (0- (7.5)

Proof: See Aumann/Dreze [ 1974, 220-221 ].

Since ~I,(P) is6) nonempty for all P E II, II(~) = II. Also note from (7.3) that i f v
is superadditive, then ~ ( P ) (i) t> 0 and hence ~ ( P ) E I ( P ) . Also, since ~ ( P ) consists
of a unique outcome for all P E 11, by Theorem 3.6 the s.c. model and the e.s. model
give identical results. For convenience, all the results in this section are stated only for
the c.s. model.
A partial existence theorem for Ko(~) is as follows:
Theorem Z2. Let F be art n-person game in which the only coalitions with positive
values are all the (n -- 1)-person and n-person coalitions. Then Ko(ff) :/: 0.

Proof: Let us denote the game as follows:

v(i) = 0 for all i EN,
v(N--(i))=a i for aI1 i EN,
v(N) = b, and v(R) = 0 for all other R C iV.

6) When there is no doubt about the game v under consideration, we shall denote ~ p(v) by
(79) which is consistent with the previous section.
 On Coalition Formation 147

We can assume (by relabeUing of the players) that

al <~a2 <~... <~an. (7.6)

n
~ ai and Ilan = {P E II: w(P) =an). Using (7.3) and (7.5) we have
Leta = i=1

9 ((N)) (i) = ((n - 1) b +a - n " ai) / (n(n - 1)). (7.7)

By (7.6) we have

(I)((N)) (1) i> ~((N)) (2) t > . . . ~> (I)((N)) (n). (7.8)
Also

ai/(n -- 1) for ] = 1 , . . . , n
(I)((N-- i) (i)) O') = ]~ i (7.9)
0 f o r / = i.
Clearly, the only c.s.'s we need look at are (N) and (N-- i) (i) for i = 1 , . . . , n. All the
c.s.'s not in Han (except (N)) are dominated by c.s.'s in IIan. From Expressions (7.7),
(7.7), (7.8) and (7.9) it follows that (iV) dom(~) (N -- n) (n) iff

(I,((N)) (n - 1) > q ) ( ( N - n) (n)) (n - 1)

i.e.iff

b > (n (an + an.l) --a)/(n -- 1).

Also ifa n = an. 1 (i.e. (N -- (n -- 1)) (n -- 1) ~ Ilan ) then

(N) dom (~) (N -- (n -- 1)) (n -- 1)

iff

~)((N)) (n) > (I)((N- (n - I)) (n - I)) (n),

i.e. iff

b > (n (a n + a n -1 ) -- a) / (n -- 1).

Now,
(N-- n) (n) dom((b) (N)
iff

(I)((N-- n) (n)) (1) > r ((N)) (1),

i.e. iff

b < ( n (an + a l ) - - a ) / ( n - - 1).

148 P.P. Shenoy

Hence we have

(N) I f b > (n (an + an_l) --a)/(n -- 1)

Ko(r = Han ifb < (n (an + a l ) - - a ) / ( n - - 1)

(.,V) u ll otherwise. []
n

Corollary 7.3. Let F be a 3-person game with side payments. Then Ko(r :# O.
In general, this is the strongest existence result we can obtain. I.e. there is a 4-person
game for which Ko(r = O. This is shown in Example 7.5.
If Co(P) :/: O, * ( P ) may not belong to Co(D. Hence Corollary 6.2 is not applicable
for the Shapley value. The following example illustrates this fact.

Example 7.1. L e t N = {1,2,3) and v be given by v(1) = v(2) = v(3) = 0, v(12) = 50,
v(13) = 50, v(13) = 56, and v(123) = 80. Then the Shapley value is given by:

(24.67, 27.67, 27.67) if P = (123)

(0, 28, 28) if P = (1) (23)
r = (25, O, 25) if P = (13) (2)
(25, 25, O) if P = (12) (3)
(0, 0, 0) if P = (1) (2) (3).

Note that Co((123))= Cony{(20, 30, 30), (24, 26, 30), (24, 30, 26)) but
r ~ Co((123)). The transition digraph is shown in Figure 7.1, and hence
Ko (r = Ka (r = (1) (23).

c121123
</
(i) (2) (3)

(12) (3)

(13) (2)
Fig. 7.hThe transition digraph for Example 7.1

The above example illustrates a weakness of the Shapley value in that the Shapley
value is derived entirely from the characteristic function rather than the bargaining
positions of the players in the process of coalition formation. However, the Shapley
value has been extensively used as an a priori measure of power of players in "simple"
games. Hence the study of Ko(~) and K~ (~) is most appropriate for simple games.
The class of all simple games forms a subclass of the class of all cooperative games
with side payments. A simple game is a game in which every coalition has value either
1 or O. A coalition R C N i s winning if v(R) = 1 and losing if v(R) = O. A simple game
 On Coalition Formation 149

can be represented by a pair (N, W) where N is the set of players and Wis the set of
winning coalitions. A simple game is monotonic iffR E W and T D R ~ T E W, and
proper iffR E W ~ N --R ~ W. A winning coalition R is called minimal winning if
every proper subset of R is losing. A monotonic simple game can be represented by the
pair (N, Wm) where Wm is the set of all minimal winning coalitions. If Wm = { {i}},
then player i is said to be a dictator. I f / E N Wm ~=O, then player] is said to be a veto
player. I f k ~ U Wm then player k is said to be a dummy. Dummies play no active role
in the game and for all practical purposes can be omitted from the set of players. A
weighted majority game is a monotonic simple game that can be represented by

[q: al, a2 . . . . . an] (7.10)

where q/> 0 is called the quota, ai >~O, i = 1. . . . . n is the weight of the i-th player,
a n d R E W ~* ~ ai >~q. Expression (7.10) is said to be a weighted majority repre-
i~R
sentation of the simple game. Two weighted majority representations are said to be
equivalent if they represent the same simple game. E.g. [ 2 ;1,1,1 ] and [5 ;2,3,4] are
equivalent since both represent the game ({1,2,3}, Wm = {(12), (13), (23)}). Not every
monotonic simple game has a weighted majority representation [see Shapley, 1962].
Example Z2. The most common of all simple games is the straight majority game
M n , n odd, in which

Wm = {R C N: IR I = (n + 1)/2}

where [ R I denotes the cardinality of coalition R. The Shapley value is given by

9 (P) (i) = {I/IRI0 iRf E

i EPRoEt hWe ,r w i s e .

It is clear that

Ki (q~) = Ko (~) = {P E II: P contains a minimal winning coalition}.

Example Z3. The pure bargaining game B n , is given by Wm = {(A0}. The Shapley
value is given by

I1/n ifP=(N)
~(P) (0
O" otherwise

clearly, KI (@) = Ko(@) = {(AT)}.

Example 7.4. Let P be a proper game with a dictator. Then

= / 1 if l i s a dictator
~(P) (i)
t0 otherwise.
150 P.P. Shenoy

Hence KI (~) = Ko(~) = II. Note that every player who is not a dictator is a dummy.
So essentially we have a 1-person game in which the only player is winning by himself.

Example 7.5. Consider the weighted majority game [3;2,1,1,1]. The minimal winning
coalitions are Wm = {(12), (13), (14), (234)}. The Shapley value is given by

(1/2, 1/6, 1/6, 1/6) if P = (1234)

(2/3, 1/6, 1/6, 0) if P = (123) (4)
(2/3, 1/6, 0, 1/6) if P = (124) (3)
(2/3, 0, 1/6, 1/6) if P = (134) (2)
~(P)= (1/2, 1/2,0,0) i f P = (12) (34) or (12) (3) (4)
(1/2, 0, 1/2, 0) if P = (13) (24) or (13) (2) (4)
(1/2, 0, 0, 1/2) if P = (14) (23) or (14) (2) (3)
(0, 1/3, 1/3, 1/3) if P = (1) (234)
(0, 0, 0, 0) otherwise.

The transition digraph of the game is shown in Figure 7.2. Since all c.s.'s that contain
only losing coalitions are dominated, these are omitted from this transition digraph.
Note that Ko (~) = g). However,
KI (~) = {(1) (234), (12) (3) (4), (12) (34), (134) (2), (13) (24)
(13) (2) (4), (124) (3), (14) (23), (14) (2) (3), (123) (4)).
A closer look at the Shapley value for different c.s.'s in Example 7.5 reveals the
following observation. If players 1 and 2 who are in a winning coalition with 3 in the
c.s. (123) (4) decide to expel player 3 from the coalition and form the smaller winning
coalition (12), one would expect both players not to decrease their power in the
smaller winning coalition (12) since there are fewer players to share the same amount
of power. However, player 1 actually does decrease his power from 2/3 to 1/2. We
shall call this phenomenon the paradox of smaller coalitions. To understand why this
phenomenon occurs, let us look at Theorem 7.1. It states that given a c.s.
(12) (34)
(12) (3) (4) " ~ (134) (2)

(124) (3)

_ (1234)
)

(13) (24)
(13) (2) (4)

(14) (23)
Fig. 7.2: The transition digraph in Example 7.5 (123) (4) (14) (2) (3)
 On Coalition Formation 151

P = (PI . . . . . Pro) the Shapley value of player i in coalition P/depends only on the
subgame v I Pj. I.e. the Shapley value of a player in a coalition is oblivious of the
presence of other players not in the coalition for bargaining purposes. We shall regard
this phenomenon as a "flaw" in the properties of the Shapley value. To make the
above discussion more formal, let P = (N, W) be a simple game and o be a payoff
value concept (i.e. for all games and for each P E H, o(P) is a single point in E n , where
n = the number of players). We say P does not exhibit the paradox o f smaller coali-
tions w.r.t, payoff value concept 0 iff the following holds:

Let P~, P2 E H such that there existsP~ E P1 N Wand

P2 E P2 n {g satisfyingP2 CP1. Then

o(P2)(i)>~o(Pa)(i) for all i EP2.

The following result is a consequence of the above definition.

Theorem 7.4. Let P be a proper monotonic simple game that does not exhibit the
paradox of smaller coalitions w.r.t, ep. Then Ko(e;) 4: ~.

Proof: Let T E Wm such that I T I <~ I R [ for all R E Wm . Let P E 11 be such that
T E P. Then q~(P) (/) = 1/[ T[ for all i E T. Suppose 3P1 EII such that
P1 domR ( ~ ) P for some R E P1, i.e., cb(P1 ) (i) > ~(P) (/) for all i E R . Let R' be
any minimal winning coalitioncontained in R, i.e. R' C R and R' C Wrn . Let
P2 EII be such that R' E P2- Then since 1~ does not exhibit the paradox,
O(P2) (i) ~> O(Pt ) (i) for all i E R ' . Also

~(P2)(i)= {10/IR'I ifiER'

otherwise.

Since r' is proper, R' n T 4: 0. Hence for all i E R ' N T,

1/I R'I = ~(P2) (i)/> ~(P1 ) (i) > ~(P) (0 = 1/[ T I, which is'a contradiction (since
IR' I~>l TI)! []
Let

t = min [R I (7.11)
R~W m
and let
II t = (P E l i : P contains a winning coalition of size t). (7.12)

Then we obtain the following.

Corollary 7.5. Let P be a proper monotonic simple game that does not exhibit the
paradox of smaller coalitions w.r.t, cI,. Then Ko (ep) D 11t.
That in general we cannot strengthen the above result is shown by the following
example.
152 P.P. Shenoy

Example 7.6. Let P be a 4-person game represented by [4;2,2,1,1]. The minimal

winning coalitions are {(12), (34), (234)). The Shapley value is given by

(1/2, 1/2, O, O) if P = (12) (34) or (12) (3) (4)

(1/2, 1/2, O, O) if P = (123) (4) or (124) (3)
a, (V) = (1/3, O, 1/3, 1/3) if P = (134) (2)
(0, 1/3, 1/3, 1/3) if P = (1) (234)
(1/3, 1/3, 1/6, 1/6) if P = (1234).

Note that the game does not exhibit the paradox of smaller coalitions. Also t = 2, and
Ht = {(12) (3) (4), (12) (34)). However, Ko(~) = {(12) (3) (4), (12) (34), (123) (4),
(124) (3)}. Observe that players 3 and 4 are dummies in the subgame on {1,2,3) and
{1,2,4) respectively.
An interesting problem raised by Theorem 7.4 is to characterize the class of games
that do not exhibit the paradox of smaller coalitions w.r.t. ~. Let us look at symmetric
games. A game (N, v) is called symmetric if the value of a coalition depends only on
the size of the coalition. A symmetric monotonic simple game is of the type
Mn, k = (N, W) where W= {R C N: I R I >~ k). The following proposition follows from
the symmetry axiom of the Shapley value.

Proposition 7.6. Let r' be a symmetric monotonic simple game. Then I~ does not
exhibit the paradox of smaller coalitions w.r.t. ~. In fact, Ko(~) = II r

Proof: The Shapley value is given by

1/I R I ifiER E P andRE W

9 (P) (i) =
0 otherwise.

Hence the result follows from Statement (7.5). []

The result in Proposition 7.6 (and also in Example 7.2) is known as "Riker's size
principle" in the political science literature [see Riker/Ordeshook]. Riker's theory is
that in zero-sum games with side payments, only minimal winning coalitions will form.
Note that l-It consists of all minimal winning coalitions only. The result in Example
7.6 shows that the size principle does not generalize further.
Since Example 7.6 does not exhibit the paradox and is not symmetric, Proposition
7.6 is not a complete characterization. A list of all proper simple games with four or
fewer players is given in the appendix along with the Shapley value ~ corresponding
to all coalition structures,, Ko (~), and whether or not the game exhibits the paradox.
Another interesting problem is to determine, if possible, a power index that has all
the desirable properties of the Shapley value but that does not exhibit the paradox of
smaller coalitions.
 On Coalition Formation 153

The most critical axiom of the Aumann-Dreze generalization of the Shapley value
is A.3.

A.3. ~p(v + u) = q~p(v) + ~p(u).

This axiom is acceptable if and only if we assume that the c.s. 19 is fixed and that
players in a coalition Pk E P cannot bargain on the basis of the value of coalitions not
contained in Pk" This assumption is not appropriate for our model where the players
are bargaining for a coalition structure and no c.s. is fixed.
Another generalization of the Shapley value (which he defined only for the grand
coalition) to the case of all coalition structures which is appropriate for monotonic
simple games is as follows.
(i) The Shapley value corresponding to the grand coalition is used as an a priori
measure of power of the players. This is suggested by Shapley/Shubik [ 1954].
(ii) And within any coalition in a c.s., a player can expect to share in the payoff
proportional to his power as defined in (i). This is suggested by Gamson [1961 ].
Assumptions (i) and (ii) define a unique value for all monotonic simple games which
we denote by ~'.
The (generalized) Shapley value ~' is a function from II • G N to E n , i.e., a func-
tion that associates with each game and a c.s. a payoff vector given by Expression (7.3)
and
iO, )
i~_~, ~i(V ) " V(ek ) where Pk E Pis such that
K

9 '(P, v) (j) = ] E P k , if] is not a null player (7.13)

0 i f / i s a null player

Note that ~'((N), v) = e~~N~(V) = r = ((~1(v) . . . . . r A simple consequence of

the definition of ~' is as follows.

Proposition 7. 7. Let 1~ be a monotonic simple game. The P does not exhibit the para-
dox of smaller coalitions w.r.t. ~'.

Proof: This follows from Expression (7.13).

In view of Corollary 7.5, we might be tempted to assert that Ko@') D Ht. However,
the following example shows that it is not true.

Example 7. 7. Consider the weighted majority game given in Example 7.5 [3 ;2,1,1,1 ].
Then ~' is given by 7)

7) When there is no doubt about the game v under consideration, we shall denote ~'(~, v) by
~'(]7) which is consistent with the established notation.
154 P.P. Shenoy,

(3/6, 1/6, 1/6, 1/6) if/9 = (1234)

(3/5, 1/5, 1/5, 0) if P = (123) (4)
dp'(p) = (3/4, 1/4, 0, 0) if P = (12) (3) (4) or (12) (34)
(0, 1/3, 1/3, 1/3) if/9 = (1) (234).

For all other c.s.'s, cI,'(p) can be determined by the symmetry of players 2, 3, and 4.
If is clear that K o ( ~ ' ) = {(1) (234)}. Note that in this example t = 2, hence
(1) (234) 9 11t .
Let

s= min ~ ~i(v), (7.14)

REoJm i~__R

and let

[Is = (P E 11: P contains a coalition R E wm such that i~R ~i (v) = s). (7.15)

Then we have the following important fact.

Theorem 7.8. Let P be a proper monotonic simple game. Then K0(~') = l-Is.

Proof: Denote ~'((N)) by r = (~bl . . . . .Cn)" Let P1 E II s. Suppose P2 E II such that

P2 domR (cI,') P1 for some R E P: such that R E Wm . Then ~'(P2) (i) > ~'(P1 ) (i)
for all i E R . Let T E P1 be such that T E Wm and 2~ r = s. Since r is proper
JET
R n T :/: 0. Pick j E R n T. Then ~'(P1 ) q) = r Since j E R, ~b'(P2) q) =
= r ~" ~ ) > r i.e., Z ~b; < s, a contradiction! Hence Ko(cb ') D Ho.
" i~R " J iER " ~
Let PI E I1s and P2 E 11 be such that P2 ~ [is" Then P1 dOmT(~') P2 where
T E P1 such that T E Wm and ~ ~bi =$ because ~(P1 ) (i) = r for all i E T and
i~T
~'(P2) (0 < r for all i E T. Hence K o ( ~ ' ) C 11s . []

8. Solutions with Respect to the Bargaining Set M1(i)

The bargaining set was first introduced by Aumann/Maschler [1964]. They defined
several types of bargaining sets. One of these, denoted by M~i), was shown to be non-
empty for every c.s. by Peleg [ 1967].
Let x R denote a vector in E r where r = [ R I, whose elements are indexed by the
players in R. Let x E I(P) and let i and j be two distinct players in coalition Pk E P.
An objection of i against j to x E I ( P ) is a vector) R , where R is a coalition containing
player i but not j, whose coordinates Yt satisfy Yi > xi' Yl >~Xl V I E R and
y~ = v(R). A counter-objection to this objection is a vector z D, where D is a coa-
I~_R "
lition containing player j but not i, whose coordinates z l satisfy z l >~x t for each 1 E D,
 On Coalition Formation 155

zt >~Yl for each I E R r and Z z l = v(D).

lED
x E l ( P ) is stable if for each objection to x, there is a counter-objection. The
bargaining set corresponding to the c.s. P E l-l, denoted by MIi) (P) is the set of all
stable individually rational payoff x E I ( P ) , i.e.,

MIi)(P) = (x E I ( P ) : x is stable). (8.1)

Theorem 8.1. Let F be an n-person cooperative game with side payments. Then
M~i) (P) :/= 0 for each PE II.

Proof. See Davis/Maschler [ 1967] and Peleg [ 1967].

As a result II (M~i)) = II. The bargaining set is a natural payoff solution concept to
study the solutions Jo and Ko for the following reasons:
(i) the bargaining set for each c.s. consists of payoffs that are stable in the sense
of objections and counter-objections. If for a particular c.s., a payoff is not in
the bargaining set, some player would have a justified objection (an objection
that has no counter-objection) which when carried out would result in breakup
of the coalition structure. Hence we are not justified in using unstable payoffs
corresponding to a c.s. to dominate another c.s. Also,
(ii) the bargaining set is nonempty for each coalition structure.
We shall now de t ermine Ko(M (i)
1 ) for all 3-person games with side payments.
Consider the 3-person game given by N = (1,2,3},

v(1) = v(2) = v ( 3 ) = 0, v(12) = a, v(13) = b, v ( 2 3 ) = c,

and (8.2)
v(123) = d, where O~<a ~<b ~<c andd>~ O.

Theorem 8.2. Let F be a 3-person game as in (8.2) with d > (a + b + c)/2.

(i) ]fd < c , then Ko(M~i)) = ((1) (23))
(ii) I f d = e, thenKo(M~ i)) = ((1) (23), (123))
(iii) I f d > c , thenKo(Mli) ) = ((123)).

Proof:
(i) In this case we have (a + b)/2 + c/2 < d < c/2 + c/2, hence a + b < c. The
bargaining set is given by

(o, 0, o) if P = (1) (2) (3),

(0, a, 0) if ]9 = (12) (3),
= (0, o, b) if/9 = (13) (2), (8.3)
Conv{(0, c -- b, b), (0, a, c - a)) if/9 = (1) (23),
(0, d / 2 - (b -- a)/2, d / 2 + (b -- a ) / 2 ) if P = (123)
156 P.P. Shenoy

Clearly (1) (23) dom(M~i)) (12) (3) and (1) (23) dom(M~i)) (13) (2). Also since
(0, c/2 -- (b --a)12, c/2 + (b -- a)12) E M~i)((1) (23)) and c > d ,
(1) (23) dom(M~i)) (123). The transition graph is shown in Figure 8.1. Hence
Case (i) follows.
(ii) In this case, the bargaining set is as in (8.3) except for c.s. (123) which is
M~i) ((123)) = M~i)((1) (23)).

Therefore (ii) follows. (See Figure 8.2.)

(iii) Case l ) c > a + b
Here the bargaining set is as in (8.3) except for c.s. (123) which is given by

M~i)((123)) = ( ( x t , x 2 , x 3 ) : X l + x2 ~ a , x t + x3 ~ b , x2 + x3 ~ c , and
xt +x2 +x3 = d ) .
For each (0, x2, c -- x2 ) E M~i) ((1) (23)) where a ~<x2 < c -- b, we have
((d - c)/3, x2 + (d - c)/3, c - - x 2 + (d - c)/3) E M~i)((123)). Hence
(123) dom(M~i)) (1) (23). The transition digraph is shown in Figure 8.3.
(iii) Case 2) c <~a + b
In this case the bargaining set is given by

(0, o, o) if p = (1) (2) (3),

(Pt, P2, 0) if P = (12)(3),
M~i)(P) = (/71,0, p3) if P = (13) (2), (8.4)
(0,p3,p3) if P = (1) (23),
Co((123)) if P = (123).
where pt = (a + b - c ) / 2 , p 2 = (a + c - - b ) / 2 , p 3 = (b + c --a)/2, and
Co((123)) = ( ( x l , x 2 , x 3 ) : x l + x2 >~a, x l + x3 >~b, x2 + x3 >~c,
andxt +x2 +x3 =d}.
Letp = (Pl +P2 +P3), then clearly,
(p~ + ( d - p ) / 3 , p 2 + ( d - - p ) / 3 , p 3 + ( d - - p ) / 3 ) E M~i)((123))

Hence c.s. (123) dominates (w.r.t. Mt(i) ) every other c.s. This case completes the
proof of the theorem. []
Theorem 8.3. Let F be a 3-person game as in (8.2) with d = (a + b + c)/2.
(i) If c ~<a + b {(12) (3), (13) (2), (1) (23), (123)).
(ii) Ifc>a+b -((1)(23)).

Proof:
(i) In this case, the bargaining set is as in (8.4) with MIi)((123)) = (Pl, P2, P3). The
result clearly follows.
(ii) In this case, the bargaining set is as in (8.3). Since d < c, the result follows. []
 On Coalition Formation 15 7

(i)(2)(3)

(12){3)~ ( 1 2 3 )

(13)( - v 23)
Fig. 8.1: The transition digraph in Theorem 8.2, (i), and in Theorem 8.4, (ii)

(i)(2)(3)

(12)(3) 9 (123)

(13)(2) : ~ . (i)(23)

Fig. 8.2: The transition digraph in Theorem 8.2, (ii)

(i)(2)(3)

(12)(3) ~ - ( 1 2 3 )

(13)(2) (i)(23)
Fig. 8.3: The transition digraph in Theorem 8.2, (iii) case 1)

Theorem 8.4. Let F be a 3-person game as in (8.2), with d < (a + b + c)/2.

(i) I f c ~<a + b then Ko(id~ i)) = ((12) (3), (13) (2), (1) (23)).
(ii) I f c > a + b then Ko(M~i)) = ((1) (23)).

~oof:
(i) In this case, the bargaining set is as in (8.4) except for c.s. (123) for which it is
given by
158 P.P. Shenoy

I (Px + (d--p)/3,p2 + (d--p)/3,p3 + (d-p)/3)

if2c-a-b<~d
M{i) ((123)) = 3 (0, d/2 -- (b --a)/2, d/2 + (b --a)/2) (8.5)

[ (0, 0,d)
ifb-a~d<2e-a-b
i f d < b --a.

In all cases, the transition graph is presented in Figure 8.4. Therefore (i) follows.
(ii) In this case the bargaining set is as in (8.3) except for c.s. (123) for which the
bargaining set is as in (8.5). The transition graph is shown in Figure 8.1. Hence
the result follows. []
/~(3)

(12)(3)-- / ~~ (123)

/
(13)(2)~
. . J \ /
~(i)(23)
Fig. 8.4: The transition graph in Theorem 8.4, (i)

Since Theorems 8.2, 8.3 and 8.4 cover all cases, we have proved the following.

Theorem 8.5. Let F be a 3-person game asin (8.2). Then Ko(M~i)) 4: 0.

For every P 6 II, i f x EI(P) belongs to Co(P), then no player can have an objection
against another player. Thus if Co(P) 4: 0, Co(P) c M~i)(P).Hence the p.s.c. M~i)
satisfies the hypothesis of Corollary 6.2. So we obtain the following.

Lemma 8. 6. Let F be an n-person game. If II (Co) 4: O then Ko (M~i)) 4: O. In fact

Ko(M
Proof: This is a consequence of Corollary 6.2 and Theorem 6.3. []
.,1(i)
NO general existence theorem for KoU~ 1 is known at this time. Example 8.1 illus-
trates a pathology for Ko(M{i)) which is due to a "flaw" in the properties of the
bargaining set.

Example 8.1. Let P be a 3-person veto player game with

v(12) = v(13) = v(123) = 1, v(R) = 0 for all other R C N .

Observe that player 1 is a veto player because all coalitions that doe not contain
player 1 are losing coalitions. However, player 1 is not a dictator since he needs either
player 2 or player 3 (or both) to form a winning coalition. The bargaining set of this
game is given by
 On Coalition Formation 159

(1, 0, 0) if P = (123), (12) (3) or (13) (2)

M~i)(P) = (0, 0, 0) for all other P in II.

Note that in every c.s. that contains a coalition which has a positive value, at least one
player in the coalition gets zero payoff in the bargaining set. As a result, due to Condi-
tion (3.5) in the definition of domination, no c.s. dominates another c.s. Hence
K0 i)) = n.
The above example exhibits a flaw in the properties of the bargaining set. E.g., in
the c.s. (12) (3) player 2 gets zero payoff in the bargaining set. This is because player 2
has no 'bargaining power' at all vis-a-vis player I. Since there are no coalitions with a
positive value that contains player 2 but not player 1, player 2 cannot even object!
However the payoff in the bargaining is counter-intuitive because we could argue: Why
should player 2 enter into a coalition with player 1 if his share of the resulting coali-
tional value is the same as what the player could have obtained had he been in a coali-
tion by himself?. In this respect, we could say that the bargaining set is derived entirely
from the bargaining positions of the players in the process of coalition formation in
contrast with the Shapley value which is derived entirely from the characteristic
function of the game. These two p.s.c.'s reflect two extreme view points in looking at
solutions of cooperative games in characteristic function form. A major research prob-
lem is to define a p.s.c, that exhibits both the strategic value and the bargaining power
of the players.
One method of attacking this problem in the case of the bargaining set is to regard
the bargaining set as an idealization (of the bargaining process) and relax the definition
of an objection by e, where e is a small positive real number. More formally, let
x E l ( P ) and i a n d / b e two distinct players in a coalition P k E P. An e-ob/ecth)n of
i against ] is a vector y R , where R is a coalition containing player i but not/, whose
coordinatesy t satisfy y i > x i + e, Yt >~Xl for all l E R , and t~R Yl = v(R). A counter-

objection to this e-objection is defined as before. We say x EI(IV) is e-stable if for

each e-objection in x, there is a counter-objection. The e-bargaining set, denoted by
M~i?e, corresponding to c.s. iv EII is the set of all e-stable x E l ( i v ) , i.e.,

M~i,)(P) = (x EI(/)): x is e-stable}. (8.6)

We could regard e as a 'sacrifice' each player is willing to make (if necessary) for
coalitional stability.
Note that the results in Theorems 8.2, 8.3, 8.4 and 8.5 as well as Lemma 8.6 remain
unchanged if we replace M~i) by Mti,)e.

E x a m p l e 8.2. Consider the game in Example 8.1. The e-bargaining set is given by

S) Denotestheset{(x l, x=, x3) : xl = l -- x= -- x a, O ~ x 2 <. e, O ~ x 3 ~ e}.

160 P.P. Shenoy

(1 --x2 --x3, O~<x2 ~<e, O~<x3 ~<e) it"a) P = (123)

/--t
(1 -x2,0~<x2 ~<e, O) if P =(12)(3)
M~',',(P)= (1--x3,0, O<~x3<~e) if P =(13)(2)
(o, o, o) for all other P in H.
It is clear that Ko (M~i,)) = {(123), (12) (3), (13) (2)} which is more intuitive than
ro(M~ i) ) = n.

Example 8.3. (The Chemical Company Game. See Anderson/Traynor [1962]). Two
chemical companies C1 and C2 supply two fabricating companies F~ and F:. The
permissible coalition structures are:

PI = (C1) (C~) (F~) (F21, P2 =(C1F1)(C2)(F2),

P3 = (ClF2) (C2) (Fl), P4 = (Cl)(C2F1)(F2),
Ps = (el) (C2F2) (F~), P6 = (ClFx)(C2F2),
P7 = (ClF2) (C2F1).
The respective payoffs (profits) to these coalitions in the particular coalition structures
are:

Px: 25,15, 75,100. P2:300,25,110.

P3 500,30,85. P4: 28,200, 105.
Ps:30,425,90. P6:400,600.
PT: 700,300.
This"partitionfuncfion"inducesthe charac~risticfunction:
v(Cl) = 25, v(C2) = 15, v(F1) = 75, v(F2) = 100, v(Ca, F1) = 300,
v(CI,F2) = 500, v(C2, Fl) = 200, v(C2,F2)= 425.
The bargainingset M~i)is ~ven by

(25,15,75,100) if P = P1
(115<xl < 2 2 5 , 1 5 , 3 0 0 - x 1 , 1 0 0 ) ifP=P2
( 9 0 < x l ~< 225,15,75,500--xl) if P = P3
(25,15 ~x2 ~ 125,200-x2,100) if P = P4
M~i)(p) =
(25,15 ~x2 ~ 125,75,425--x2) if P = Ps
(xa,x2,300--Xl,425--x2) if P = P6
where x~,x: are asin Figure8.5.
(yl,y2,200--y2,500--yl) if P = P7
whereyl,y2are asin Figure 8.6.
 On Coalition Formation 161

~2

125

15,
/
!
90
I
115
I I
200 225
~-- Yl
Fig. 8.5: The bargaining set --a_--_M~,)(/~6
the chemical company game
) for

x2

xl Fig. 8.6: The bargaining set M~')[

' J; - -VT)for
--
I! !
90 115 225 the chemical company game

The transition digraph is shown in Figure 8.7. Hence K0(M~i)) = {(C1FI) (C2F2),
(CIF2) (C2F, )}. Pl

P 7

P4 P5
Fig. 8.7: The transition digraph of the chemical company game
162 P.P. Shenoy

9. Some Modifications of the Coalition Structure Model

In this section, we look at some modifications of the domination relation in the

abstract game (II(S), dom(S)). We def'me two other domination relations one of
which is stronger than dom(S) and the other weaker than dom(S).

Definition 9.1. Let Pl, P2 E l i ( S ) and S be a p.s.c. Then P1 weakly dominates P2,
denoted by P1 w-dom(S) Pz, iff

for eachy E S (P2), 3 a nonempty R E P1 and x E S (P I ) (9.1)

such thatx i >Yi for all i ER.

Definition 9.2. Let PI, P2 E II(S) and S be a p.s.c. Then P1 strongly dominates P2,
denoted by P1 s-dora(S) P2, iff 3 a nonempty R E P1 and x E S(PI ) such that for
ally E S(P~), x i >Yi for all i E R .
The following relations are direct consequence of Definitions 3.6, 9.1 and 9.2.

If P1 s-dora(S) P2, then P1 dom(S) P2- (9.2)

If P1 dom(S) P2, then P1 w-dom(S) P2- (9.3)

Let KO, w (S) and KO,s(S ) denote the cores of the abstract games (II(S), w-dom(S))
and (H(S), s-dom(S)) respectively. As a consequence of Relations (9.2) and (9.3), we
have

Ko,s(S) D Ko (S) D KO, w (S). (9.4)

Also, if S is a p.s.c, such that for each P E H, S(P) is either a single point set in
E n or an empty set, then

K0,s (S) = Ko (S) = K0, w (S). (9.5)

Appendix: The Aumann-Dreze Generalization of the Shapley Value for all Simple
Games with Four or Fewer Players

The table on the following page contains all distinct proper simple games of four
or fewer players excluding dummies. All winning coalitions are listed - the minimal
winning coalitions are listed first and separated from the rest by a semicolon. The
weighted voting representation given in column 4 are the simplest ones. The Shapley
value (D of a c.s. depends only on the winning coalition contained in the c.s. The
Shapley value of all c.s.'s containing winning coalitions, in the sequence as in column
3, is given in column 5. The Shapley value of a c.s. not containing any winning coali-
tion is zero for each player and therefore is not given in column 5. Column 6 contains
all c.s.'s in Ko(~) identified by the winning coalition it contains. The last column
indicates whether the game exhibits the paradox of smaller coalitions or not.
 Number of Weighted Voting
Players W Representation K e (cb) Paradox?
A [1;11 (1) A no
AB [2; 1,11 (1/2, 1/2) AB no
ABC 13;1,1,11 (1/3, 1/3, 1/3) ABC no
AB, AC; ABC [3; 2,1,11 (1/2, 1/2, 0), (1/2, O, 1/2), (2/3, 1/6, 1/6) AB, AC, ABC yes
AB, AC, BC; 12;1,1,11 (1/2, 1/2, 0), (1/2, O, 1/2), (0, 1/2, 1/2). AB, AC, BC no
ABC. (1/3, 1/3, 1/3)
ABCD [4; 1,1,1,11 (1/4, 1/4, 1/4, 1/4) ABCD no

ABC, ABD; [5;2,2,1,11 (1/3, 1/3, 1/3, 0), (1/3, 1/3, O, 1/3), ABC, ABD yes
ABCD (5/12, 5/12, 1/12, 1/12) ABCD
ABC, ABD [4; 2,1,1,11 (1/3, 1/3, 1/3, 0), (1/3, 1/3, O, 1/3), ABC, ABD yes
ACD; ABCD (1/3, O, 1/3, 1/3), (1/2, 1/6, 1/6, 1/6) ACD, ABCD o
ABC, ABD, [3; 1,1,1,11 (1/3, 1/3, 1/3, 0), (1/3, 1/3, O, 1/3), ABC, ABD, no
0
ACD, BCD; (1/3, O, 1/3, 1/3), (0, 1/3, 1/3, 1/3), ACD, BCD
ABCD (1/4, 1/4, 1/4, 1/4)
AB, ACD; [5; 3,2,1,11 (1/2, 1/2, O, 0), (1/3, O, 1/3, 1/3), AB, ABD, yes
ABD, ABC, (1/2, 1/2, O, 0), (1/2, 1/2, O, 0), ABC, ABCD .,.rl
o
ABCD (7/12, 3/12, 1/12, 1/12)
AB, ACD, [4; 2,2,1,11 (1/2, 1/2, O, 0), (1/3, O, 1/3, 1/3), AB, ABD, ABC no
0
BCD; ABD (0, 1/3, 1/3, 1/3), (1/2, 1/2, O, O)
ABC, ABCD (1/2, 1/2, O, 0), (1/3, 1/3, 1/6, 1/6)
AB, AC, [5; 3,2,2,11 (1/2, 1/2, O, 0), (1/2, O, 1/2, 0), AB, ABD, ABC, yes
BCD; ACD, (0, 1/3, 1/3, 1/3), (1/2, O, 1/2, 0), AC, ACD
ABD, ABC, (1/2, 1/2, O, 0), (2/3, 1/6, 1/6, 0),
ABCD (5/12, 3/12, 3/12, 1/12)
AB, AC, AD; 14; 3,1,1,11 (1/2, 1/2, O, 0), (1/2, O, 1/2, 0), ABC, ABD, ACD, yes
ABC, ABD, (1/2, O, O, 1/2), (2/3, 1/6, 1/6, 0), ABCD
ACD, ABCD (2/3, 1/6, O, 1/6), (2/3, O, 1/6, 1/6),
(9/12, 1/12, 1/12, 1/12)
AB, AC, AD, 13;2,1,1,11 (1/2, 1/2, O, 0), (1/2, O, 1/2, 0), yes
BCD;ABC, (1/2, O, O, 1/2), (0, 1/3, 1/3, 1/3),
ABD, ACD, (2/3, 1/6, 1/6, 0), (2/3, 1/6, O, 1/6),
ABCD (2/3, O, 1/6, 1/6), (1/2, 1/6, 1/6, 1/6)
Tab. AI: The Aumann-Dreze generalization of the Shapley alue for simple games
164 P.P. Shenoy

References

Anderson, S.L., and E.A. Traynor: An application of the Aumann-Maschler n-person cooperative
game. Recent Advances in Game Theory. Ed. by M. Maschler. Princeton 1962, 265-270.
Aumann, R.J., and J. Dreze: Cooperative games with coalitiotl structures. International Journal of
Game Theory 3, 1974, 217-237.
Aumann, R.s and M. Maschler: The bargaining set for cooperative games. Annals of Mathematics
Study 52, 1964, 443-476.
Bondareva, O.N. : Theory of the core in the n-person game. Leningrad State University Vestnik L.
G. U. 13, 1962, 141-142. (In Russian.)
-: Some applications of linear programming methods to the theory of cooperative games.
Problemy Kibernetiki 10, 1963, 119-139. (In Russian.)
Brains, S.Z: Paradoxes in Politics. New York 1976.
Davis, M., and M. Maschler: Existence of stable payoff configurations for cooperative games.
Essays in Mathematical Economics in Honor of Oskar Morgenstern. Ed. by M. Shubik. Princeton
1967, 39-52.
Gamson, Ir : A theory of coalition formation. American Sociological Review 26, 1961, 373-382.
Gillies, D.B. : Solutions to general non-zero-sum games. Annals of Mathematics Study 40, 1959,
47-85.
Harary, F. : Graph Theory. Massachusetts 1959.
Kalai, E., E.A. Pazner and D. Schmeidler: Collective choice correspondences as admissible outcomes
of social bargaining processes. Econometrica 44, 1976, 2 2 3 - 240.
Lucas, W.F.: A game with no solution. Bull. Amer. Math. Soc. 74, 1968, 237-239.
- : A proof that a game may not have a solution. Trans Amer. Math. Soc. 137, 1969, 219-229.
Lucas, Ir and J.C. Maceli: Discrete partition function games. Game Theory and Political Science.
Ed. by P. Ordeshook. New York 1978, 191-213.
Peleg, B. : Existence theorem for the bargaining set. Essays in Mathematical Economics in Honor
of Oskar Morgenstern. Ed. by M. Shubik. Princeton 1967, 5 3 - 7 6 .
Riker, Ir and P. Ordeshook: An Introduction to Positive Political Theory. New York 1973.
Shapley, L, S. : A value for n-person games. Annals of Mathematics Study 28, 1953, 3 0 7 - 317.
- : Simple games: An outline of the descriptive theory. Behavioral Science 7, 1962, 5 9 - 6 6 .
- : On balanced sets and cores. Naval Research Logistics Quarterly 14, 1967, 4 5 3 - 4 6 0 .
Shapley, L.S., and M. Shubik: A method for evaluating the distribution of power in a committee
system. Amer. Political Science Review 48, 1954, 787-792.
Shenoy, P.P. : A dynamic solution concept for abstract games. Mathematics Research Center, Tech-
nical Summary Report No. 1804, University of Wisconsin, Madison 1977a.
- : On game theory and coalition formation. School of Operations Research and Industrial Engi-
neering, Cornell University, Technical Report No. 342, New York, 1977b.
- : On coalition formation in simple games: A mathematical analysis of Caplow's and Gamson's
theories. Journal of Mathematical Psychology 18, 1978, 177-194.
Thrall, R.M., and Ir Lucas: n-person games in partition function form. Naval Research Logistics
Quarterly 10, 1963, 281-298.
Von Neumann, J., and O. Morgenstern: Theory of Games and Economic Behavior. Princeton 1944,
3rd edition, 1953.

Received May, 1978

(revised version June, 1979)