Winter 2002

Chapter 53
THE SHAPLEY VALUE
EYAL WINTER
Center for Rationality & Interactive Decision Theory, Hebrew University of Jerusalem,
Jerusalem, Israel
Contents
1. Introduction 2027
2. The framework 2028
3. Simple garnes 2030
4. The Shapley value as a von Neumann-Morgenstern utility function 2031
5. Alternative axiomatizafions of the value 2033
6. Sub-classes of garnes 2037
7. Cooperation structures 2039
8. Sustaining the Shapley value via non-cooperative garnes 2045
9. Practice 2049
9.1. Measuring states' power in the U.S. presidential election 2049
9.2. Allocation of costs 2051
References 2052
Handbook of Garne Theory, Volume 3, Edited by R.J. Aumann and S. Hart

© 2002 Elsevier Science B.V. All rights reserved
2026 E. Winter
Abstract
This chapter surveys some of the literamre in game theory that has emerged from Shap-
ley's seminal paper on the Value. The survey includes both contfibutions which offer
different interpretations of the Shapley value as well as several different ways to char-
acterize the value axiomatically. The chapter also surveys some of the literature that
generalizes the nofion of the value to situations in which a priori cooperation structure
exists, as well as a different literature that discusses the relation between the Shapley
value and models of non-cooperative bargaining. The chapter concludes with a discus-
sion of the applied side of the Shapley value, primarily in the context of cost allocation
and voting.
Keywords
Shapley value, cooperative games, coalitions, cooperation structures, voting
J E L classification: C71, D72

Ch. 53: The Shapley Value 2027
1. Introduction
To promote an understanding of the importance of Shapley's (1953) paper on the

value, we shall start nine years earlier with the groundbreaking book by von Neumann
and Morgenstern that laid the foundations of cooperative garne theory. Unlike non-
cooperative garne theory, cooperative garne theory does not specify a garne through
a minute description of the strategic environment, including the order of moves, the
set of actions at each move, and the payoff consequences relative to all possible plays,
but, instead, it reduces this collection of data to the coalitional form. The cooperative
garne theorist must base his prediction strictly on the payoff opportunities, conveyed
by a single real number, available to each coalition: gone are the actions, the moves,
and the individual payoffs. The chief advantage of this approach, at least in multiple-
player environments, is its practical usefulness. A real-life situation fits more easily
into a coalitional form garne, whose structure has proved more tractable than that of a
non-cooperative garne, whether that be in normal or extensive form.
Prior to the appearance of the Shapley value, one solution concept alone ruled the
kingdom of (cooperative) garne theory: the von Neumann-Morgenstern solution. The
core would not be defined until around the same time as the Shapley value. As set-valued
solutions suggesting "reasonable" allocations of the resources of the grand coalition,
the von Neumann-Morgenstern solution and the core both are based on the coalitional
form garne. However, no single-point solution concept existed as of yet by which to
associate a single payoff vector to a coalitional form garne. In fact the coalitional form
game of those days had so little information in its black box that the creation of a
single-point solution seemed untenable. It was in spite of these sharp limitations that
Shapley came up with the solution. Using an axiomatic approach, Shapley constructed
a solution remarkable not only for its attractive and intuitive definition but also for its
unique characterization by a set of reasonable axioms. Section 2 of this chapter reviews
Shapley's result, and in particular a version of it popularized in the wake of his original
paper. Section 3 turns to a special case of the value for the class of voting garnes, the
Shapley-Shubik index.
In addition to a model that attempts to predict the allocation of resources in multi-
person interactions, Shapley also viewed the value as an index for measuring the power
of players in a game. Like a price index or other market indices, the value uses averages
(or weighted averages in some of its generalizations) to aggregate the power of players
in their various cooperation opportunities. Alternatively, one can think of the Shapley
value as a measure of the utility of players in a garne. Alvin Roth took this interpretation
a step further in formal terms by presenting the value as a von Neumann-Morgenstern
utility function. Roth's result is discussed in Section 4.
Section 5 is devoted to alternative axiomatic characterizations of the Shapley value,
with particular emphasis on Young's axiom of monotonicity, Hart and Mas-Colell's
axiom of consistency, and the last-named pair's notion of potential (arguably a single-
axiom characterization).
2028 E. Winter
To be able to apply the Shapley value to concrete problems such as voting situations,
it is important to be able to characterize it on sub-classes of garnes. Section 6 discusses
several approaches in that direction. Section 7 surveys several attempts to generalize the
Shapley value to a framework in which the environment is described by some a priori
cooperation structure other than the coalitional form garne (typically a partition of the
set of players). Aumann and Drèze (1975) and Owen (1977) pioneered examples of
such generalizations.
While the Shapley value is a classic cooperative solution concept, it has been shown
to be sustained by some interesting strategic (bargaining) garnes. Section 8 looks at
some of these results. Section 9 closes the chapter with a discussion of the practical im-
portance of the Shapley value in general, and of its role as an estimate of parliamentary
and voter power and as a rule for cost allocation in particular.
Space forbids discussion of the vast literature inspired by Shapley's paper. Certain of
these topics, such as the various extensions of the value to NTU garnes, and the values
of non-atornic garnes to emerge from the seminal book by Aumann and Shapley (1974),
are treated in other chapters of this Handbook.
2. The framework
Recall that a coalitionalform game (henceforth game) on a finite set of players N =

