WPS4072
COOPERATIVE GAME THEORY AND ITS
APPLICATION TO NATURAL, ENVIRONMENTAL
AND WATER RESOURCE ISSUES:
1. Basic Theory
Irene Parrachino, Stefano Zara and Fioravante Patrone
Abstract
Game theory provides useful insights into the way parties that share a scarce resource may
plan their utilization of the resource under different situations. This review provides a brief
and self-contained introduction to the theory of cooperative games. It can be used to get
acquainted with the basics of cooperative games. Its goal is also to provide a basic
introduction to this theory, in connection with a couple of surveys that analyze its use in the
context of environmental problems and models. The main models (bargaining games,
transfer utility and non transfer utility games) and issues and solutions are considered:
bargaining solutions, single-value solutions like the Shapley value and the nucleolus, and
multi-value solutions such as the core. The cooperative game theory (CGT) models that are
reviewed in this paper favor solutions that include all possible players and ignore the strategic
stages leading to coalition building. They focus on the possible results of the cooperation by
answering questions such as: Which coalitions can be formed? And how can the coalitional
gains be divided in order to secure a sustainable agreement? An important aspect associated
with the solution concepts of CGT is the equitable and fair sharing of the cooperation gains.
World Bank Policy Research Working Paper 4072, November 2006
The Policy Research Working Paper Series disseminates the findings of work in progress to encourage the
exchange of ideas about development issues. An objective of the series is to get the findings out quickly, even if
the presentations are less than fully polished. The papers carry the names of the authors and should be cited
accordingly. The findings, interpretations, and conclusions expressed in this paper are entirely those of the
authors. They do not necessarily represent the view of the World Bank, its Executive Directors, or the countries
they represent. Policy Research Working Papers are available online at http://econ.worldbank.org.
This Working paper is a product of the first phase of the study "Cooperative Arrangements
for Allocation of Water among Production and Environmental Uses under Stochastic Supply
Conditions", funded by the Italian Trust Fund and the Development Economics Research
Group of the World Bank. Members of the study team include: Ariel Dinar (Task Manager),
Fioravante Patrone, Irene Parrachino, Stefano Zara of the University of Genoa, Carlo Carraro,
Carmen Marchiori, and Alessandra Sgobbi of the University of Venice. Comments by Rashid
Sumaila, University of British Columbia, Canada and Kim Hang Pham Do, Massey
University, New Zealand, and participants of the 6th meeting on Game Theory and Practice
Dedicated to Development, Natural Resources and the Environment, July 10-12, Zaragoza,
Spain, are much appreciated. Two additional Working Papers are also devoted to some
special topics, which are chosen having in mind their use in applications to environmental
issues: 2. Application to Natural and Environmental Resources (PRWP 4073), and 3.
Application to Water Resources (PRWP 4074).
CONTENTS
A SEMI-TECHNICAL BACKGROUND.............................................................................................................3
WHAT IS GAME THEORY?...........................................................................................................................................3
THE COOPERATIVE BARGAINING PROBLEM...........................................................................................4
THE MAIN BARGAINING SOLUTIONS............................................................................................................................6
The Nash solution.............................................................................................................................................6
The Kalai-Smorodinski solution.......................................................................................................................7
N-PERSON COOPERATIVE GAMES ................................................................................................................7
SUBSET SOLUTION CONCEPTS ...................................................................................................................................10
The Core .........................................................................................................................................................11
The bargaining set..........................................................................................................................................14
The Kernel ......................................................................................................................................................15
The Least Core ...............................................................................................................................................16
Unique (One-point) solution concepts...........................................................................................................16
The Nucleolus..............................................................................................................................................................16
The Shapley value........................................................................................................................................................17
The - value...............................................................................................................................................................19
Modifications to the above solution concepts.............................................................................................................20
NON TRANSFERABLE UTILITY (NTU)-GAMES ........................................................................................21
COST GAMES .......................................................................................................................................................21
COST-SHARING RULES ..............................................................................................................................................22
The Alternate Cost Avoided (ACA) and the Separable Cost Remaining Benefits (SCRB) methods ............23
Monotonicity................................................................................................................................................................24
, AND -CHARACTERISTICFUNCTIONS...........................................................................................25
CONCLUDING REMARKS ................................................................................................................................26
REFERENCES.......................................................................................................................................................28
2
ASEMI-TECHNICALBACKGROUND
Resource scarcity is a growing concern to individuals as well as to governments.
Competition over smaller amounts of water and other environmental amenities of
deteriorating quality is increasingly becoming common in many parts of the world. As more
have to share less, the question of strategic behavior becomes imminent. In such a situation,
Game Theory (GT) may provide useful insights into the way parties that share a scarce
resource should plan their utilization of the resource under different situations.
The purpose of this working paper is twofold. First it provides the basic building blocks of
Cooperative Game Theory (CGT), presented in simple and applicable terms. Second, it
reviews the literature dealing with application of cooperative game theory in environmental
and water resources and explores the possibilities of expanding its use. The paper does not
provide a general introduction to GT, or even to CGT: it is just a sketchy introduction,
focusing on the tools that have been used in applications to water and environmental
problems. The goal is to offer a self-contained introduction, instrumental to the reading and
understanding of companion surveys, for people who do not have a general GT background.
What is Game Theory?
Game Theory (hereafter GT) is the study of mathematical modeling of strategic behavior of
decision makers (players), in situations where one player's decisions may affect the other
players. The basic assumption of Game Theory is that decision makers are rational players,
that they are intelligent, so, while pursuing well-defined objectives, players take into account
other decision-makers' rationality and, accordingly, build expectations on their behavior.
GT consists of a modeling part and a solution part. Mathematical models of conflicts and of
cooperation provide strategic behavioral patterns, and the resulting payoffs to the players are
determined according to certain solution concepts.
There are two main branches of GT.1 The first is non-cooperative Game Theory (hereafter
NCGT) and the second is cooperative Game Theory (hereafter CGT). The main distinction
between the two is that NCGT models situations where players see only their own strategic
objectives and thus binding agreements among the players are not possible, while CGT
actually is based mainly on agreements to allocate cooperative gains (solution concepts).
Therefore, while NCGT models describe and take into account the strategic interaction
among the players, CGT ignores the strategic stages leading to coalition building and focuses
on the possible results of the cooperation. CGT attempts answering questions such as which
coalitions can be formed? And how can the coalitional gains be divided in order to secure a
sustainable agreement? In particular, CGT favors solutions that include all possible players
(Grand Coalition), and thus most CGT solution concepts refer to the Grand Coalition.
An important aspect associated with the solution concepts of CGT is the equitable and fair
sharing of the cooperation gains. Young (1994) notices that equity is something dealt with in
everyday life. One can refer to equity in a comprehensive framework, that is, social justice: a
proper distribution of resources, welfare, rights, duties, opportunities, or in the narrow
framework, for example, how to solve everyday distributive problems. This second case is
the one more frequently addressed by GT, which provides the tools to examine equity in a
1Additional typologies hold as well, e.g., static and dynamic games, one-shot games and repeated games.
3
rigorous way, and the problem turns out to be a choice between rules under an axiomatic
perspective. But, as Young underlines, the axiomatic approach has two weaknesses: first, the
axioms, reasonable by themselves, may lead to "impossibility theorems"; second, the
axiomatic method may result in a solution that is too far from the practical problem dealt
with: the perceived equity always depends on the particulars of the case. Furthermore, the
empirical rules of equity, that one can see applied in real situations, are usually more
complex than a single normative principle, and often represent a balance or compromise
between competing principles.
The term fairness in the literature is sometimes used as a synonym for equity, but some
authors often mean something different: their idea of fairness coincides with the acceptability
and stability of the cost-benefit apportionment among the players.
As was indicated above, the following background is not intended to provide a
comprehensive technical basis in GT. Readers who wish to widen their familiarity with the
field of GT could refer to Owen (1995), Myerson (1991), Osborne and Rubinstein (1994),
Driessen (1988), Peters (1997), and Aumann and Hart (1992, 1994, 2002).
THE COOPERATIVE BARGAINING PROBLEM
A GT approach to bargaining was first introduced in Nash (1950), who developed a
cooperative and static game model. In a two-person bargaining problem, two players have
access to a set of alternatives, which is called the feasible set. It is assumed that each player
has preferences over the alternatives, and that the preferences are represented by a couple of
functions u1 and u2 . In the original approach by Nash, as in many later developments, it has
been assumed that these utility functions are von Neumann-Morgenstern utilities2.
The utility functions, u1 and u2 , define a subset S of R2, which is the image of the set of
feasible alternatives. Each point of S represents a solution for the bargaining problem that is
an agreement between the players. Note that the solution is defined in the `image' space, so
that in principle it could correspond to more different `equivalent' agreements.
Within the feasible set there is also a point, called threat point or disagreement point, which
is where "the game ends" should no agreement be reached. We will call S the feasible set
and d the disagreement point.
While defining his axiomatic solution, Nash wanted it to be a rule that associates a point of S
with each problem (S, d). To develop it, we will introduce the formal model (and an
example), then we will report the Nash axiomatic solution and finally we will present some of
the other solution concepts proposed after Nash.
Definition: A two-person bargaining problem is a pair (S, d) such that
S is convex, closed (it contains its boundary) and a comprehensive3 subset of R2;
d S , and there exists at least one xS such that x > d ; 4
2 von Neumann-Morgenstern utility: An axiomatic extension of the ordinal concept of utility to uncertain
payoffs. An agent characterized by a von Neumann-Morgenstern utility function ranks uncertain payoffs
according to (higher) expected value of the utility of the individual outcomes that may occur.
3 xS R2, yR2, y x yS
4
Sd := {xS | x d} is a compact set.
We'll call B2 the set of two-person bargaining problems.
EXAMPLE: dividing wine (no money admitted).
A father says to his two sons: "Here is a container of 9 liters of wine; if you come to an
agreement in order to divide the wine, then it is yours, otherwise I'll take the container back."
The possible shares are (t,9 -t), 0 t 9. Assume that an amount x has utility u1 (x) for
the first son, and an amount y has utility u2 ( y) for the second one, with:
u1 (x) = x
u2 ( y) = y
A generic splitting (t,9 -t) provides the couple of utility values ( t,9 -t . This situation
)
leads to a bargaining problem (S, d), where d = (0, 0) (no wine) and
S = compr {( t,9 -t :0 t 9 .
) }
Source: Authors
Definition: A solution for two-person bargaining problems is a map : B2 R2 satisfying:
(S,d)S , for all (S,d)B2;
(S,d) d , for all (S,d)B2.
A solution associates with each bargaining element (S,d)B2 a unique point of S
interpreted as a prediction, or recommendation, for that bargaining problem.
In the axiomatic characterization of his solution concept, Nash required some properties and
proved that they characterize only one solution, now called the Nash solution of bargaining
problems.
4 x = (x1, x2 ); d = (d1,d2 ); x,d R2. Then, x > d if x1 > d1 and x2 > d2
5
The main bargaining solutions
The Nash solution
As mentioned before, the Nash bargaining solution is based on several axioms:
1. Individual Rationality. Each player receives at least what he would receive in the threat
point, that is, for all (S,d)B2 we have (S,d ) d ;
2. Pareto optimality. This is a standard efficiency condition and means that all gains from
cooperation should be shared. Formally, it is expressed as follow:
satisfies the Pareto optimality if, for each (S,d)B2 and for each xS ,x (S,d); then
x =(S,d) ;
3. Independence from Irrelevant Alternatives. If an alternative is judged to be the solution to
a problem, then it should still be considered the most suitable for any sub-problem containing
it. Formally, it is expressed as follows:
satisfies this property if (S,d)T implies (T,d) =(S,d), for each (S,d)B2 and for
each T S such that (T,d) B2;
4. Covariance under positive affine transformations. The solution is required to be
independent of any particular members in the families of von Neumann and Morgenstern's
utility functions (von Neumann and Morgenstern, 1944) representing the agents' preferences
chosen to describe the problem. Formally, it is expressed as follows:
A positive affine transformation is a map A: R2 R2 such that, for every i{1,2},
Ai(x) = aixi + bi ,
where a1,a2,b1,b2 R , a1 and a2 being positive ( Ai(x) denotes the i-th component of
A(x)).
satisfies covariance with positive affine transformation if, for each (S,d)B2 and for each
positive affine transformation A , (A(S), A(d)) = A((S,d));
5. Symmetry. If the bargaining problem is invariant with interchanging the agents, the
solution should give the same to both. Formally, it is expressed as follows:
satisfies symmetry if, for each (S,d)B2 such that S is symmetric (i.e. (x1,x2)S then
(x2, x1)S ) and d1 = d2 , it holds that 1(S,d) = 2(S,d).
Nash proved that there is a unique solution, , satisfying all these axioms, that is expressed
in the following formula:
=max(x1 -d1)(x2 -d2).
Sd
No axiom is universally applicable; for a critique to the set of these 5 axioms see Thomson
(1994).
The Nash solution has been generalized by Harsanyi (1959) for n players with n > 2. The
Nash-Harsanyi solution, Z, to a n-person bargaining game is given below.
n
Z = (x i-di).
i=1
6
The Kalai-Smorodinski solution
Kalai and Smorodinski (1975) thought that the Nash solution does not take sufficiently into
account the aspirations of the players: they believed that if the preferences and the utility
values of the players change, the compromise point between the agents should not vary.
They proposed a solution taking into account the aspiration levels of the players. The
property introduced is the following:
Individual monotonicity. It requires that an expansion of the feasible set "in a direction
favorable to a particular agent", always benefits the agent. Formally it is expressed as
follows:
Let ui(S,d) be max{xi | xSd} (for n = 2 ): if T S , and uj(T) = uj(S) , then
i(T,d) i(S,d), for i j.
By simply replacing independence of irrelevant alternatives by individual monotonicity in the
list of axioms proposed by Nash, Kalai and Smorodinski obtained the characterization of their
proposed solution.
The Kalai-Smorodinski solution (a unique solution satisfying the above axioms) is:
For every (S,d)B2, (S,d ) = d + t u S,d ) - d( ( )
where t = max t R | d + t u S,d ) - d Sd .
{ ( ( ) }
Although there are several solutions to bargaining problems; the two solutions presented here
are the most important ones. Other solution concepts in the game theoretical literature can be
found in Peters (1992). For example, Armstrong (1994) applies the Salukvadze solution (Yu
and Leitman, 1974) to a fishery management problem.
N-PERSON COOPERATIVE GAMES
Definition: An n-person cooperative game in the characteristic function form is an ordered
pair G = (N,v) where N = {1,2,...,n} is a finite set with n elements.
N = {1,2,...n} is the set of players. A subset S of the player set N (notation: S N) is called
coalition, and the collection of 2n coalitions of N (i.e. P(N )) is denoted by 2n , including N
itself, the empty set and all the one-element subsets.
v : P(N ) R is real-valued function defined over all the subsets of N and such that
v() = 0, where is the empty set.
N is the grand coalition and it consists of the set of all the players. The number of the players
of a coalition S is denoted by S or, sometimes, s. v is the characteristic function, or
coalitional function, and assigns a "worth" v(S) to each coalition S. 5
5 It is necessary to note that the characteristic function is defined considering only the players within
coalition S, without considering those players which are outside of the coalition and that, specifically in
environmental issues, could affect v S . For a better explanation, see Section 6.
( )
7
In many cases the elements of the players' set N represent real people, e.g., landowners and
peasants, traders, creditors or voters, but the player set can also consist of more abstract
membership, such as sectors, as in the well-known Tennessee Valley Authority case (Straffin
and Heaney), or (in the "airport game") of landing by planes, or agricultural associations and
city water services.
It is often assumed that the coalitional/characteristic function is expressed in units of an
infinitely divisible commodity which "stores" utility, and which can be transferred without
loss to the players. If a subset of players (coalition) can obtain a total utility v , this utility
can be divided among the members of the coalition in any possible way. It is also assumed
that there exist some transferable commodity that enables the transfers among players in
order to reallocate the benefits gained through the coalition, and that there is a common scale
to compare the players' utilities.
The theory developed based on these assumptions is called the side-payments theory. We
will call games satisfying the above presumptions transferable utility games, or TU-games.
We will often refer to (N,v) simply as v , and will denote by G(N ) the class of TU-games
with set of players N. The coalitional function is often called a game (with transferable
utility) in the characteristic form.
Definition: In a TU-game vG(N ) v is superadditive if, for all S,T N , with S T = ,
v(S T ) v(S ) + v(T ) .
Definition: Let vG(N ) . v is said to be constant-sum if, for all S N ,
v(S) + v(N \ S) = v(N ) .
If a game is superadditive, then players have real incentives for cooperation, in the sense that
the union of any two disjoint groups of players shall never diminish the total benefits; the
merger of the disjoint coalitions can only improve their prospects. The superadditivity of the
game is guaranteed in case v (S) is defined as the total amount of utility that coalition C can
guarantee for itself, irrespective of the strategies adopted by the remaining players (see the
definition of the - characteristic function given in the last section). It is not always sensible
to assume superadditivity, and this assumption may be questioned in some environmental
applications, due to the presence of externalities (again, see the last section for some
comments on this issue). Assuming superadditivity means that the grand coalition is efficient,
thus the problem may turn to be the sharing of the overall utility v(N ) among all the players.
In this paper we focus on the class of superadditive games, explicitly specifying if a particular
game doesn't fulfill the above condition. A stronger notion than superadditivity is convexity.
Definition: Let vG(N ) . v is convex if for all coalitions S and T,
v(S T ) + v(S T ) v(S) + v(T ).
An equivalent definition is that for any player i , and any coalitions S T not containing i ,
v(S i) - v(S) v(T i) - v(T ) . The larger the coalition, the greater the marginal
contribution6 of new members.
6 For the concept of Marginal Contribution see the section of the Shapley value
8
With the characteristic function at hand and supposing that the players agree to work together
on a certain objective, they will have to divide the total payoff v(N) of the grand coalition.
"An allocation problem arises whenever a bundle of resources, rights, burdens, or costs is
temporarily held in common by a group of individuals and must be allotted to them
individually. An allocation or distribution is an assignment of the objects to specific
individuals." (Young, 1994: p.7)
An allocation, usually, requires two different types of decisions: (a) the choice of the total
amount of the good to be distributed and (b) the formula or principle of the allocation of that
amount. The focus in this review is on the second choice. "An allocation rule is a method,
process, or formula, which allocates any given supply of goods among any potential group of
claimants according to the salient characteristics of these claimants." (Young, 1994)
A distribution of the amount of v(N) among the players will be represented by a real value
function x on the player set N satisfying the efficiency principle:
x(i)=v(N).
iN
Here x(i), also denoted xi, represents the payoff to player i, according to the involved payoff
function x.
We usually identify the function xRN on N with the corresponding n-tuple
x = (x1,K, xn )RN of real numbers, called allocation. The vectors xRn satisfying the
efficiency principle are called efficient payoff vectors or pre-imputations.
Most of the proposed solution concepts meet also the individual rationality principle,
requiring that the payoff to any player i by the payoff vector x be at least the amount that
player i can attain by himself.
This determines the set of imputations:
Definition: Let vG(N ) . An imputation of v is a vector xRn such that:
x (efficiency)
i = v(N),
iN
xi vi, for all i N . (individual rationality)
I(v):= x RN
x i
iN = v(N),xi v(i)iN.
I(v) denotes the set of imputations of v. It is the set of allocations of v(N ) among the
players satisfying efficiency and individual rationality (that is, as we already mentioned, one
player joining a coalition should gain at least what he/she would get playing alone).
Applying superadditivity repeatedly (i.e.: adding the players one by one), it is clear that
v(N ) v {i} .
( )
iN
If v(N ) = v {i} , and xi vi, i (x is an imputation), then xi = vi, i . There is only
( )
iN
one imputation and the game is called inessential. In this situation, there isn't any incentive
to form coalitions because they don't get more than the sum of the stand-alone payoffs. The
other games are called essential.
9
An important approach, developed by von Neumann and Morgenstern (1944) deals with the
concepts of dominance, D-Core and Stable Sets. We couldn't find, in our literature review of
CGT and environmental and water resources, any explicit applications of this approach, but
still, we have to mention it because of its relevance in GT evolution.
In a game we may find many allocations satisfying the requisites above, namely being
imputations, but what we might need is a criterion to make a distinction between different
possible imputations. Dominance is such a criterion.
Definition: Given vG(N ), a non-empty S N , and x, y I (v) , then x dominates y
through S if:
xi > yi for all iS . This states that all of the members of S prefer x to y; and
x i v(S). This states that the players of S are able, via cooperation by themselves, to
iS
obtain the allocation x.
As we will better observe later, CGT tools are used not only to share benefits from
cooperation, but also to allocate costs. In this case it is useful to consider a cost function c
instead of v, and this change doesn't introduce substantial differences in the model. In such a
cost allocation situation it's also possible to develop a model dealing with the function v,
which describes the savings of the players that are the result of cooperation.
The main goal of the theory of TU-games is to select, for every TU-game, an allocation, or a
set of allocations, which is admissible to the players.
In the next section we will present some of the most important CGT solution concepts, which
have been associated with the applications that we found in the literature on CGT and
environmental and water resources.
As we indicated earlier, the questions addressed in a CGT model are:
1. Which coalitions form?
2. If the grand coalition forms, how do the players divide v(N) (or allocate costs)?
The solution concepts give many answers to these questions.
One can find two groups of solution concepts: (a) Subset solution concepts: Core (Gillies,
1953; Shapley, 1971), D-Core, Stable sets (von Neumann and Morgenstern, 1944),
bargaining set (Aumann and Maschler, 1964), Kernel, Least Core, and (b) One-point
(unique) solution concepts: Nucleolus (Schmeidler, 1969), Shapley value (Shapley, 1953); -
value (Tijs, 1981).
Apart from those quoted above, in the GT literature other solutions can be found, or variants.
In this paper, we'll confine ourselves to an overview of the CGT solution concepts that have
been applied in the literature on environmental and water resources issues.
Subset solution concepts
The solution concepts in this group refer to a `range' of values that fulfill certain conditions
as will be seen below. The flexibility subset solution concepts provide is very convenient in
practice as they allow the decision maker consideration of various policy interventions and
their evaluation.
10
The Core
This concept was introduced by Gillies (1953). An allocation satisfying the two properties
(efficiency and individual rationality) stated before is an imputation. From a "practical" point
of view, an imputation is a distribution of gains that satisfies only the individual rationality.
A similar condition for coalitions should also be taken into account.
So, we can introduce another condition, called coalitional rationality that extends the concept
of individual rationality to each of the coalitions.
Definition: Let vG(N ) . A Core element of a game v is an allocation xRN such that:
x (coalitional rationality)
i v(S) for all S N ;
iS
x (efficiency)
i= v(N).
iN
The Core of v, that we denote C(v), is the following set of vectors:
C( ) := x RN |
x = v(N), and v(S), S N
i x i
iN iS
Core allocations provide incentives for cooperation. If the Core exists, however, there are
usually an uncountable number of allocations. Which is the most equitable? Thus, two
problems may arise: first, the Core may have more than one allocation; second the Core
might be empty. The two following examples underline these problems.
EXAMPLE: a game with a nonempty Core.
Consider the game G = (N,v) with N = {1,2,3} and v defined as follows:
v() = v(1) = v(2) = 0
v(3) =1
v(1,2) = 9
v(2,3) = 5
v(1,3) = 6
v(1,2,3) =12
The simplex in R3 , with vertexes (12, 0, 0), (0, 12, 0), (0, 0,12) represents the part of the pre-
3
imputation set ( x i=12) which satisfies xi 0. Individual rationality is already satisfied
i=1
for players 1 and 2, but to get the imputation set we have to consider the condition for player
3 also (see the line x3 v(3) =1 in the figure below).
11
(The arrows stand for the direction of the inequalities.)
Source: Authors
The set of imputations consists of all xR3 such that:
x1 0
x2 0
x3 1
x1 + x2 + x3 =12
The Core (lined area) consists of all imputations, which further satisfy:
x1 + x2 9
x1 + x3 5
x2 + x3 6
We know that x1 + x2 + x3 =12 , thus we can substitute x1 + x2 =12 - x3 (and similarly for the
other two inequalities). We will get:
x1 0
x2 0
x3 1
x3 9
x2
5
x3 6
x1 + x2 + x3 =12
that is exactly what we can see represented in the above figure.
EXAMPLE: a game with an empty Core.
12
A typical example of a game with an empty Core is the simple majority game. A coalition
wins if it is composed by more than half of the participants, N = {1,2,....,n} . Then:
1 if S > n
v(S) = 2
0 if S n
2
The Core conditions for this game provide no solutions.
For example, if we consider a three-person simple majority game we will have: N = {1,2,3}
and
v() = v(1) = v(2) = v(3) = 0
v(1,2) = v(1,3) = v(2,3) =1
v(1,2,3) =1
The Core will be defined by the following system:
x1 0
x2 0
x3 0
x1 + x2 1
x1
+ x3 1
x2 + x3 1
x1 + x2 + x3 =1
There is no (x1, x2, x3) satisfying the above conditions. In fact, if we sum the third, fourth and
fifth inequality we get:
2(x1 + x2 + x3 ) 3,
that is,
(x1 + x2 + x3) , 3
2
and this is impossible because of the last Core condition (efficiency).
Bondareva (1963) and Shapley (1967) provided necessary and sufficient conditions for a
game to have a nonempty Core in terms of balanced conditions.
Theorem: (Bondareva, 1963 and Shapley, 1967) A TU-game has nonempty Core if and only
if it is balanced7.
Another well-known relation between convexity of games and the existence of Core elements
is as follows:
Theorem: (Shapley, 1971) If a game (N,v) is convex, then C (v) is a nonempty set.
7 Entering into a detailed analysis of the concept of balancedness, is not useful in this paper.
13
Note that convexity implies that the game has a nonempty Core, but the reverse is not true.
The bargaining set
The bargaining set was introduced by Aumann and Maschler (1964). Here we follow
Maschler (1992). It is necessary to start form this concept, in order to better understand two
other game theoretic concepts: the Kernel and the Nucleolus.
The idea is that it is necessary to have a process through which it is possible to allocate the
gains from cooperation when the grand coalition has not been formed, but we have a certain
coalition structure:
Definition: Let (N,v) be a TU-game. A coalition structure is a partition B ={B1,...,Bk} of
the n players, i.e., U Bi = N and for all i j , Bi Bj = .
k
i=1
When a particular coalition structure is formed, it is necessary to define an appropriate payoff
configuration, satisfying individual and group rationality.
We will use the notation x(Bi) = xh , with hBi, to indicate the sum of the payoffs of the
h
players in a certain coalition Bi.
Definition: An imputation for a coalition structure B is a payoff vector
x = (x1, x2,..., xn )satisfying:
x(Bi) = v(Bi), for all Bi in B (coalitional rationality);
xi v i
({ }), for all i in N (individual rationality).
We denote by X(B) the space of all the imputations for the coalition structure Bi.
The players belonging to each coalition try to reach their best outcome advancing proposals
about their needs, according with the imputation.
Definition: Let x be an imputation in a game (N,v) for a coalition structure B. Let k and l
be two distinct players in a coalition Bi of B. An objection of k against l at x is a
pair(S, y), satisfying:
S N, k S, l S;
y RS , y(S) = v(S); yi > xi, all iS .
This is a way for k to inform l that he could gain more someplace else, and to say to l that
he should transfer some of its gains to k .
But l can answer with a counter-objection:
Definition: Let (S, y) be an objection of k against l at x , x X(B), k,l BiB. A
counter-objection to this objection is a pair (T, z) , satisfying:
T N, l T, k T ;
z RT , z(T ) = v(T );
zi yi, all i in T S ;
14
zi xi, all i in T \ S .
In the counter-objection, player l claims that he can assure to himself his gain by formingT .
It is important to note that k can object against l only if they belong to the same coalition of
the coalition structure. The objection is justified if it has no counter-objection; otherwise, the
objection is unjustified.
The bargaining set will be defined as follows:
Definition: Let (N,v) be a cooperative game with side payments. The bargaining set M1 (B) i
for a coalition structure B is:
M1 (B) := {x X(B): every objection at x can be countered}
i
= {x X(B): there exists no justified objection at x}.
When a particular coalition structure has formed, the aim is to find a particular imputation in
order to create some "stability" among the coalitions in the coalition structure.
To compute, at least partially, the bargaining set, the Kernel has been introduced. If the game
is superadditive, then the Kernel is non-empty and it is a subset of the bargaining set.
The Kernel
For the n-person game v, let S be a coalition ( S N ) and x = (x1,..., xn ) a payoff vector (not
necessarily an imputation).
We define excess of S with regards to the imputation x as the quantity
e(S, x) = v(S) - xi .
iS
corresponding to the difference between the value of the coalition S (given by the
characteristic function) and the utility received according to x.
If we consider two different players (i j ) the surplus of i against j can be defined as:
sij (x) = max e(S, x),
where the maximum is taken over all coalitions S such that xS and j S .
Thus, sij represents the maximum gain that player i can hope to get without the cooperation
of j.
Now, if we consider an individually rational payoff configuration x, we can say that i
outweighs j (notation i ff j ) if and only if:
sij (x) > sji (x) and xj > v( j) .
If i ff j there is a certain instability, because i can make j a demand that he cannot counter.
The Kernel is the set of individually rational payoff configurations for which such instability
does not occur, that is S N , there are no i, j S , such that i ff j .
15
The Least Core
Given an n-person game v, we can consider any coalition S N and any imputation
x = (x1,..., xn ) I (v) ; the excess of S with regard to the imputation x is described by the
quantity
e(S, x) = v(S) - xi .
iS
Let e1 (x) be the largest excess of any coalition relative to x, e2 (x) the second largest
excess, e3 (x) the next and so on.
The Least Core is the set X1 of all x that minimize e1 (x) .
Unique (One-point) solution concepts
Under this group of solution concepts we find several solution concepts such as the
Nucleolus, the Kernel, the Shapley Value, and the -value.
The Nucleolus
Starting from the definition of the Least Core, let X2 be the set of all x in X1 that minimize
e2 (x), X3 the set of all x in X2 that minimize e3 (x) , ...
This process will eventually lead to an Xk consisting of a single imputation x (as Schmeidler
proved), called the Nucleolus.
We can better understand and formalize this concept defining the 2n-vector (x), as the
vector whose components are the excesses of the 2n subsets S N , arranged in decreasing
order, i.e.,
k (x) =(e(Sk,x))SN
where S1,S2,...,S2n are the subsets of N arranged bye(Sk, x) e(Sk , x).
+1
EXAMPLE: For the three person game v, where v(S) =1, if S has two or three players
and v(S) = 0 otherwise, the payoff vectors x = (0.3, 0.5, 0.2) and y = (0.1, 0.5, 0.4) give the
following excesses:
S e(S, x) e(S, y)
0 0
1 - 0.3 - 0.1
2 - 0.5 - 0.5
3 - 0.2 - 0.4
1, 2 0.2 0.4
1, 3 0.5 0.5
2, 3 0.3 0.1
N 0 0
16
We get (x) = (0.5,0.3,0.2,0,0,-0.2,-0.3,-0.5)
and ( y) = (0.5,0.4,0.1,0,0,-0.1,-0.4,-0.5) .
We can order the several vectors (x) by the lexicographic order. The lexicographic order
can be applied comparing the first components of two vectors: if they are equal, compare the
seconds and so on, until we find two different components. The (lexicographically) bigger
vector will be the one containing the higher of these two different components. Formally,
given two vectors = 1,...,q
( ) and = 1,...,q , we say that is lexicographically
( )
smaller than if there is some integer k, 1 k q , such that:
l = l for 1l k,
k < k
and we can write