{1, 2, 3 . . . . , n} is a function v from the set of all coalitions 2 N to the set of real numbers
R with v(0) = 0. v(S) represents the total payoff or rent the coalition S can get in the
garne v.
A value is an operator ~b that assigns to each garne v a vector of payoffs q5(v) =
(~bl, (b2 ..... ~ßn) in IRn. q~i(v) stands for i's payoff in the garne, or altematively for the
measure of i's power in the game.
Shapley presented the value as an operator that assigns an expected marginal contri-
bution to each player in the garne with respect to a uniform distribution over the set of
all permutations on the set of players. Specifically, letzr be a permutation (or an order)
on the set of players, i.e., a one-to-one function from N onto N, and let us imagine the
players appearing one by one to collect their payoff according to the order fr. For each
player i we can denote by pi7E = {j: 7r(i) > 7c(j)} the set of players preceding player
i in the order re. The marginal contribution of player i with respect to that order rc is
v(p i U i) - v ( p i ) . Now, if permutations are randomly chosen from the set/7 of all per-
mutations, with equal probability for each one of the n ! permutations, then the average
marginal contribution of player i in the garne v is
cki(v) = l/n! ~_ù [v (p~Ui i ) - v ( p i ) ] , (1)

7cE/7
which is Shapley's definition of the value.

While the intuitive definition of the value speaks for itself, Shapley supported it by
an elegant axiomatic characterization. We now impose four axioms to be satisfied by a
value:
The first axiom requires that players precisely distribute among themselves the re-
sources available to the grand coalition. Namely,
EFFICIENCY. Y~'iöN q~i(V) = v ( N ) .
The second axiom requires the following notion of symmetry:

Players i, j c N are said to be symmetric with respect to garne v if they make the
same marginal contribution to any coalition, i.e., for each S C N with i, j ~ S, v(S U
i) = v(S U j). The symmetry axiom requires symmetric players to be paid equal shares.
SYMMETRY. l f players i and j are symmetric with respect to garne v, then qbi (V) =
4~j(v).
The third axiom requires that zero payoffs be assigned to players whose marginal
contribution is null with respect to every coalition:
DUMMY. If i is a dummy player, i.e., v(S U i) - v(S) = 0 for every S C N, then

4~i (v) = O.
Finally, we require that the value be an additive operator on the space of all garnes,
i.e.,
ADDITIVITY. (b(v + to) = ~b(v) + ~(w), where the garne v + w is defined by (v +

w)(S) -~ v(S) + w(S) f o r all S.
Shapley's amazing result consisted in the fact that the four simple axioms defined
above characterize a value uniquely:
THEOREM 1 [Shapley (1953)]. There exists a unique value satisfying the efficiency,
symmetry, dummy, and additivity axioms: it is the Shapley value given in Equation (1).
The uniqueness result follows from the fact that the class of games with n players
forms a 2 n- 1-dimensional vector space in which the set of unanimity garnes constitutes
a basis. A garne uR is said to be a unanimity garne on the domain R if un(S) -= 1,
whenever R C S and 0 otherwise. It is clear that the dummy and symmetry axioms
together yield a value that is uniquely determined on unanimity garnes (each player in
the domain should receive an equal share of 1 and the others 0). Combined with the
additivity axiom and the fact that the unanimity games constitute a basis for the vector
space of garnes, this yields the uniqueness result.
2030 E. Winter
Here it should be noted that Shapley's original formulation was somewhat different
from the one described above. Shapley was concerned with the space of all games that
can be played by some large set of potential players U, called the universe. For every
game v, which assigns a real number to every finite subset of U, a carrier N is a
subset of U such that v(S) = v(S M N) for every S C U. Hence, the set of players who
actually participate in the game must be contained in any carrier of the garne. If for
some carrier N a player i is not in N, then i must be a dummy player because he does
not affect the payoff of any coalition that he joins. Shapley imposed the carrier axiom
onto this framework, which requires that within any carrier N of the garne the players
in N share the total payoff of v (N) among themselves, lnterestingly, this axiom bundles
the efficiency axiom and the dummy axiom into one property.
3. Simple games
Some of the most exciting applications of the Shapley value involve the measurement of
political power. The reason why the value lends itself so well to this domain of problems
is that in many of these applications it is easy to identify the real-life environment with
a specific coalitional form game. In politics, indeed in all voting situations, the power
of a coalition comes down to the question of whether it can impose a certain collective
decision, or, in a typical application, whether it possesses the necessary majority to
pass a bill. Such situations can be represented by a collection of coalitions W (a subset
of 2N), where W stands for the set of "winning" coalitions, i.e., coalitions with enough
power to impose a decision collectively. We call these situations "simple garnes". While
simple garnes can get rather complex, their coalitional function v assumes only two
values: 1 for winning coalitions and 0 otherwise (see Chapter 36 in this Handbook). If
we assume monotonicity, i.e., that a superset of a winning coalition is likewise winning,
then the players' marginal contributions to coalitions in such garnes also assume the
values 0 and 1. Specifically, player i's marginal contribution to coalition S is 1 if by
joining S player i can turn the coalition from a non-winning (or losing) to a winning
coalition. In such cases, we can say that player i is pivotal to coalition S. Recalling the
definition of the Shapley value, it is easy to see that in such garnes the value assigns
to each player the probability of being pivotal with respect to his predecessors, where
orders are sampled randomly and with equal probability. Specifically,
d?i(v) = [{rc E 17; p i Ui ~ W a n d p / ¢ w } l / n ! .
This special case of the Shapley value is known in the literature as the Shapley-Shubik
index for simple games [Shapley and Shubik (1954)].
A very interesting interpretation of the Shapley-Shubik index in the context of voting
was proposed by Straffin (1977). Consider a simple (voting) garne with a set of winning
coalitions W representing the distribution of power within a committee, say a parlia-
ment. Suppose that on the agenda are several bills on which players take positions. Let
us take an ex a n t e point of view (before knowing which bill will be discussed) by as-
suming that the probability of each player voting in favor of the bill is p (independent
over i). Suppose that a player is asking himself what the probability is that his vote will
affect the outcome. Put differently, what is the probability thät the bill will pass if and
only if I support it? The answer to this question depends on p (as well as the distribution
of power W). If p is 1 or 0, then I will have no effect unless I am a dictator. But because
we do not know which bill is next on the agenda, it is reasonable to assume that p itself
is a random variable. Specifically, let us assume that p is distrihuted uniformly on the
interval [0, 1]. Straffin points out that with this model for random bills the probability
that a player is effective is equivalent to his Shapley-Shubik index in the corresponding
garne (see Chapter 32 in this Handbook). We shall demonstrate this with an example.
EXAMPLE. Let [3; 2, 1, 1] be a weighted majority garne, 1 where the minimal winning
coalitions are {1, 2} and {1,3 }. Player 2 is effective only if player 1 votes for and player 3
votes against. For a given probability p of acceptance, this occurs with probability p (1 -
p). Since 2 and 3 are symmetric, the same holds for player 3. Now player l's vote is
ineffective only if 2 and 3 both vote against, which happens with probability (1 - p)2.
Thus player I is effective with probability 2p - p2. Integrating these functions between
0 and 1 yields q~l = 2/3, ~b2 = ~b3 = 1/6.
It is interesting to note that with a different probability model for bills one can derive
a different well-known power index, namely the Banzhaf index (see Chapter 32 in this
Handbook). Specifically, if player k's probability of accepting the bill is Ph, and if
p l . . . . . Pn are chosen independently, each from a uniform distribution on [0, 1], then
player i's probability of being effective coincides with his Banzhaf index.
4. The Shapley value as a von Neumann-Morgenstern utility function
If we interpret the Shapley value as a measure of the benefit of "playing" the garne (as
was indeed suggested by Shapley himself in his original paper), then it is reasonable to
think of different positions in a garne as objects for which individuals have preferences.
Such an interpretation immediately gives rise to the following question: What properties
should these preferences possess so that the cardinal utility function that represents them
coincides with the Shapley value? This question is answered by Roth (1977).
Roth defined a position in a garne as a pair (i, v), where i is a player and v is a garne.
He then assumed that individuals have preferences defined on the mixture set M that
contains all positions and lotteries whose outcomes are positions. Using " ~ " to denote
indifference and ">-" to denote strict preference, Roth imposed several properties on
preferences. The first two properties are simple regularity conditions:
1 In a weighted majority garne [q; wI . . . . . ton], a coalition S is winning if and ordy i f EiES Wi ~ q"
2032 E. Winter
A1. Let v be a garne in which i is a dummy. Then (i, v) ~ (i, vo), where vo is the null
garne in which every coalition earns zero. Furthermore, (i, vi) >- (i, vo), where vi is the
game in which i is a dictator, i.e., vi ( S) -= 1 if i ~ S and vi ( S) = 0 otherwise.
The second property, which relates to Shapley's symmetry axiom, requires that indi-
vidual preferences not depend on the names of positions, i.e.,
A2. For any garne v and permutation yr, (i, v) ~ (yr(i), 7g(l))). 2
The two remaining properties are more substantial and deal with players' attitudes
towards risk. The first of these properties requires that the certainty equivalent of a
lottery that yields the position i in either garne v o r game w (with probabilities p and
1 - p) be the position i in the garne given by the expected value of the coalitional
function with respect to the same probabilities. Specifically, for two positions (i, v)
and (i, w), we denote by Ip(i, v); (1 - p)(i, w)] the lottery where (i, v) occurs with
probability p and (i, w) occurs with probability 1 - p.
A3. Neutrality to Ordinary Risk: (i, ( p w + (1 - p ) v ) ) ~ [p(i, w); (1 - p)(i, v)].
Note that a weaker version of this property requires that (i, v) ~ [(1/c)(i, cv); (1 -
1/c)(i, v0)] for c > 1. It can be shown that this property implies that the utility
function u, which represents the preferences over positions in a garne, taust satisfy
u(cv, i) = cu(v, i).
The last property asserts that in a unanimity game with a carrier of r players the utility
of a uon-dummy player is 1 / r of the utility of a dictator. Specifically, let vR be defined
by VR (S) = 1 if R C S and 0 otherwise.
A4. Neutrality to Strategic Risk: (i, VR) ~ (i, ( 1 / r ) v i ) .
An elegant result now asserts that:
THEOREM [Roth (1977)]. Let u be a von Neumann-Morgenstern utility function over

positions in garnes, which represents preferences satisfying the f o u r axioms. Suppose
that u is normalized so that u(i, vi) = 1 and ui (i, vo) = O. Then u(i, v) is the Shapley
value of player i in the garne v.
Roth's result can be viewed as an alternative axiomatization of the Shapley value.

I will now survey several other chm'acterizations of the value, which, unlike Roth's
utility function, employ the standard concept of a payoff function.
2 fr(v) is the garne with yr(v)(S) = v(re(S)), where re(S) = {j; j = re(i) for some i 6 S}.
5. Alternative axiomatizations of the value
One of the most elegant aspects of the axiomatic approach in game theory is that the
same solution concept can be characterized by very different sets of axioms, sometimes
to the point of seeming unrelated. But just as a sculpture seen from different angles is
understood in greater depth, so is a solution concept by means of different axiomafi-
zations, and in this respect the Shapley value is no exception. This section examines
several alternative axiomatic treatments of the value.
Perhaps the most appealing property to result from Definition (1) of the Shapley value
is that a player's payoff is only a function of the vector of bis marginal contributions to
the various coalitions. This raises an interesting quesfion: Without forgoing the above
property, how far can we depart from the Shapley value? "Not much", according to
Young (l 985), whose finding also yields an alternative axiomatization of the value.
For a garne v, a coalition S, and a player i ¢ S, we denote by Di (v, S) player i's
marginal contribution to the coalition S with respect to the garne v, i.e., D i (v, S) =
v(S U i) - v(S). Young introduced the following axiom:
STRONG MONOTONICITY. Suppose that v and w are two games such that f o r some
i c N Di (v, S) >/Di (w, S). Then cBi(v) ». ~)i (W).
Young then showed that this property plays a central role in the characterization of
the Shapley value. Specifically,
THEOREM [Young (1985)]. There exists a unique value Ó satisfying strong monotonic-
ity, symmetry, and efficiency, namely the ShapIey value.
Note that Young's strong monotonicity axiom implies the marginality axiom, which
asserts that the value of each player is only a fnnction of that player's vector of marginal
contributions. Young's axiomatic characterization of the value thus supports the claim
that the Shapley value to some extent is a synonym for the principle of marginal contri-
bution - a time-honored principle in economic theory. But we taust be clear about what
is meant by marginal contribution. In Young's framework, as in Shapley's definition of
the value, players contribnte by increasing the wealth of the coalition they join (or de-
creasing it if contributions are negative). This caused Hart and Mas-Colell (1989) to ask
the following question: Can the Shapley value be derived by referring the players' mar-
ginal contributions to the wealth generated by the entire multilateral interaction, instead
of tediously listing all the coalitions they can join? Offhand, the question sounds some-
what amorphous, for how is one to define an "entire interaction"? Absent a satisfactory
definition, we shall proceed by way of supposition. Suppose each pair (N, v) is associ-
ated with a single real number P ( N , v) that sums up the wealth generated by the entire
interaction in the game. We are already within an ace of defining marginal contributions.
Specifically, player i's marginal contribution with respect to (N, v) is simply:
Dip(N,v) = P(N,v)- P(N \i,v),

2034 E. Winter
where (N \ i, v) is the game v restricted to the set of players N \ i. To be associated

with a measure of power in the game, these marginal contributions need to add up to
the total resources available to the grand coalitions, i.e., v(N). So we will say that P is
a potential function if
Z Di P(N, v) = v(N). (2)

lEN
Moreover, we normalize P to satisfy P(0, v) = 0. Given the mild requirement on p,

there seems to be enough flexibility for many potential functions to exist. The remark-
able result of Hart and Mas-Colell (1989) is that there is in fact only orte potential
function, and it is closely related to the Shapley value. Specifically,
THEOREM [Hart and Mas-Colell (1989)]. There exists a unique potential func-
tion P. Moreover, the corresponding vector of marginal contributions ( D I p ( N, v) . . . . .
D n P(N, v)) coincides with the Shapley value of the garne (N, v).
Let us note that by rewrifing Equation (2) we obtain the following recursive equation:
P(N, v ) = (1/INI)Iv(N) + ~-~ P(N \ i, v)]. (3)

icN
Starting with P(0, v) = 0, Equation (3) determines p recursively. It is interesting to

note that the potential is related to the notion of "dividends" used by Harsanyi (1963)
to extend the Shapley value to garnes without transferable utility. Specifically, let
~ T c N aTur be the (unique) representation of the game (N, v) as a linear combina-
tion of unanimity games. In any unanimity garne u r on the carrier T, the value of each
player in T is the "dividend" dT = ar/[TI, and the Shapley value of player i in the
game (N, v) is the sum of dividends that a player eams from all coalitions of which
he is a member, i.e., ~ ( T ; i e r / d r . Given the definition and uniqueness of the potential
funcfion, it follows that P(N, v) = Y~~TdT, i.e., the total Harsanyi dividends across all
coalitions in the game.
One can view Hart and Mas-CoMl's result as a concise axiomatic characterization of
the Shapley value - indeed, one that builds on a single axiom. In the same paper, Hart
and Mas-Colell propose another axiomatization of the value by a different but related
approach based on the notion of consistency.
Unlike in non-cooperative game theory, where the feasibility of a solution concept is
judged according to strategic or optimal individual behavior, in cooperative garne theory
neither strategies nor individual payoffs are specified. A cooperative solution concept
is considered attractive if it makes sense as an arbitration scheme for allocating costs
or benefits. It comes as no surprise, then, that some of the popular properties used to
support solution concepts in this field are normative in nature. The symmetry axiom is a
case in point. It asserts that individuals indistinguishable in terms of their contributions
to coalitions are to be treated equally. One of the most fundamental requirements of

any legal system is that it be internally consistent. Consider some value (a single-point
solution concept) ~b, which we would like to use as a scheme for allocating payoffs in
games. Suppose that we implement q~ by first making payment to a group of players Z.
Examining the environment subsequent to payment, we may realize that we are facing a
different (reduced) garne defined on the remaining players N \ Z who are still waiting to
be paid. The solution concept q~ is said to be consistent if it yields the players in the re-
duced game exactly the same payoffs they are getting in the original garne. Consistency
properties play an important role in the literature of cooperative game theory. They were
used in the context of the Shapley value by Hart and Mas-Colell (1989). The difference
between Hart and Mas-Colell's notion of consistency and that of the related literature
on other solution concepts lies in their definition of reduced garne. For a given value qS,
a garne (N, v), and a coalition T, the reduced garne (T, v r ) on the set of players T is
defined as follows:
vr (S) = v (S U T «) - ~ q~i(v Isur«) for every S C T,

iŒTc
where VIR denotes the garne v restricted to the coalition R.

The worth of coalition S in the reduced garne Vr is derived as follows. First, the
players in S consider their options outside T, i.e., by playing the garne only with the
complementary coalition T c. This restricts the game v to coalition S U T c. In this game
the total payoff of the members of T c according to the solution Ó is ~ i c T c ~)i (U[SUT «).
Thus the resources left available for the members of S to allocate among themselves are
precisely VT ( S).
A value Ó is now said to be consistent if for every garne (N, v), every coalition T,
and every i c T, one has ~bi (T, Vr) = Ói (N, v).
Hart and Mas-Colell (1989) show that with two additional standard axioms the con-
sistency property characterizes the Shapley value. Specifically,
THEOREM [Hart and Mas-Colell (1989)]. There exists a unique value satisfying sym-
metry, efficiency and consistency, namely the Shapley value. 3
It is interesting to note that by replacing Hart and Mas-Colell's property with a differ-
ent consistency property one obtains a characterization of a different solution concept,
namely the pre-nucleolus. Sobolev's (1975) consistency property is based on the fol-
lowing definition of the reduced garne:
~,~,~~ Qmùx
cN\T
E~~~~,~ iEQ
~~,,~~ ] ~f,~~ ~
3 Hart and Mas-Colell (1989) in fact showedthat instead of the efficiencyand symmetryaxioms it is enough
to require that the solution be "standard" for two-person games, i.e., that for such garnes ~bi ({i, j}, v) =
v(i) + (1/2)[v({i, j}) - v(i) - v(j)].
2036 E. W i n ~ r
v~(S)=~¢i(v) ifS=T, and v~(S)=0 ifS=0.

iET
Note that in Sobolev's definition the members of S evaluate their power in the reduced
garne by considering their most attractive options outside T. Furthermore, the collabo-
rators of S outside T are paid according to their share in the original game v (and not
according to the restricted game as in Hart and Mas-Colell's property). It is surprising
that while the definifions of the Shapley value and the pre-nucleolus differ completely,
their axiomatic characterizations differ only in terms of the reduced game on which the
consistency property is based. This nicely demonstrates the strength of the axiomatic
approach in cooperative garne theory, which not only sheds light on individual solution
concepts, but at the same time exposes their underlying relationships.
Hart and Mas-Colell's consistency property is also related to the "balanced contribu-
tions" property due to Myerson (1977). Roughly speaking, this property requires that
player i contribute to player j ' s payoff what player j contributes to player i's payoff.
Formally, the property can be written as follows:
BALANCED CONTRIBUTION. For every two players i and j, ~i(v) - ~i(VIN\j) :

¢ j (v) -- ~oj (VIN\j).
Myerson (1977) introduced a value that associates a payoff vector with each game v
and graph g on the set N (representing communication channels between players). His
result implies that the balanced contributions property, the efficiency axiom, and the
symmetry axiom characterize the Shapley value.
We will close this section by discussing another axiomatization of the value, pro-
posed by Chun (1989). It employs an interesting property which generalizes the strate-
gic equivalence property traceable to von Neumann and Morgenstern (1944). Chun's
coalitional strategic equivalence property requires that if we change the coalitional form
garne by adding a constant to every coalition that contains some (fixed) coalifion T C N,
then the payoffs to players outside S will not change. This means that the extra benefit
(or loss if the added constant is negative) accrues only to the members of T. Formally:
COALITIONAL STRATEGIC EQUIVALENCE. F o r all T C N and a c R, let w aT be the

garne defined by wä ( S) = a if T C S and 0 otherwise. For all T C N and a E R, if
v = w + wä, then d?i (v) = (ai (w) for all i E N \ T.
Von Neumann and Morgenstern's strategic equivalence imposes the same require-
ment, but only for IT1 =- 1.
Another similar property proposed by Chun is fair ranking. It requires that if the un-
derlying game changes in such a way that all coalitions but T maintain the same worth,
then although the payoffs of members of T will vary, the ranking of the payoffs within T
will be preserved. This directly reflects the idea that the ranking of players' payoffs
within a coalition depends solely on the outside opfions of their members. Specifically:
FAIR RANKING. Suppose that v(S) = w ( S ) f o r every S ~ T; then f o r all i, j c

T, fbi(v) > dpj(v) if and only if ~bi(w) > qSj(w).
To characterize the Shapley value an additional harmless axiom is needed.
TRIVIALITY. If VO is the constant zero garne, i.e., vo(S) = 0 f o r all S C N, then

dpi(vo) : Of o r all i E N.
The following characterization of the Shapley value can now be obtained:
THEOREM [Chun (1989)]. The Shapley value is the unique value satisfying efficiency,
triviality, coalitional strategic equivalence, and fair ranking.
6. Sub-classes ofgames
Much of the Shapley value's attractiveness derives from its elegant axiomatic character-
ization. But while Shapley's axioms characterize the value uniquely on the class of all
games, it is not clear whether they can be used to characterize the value on subspaces.
It sounds puzzling, for what could go wrong? The fact that a value satisfies a certain
set of axioms trivially implies that it satisfies those axioms on every subclass of games.
However, the smallem the subclass, the less likely these axiorns are to determine a unique
value on it. To illustrate an extreme case of the problem, suppose that the subclass con-
sists of all integer multiples of a single garne v with no d u m m y players, and no two
players are symmetric. On this subclass Shapley's symmetry and dummy axioms are
vacuous: they impose no restriction on the payoff function. It is therefore easy to verify
that any allocation of v ( N ) can be supported as the payoff vector for v with respect to
a value on this subclass that satisfies all Shapley's axioms. Another problem that can
arise when considering subclasses of garnes is that they may not be closed under oper-
ations that are required by some of the axioms. A classic example of this is the class of
all simple games. It is clear that the additivity axiom cannot be used on such a class,
because the sum of two simple garnes is typically not a simple garne anymore. One
can revise the additivity axiom by requiring that it apply only when the sum of the two
garnes falls within the subclass considered. Indeed, Dubey (1975) shows that with this
amendment to the additivity4 axiom, Shapley's original p r o o f of uniqueness still applies
to some subclasses of garnes, including the class o f all simple garnes. However, even
in conjunction with the other standard axioms, this axiom does not yield uniqueness in
the class of all monotonic 5 simple garnes. To redress this problem, Dubey (1975) intro-
duced an axiom that can replace additivity: for two simple garnes v and v/, we define
4 Specifically, one has to require the axiom only for garnes vi, v2 whose sum belongs to the underlying
subclass.
5 Recall that a simple garne v is said to be monotonic if v(S) = 1 and S C T implies v(T) = 1.
2038 E. Winter
by min{v, v'} the simple game in which S is winning if and only if it is winning in both
v and v r. Similarly, we define by max{v, v r } the game in which S is winning if and only
if it is winning in at least one of the two games v and v r. Dubey imposed the property
of
MODULARITY. 4ffmin{v, vr}) + qS(max{v, vr}) = q~(v) + ~b(vr).
One can interpret this axiom within the framework of Roth's model in Section 3.
Suppose that ~bi (v) stands for the utility of playing i's position in the game v, and
player i is facing two lotteries. In the first lottery he will participate in either the game v
or the garne v r with equal probabilities. The other lottery involves two more "extreme"
garnes: max{v, vr}, which makes winning easier than with v and v r, and min{v, vr},
which makes winning harder. As before, each of these garnes will be realized with
probability 1/2. Modularity imposes that each player be "risk neutral" in the sense that
he be indifferent between these two lotteries.
Note that min{v, v r } and max{v, v r} are monotonic simple garnes whenever v and v r
are, so we do not need any conditioning in the formulation of the axiom. Dubey char-
acterized the Shapley value on the class of monotonic simple games by means of the
modularity axiom, showing that:
THEOREM [Dubey (1975)]. There exists a unique value on the class of monotonic 6 sim-
ple garnes satisfying efficiency, symmetry, dummy, and modularity, and it is the Shapley-
Shubik value.
When trying to apply a solution concept to a specific allocation problem (or game),
one may find it hard to justify the Shapley value on the basis of its axiomatic charac-
terization. After all, an axiom like additivity deals with how the value varies as a result
of changes in the garne, taking into account games which may be completely irrelevant
to the underlying problem. The story is different insofar as Shapley's other axioms are
concerned, because the three of them impose requirements only on the specific game
under consideration. Unformnately, one cannot fully characterize the Shapley value by
axioms of the second type only 7 (save perhaps by imposing the value formula as an
axiom). Indeed, if we were able to do so, it would mean that we could axiomatically
characterize the value on subclasses as small as a single garne. While this is impossi-
ble, Neyman (1989) showed that Shapley's original axioms characterize the value on
the additive class (group) spanned by a single garne. Specifically, for a garne v let G(v)
denote the class of all games obtained by a linear combination of restricted garnes of
v, i.e., G(v) = {v r s.t. v r = ~ i kivIsi, where ki are integers and vlsi is the game v
restricted to the coalition Si }.
6 The sarne result was shownby Dubey (1975) to hold for the class of superadditive simple games.
7 A similar distinction can be made within the axiomatization of the Nash solution where the symmetryand
efficiency axioms are "within garnes" while IIA and Invarianceare "between garnes".
Note that by definition the class G(v) is closed under sumrnation of games, which
makes the additivity axiom well defined on this class. Neyman shows that:
THEOREM [Neyman (1989)]. For an 3, v there exists a unique value on the subclass
G(v) satisfying efficiency, symmetry, dummy, and additivity, namely the Shapley value.
It is worth noting that Hart and Mas-Colel1's (1989) notion of Potential also character-
izes the Shapley value on the subclass G(v), since the Potential is defined on restricted
garnes only.
7. Cooperation structures
One of Shapley's axioms which characterize the value is the symmetry axiom. It re-
quires that a player's value in a garne depend on nothing but his payoff opportunities
as described by the coalitional form garne, and in particular not on the his "name". In-
deed, as we argued earlier, the possibility of constructing a unique measure of power
axiomatically from very limited information about the interactive environment is doubt-
less one of the value's most appealing aspects. For some specific applications, however,
we might possess more information about the environment than just the coalitional form
garne. Should we ignore this additional information when attempting to measure the rel-
ative power of players in a garne? One source of asymmetry in the environment can fol-
low simply from the fact thät players differ in their bargaining skills or in their property
rights. This interpretation led to the concept of the weighted Shapley value by Shap-
ley (1953) and Kalai and Samet (1985) (see Chapter 54 in this Handbook). But asym-
metry can derive from a completely different source. It can be due to the fact that the
interaction between players is not symmetric, as happens when some players are orga-
nized into groups or when the communication structure between players is incomplete,
thus making it difficult if not impossible for some players to negotiate with others. This
interpretation has led to an interesting field of research on the Shapley value, which is
mainly concerned with generalizations.
The earliest result in this field is probably due to Aumann and Drèze (1975), who
consider situations in which there exists an exogenous coalition structure in addition to
the coalitional form garne. A coalition structure B = (& . . . . . Sm) is simply a partition
of the set ofplayers N, i.e., [_J Sj = N and Si f) Sj = 0 for i ¢ j. In this context a value is
an operator that assigns a vector of payoffs ~b(B, v) to each pair (B, v), i.e., a coalition
structure and a coalitional form garne on N. Aumann and Drèze (1975) imposed the
following axioms on such operators. First, the efficiency axiom is based on the idea that
by forming a group, players can allocate to themselves only the resources available to
their group. Specifically,
RELATIVE EFFICIENCY. For every coalition structure B = (S1 . . . . , Sm) and 1 <~k <~
m, we have ~ j ~ & qSj(B, v) = v(Sk).
2040 E. Winter
The remaining three axioms are straightforward extensions of their counterparts in

the benchmark model.
SYMMETRY, For every permutation ~ on N and every coalition structure B, we have

O(rc B, ~rv) = Jvqb(B, v), where Jv B is the coalition structure with (~r B)i = rr Si.
DUMMY. I f i is a dummy player in v, then Ói (B, v) = 0 for all B.
ADDITIVITY. qb(B, v + w) = O(B, v) q- ~)(B, to) for all B and any pair of games v
and w.
Aumann and Drèze showed that the above axioms characterize a value uniquely.
This value assigns the Shapley value to each player in the garne restricted to bis group.
Specifically, for each coalition S and garne v, we define by v] S the garne on S given by
(v]s)(T) ----v(T) for all T C S. We now have:
THEOREM [Aumann and Drèze (1975)]. For a given set of players N and a coalition
structure B, there exists a unique B-value satisfying the four above axioms, nameIy
Ói (B, 1)) = ~i (riß(i)), where B(i) denotes the component of B that includes player i,
and Ó stands f o r the Shapley value.
Aumann and Drèze then defined the coalition structure of all the major solution con-
cepts in cooperative game theory, in addition to the Shapley value. In so doing they
exposed a startling property of consistency satisfied by all but orte of them. The Shapley
value is the exception. Hart and Mas-Colell (1989) would later show that the Shapley
value satisfies a version of this property (discussed earlier in Section 5).
In Aumann and Drèze's fi'amework, the coalition structure can be thought of as repre-
senting contractual relationships that affect players' property rights over resources, i.e.,
players in S c B "own" a total resource v(S), from which transfers to players outside
S are forbidden. This is apparent from both the definition and the efficiency axiom that
depends on the coalition structure. Roughly speaking, players from orte component of
the partition cannot share benefits with any player from another component. But in real
life coalition formation often takes place merely for strategic reasons without affecting
the fundamentals of the economy. A group may form in order to pressure another group,
or to enhance the bargaining position of its members vis-ä-vis other members without
affecting the constraint that all players in N share the total pie v(N). It is thus reason-
able to ask whether it is possible to extend the Shapley value to this context as well.
Owen (1977), Hart and Kurz (1983), and Winter (1989, 1991, 1992) take up this ques-
tion. Owen proposed a value, like the Shapley value, in which each player receives his
expected marginal contribution to coalitions with respect to a random order of players.
But while the Shapley value assumes that all orders are of equal probability, the Owen
value restricts orders according to the coalition structure. Specifically, for a given coali-
tion strucmre B, let us consider a subset of the set of all orders, which includes only
the orders in which players of the same component of B appear successively. Denote
this set of orders 17(B). The set of orders FI(B) can be obtained by first ordering the
components of B and then ordering players within each component of the partition. Ac-
cording to the Owen value, each player is assigned an expected marginal contribution
to the coalition of preceding players with respect to a uniform distribution over the set
of orders i n / 7 ( B ) , More formally, let B = (S1 . . . . . Sm) be a coalition structure. Set
FI(B) = {zr 6 / 7 ; if i, j E Sk and zr(i) < re(r) < 7r(j), then r c Sk}, which is the set of
all permutations consistent with the coalition structure B. The Owen value of player i
in the garne v with the coalition structure B is now given by
c~i(B,v)=(1/[/7(B)l) ~ [v(p i U i ) - v ( p i ) ] .
~rcFI(B)
Note that the Owen value satisfies efficiency with respect to the grand coalition, i.e.,
the total payoff across all players is v(N). This is due to the fact that the total marginal
contribution of all players with respect to a fixed order sums up to precisely v(N).
Like the Shapley value, the Owen value can be characterized axiomatically in more
than orte way, including the way proposed by Owen himself and that of Hart and
Kurz (1983). We will introduce here orte version that was used in Winter (1989) for
the characterization of level structure values, which generalize the Owen value.
First note that for a given coalition structure B = ($1 . . . . . Sm) and garne v, we can
define a "garne between coalitions" in which each coalition Si acts as a player. A coali-
tion acting as a player will be denoted by [Si]. Specifically, the worth of the coalition
{ [ S / l ] . . . . . [Sik]} is v(Sil U S i 2 , . . , USik). We will denote this garne by v*.
We now impose two symmetry axioms:
SYMMETRY A«ROSS COALITIONS. If players [Sk] and [Sl] are symmetric in the
game v*, then the total values for these coalitions are equal, i.e., ~ s l ~bj(B, v) =
~sk ~J (8, v).
SYMMETRY WITHIN COALITIONS. For any two players i and j who are symmetric
in v and belong to the same coalition in B, i.e., i, j E Sk c B, we have Oi(B, v) -=
O«(B, v).
We recall that the Owen value satisfies:
EFFICIENCY. ~ i c N qSi(B, v) = v(N).
With the above axioms we now have:
THEOREM [Owen (1977)]. For a given set of players N and a coalition structure B,
the Owen value is the unique B-value satisfying symmetry across coalitions, symmetry
within coalitions, dummy, additivity, and efficiency.
2042 E. Winter
Hart and Kurz (1983) formulated a different axiom which can be used to characterize
the Owen value requiring that:
INESSENTIAL GAMES AMONG COALITIONS. If v(N) = ~ k v(Sk), then for all k we

have ~ j ~ s k c~j(B, v) = v(Sk).
Hart and Kurz (1983) show that this axiom together with symmetry, additivity, and
a carrier axiom combining dummy and efficiency yield a characterization of the Owen
value. Hart and Kurz also used the Owen value to model processes of coalition forma-
tion.
Other papers take the Owen value as a starting-point either to suggest alternative ax-
iomatizations or to develop further generalizations. Winter (1992) used the consistency
and the potential approach to characterize the Owen value. Calvo, Lasaga, and Win-
ter (1996) used Myerson's approach of balanced contributions for another axiomatiza-
tion of the Owen value. In Owen and Winter (1992), the multilinear extension approach
[see Owen (1972)] was used to propose an alternative interpretation of the Owen value
based on a model of random coalitions. Finally, Winter (1991) proposed a general solu-
tion concept, special cases of which are the Harsanyi (1963) solution on standard NTU
garnes and the Owen value for TU garnes with coalition structures (as well as other
non-symmetric generalizations of the Shapley value).
As argued earlier, there is an intrinsic difference between Aumann and Drèze's inter-
pretation of coalition structures and that of Owen. Thinking of coalition structures as
unions or clubs, which define an asymmetric "closeness" relation between the various
individuals, suggests several alternatives for introducing cooperation structures into the
Shapley value ffamework. One such approach was proposed by Myerson (1977), who
used graphs to represent cooperäfion structures between players. This important paper
is discussed thoronghly in Monderer and Samet (see Chapter 54 in this Handbook).
Another approach that is closer to Owen's (and indeed generalizes it) was analyzed by
Winter (1989). Here cooperation is descfibed by the notion of (hierarchical) level struc-
tures. Formally, a level strucmre is a finite sequence of partitions B = (B1, B2 . . . . . Bin)
such that Bi is a refinement of Bi+ 1. That is, if S ~ Bi, then S C T for some T ~ Bi+i.
The idea behind level structure is that individuals inherit connections to other in-
dividuals by association to groups with various levels of commitment. In the context
of international trade, one can think of Bm (the coarsest partition) as represenfing ffee
trade agreements within, say, Nafta, the European Union, Mercusor, etc. Each bloc in
this coalifion strucmre is partifioned into countries, each country into federal states or
regions, and so on down to the elementary units of households,
In order to define the extension of the Owen value within this framework, we adopt
the interpretation that the partition B j represents a stronger connecfion between players
than that of the coarser Bk where k > j. Ler us think of a permutafion as the order by
which players appear to collect their payoffs. To make payoffs dependent on the coop-
eration structure, we restrict ourselves to orders in which no player i follows player j if
there is another player, say k, who is "closer" to player i and who has still not appeared.
Formally, we can construct this set of orders inductively as follows:
For a given level structure B = (B1 . . . . . Bin), define
Hm ~ {re E/7; for each l, j E S ~ Bm and i E N, re(l) < re(i) < re(j)
implies i E S}
and
/Tr = {re 6 H r + l ; for each l, j E S e Br and i E N, re(1) < re(i) < re(j)
implies i 6 S}.
The proposed value gives an expected marginal contribution to each player with re-
spect to the uniform distribution over all the orders that are consistent with the level
structure B, i.e., the orders in/71. Specifically,
(gi(B, v) = (1/I/71l) ~ [1)(pi U i ) - v(p~r)].i (4)

rc~/71
Note that when the level structure consists of only one partition (i.e., m = 1), we are
back in Owen's framework. Moreover, in contrast to the special case of Owen, in which
there is only one garne between coalitions, this framework gives rise to m garnes be-
tween coalitions, one for each hierarchy level (partition). We denote these games by
V 1 , 1)2 . . . . . Vm . The following axiom is an extension of the axiom of syrnmetry across
coalitions that we defined earlier in relation to the Owen value.
COALITIONAL SYMMETRY. Ler B = ( B 1 , . . . , Bin) be a level structure. For each level

1 <~ i <~ m, if S, T E Bi are symmetric as players ([S] and [T]) in the game v i and if
S and T are subsets o f the same component in Bj f o r all j > i, then ~ r ~ S Or (B, v) =
~ r ö T ~r (B, 1)).
In order to axiomatize the level structure value, we need another symmetry axiom
that requires equal treatment for symmetric players within the sarne coalition:
SYMMETRY WITHIN COALITIONS. Irk and j are two symmetric players with respect
to the garne v, where f o r every level 1 <~i <~m, and any non-singleton coalition S E BI,
then k E S iff j E S, and 4)i(B, v) -=qSj(B, v).
Using straightforward gerleralizations of the rest of the axioms of the Owen value, it
can be shown that:
THEOREM [Winter (1989)]. There exists a unique level structure value satisfying coali-
tional symmetry, symmetry within coalitions, dummy, additivity, and efficiency. This
value is given by (4).
2044 E. Winter
Several other approaches to cooperation structures have been proposed. We have al-
ready mentioned Myerson (1977), who uses a graph to represent bilateral connections
(of communications) between individuals. An interesting application of Myerson's so-
lution was proposed by Aumann and Myerson (1988). They considered an extensive
form game in which players propose links to other players, sequentially. Using the My-
erson value to represent the players' returns from each graph that forms, they analyze
the endogenous graphs that form (given by the subgame perfect equilibria of the link
formation garne). Myerson (1980) discusses conference structures that are given for-
mally by an arbitrary collection of coalitions representing a (possibly non-partitional)
set of associations to which individuals belong. Derks and Peters (1993) consider a ver-
sion of the Shapley value with restricted coalitions, representing a set of cooperation
constraints. These are given by a mapping p : 2 N --+ 2 N, such that (1) p ( S ) C S, (2)
S C T implies p ( S ) C p ( T ) , and (3) p ( p ( S ) ) = p ( S ) . This mapping can be interpreted
as institutional constraints on the communications between players, i.e., p (S) represents
the most comprehensive agreement that can be attained within the set of players S. Van
den Brink and Gilles propose Permission Structures, based on the idea that some inter-
actions take place in hierarchical organizations in which cooperation between two indi-
viduals requires the consent of their supervisors. Permission structures are thus given by
a mapping p : N --+ 2 N, where j ~ p ( i ) stands for " j supervises i". The function p im-
poses exogenous restrictions on cooperation and allows for an extension of the Shapley
value.
I will conclude this section by briefly discussing another interesting (asymmetric)
generalization of the value. Unlike the others, this one was proposed by Shapley himself
(see also Chapter 32 in this Handbook). Shapley (1977) examines the power of indices
in political games, where players' political positions affect the prospects of coalition
formation. Shapley's aim was to embed players' positions in an m-dimensional Euclid-
ean space. The point xi ~ R m of player i summarizes i's position (on a scale of support
and opposition) on each of the relevant m "pure" issues. General issues faced by legis-
lators typically involve a combination of several pure ones. For example, if the two pure
issues are government spending (high or low) and national defense policy (aggressive
or moderate), then the issue of whether or not to launch a new defense missile project
is a combination of the two pure issues. Shapley's suggestion was to describe general
issues as vectors of weights w =- ( w l . . . . . wm). Note that every vector w induces a nat-
ural order over the set of players. Specifically, j appears after i if w • xi > w . x j (where
x • y stands for the inner product of the vectors x and y). The main point to notice
here is that different vectors induce different orders on the set of players. To measure
the legislative power of each player in the game, orte has to aggregate over all possible
(general) issues. Let us therefore assume that issues occur randomly with respect to a
uniform distribution over all issues (i.e., vectors w in Rm). For each order of players
re, let 0(re) be the probability that the random issue generates the order 7r. Thus the
players' profile of political positions (xl, x2 . . . . . Xn) is mapped into a probability dis-
tribution over the set of all permutations. Shapley's political value yields an expected
marginal contribution to each player, where the random orders are giveu by the prob-
ability distribution 0. Note that the political value is in the class of Weber's random
order values [see Weber (1988)]. A random order value is characterized by a probabil-
ity distribution over the set of all permutations. According to this value, each player
receives his expected marginal contribution to the players preceding him with respect
to the underlying probability distribution on orders. The relation between the political
value and the Owen value is also quite interesting. Suppose that the vector of positions
is represented by m clusters of points in IR2, where the cluster k consists of the players
in Sk, whose positions are very close to each other but further away than those of other
players (in the extreme case we could think of the members of Sk as having identical
positions). It is pretty clear that the payoff vector that will emerge from Shapley's po-
litical value in this case will be very close to the Owen value for the coalition structure
B : (Sl ..... Sm).
8. Sustaining the Shapley value via non-cooperative garnes
If the Shapley value is interpreted merely as a measure for evaluating players' power in
a cooperative game, then its axiomatic foundation is strong enough to fully justify it. But
the Shapley value is often interpreted (and indeed sometimes applied) as a scheine or
a rule for allocating collective benefits or costs. The interpretation of the value in these
situations implicitly assumes the existence of an outside authority - call it a planner -
which determines individual payoffs based on the axioms that characterize the value.
However, simations of benefit (or cost) allocation are, by their very nature, situations in
which individuals have conflicting interests. Players who feel underpaid are therefore
likely to dispute the fairness of the scheme by challenging one or more of its axioms.
It would therefore be nice if the Shapley value could be supported as an outcome of
some decentralized mechanism in which individuals behave strategically in the absence
of a planner whose objectives, though benevolent, may be disputable. This objective has
been pursued by several authors as part of a broader agenda that deals with the interface
between cooperative and non-cooperative garne theory. The concern of this literature is
the construction of non-cooperative bargaining games that sustain various cooperative
solution concepts as their equilibrium outcomes. This approach, offen referred to in the
literature as "the Nash Program", is attributed to Nash's (1950) groundbreaking work
on the bargaining problem, which, in addition to laying the axiomatic foundation of the
solution, constructs a non-cooperative game to sustain it.
Of all the solution concepts in cooperative garne theory, the Shapley value is ar-
guably the most "cooperative", undoubtedly more so than such concepts as the core and
the bargaining set whose definitions include strategic interpretations. Yet, perhaps more
than any other solution concept in cooperative game theory, the Shapley value emerges
as the outcome of a variety of non-cooperative garnes quite different in structure and
interpretation.
Harsanyi (1985) is probably the first to address the relationship between the Shapley
value and non-cooperative garnes. Harsanyi's "dividend garne" makes use of the relation
2046 E. Win~r
between the Shapley value and the decomposition of garnes into unanimity garnes. To
the more recent literature which uses sequential bargaining garnes to sustain cooperative
solution concepts, Gul (1989) makes a pioneering contribution. In Gul's model, play-
ers meet randomly to conduct bilateral trades. When two players meet, one of them is
chosen randomly (with equal probabilities 1 / 2 - 1 / 2 ) to make a proposal. In a proposal
by player i to player j at period t, player i offers to pay rt to player j for purchasing
j ' s resources in the garne. If player j accepts the offer, he leaves the game with the
proposed payoff, and the coalition {i, j} becomes a single player in the new coalitional
form game, implying that i now owns the property rights of player j. If j rejects the
proposal by i, both players retum to the pool of potential traders who meet through
random matching in a subsequent period. Each pair's probability of being selected for
trading is 2~(nr (nr - 1)), where nt is the number of players remaining at period t. The
game ends when only a single player is left. For any given play path of the game, the
payoff of player j is given by the current value of his stream of resources minus the
payments he made to the other players. Thus, for a given strategy combination ~r and a
discount factor 6, we have
O~
v'(,,,6)= ~(1- 6)[v(M;)- r~]6',

0
where M[ is the set of players whose resources are controlled by player i at time t and
6 is a discount factor. Gul confines himself to the stationary subgame perfect equilibria
(SSPE) of the game, i.e., equilibria in which players' actions at period t depend only
upon the allocation of resources at time t. He argues that SSPE outcomes may not be
efficient in the sense of maximizing the aggregate equilibrium payoffs of all the players
in the economy, but he goes on to show that in any no-delay equilibrium (i.e., an equi-
librium in which all pairwise meetings end with agreements) players' payoffs converge
to the Shapley value of the underlying game when the discount factor approaches 1.
Specifically,
THEOREM [Gul (1989)]. Let cr (6k) be a sequence o f SSPEs with respect to the discount
factors {6/c}which converge to 1 as k goes to infinity. If cr(6k) is a no-delay equilibrium
for all k, then U i (er (6k ), 6k ) converges to i's Shapley value o f V as k goes to infinity.
It should be argued that in general the SSPE outcomes of Gul's game do not con-
verge to the Shapley value as the discount factor approaches 1. Indeed, if delay occurs
along the equilibrium path, the outcome may not be close to the Shapley value even
for 6 close to 1. Gul's original formulation of the above theorem required that cr (6k) be
efficient equilibria (in terms of expected payoffs). Gul argues that the condition of effi-
ciency is a sufficient guarmatee that along the equilibrium path every bilateral matching
terminates in an agreement. However, Hart and Levy (1999) show in an example that ef-
ficiency does not imply immediate agreement. Nevertheless, in a rejoinder to Hart and
Levy (1999), Gul (1999) points out that if the underlying coalitional game is strictly
convex, 8 then in his model efficiency indeed implies no delay.
A different bargaining model to sustain the Shapley value through its consistency
property was proposed by Hart and Mas-Colell (1996). 9 Unlike in Gul's mode1, which
is based on bilateral agreements, in Hart and Mas-Colell's approach players submit
proposals for payoff allocations to all the active players. Each round in the game is
characterized by a set S C N of "active players" and a player i c S who is designated
to make a proposal after being randomly selected from the set S. A proposal is a fea-
sible payoff vector x for the members in S, i.e., Zj~sXj ~~-v(S). Once the proposal
is made, the players in S respond sequentially by either accepting or rejecting it. If all
the members of S accept the proposal, the garne ends and the players in S share payoffs
according to the proposal. Inactive players receive a payoff of zero. If at least one player
rejects the proposal, then the proposer i runs the risk of being dropped from the garne.
Specifically, the proposer leaves the garne and joins the set of inactive players with a
probability of 1 - p, in which case the garne continues into the next period with the set
of active players being S \ i. Or the proposer remains active with probability p, and the
garne continues into the next period with the same set of active players. The garne ends
either when agreement is reached or when only one active player is left in the garne.
Hart and Mas-Colell analyzed the above (perfect information) garne by means of its
stationary subgame perfect equilibria, and concluded:
THEOREM [Hart and Mas-Colell (1996)]. For every monotonic and non-negative l°
garne v and f o r every 0 «, p < 1, the bargaining game described above has a unique
stationary subgame perfect equilibrium (SSPE). Furthermore, if as is the SSPE pay-
off vector of a subgame starting with a period in which S is the active set o f players,
then as = 49(v Is) (where 49 stands f o r the Shapley value and v ls f o r the restricted garne
on S). In particular, the SSPE outcome o f the whole garne is the Shapley value o f v.
A rough summary of the argument for this result runs as follows. Let as,i denote
the equilibrium proposal when the set of active players is S and the proposer is i c S.
In equilibrium, player j 6 S with j ~ i should be paid precisely what he expects to
receive if agreement fails to be reached at the current payoff. As the protocol specifies,
with probability p we remain with the same set of players and the next period's expected
proposal will be as = 1/[SI Y~~iEsas, i" With the remaining probability 1 - p, players i
will be ejected so that the next period's proposal is expected to be as\i. We thus obtain
the following two equations for as,i:
(1) ~ j aJs,i = v(S) (feasibility condition), and
8 We recall that a game v is said to be strictly convexif v(S Ui) - V (S) > v(T t3i) - v(T) whenever T C S
and SS&T.
9 In the original Hart and Mas-Colell (1996) paper, the bargalning garne was based on an underlying non-
transferable utility garne.
10 v(S) >10 for all S C N, and v(T) <~v(S) for T C S.
2048 E. Winter
(2) a s,i
j
= paJs + (1 - p)ds\ i (equilibrium condition).
Rewriting the second condition we notice that the two of them correspond precisely
to the two properties of Myerson (1977), which we discussed in Section 5 and which
together with efficiency characterize the value uniquely.
In a recent paper, Perez-Castrillo and Wettstein (1999) suggested a garne that modi-
fies that of Hart and Mas-Colell (1996) so as to allow the (random) order of proposals to
be endogenized. The game runs as follows. Prior to making a proposal there is a bidding
phase in which each player i commits to pay a payoff vi to player j. These bids are
made simultaneously. The identity of the proposal is determined by the bids. Specifi-
cally, the proposer is chosen to be the player i for which the difference between the bids
made by i and the bids made to i is maximized, i.e., i -~ argmax~eN [Y~~j v/ - ~ j v~]
(players' bids to themselves is always zero). If there is more than one player for
which this maximum is attained, then the proposer is chosen from among these play-
ers with an equal probability for each candidate. Following player i's recognition to
propose, the game proceeds according to Hart and Mas-Colell's protocol, with p = 1.
Namely, upon rejection, player i leaves the garne with probability 1. Perez-Castrillo
and Wettstein (1999) show that this garne implements the Shapley value in a unique
subgame perfect equilibrium (since the garne is of a finite horizon, no stationarity re-
quirement is needed).
Almost all the bargaining garnes that have been proposed in the literature on the im-
plementation of cooperative solutions via non-cooperative equilibria are based on the
exchange of proposals and responses. A different approach to multilateral bargaining
was adopted in Winter (1994). Rather than a model in which players make full proposals
concerning payoff allocations and respond to such proposals, a more descriptive feature
of bargaining situations is sought by assuming that players submit only demands, i.e.,
players announce the share they request in return for cooperation. A coalition emerges
when the underlying resources are sufficient to satisfy the demands of all members.
I will describe here a simple version of the Winter (1994) model and some of the results
that follow.
Consider the order in which players move according to their name, i.e., player 1
followed by 2, etc. Each player i in his turn publicly announces a demand di (which
should be interpreted as a statement by player i of agreeing to be a member of any
coalition provided that he is paid at least di). Before player i makes bis demand, we
check whether there is a compatible coalition among the i - 1 players who already
made their demands. A coalition S is said to be compatible (to the underlying garne v)
if S can satisfy the demands of all its members, i.e., ~ j e s dj <~v(S). If compatible
coalitions exist, then the largest one (in terms of membership) leaves the garne and each
of its members receives bis demand. The game then proceeds with the set of remaining
players. If no such coalition exists, then player i moves ahead and makes his demand.
The game ends when all players have made their demands. Those players who are not
part of a compatible coalition receive their individually rational payoff.
Consider now a garne that starts with a chance move that randomly selects an or-
der with a uniform probability distribution over all orders and then proceeds in ac-
cordance with the above protocol. We call this game the demand commitment garne.
Winter (1994) shows that the demand commitment game implements the Shapley value
if the underlying game is strictly convex.
THEOREM [Winter (1994)]. For strictly convex (cooperative) garnes, the demand com-
mitment garne has a unique subgame perfect equilibrium, and each player's equilibrium
payoff equals his Shapley value.
Winter (1994) also considers a protocol that requires a second round of bidding in
the event that the first round ends without a grand coalition that is compatible. It can be
shown that with small delay costs the Shapley value emerges not only as the expected
equilibrium outcome for each player, but that the actual demands made by the players
in the first round coincide with the Shapley value of the underlying garne.
Several other papers have followed the same approach in different contexts. Dasgupta
and Chiu (1998) discuss a modified version of the Winter (1994) game, which allows
for the implementation of the Shapley value in general garnes. Roughly, the idea is to
allow outside transfers (or gifts) that will convexify a non-convex garne. A balanced
budget is guaranteed by a schedule of taxes dependent on the order of moves. Bag and
Winter (1999) used a demand commitment-type mechanism to implement stable and ef-
ficient allocations in excludable public goods. Morelli (1999) modified Winter's (1994)
model to describe legislative bargaining under various voting rules. Finally, Mutuswami
and Winter (2000) used demand mechanisms of the same kind to study the formation of
networks. They also noted that if the mechanism in Winter (1994) is amended to allow
a compatible coalition to leave the game only when it is connected (i.e., only when it
includes the last k players for some 1 ~< k ~< n), then the resulting garne implements the
Shapley value not only in the case of convex games but in all games.
9. Practice
While garne theory is thought of as "descriptive" in its attempt to explain social phenom-
ena by means of formal modeling, cooperative garne theory is primarily "prescriptive".
It is not surprising that rauch of the literature on cooperative solution concepts finds its
way not into economics journals but into journals of management science and opera-
tions research. Cooperative garne theory does not set out to describe the way individu-
als behave. Rather, it recommends reasonable rules of allocation, or proposes indices to
measure power. The prospect of using such a theory for practical applications is there-
fore quite attractive, the more so for its single-point solution and axiomatic foundation.
In this section, I discuss two areas in which the Shapley value can be (and indeed has
been) used as ä practical tool: the measurement of voter power and cost allocation.
9.1. Measuring states' power in the U.S. presidential election
The procedure for electing a president in the United States consists of two stages. First,
each state elects a group of representatives, or "'Great Electors", who comprise the Elec-
2050 E. Winter
toral College. Second, the Electoral College elects the president by simple majority rule.
It is assumed that each Great Elector votes for the candidate preferred by the majority of
his/her state. Since the Electoral College of each state grows in proportion to its census
count, a narrow majority in a densely populated state, like California, can affect an elec-
tion's outcome more than wide majorities in several scarcely populated states. Mann and
Shapley (1962) and Owen (1975) measured the voting power of voters from different
states, using the Shapley value together with the interesting notion of compound simple
garnes.
Let M1, M2 . . . . . Mr~ be a sequence of n disjoint sets of players. Let wl, w2 . . . . . wn
be a sequence of n simple garnes defined on the sets M1 . . . . . Mn respectively. And let v
be another simple game defined on the set N = {1, 2 . . . . . n}. We will refer to the players
in N as distxicts. The compound game u = v[wl . . . . . wn] is a simple game defined on
the set M = Mi t_J M2 U - . . U Mn by u(S) = v ( { j l w j ( S 71Mj) = 1}). In words: We say
that S wins in district j if S's members in that district form a winning coalition, i.e., if
wj (S 71Mj) = 1. S is said to be winning in the garne u if and only if the set of districts
in which S is winning is itself a winning coalition in v. In the context of the presidential
face, Mj is the set of voters in state j , wj is the simple majority garne in state j, and
v is the electoral college garne. Specifically, the electoral college garne can be written
as the following weighted majority game [270; Pl . . . . . Ps1], where 51 stands for the
number of states, and Pi is the number of electors nominated by a state i (e.g., 45 for
California and 3 for the least populated states and the District of Columbia).
In general compound garnes, Owen has shown that the value of player i is the product
of his value in the garne within his district and the value of his district in the game v,
i.e., cbi(u) = Ój (1J)Ói(Wj).
Since the districts' games are all symmetric simple majority garnes, the value of each
player in the voting garne in his state is simply 1 divided by the number of voters.
To compute the value of the garne v, Owen used the notion of a multilinear extension
[see Owen (1972)]. Overall, he found that the power of a voter in a more populated
state is substantially greater than that of a voter in a less populated state. For example,
California voters enjoy more than three times the power of Washington D.C. voters.
Others have used the Shapley value (as well as other indices) to measure political
power. Seidmann (1987) used it to compare the power of governments in Ireland follow-
ing elections in the early and mid 80s. He argued that a government's durability greatly
depends on the distribution of power across opposition parties, which can be estimated
by means of the Shapley-Shubik index. Carreras, Garcfa-Jurado, and Pacios (1993)
used the Shapley and the Owen value to evaluate the power of each of the parties in all
the Spanish regional parliaments. Fedzhora (2000) uses the Shapley-Shubik index to
study the voting power of the 27 regions (oblasts) in the Ukraine in the run-off stage of
the presidential elections between 1994 and 1999. She also compares these indicators to
the transfers that Ukrainian governments were making to the different regions. Another
interesting application of the Shapley value to political science is due to Rapoport and
Golan (1985). Immediately after the election of the tenth Israeli parliament, 21 students
of political science, 24 Knesset members, and 7 parliamentary correspondents were
invited to assess the political power ratlos of the 10 parties represented in the Knes-
set. These assessments were then compared with various power indices, including the
Shapley value. The value provided the best fit for 31% of the subjects, but the authors
claimed the Banzhaf index performed better.
9.2. Allocation o f costs
The problem of allocating the cost of constructing or maintaining a public facility

among its various users is of great practical importance. Young (1994) (see Chap-
ter 34 in this Handbook) offers a comprehensive survey of the relation between garne
theory and cost atlocation. An interesting allocation rule for such problems, which is
closely related to the Shapley value, emerges from the "Airport Garne" of Littlechild
and Owen (1973). Specifically, consider n planes of different size for which a runway
needs to be built. Suppose that there arem types of planes and that the construction of a
runway sufficient to service a type j plane is c j with Cl < c2 < .-- < Cm. Let N j be the
number of planes of type j so that U N j = N is the set of all planes which need to be
service& A runway servicing a subgroup of planes S C N will häve to be long enough
to allow the servicing of the largest plane in S. This gives rise to the following natural
cost-sharing garne (in coalitional form) defined on the set of planes: c ( S ) = cj(s) and
c(0) = 0, where j (S) -~ max{jIS N N j 7& 0}. Littlechild and Owen's (1973) suggestion
was to use the garne c to determine the allocation of cost by applying the Shapley value
on the garne.
Note that the garne v can be decomposed into m unanimity garnes. Specifically, define
Rk = Rk U Rk + l U . . . U Rm and consider the coalitional form garnes vk with vk ( S) = 0
when S (q Rk -----0 and Vk (S) = ck -- Ck-1 otherwise (we set co = 0). It is easy to verify
that the sum of the games vk is exactly the cost-sharing garne, i.e., vl (S) + . . . + Vm (S) =
c ( S ) for every coalition of planes S. The additivity of the Shapley value implies that the
value of the garne c is ~b(c) = ~P(vl) + . . - + qS(Vm). But each vk is a unanimity garne
with (gi(vk) = 0 for i ~ N \ Rk and ~bi(Vk ) = (Ck -- Ck-1)/]Rkl for i ~ Rk. We therefore
obtain that the Shapley value of the garne c is given by q~i(c) = (c2 - cl)/IR11 ÷ (c3 -
c2)/IR21 + ' " + (cj - c j - 1 ) / I R j[ for a plane of type j.
The rule suggested by Littlechild and Owen (1973) has the following interesting in-
terpretation. First, all players share equally the cost of a runway for type 1 planes. Then
all players who need a larger facility share the marginal extra cost, i.e., c2 - cl. Next,
all players who need yet a larger runway share equally the cost of upgrading to a run-
way large enough to service type 3 planes. We now continue in this manner until all the
residual costs are allocated, which will ultimately allow for the acquisition of a runway
long enough to service all planes.
A version of the Airport garne was studied by Fragnelli et al. (1999). Their work
was part of a research project funded by the European Commission with the aim of de-
termining cost allocation rules for the railway infrastructure in Europe. Fragnelli et al.
realized that the original Airport garne is ill-suited to their problem since the mainte-
nance cost of a railway infrastructure depends on the number of users. They constructed
2052 E. Winter
a n e w g a r n e w h i c h d i s t i n g u i s h e s c o n s t r u c t i o n costs ( w h i c h d o n o t d e p e n d o n t h e n u m b e r
o f users) f r o m m a i n t e n a n c e costs, a n d d e r i v e d a s i m p l e f o r m u l a for t h e S h a p l e y v a l u e
o f t h e garne. T h e y also u s e d real data c o n c e r n i n g the m a i n t e n a n c e o f r a i l w a y i n f r a s t r u c -
tures to e s t i m a t e the a l l o c a t i o n o f cost a m o n g d i f f e r e n t users.
References
Aumann, R.J., and J. Drèze (1975), "Cooperative garnes with coalition structures", International Journal of
Garne Theory 4:217-237.
Aumann, R.J., and R.B. Myerson (1988), "Endogenous formation of links between players and of coalitions:
An application of the Shapley value", in: A.E. Roth, ed., The Shapley Value (Cambridge University Press,
Cambridge), 175-191.
Aumann, R.J., and L.S. Shapley (1974), Values of Non-Atomic Games (Princeton University Press, Prince-
ton).
Bag, EK., and E. Winter (1999), "Simple subscription mechanisms for the production of public goods",
Journal of Economic Theory 87:72-97.
Banzhaf, J.E III (1965), "Weighted voting does not work: A mathematical analysis", Rutgers Law Review
19:317-343.
Calvo, E., J. Lasaga and E. Winter (1996), "On the principle of balanced contributions", Mathematical Social
Sciences 31:171-182.
Carreras, E, I. Garcia-Jurado and M.A. Pacios (1993), "Estudio coalicional de los pm-lamentos autonómicos
espafioles de régimen comün", Revista de Estudios Polfticos 82:152-176.
Chun, Y. (1989), "A new axiomatization of the Shapley value", Games and Economic Behavior 1:119-130.
Dasgupta, A., and Y.S. Chiu (1998), "On implementation via demand commitment garnes", International
Journal of Garne Theory 27:161-190.
Derks, J., and H. Peters (1993), "A Shapley value for garnes with restricted coalitions", International Journal
of Garne Theory 21: 351-360.
Dubey, E (1975), "On the uniqueness of the Shapley value", International Journal of Garne Theory 4:131-139.
Fedzhora, L. (2000), "Voting power in the Ukrainian presidential elections", M.A. Thesis (Economic Educa-
tion and Research Consortium, Kiev, Ukraine).
Fragnelli, V., I. Garda-Jurado, H. Norde, E Patrone and S. Tijs (1999), "How to share rallway infrastructure
costs?', in: I. Garcla-Jurado, F. Patrone and S. Tijs, eds., Garne Practice: Contfibutions from Applied Garne
Theory (Kluwer, Dordrecht).
Gul, E (1989), "Bargaining foundations of Shapley value", Econometrica 57:81-95.
Gul, F. (1999), "Efficiency and immediate agreement: A reply to Hart and Levy", Econometrica 67:913-918.
Harsanyi, J.C. (1963), "A simplified bargaining model for the n-person cooperative garne", International
Economic Review 4:194-220.
Harsanyi, J.C. (1985), "The Shapley value and the risk dominance solutions of two bargaining models for
characteristic-function garnes", in: R.J. Aumann et al., eds., Essays in Garne Theory and Mathematical
Economics (Bibliographisches Institut, Mannheim), 43-68.
Hart, S., and M. Kurz (1983), "On the endogenous formation of coalitions", Econometrica 51:1295-1313.
Hart, S., and Z. Levy (1999), "Efficiency does not imply immediate agreement", Econometrica 67:909-912.
Hart, S., and A. Mas-Colell (1989), "Potential, value and consistency', Econometrica 57:589-614.
Hart, S., and A. Mas-Colell (1996), "Bargaining and value", Econometrica 64:357-380.
Kalai, E., and D. Samet (1985), "Monotonic solutions to general cooperative garnes", Econometriea 53:307-
327.
Littlechild, S.C., and G. Owen (1973), "A simple expression for the Shapley value in a special oase", Man-
agement Science 20:99-107.
Mann, I., and L.S. Shapley (1962), "The a-priori voting strength of the electoral college", American Political
Science Review 72:70-79.
Monderer, D., and D. Samet (2002), "Variations on the Shapley value", in: R.J. Aumann and S. Hart, eds.,
Handbook of Garne Theory, Vol. 3 (North-Holland, Amsterdam) Chapter 54, 2055-2076.
Morelli, M. (1999), "Demand competition and policy compromise in legislative bargaining", American Polit-
ical Science Review 93:809-820.
Mutuswami, S., and E. Winter (2000), "Subscription mechanisms for network fomaation", Mimeo (The Center
for Rationafity and Interactive Decision-Making, The Hebrew University of Jerusalem).
Myerson, R.B. (1977), "Graphs and cooperation in garnes", Mathematics of Operations Research 2:225-229.
Myerson, R.B. (1980), "Conference strucmres and fair allocation rules", International Joumal of Garne The-
ory 9:169-182.
Nash, J. (1950), "The bargaining problem", Econometrica 18:155-162.
Neyman, A. (1989), "Uniqueness of the Shapley value", Garnes and Economic Behavior 1:116-118.
Owen, G. (1972), "Multilinear extensions of garnes", Management Science 18:64-79.
Owen, G. (1975), "Evaluation of a presidential election garne", American Political Science Review 69:947-
953.
Owen, G. (1977), "Values of garnes with a priori unions", in: R. Henn and O. Moeschlin, eds., Essays in
Mathematical Economics and Garne Theory (Springer-Verlag, Berlin), 76-88.
Owen, G., and E. Winter (1992), "The multilinear extension and the coalition value", Garnes and Economic
Behavior 4:582-587.
Perez-Castrillo, D., and D. Wettstein (1999), "Bidding for the surplus: A non-cooperative approach to the
Shapley value", DP 99-7 (Ben-Gurion University, Monaster Center for Economic Research).
Rapoport, A., and E. Golan (1985), "Assessment of political power in the Israeli Knesset", American Political
Science Review 79:673-692.
Roth, A.E. (1977), "The Shapley raine as a von Neumann-Morgenstem utility", Econometrica 45:657-664.
Seidmann, D. (1987), "The distribution of power in Da'il E'ireann", The Economic and Social Review 19:61-
68.
Shapley, L.S. (1953), "A value for n-person garnes", in: H.W. Kuhn and A.W. Tucker, eds., Contributions
to the Theory of Garnes II (Annals of Mathematics Studies 28) (Princeton University Press, Princeton),
307-317.
Shapley, L.S. (1977), "A comparison of power indices and a nonsymmetric generalization", P-5872 (The
Rand Corporation, Santa Monica, CA).
Shapley, L.S., and M. Shubik (1954), "A method for evaluating the distribution of power in a committee
system", American Political Science Review 48:787-792.
Sobolev, A.I. (1975), "The charactefization of optimality principles in cooperative garnes by functional equa-
tions", Matliematical Methods in Social Sciences 6:94-151 (in Russian).
Straffin, RD. (1977), "Homogeneity, independence and power indices", Public Choice 30:107-118.
Straffin, ED. (1994), "Power and stability in polifics", in: R.J. Aumann and S. Hart, eds., Handbook of Garne
Theory, Vol. 2 (North-Holland, Amsterdam) Chapter 32,1127-1152.
Von Neumann, J., and O. Morgenstern (1944), Theory of Games and Economic Behavior (Princeton Univer-
sity Press, Princeton).
Weber, R. (1988), "Probabilistic values for garnes", in: A.E. Roth, ed., The Shapley Value (Cambridge Uni-
versity Press, Cambridge), 101-120.
Weber, R. (1994), "Garnes in coalitional form", in: R.J. Aumann and S. Hart, eds., Handbook of Game Theory,
Vol. 2 (North-Holland, Amsterdam) Chapter 36, 1285-1304.
Winter, E. (1989), "A value for garnes with level structures", International Journal of Garne Theory 18:227-
242.
Winter, E. (1991), "A solution for non-transferable utility garnes with coalition stmcture", International Jour-
nal of Game Theory 20:53-63.
Winter, E. (1992), "The consistency and the potential for values with garnes with coalition structure", Games
and Economic Behavior 4:132-144.
Winter, E. (1994), "The demand commitment bargaining and snowballing cooperation", Economic Theory
4:255-273.
2054 E. Winter
Young, H.P. (1985), "Monotonic solutions of cooperative garnes", International Journal of Garne Theory
14:65-72.
Young, H.P. (1994), "Cost allocation", in: R.J. Aumann and S. Hart, eds., Handbook of Game Theory, Vol. 2
(North-Holland, Amsterdam) Chapter 34, 1193-1235.

Winter 2002

Uploaded by

Copyright:

Available Formats

Winter 2002

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Winter 2002

Uploaded by

Copyright:

Available Formats

Chapter 53

THE SHAPLEY VALUE

Handbook of Garne Theory, Volume 3, Edited by R.J. Aumann and S. Hart

Shapley value, cooperative games, coalitions, cooperation structures, voting

J E L classification: C71, D72

To promote an understanding of the importance of Shapley's (1953) paper on the

Recall that a coalitionalform game (henceforth game) on a finite set of players N =

cki(v) = l/n! ~_ù [v (p~Ui i ) - v ( p i ) ] , (1)

which is Shapley's definition of the value.

EFFICIENCY. Y~'iöN q~i(V) = v ( N ) .

The second axiom requires the following notion of symmetry:

DUMMY. If i is a dummy player, i.e., v(S U i) - v(S) = 0 for every S C N, then

ADDITIVITY. (b(v + to) = ~b(v) + ~(w), where the garne v + w is defined by (v +

d?i(v) = [{rc E 17; p i Ui ~ W a n d p / ¢ w } l / n ! .

4. The Shapley value as a von Neumann-Morgenstern utility function

A3. Neutrality to Ordinary Risk: (i, ( p w + (1 - p ) v ) ) ~ [p(i, w); (1 - p)(i, v)].

A4. Neutrality to Strategic Risk: (i, VR) ~ (i, ( 1 / r ) v i ) .

An elegant result now asserts that:

THEOREM [Roth (1977)]. Let u be a von Neumann-Morgenstern utility function over

Roth's result can be viewed as an alternative axiomatization of the Shapley value.

5. Alternative axiomatizations of the value

Dip(N,v) = P(N,v)- P(N \i,v),

where (N \ i, v) is the game v restricted to the set of players N \ i. To be associated

Z Di P(N, v) = v(N). (2)

Moreover, we normalize P to satisfy P(0, v) = 0. Given the mild requirement on p,

P(N, v ) = (1/INI)Iv(N) + ~-~ P(N \ i, v)]. (3)

Starting with P(0, v) = 0, Equation (3) determines p recursively. It is interesting to

to coalitions are to be treated equally. One of the most fundamental requirements of

vr (S) = v (S U T «) - ~ q~i(v Isur«) for every S C T,

where VIR denotes the garne v restricted to the coalition R.

v~(S)=~¢i(v) ifS=T, and v~(S)=0 ifS=0.

BALANCED CONTRIBUTION. For every two players i and j, ~i(v) - ~i(VIN\j) :

COALITIONAL STRATEGIC EQUIVALENCE. F o r all T C N and a c R, let w aT be the

FAIR RANKING. Suppose that v(S) = w ( S ) f o r every S ~ T; then f o r all i, j c

To characterize the Shapley value an additional harmless axiom is needed.

TRIVIALITY. If VO is the constant zero garne, i.e., vo(S) = 0 f o r all S C N, then

The following characterization of the Shapley value can now be obtained:

MODULARITY. 4ffmin{v, vr}) + qS(max{v, vr}) = q~(v) + ~b(vr).

The remaining three axioms are straightforward extensions of their counterparts in

SYMMETRY, For every permutation ~ on N and every coalition structure B, we have

DUMMY. I f i is a dummy player in v, then Ói (B, v) = 0 for all B.

EFFICIENCY. ~ i c N qSi(B, v) = v(N).

With the above axioms we now have:

INESSENTIAL GAMES AMONG COALITIONS. If v(N) = ~ k v(Sk), then for all k we

(gi(B, v) = (1/I/71l) ~ [1)(pi U i ) - v(p~r)].i (4)

COALITIONAL SYMMETRY. Ler B = ( B 1 , . . . , Bin) be a level structure. For each level

8. Sustaining the Shapley value via non-cooperative garnes

v'(,,,6)= ~(1- 6)[v(M;)- r~]6',

9.1. Measuring states' power in the U.S. presidential election

9.2. Allocation o f costs

The problem of allocating the cost of constructing or maintaining a public facility

You might also like