Cooperative Games
Players in a cooperative game strive for a common goal, from which they possibly profit. Of special interest is the class of TU-games with a transferable utility potential, which is best studied within the context of linear algebra. Central is the question how to distribute the achieved goal’s profit appropriately. The core of a cooperative game is an important analytical notion. It strengthens the VON NEUMANN–MORGENSTERN solution concept of stable sets and provides a link to the theory of discrete optimization and greedy algorithms. It turns out that the core is the only stable set in so-called supermodular games. Values of cooperative games are more general solution concepts and can be motivated by stochastic models for the formation of coalitions. Natural models for the dynamics of coalition formation are closely related to thermodynamical models in statistical physics and offer an alternative view on the role of equilibria.
While the agents in the n-person games of the previous chapters typically have individual utility objectives and thus possibly opposing strategic goals, the model of a cooperative game refers to a finite set N of n = |N| players that may or may not be active towards a common goal. A subset S ⊆ N of potentially active players is traditionally called a coalition. Mathematically, there are several ways of looking at the system of coalitions:
From a set-theoretic point of view, one has the system of the 2n coalitions
On the other hand, one may represent a subset 
by its incidence vector 
with the coordinates
The incidence vector x(S) suggests the interpretation of an “activity vector”:
The coalition S would thus be the collection of active players.
A further interpretation imagines every player i ∈ N to have a binary strategy set Xi = {0, 1} from which to choose one element. An incidence vector
represents the joint strategy decision of the n players and we have the correspondence
By a cooperative game we will just understand a n-person game Γ with player set N and state set
depending on a set-theoretic or on a vector space point of view. A general cooperative game Γ = (ui | i ∈ N) with individual utility functions 
is therefore a matrix game where each player has the choice between two alternative actions.
In the following, we will concentrate on cooperative games whose individual utilities are implied by a general potential on 
.
1.Cooperative TU-games
A transferable utility relative to a set N of players is a quantity υ whose value υ(S) depends on the coalition S of active players and hence is a potential
The potential υ implies the utility measure ∂υ : × → ℝ with the values
We denote resulting potential game by Γ = (N, υ) and refer to it as a cooperative TU-game with characteristic function υ.
EX. 8.1. Assume that the players i ∈ N evaluate their utility relative to a coalition S ⊆ N by a real parameters ui(S), which means that each player i ∈ N has an individual utility function
The aggregated utility u = Σi∈N ui is then a transferable utility and defines the TU-game Γ = (N, u). For each S ⊆ N and player i ∈ N, one finds:
REMARK 8.1 (Terminology). Often the characteristic function υ of a cooperative TU-game (N, υ) is already called a cooperative game. In discrete mathematics and computer science a function
is also known as a pseudo-boolean function. Decision theory refers to pseudo-boolean functions as set functions.1
The characteristic function υ can represent a cost utility or a profit utility. The real-world interpretation of the mathematical analysis, of course, depends on whether a cost or a gain model is assumed. Usually, the modeling context makes it clear, however.
Equilibria. Since is a finite set, a TU-game (N, υ) has equilibria. Indeed, any coalition S with maximal value
is a gain equilibrium, while a minimizer of υ is a cost equilibrium.
Normalizations. We will always assume that the characteristic function υ of a TU-game is zero-normalized in the sense
The assumption (45) is made for mathematical convenience. In the case υ(
) ≠ 0, one may study the related zero-normalized game (N, υ′) with
Essential features of (N, υ) are shared by (N, υ′). υ and υ′ imply the same utility measure, for example. In this sense, zero-normalization does not result in a loss of generality in the mathematical analysis.
Other normalizations are sometimes useful. Setting, for example,
one obtains a related game (N, υ″) where the individual players i ∈ N have the potential value υ″({i}) = 0.
In the sequel, we will concentrate on (zero-normalized) TU-games and therefore just talk about a cooperative game (N, υ).
2.Vector spaces of TU-games
Identifying a TU-game (N, υ) with its characteristic function υ, we think of the function space
as the vector space of all (not necessarily zero-normalized) TU-games on the set N. 
is isomorphic with coordinate space 
and has dimension
The 2n unit vectors of correspond to the so-called DIRAC functions δS ∈ with the values
The set {δS | S ∈ } is a basis of . Any υ ∈ has the representation
2.1.Duality
It is often advantageous to retain as the index set explicitly in the game-theoretic analysis and make use of the set-theoretic structure of the coalition ensemble . One such example is the duality operator υ ↦ υ* on , where
We say that the game (N, υ*) is the dual of (N, υ). For any possible coalition S ∈ , the numerical value
is the “surplus” of the so-called grand coalition N υs. S in the game (N, υ). So duality expresses a balance
EX. 8.2. Show:
| (1) | υ ↦ υ* is a linear operator on . |
| (2) | The dual υ** = (υ*)* of the dual υ* of υ yields exactly the zero-normalization of υ. |
For any υ ∈ , let us define its MÖBIUS2 transform as the function 
with values
(S) aggregates the υ-values of all subcoalitions T ⊆ S. In this sense, the MÖBIUS transformation υ ↦ is a kind of “discrete integral” on the function space .
EX. 8.3 (Unanimity games). The MÖBIUS transform 
of the DIRAC function δS is known as a unanimity game and has the values
A coalition T has a non-zero value (T) = 1 exactly when the coalition T includes all members of S. Unanimity games appear to be quite simple and yet are basic (Corollary 8.1 below). Many concepts in cooperative game theory are tested against their performance on unanimity games.
Clearly, the MÖBIUS transformation is a linear operator on . The important observation concerns an inverse property: every characteristic function υ arises as the transform of a uniquely determined other characteristic function w.
THEOREM 8.1 (MÖBIUS INVERSION). For each υ ∈ , there is a unique w ∈ such that 
.
Proof. Recall from linear algebra that, in view of the linearity of the MÖBIUS transformation, it suffices to show:
i.e., the kernel of the map υ ↦ contains just the zero vector O ∈ .
So assume that z ∈ transforms to 
= O. Let S ∈ be a coalition and observe in the case S = :
Assume now, by induction, that z(T) = 0 holds for all T ∈ of size |T| < |S|. Then the conclusion
follows and completes the inductive step of the proof. So z(S) = 0 must be true for all coalitions S.
Since the MÖBIUS operator is linear, Theorem 8.1 implies that it is, in fact, an automorphism of , which maps bases onto bases. In particular, we find:
COROLLARY 8.1 (Unanimity Basis). The unanimity games form a basis of , i.e., each υ ∈ admits a unique representation of the form
EX. 8.4 (HARSANYI dividends). Where , the values w(S) are known as the HARSANYI dividends of the coalitions S in the game (N, υ). It follows that the value υ(S) of any coalition S is the sum of the HARSANYI dividends of its subcoalitions T:
REMARK 8.2. The literature is not quite clear on the terminology and often refers to the inverse transformation ↦ υ as the MÖBIUS transformation. Either way, the MÖBIUS transformation is a classical and important tool also in in number theory and in combinatorics.3
2.3.Potentials and linear functionals
A potential f : → ℝ, interpreted as a vector f ∈ defines a linear functional 
with the values
If g(S) is the (0, 1)-incidence vector of a particular coalition S ∈ , we have
which means that 
extends the potential f on 2N (= ) to all of .
Conversely, every linear functional g ↦ 〈f|g〉 on defines a unique potential f on via
These considerations reveal characteristic functions on and linear functionals on to be two sides of the same coin. From the point of view of linear algebra, one can therefore equivalently define:
•A cooperative TU-game is a pair Γ = (N, υ), where N is a set of players and υ ↦ 〈υ|g〉 is a linear functional on the vector space .
The characteristic function υ of the cooperative game (N, υ) implies the utility measure4
Individual players i ∈ N will assess their value with respect to υ by evaluating the change in υ that they can effect by being active or inactive.
For a player i ∈ N, we thus obtain its marginal value with respect to the coalition S as
EX. 8.5 (Symmetric difference). The symmetric difference of two sets S, T is the set
With this notion, the marginal value of player i ∈ N in (N, υ) becomes
3.Examples of TU-games
3.1.Additive games
The marginal value ∂iυ(S) of a player i depends on the coalition S it refers to. Different coalitions may yield different marginal values for the player i.
The TU-game (N, υ) is said to be additive if a player would add the same marginal value to each coalition it joins. This means: There is a number υi for each i ∈ N such that for all coalitions S ⊆ N with i ∉ S,
Hence, if υ is zero-normalized and additive, one has
Conversely, every vector a ∈ ℝN defines a unique zero-normalized additive game (N, a) with the understanding
EX. 8.6. Which unanimity games (see Ex. 8.3) are additive? Show that the vector space of all additive games on N has dimension |N| + 1. The subspace of all zero-normalized additive games on N has dimension |N|.
3.2.Production games
Similar to the situation in Section 4.3, consider a set N of players in an economic production environment where there are m raw materials, M1, . . . , Mm from which goods of k different types may be manufactured.
Let x = (x1, . . . , xk) be a plan that proposes the production of xj ≥ 0 units of the jth good and assume:
| (1) | x would need ai(x) units of material Mi for all i = 1, . . . , m; |
| (2) | each supplier s ∈ N has bis ≥ 0 units of material Mi at its disposal; |
| (3) | the production x could be sold for the price of f(x). |
So the coalition S ⊆ N could guarantee a production of market value
The corresponding cooperative TU-game (N, υ) is a production game.
What is the worth of a player? This is one of the central questions in cooperative game theory. In the context of the production game (N, υ), one natural approach to resolve this question is the market price principle:
| (MP) | Assuming that each material Mi has a market price of yi per unit, assign to each supplier s ∈ N the market value ws of its inventory: |
|
|
An objection against a simple application of the principle (MP) could possibly be made if
In this case, S could generate a market value that is strictly larger than the market value of its inventory. So the intrinsic economic value of the members of S is actually larger than the value of their inventory. This consideration leads to another worth assessment principle:
| (CA) | Assign numbers ws to the members of N such that |
An allocation w ∈ ℝN according to principle (CA) is a so-called core allocation. Core allocations do not necessarily exist in a given cooperative game, however.5
As it turns out, the principles (MP) and (CA) can be satisfied simultaneously if the production game (N, υ) has a linear objective and linear restrictions.
Linear production games. Assume that the production game with characteristic function (50) is linear in the sense
and admits an optimal production plan x* with market value
x* is the solution of a linear program. So also an optimal solution y* exists for the dual linear program
where we have used the notation for the aggregated inventory of the members of a coalition:
The components 
of y* are the shadow prices of the materials Mi. According to principle (MP), let us allocate the individual worth
To see that w* satisfies also the principle (CA), observe first from linear programming duality:
The dual of any S-restricted production problem (50) differs only in the coefficients of the objective function. Expressed in terms of the dual linear program, one has
Since y* is a feasible (although not necessarily optimal) dual solution for any S-restricted problem, one concludes:
3.3.Network connection games
Consider a set N = {p1, . . . , pn} of users of some public utility6 that are to be linked, either directly or indirectly (via other users), to some supply node p0. Assume that the cost of establishing a link between pi with pj would be cij (euros, dollars or whatever). The associated cooperative game has the utility function
The relevant question is:
•How much should a user pi ∈ N be charged so that a network with the desired connection can be established?
One possible cost distribution scheme is derived from a construction method for a connection of minimal total cost c(N):
The greedy algorithm builds up a chain of coalitions
according to the following iterative procedure:
The greedy algorithm makes sure that the user set N in total is charged the minimal possible connection cost:
The greedy algorithm is efficient in the sense that the total cost c(N) is distributed. Nevertheless, the greedy cost allocation scheme may appear quite “unfair” from the point of view of individual users (see Ex. 8.7).7
EX. 8.7. Consider a user set N = {p1, p2} with connection cost coefficients c01 = 100, c02 = 101 and c12 = 1. The greedy algorithm constructs the coalition chain
and charges c(S1) = 100 to user p1, while user p2’s marginal cost is
So p1 would be to bear more than 99% of the total cost c(N) = 101.
Assume there is a set N of n voters i of not necessarily equal voting power. Denote by wi the number of votes voter i can cast. Given a threshold w, the associated voting game8 has the characteristic function
In the voting context, υ(S) = 1 has the interpretation that the coalition S has the voting power to make a certain proposed measure pass. Notice that in the case υ(S) = 0, a voter i with marginal value
has the power to swing the vote by joining S. The general question is of high political importance:
•How can (or should) one assess the overall voting power of a voter i in a voting context?
REMARK 8.3. A popular index for individual voting power is the BANZHAF power index (see Section 8 below). However, there are alternative evaluations that also have their merits. As in the case of network cost allocation, abstract mathematics cannot decide what the “best” method would be.
4.Generalized coalitions and balanced games
Let us assume that the TU-game (N, υ) can be played by several coalitions S ⊆ N “simultaneously”, requiring an activity level yS ≥ 0 from every member i ∈ S so that no player has to invest more than 100% of its available activity resources in total. With this in mind, we define a generalized coalition9 to be a nonnegative vector
and associate with it the utility value
EX. 8.8. Assume that y = (yS|S ⊆ N) is a generalized coalition with binary components yS ∈ {0, 1}. Show that y is the incidence vector of a family of pairwise disjoint coalitions.
EX. 8.9 (Fuzzy coalitions). Let π = (πS|S ⊆ N) be a probability distribution on the family of all coalitions. Then one has πS ≥ 0 for all S ∈ and
So π represents a generalized coalition which generalizes the notion of a fuzzy coalition in the sense of Ex. 6.2.
Denote by 
the collection of all generalized coalitions y and note that 
is a nonempty, convex and compact set. The optimal utility value 
is the optimal solution of a feasible linear program:
Taking yN as the vector with components yN = 1 and yS = 0 if S ≠ N, we see immediately:
The game (N, υ) is called (positively) balanced if equality is achieved:
The dual linear program associated with (51) has the same optimal value:
Hence linear programming10 duality yields:
THEOREM 8.2 (BONDAREVA [5]). For any cooperative game (N, υ), the two statements are equivalent:
| (1) | (N, υ) is (positively) balanced. |
| (2) | For each i ∈ N there is a number xi ≥ 0 such that |
EX. 8.10. Let (N, υ) be a balanced game. Show:
EX. 8.11 (Linear production games). Show that a linear production game is positively balanced if and only if it admits an optimal production plan.
Covers. The generalized coalition y = (yS|S ⊆ N) is said to cover the set N if equality
which means that each agent i’s activity resource of unit value 1 is fully used under y. The covering value of (N, υ) is the number
As in the derivation of Theorem 8.2, we can characterize the covering value by linear programming duality and find
EX. 8.12. Prove formula (53).
Clearly, one has υ(N) ≤ υc ≤ . Calling the game (N, υ) strongly balanced if it yields the equality
we therefore find:
PROPOSITION 8.1. Every positively balanced game is strongly balanced.
5.The core
5.1.Stable sets
Let us generally understand by a payoff vector of a cooperative game (N, υ) an assignment x of individual values xi ∈ ℝ to the members i ∈ N and hence a parameter vector x ∈ ℝN. For any coalition S ⊆ N, we customarily use the notation
for the total payoff to the members of S under x. The payoff x is said to be feasible11 if
Solution concepts. One of the central issues of cooperative game theory is the question of defining (and then finding) appropriate payoffs to the players in a cooperative game (N, υ). A concept for such payoffs is a solution concept.
The classical solution concept suggested by VON NEUMANN and MORGENSTERN [34] consists in the identification of so-called stable sets of payoff vectors.
To make this notion precise, say that x ∈ ℝN dominates y ∈ ℝN (relative to υ) if there is a coalition S ⊆ N such that each of the members of S is served better under x than under y without exceeding the value υ(S), i.e.,
In this context, a set 
is called stable if
| (1) | All members of  are feasible. |
| (2) | Every feasible payoff z ∉ is dominated by at least one x ∈ . (Hence must be, in particular, nonempty.) |
| (3) | No x ∈ dominates any other y ∈ . |
EX. 8.13 (VON NEUMANN–MORGENSTERN). Let N = {1, 2, 3} and consider the voting game Γ = (N, υ) with
Show that = {(1/2, 1/2, 0), (1/2, 0, 1/2), (0, 1/2, 1/2)} is a stable set.
As intuitively attractive as the solution concept of stable sets may appear, there are some practical drawbacks:
•Not every cooperative game admits a stable set.
•Even if stable sets exist, it may be difficult to identify one.
In the sequel, we will discuss a related solution concept. Although it has similar practical drawbacks, its mathematical ramifications are far-reaching and provide an important link to the mathematical theory of discrete optimization.
5.2.The core
Say that the payoff x ∈ ℝN is coalition rational in the game (N, υ) if each coalition is awarded at least its own value, i.e., if
The core of a cooperative profit game (N, υ) is the set of all feasible coalition rational payoff vectors:
REMARK 8.4 (Efficiency). Note that every payoff vector x ∈ core(υ) is efficient in the sense
EX. 8.14. Let x, y ∈ core(υ). Then x cannot dominate y because otherwise a coalition S would exist with the property
which is a mathematical contradiction.
PROPOSITION 8.2. Let be an arbitrary stable set of the cooperative game (N, υ). Then
Proof. Suppose to the contrary, that a vector y ∈ core(υ)\ exists. Since is stable, it contains a payoff x ∈ that dominates y, i.e, there exists a coalition S ⊆ N so that
which is impossible.
The core of a cost game (N, c) is defined analogously:
Every allocation x ∈ core*(c) distributes the cost c(N) among the players i ∈ N so that no coalition S pays more than its proper cost c(S).
EX. 8.15. Show for the (zero-normalized) cooperative game (N, υ) and its dual (N, υ*):
EX. 8.16. Give an example of a game (N, υ) with core(υ) = .
PROPOSITION 8.3. Let (N, υ) be an arbitrary TU-game.
Then:
| (1) | core(υ) ≠ ⇔ (N, υ) is strongly balanced. |
| (2) | If υ({i}) ≥ 0 holds for all i ∈ N in the game (N, υ), then |
Proof. Exercise left to the reader (cf. Theorem 8.2 and Proposition 8.1).
6.Core relaxations
As Ex. 8.16 shows, the core is not a generally applicable concept for “fair” profit (or cost) distributions to the individual players in a cooperative game (N, υ) because it may be empty. To deal with this drawback, various ways have been suggested to relax (and to strengthen) the idea of the core.
6.1.The open core and least cores
We associate with (N, υ) the open core as the set
The set coreo(υ) is obviously never empty. Hence, every nonnegative parameter vector 
yields a feasible linear program
Notice that the objective function of (54) is bounded from below, because every x ∈ coreo(υ) satisfies
Hence an optimal solution x* with an optimal value c* = c*(υ) = cTx* exists. We call the set
the least c-core of (N, υ).
EX. 8.17 (Classical least core). For cT = (1, 1, . . . , 1) with components ci = 1, c* is precisely the covering value υc of (N, υ) (cf. Section 4). The set
is the classical least core of (N, υ).12
REMARK 8.5. The least core has a natural game-theoretic interpretation: Suppose that a coalition-rational payoff x ∈ ℝN to the players incurs the cost cTx. Then core (υ, c) is the collection of all cost-minimal coalition-rational payoffs.
6.2.Nuclea
The idea of the least core is a relaxation of the constraint x(N) = υ(N) while retaining the other core constraints x(S) ≥ υ(S).
An alternative approach to a relaxation of the core concept consists in retaining the equality x(N) = υ(S) while possibly relaxing the other constraints.
To make the idea precise, say that f ∈ is a relaxation vector if
f is feasible for υ if there exists some scalar ϵ ∈ ℝ such that
Hence, if core(υ) ≠ , every relaxation vector f is feasible (with ϵ = 0, for example).
LEMMA 8.1. Assume that f is a feasible relaxation with fS > 0 for at least one S ∈ . Then there exists a scalar ϵ0 ∈ ℝ such that
Proof. Since f is feasible, the linear program
is feasible. Moreover, the objective of the linear program is bounded from below since every feasible solution x satisfies
and therefore
So an optimal minimal value ϵ0 with the desired property exists.
If it exists, ϵ0 tightens the relaxation f to the best possible and yields the nonempty core relaxation
In the case C0 ≠ , one may try to tighten the constraints further in the same way. To this end, we define the family
Let r0 = r(
0) be the rank of the matrix of incidence vectors of the members of 0. Since each incidence vector is n-dimensional and N ∈ 0 holds, we have
LEMMA 8.2. If r0 = n, then C0 contains exactly one single vector xf.
Proof. r0 = n means that every S ∈ is a linear combination of the members of S ∈ 0. In particular the singleton coalitions {i} are such linear combinations. Since the values x(S) are uniquely determined for all S ∈ 0, it follows that also the component values xi = x({i}) are uniquely determined for any x ∈ C0. Hence there can be only one such x.
In the case r0 = n, we call the unique vector xf ∈ C0 the f-nucleon of the game (N, υ).
If r0 < n, let 
be the family of coalitions S that are linearly independent of 0. For every S ∈ ,
Hence there must exist a vector x ∈ C0 such that
So these inequalities could possibly be tightened even further and one can try to find the best such ϵ1 < ϵ0 as the optimal solution of the linear program
Proof. Completely analogous to the proof of Lemma 8.1 and left to the reader.
If ϵ1 exists, we set
and
Since S ∈ 1 holds for at least one S ∈ , we have
If r1 = n, C1(f) contains a singleton vector xf, which we now term the f-nucleon of (N, υ).
In the case r1 < n, the set 
1 of coalitions S that are not linearly dependent on 1 is non-empty. If fS > 0 holds for at least one S ∈ 1, we derive the existence of a minimal objective value
for the linear program
in exactly the same way as before. And so on.
After ν ≤ n iterations, we arrive at a situation where one of the two possibilities occurs:
| (1) | Cν(f) = {xf}. Then the vector xf is the f-nucleon of (N, υ). |
| (2) | fS = 0 holds for all S ∈ ν. Then the set Cν(f) is the f-nucleon of (N, υ). |
PROPOSITION 8.4. Let f be a feasible relaxation vector for the game (N, υ) and 
. Then the f-nucleon set Cν(f) has the property
| (1) | ν ≤ r( ). |
| (2) | If r() = n, Cν(f) consists of a singleton xf. |
6.3.Nucleolus and nucleon
The nucleolus of the game (N, υ) introduced by SCHMEIDLER [40] is the f1-nucleon relative to the relaxation vector f1 with the unit parameters
By Proposition 8.4, it is clear that the nucleolus always exists and is a singleton.13
The nucleon14 of a game (N, υ) with a nonnegative characteristic function is the fυ-nucleon of the game relative to the relaxations
i.e., the relaxation with the coefficients fυ(S) = υ(S) for S ≠ N.
The choice ϵ = 1 shows that the nucleon relaxation is feasible. The nucleon is a singleton vector xυ if the (incidence vectors of the) coalitions S ∈ with value υ(S) > 0 yield a system of full rank n.
6.4.Excess minimization
Let f be a relaxation vector for (N, υ) and assume15:
This assumption implies that f is a feasible relaxation and that (N, υ) enjoys a unique f-nucleon xf.
For any x ∈ ℝN with x(N) = υ(N), define the excess of a coalition S with fS > 0 as
Since f is feasible, at least one such x exists so that e(x, S) ≥ 0 holds for all excesses. Set
The parameter ϵ0 yields the minimal possible overall bound for the excess of a vector x ∈ and one has
One can now continue and determine the members of C0(f) with minimal excess and the family of coalitions whose excess is not yet fixed. This yields the next parameter ϵ1 and the set
And so on. This shows:
•The f-nucleon xf of (N, υ) arises from a sequence of excess minimizations.
In other words:
The nucleon xf is the unique vector that distributes the value υ(N) among the members of N so that each coalition ends with the minimal possible excess.
There are further value assignment concepts in cooperative games that are of interest. Section 8 will provide examples of such concepts. For the moment, let us continue with the study of the core in its own right.
7.MONGE vectors and supermodularity
In principle, it suffices to compute the nucleon xf of a cooperative game relative to a suitable relaxation vector f in order to have a core vector if the core is nonempty at all (cf. Ex. 8.18). The nucleon is typically difficult to compute, however. MONGE16 vectors are based on an alternative approach, which is computationally more direct. Games all of whose MONGE vectors lie in the core turn out to be particularly interesting.
Throughout the discussion in this section, we consider a fixed zero-normalized cooperative game (N, υ) with n players and collection of coalitions.
7.1.The MONGE algorithm
Given a parameter vector c ∈ ℝN and an arrangement π = i1i2 . . . in of the elements of N, the MONGE algorithm constructs a primal MONGE vector xπ ∈ ℝN and a dual MONGE vector yπ ∈ as follows:
| (M1) | Set  and  for k = 1, 2, . . . , n. |
| (M2) | Set  for k = 1, 2, . . . , n. |
| (M3) | Set  and  for ℓ = 1, 2, . . . , n − 1. Set  otherwise. |
Notice that the construction of the primal MONGE vector xπ proceeds like the greedy algorithm for the cost distribution in network connection games of Section 3 relative to the chain
It is not hard to see17 that the MONGE vectors xπ and yπ satisfy the identity
Different arrangements π and ψ of N, of course, may yield different MONGE sums mπ(c) and mψ(c). Important is the following observation.
LEMMA 8.4. Let π = i1i2 . . . in and ψ = j1j2 . . . jn be two arrangements of N with non-increasing c-values:
Then
Proof. Note that ciℓ = ciℓ+1, for example, implies 
. So we may assume that the components of c have pairwise different values. But then π = ψ holds, which renders the claim trivial.
7.2.The MONGE extension
Lemma 8.4 says that there is a well-defined real-valued function c ↦ [υ](c) with the values
The function [υ]: ℝN → ℝ is called the MONGE extension of the characteristic function υ : → ℝ.
To justify the terminology “extension”, consider a coalition S ⊆ N and its (0, 1)-incidence vector c(S) with the component 
in the case i ∈ S.
An appropriate MONGE arrangement of the elements of N first lists all 1-components and then all 0-components:
Hence we have 
and 
for T ≠ S and conclude
which means that 
and υ agree on (the incidence vectors of) .
REMARK 8.6 (CHOQUET [8] and LOVÁSZ [27]).
Applying the idea and construction of the MONGE sums (58) to non-decreasing value arrangements f1 ≤ . . . ≤ fn of nonnegative functions f : N → ℝ+, one arrives at the CHOQUET integral
where Ak = {k, k + 1, . . . , n} and An+1 = .
The map f ↦ ∫ fdυ is the so-called LOVÁSZ extension of the function υ : → ℝ. Of course, mutatis mutandis, all structural properties carry over from MONGE to CHOQUET and LOVÁSZ.
7.3.Linear programming aspects
Generalizing the approach to the notion of balancedness of Theorem 8.2, let us consider the linear program
and its dual
for a given parameter vector c ∈ ℝN. Observe in the case
that the dual MONGE vector yπ relative to c is a dually feasible solution since 
holds for all S ≠ N. The feasible primal solutions, on the other hand, are exactly the members of core(υ).
Hence, if core(υ) ≠ , both linear programs have optimal solutions. Linear programming duality then further shows
THEOREM 8.3. 
holds for the game (N, υ) if and only if all primal MONGE xπ vectors lie in core(υ).
Proof. Assume ci1 ≥ . . . ≥ cin and π = i1 . . . in. If xπ ∈ core(υ), then xπ is a feasible solution for the linear program (60). Since the dual MONGE vector yπ is feasible for (61), we find
Conversely, means that the dual MONGE vector is guaranteed to yield an optimal solution for (61). So consider an arrangement ψ = j1 . . . jn of N and the parameter vector c ∈ ℝN with the components
The dual vector yψ has strictly positive components 
on the sets 
. It follows from the KKT-conditions for optimal solutions that an optimal solution x* ∈ core(υ) of the corresponding linear program (60) must satisfy the equalities
which means that x* is exactly the primal MONGE vector xπ and, hence, that xπ ∈ core(υ) holds.
7.4.Concavity
Let us call the characteristic function υ : 2N → ℝ concave if υ arises from the restriction of a concave function to the (0, 1)- incidence vector c(S) of the coalitions S, i.e., if there is a concave function f : ℝN → ℝ such that
Accordingly, the cooperative game (N, υ) is concave if υ is concave. We will not pursue an investigation of general concave cooperative games here but focus on a particularly important class of concave games which are closely tied to the MONGE algorithm via Theorem 8.3.
PROPOSITION 8.5. If all MONGE vectors of the game (N, υ) lie in core(υ), then (N, υ) is concave.
Proof. By Theorem 8.3, the hypothesis of the Proposition says
Consequently, it suffices to demonstrate that 
is a concave function. Clearly, 
holds for all scalars λ > 0, i.e., is positively homogeneous.
Consider now arbitrary parameter vectors c, d ∈ ℝN and x ∈ core(υ) such that (c + d) = (c + d)Tx. Then
which exhibits as concave.
REMARK 8.7. The converse of Proposition 8.5 is not true: there are concave games whose core does not include all primal MONGE vectors.
A word of terminological caution. The game-theoretic literature often applies the terminology “convex cooperative game” to games (N, υ) having all primal MONGE vectors in core(υ). In our terminology, however, such games are not convex but concave.
To avoid terminological confusion, one may prefer to refer to such games as supermodular games (cf. Theorem 8.4 below).
7.5.Supermodularity
The central notion that connects the MONGE algorithm with concavity is the notion of supermodularity:
THEOREM 8.4. For the cooperative game (N, υ), the following statements are equivalent:
| (I) | All MONGE vectors xπ ∈ ℝN lie in core(υ). |
| (II) | υ is supermodular, i.e., υ satisfies the inequality |
Proof. Assuming (I), arrange the elements of N to i1i2 . . . in such that
By the definition of the MONGE algorithm, xπ then satisfies
Moreover, xπ(T) ≥ υ(T) holds if xπ ∈ core(υ). So we deduce the supermodular inequality
Conversely, let π = i1, . . . , in be an arrangement of N. We want to show:
Arguing by induction on n = |N|, we note xπ() = υ() and assume:
Consequently, if in ∈ S, the supermodularity of υ yields
EX. 8.19. The preceding proof uses the fact that any vector x ∈ ℝN satisfies the modular equality
As SHAPLEY18 has observed, the concepts of core and stable sets coincide in supermodular games.
THEOREM 8.5 (SHAPLEY [44]). The core of a supermodular game (N, υ) is a stable set.
Proof. We already know that no core vector dominates any other core vector. Let y ∉ core(υ) be an arbitrary feasible payoff vector. We claim that y is dominated by some core vector a. Consider the function
Since y ∉ core(υ), the maximum value g* of g is strictly positive and attained at some coalition Z. Choose an order π = i1 . . . ij . . . in of the elements of N such that Z = {i1, . . . , ik} and let xπ be the corresponding primal MONGE vector.
Define the payoff vector a ∈ ℝN with components
Because xπ(Z) = υ(Z) = kg* + y(S), it is clear that a is feasible and dominates y relative to the coalition Z. It remains to show that a is a core vector.
Keeping in mind that xπ ∈ core(υ) holds (since υ is supermodular), we find for any coalition S:
REMARK 8.8. Since the core of a supermodular game is stable and hence contains any other stable set, we know that core(υ) is actually the unique stable set of the supermodular game (N, υ).
A characteristic function υ is called submodular if the inequality
EX. 8.20. Show for the zero-normalized game (N, υ) the equivalence of the statements:
(1) υ is supermodular.
(2) υ* is submodular.
(3) w = −υ is submodular.
In view of the equality core(c*)= core*(c) (Ex. 8.15), we find that the MONGE algorithm also constructs vectors in the core*(c) of cooperative cost games (N, c) with submodular characteristic functions c.
REMARK 8.9. Note the fine point of Theorem 8.4, which in the language of submodularity says: (N, c) is a submodular cost game if and only if all MONGE vectors xπ lie in core*(c).
Network connection games are typically not submodular. Yet, the particular greedy cost distribution vector discussed in Section 3.3 does lie in core*(c), as the ambitious reader is invited to demonstrate.
REMARK 8.10. Because of the MONGE algorithm, sub- and super-modular functions play a prominent role in the field of discrete optimiziation.19 In fact, many results of discrete optimization have a direct interpretation in the theory of cooperative games. Conversely, the model of cooperative games often provides conceptual insight into the structure of discrete optimization problems.
REMARK 8.11 (Greedy algorithm). The Monge algorithm, applied to linear programs with core-type constraints, is also known as the greedy algorithm in discrete optimization.
While the marginal value ∂iυ(S) of player i’s decision to join respectively to leave the coalition S is intuitively clear, it is less clear how the overall strength of i in a game should be assessed. From a mathematical point of view, there are infinitely many possibilities to do this.
In general, we understand by a value for the class of all TU-games (N, υ) a vector-valued function
that associates with every characteristic function υ a vector Φ(υ) ∈ ℝN. Given Φ, the coordinate value Φi(υ) is the assessment of the strength of i ∈ N in the game (N, υ) according to the evaluation concept Φ.
8.1.Linear values
The value Φ is said to be linear if Φ is a linear operator, i.e., if one has for all games υ, w and scalars λ ∈ ℝ, the equality
In other words: Φ is linear if each component function Φi is a linear functional on the vector space .
Recall from Ex. 8.3 that the unanimity games form a basis of , which means that every game υ can be uniquely expressed as a linear combination of unanimity games. Hence a linear value Φ is completely determined by the values assigned to unanimity games. The same is true for any other basis of , of course.
Indeed, if υ1, . . . , υk ∈ are (the characteristic functions of) arbitrary TU-games and λ1, . . . , λk arbitrary real scalars, the linearity of Φ yields
We give two typical examples of linear values.
The value of SHAPLEY [43]. Consider the unanimity game 
relative to the coalition T ∈ where
In this case, it might appear reasonable to assess the strength of a player s ∈ N \ T as null, i.e., with the value 
, and the strength of each of the players t ∈ T in equal proportion as
Extending ΦSh to all games υ by linearity in the sense
one obtains a linear value υ ↦ ΦSh(υ), the so-called SHAPLEY value.
EX. 8.21. Show that the players in (N, υ) and in its zero-normalization (N, υ**) are assigned the same SHAPLEY values.
The power index of BANZHAF [2]. The BANZHAF power index ΦB appears at first sight to be quite similar to the SHAPLEY value, assessing the power value
while treating all t ∈ T as equals. Assuming T ≠ , the mathematical difference lies in the scaling factor:
As done with the SHAPLEY value, the BANZHAF power index is extended by linearity from unanimity games to all games (N, υ) and thus gives rise to a linear value υ ↦ ΦB(υ).
We will see in Section 8.2 that the difference between the values ΦSh and ΦB can also be explained by two different probabilistic assumptions about the way coalitions are formed.
REMARK 8.12 (Efficiency). If |T| ≥ 1, the SHAPLEY value distributes the total amount
to the members of N and is, therefore, said to be efficient. In contrast, we have
So the BANZHAF power index in not efficient.
REMARK 8.13. One can show that linear values for TU-games typically arise as so-called least square values, namely as values obtained from least square approximations with additive games under linear constraints.20
8.2.Random values
The concept of a random value is based on the assumption that a player i ∈ N joins a coalition S ⊆ N \ {i} with a certain probability πS as a new member. The expected marginal value of i ∈ N thus is
The function Eπ : → ℝN with components 
is the associated random value.
Notice that marginal values are linear. Indeed, if u = λυ + w, one has
for all i ∈ N and S ⊆ N. Therefore, the random value Eπ is linear as well:
REMARK 8.14. The linearity relation (63) implicitly assumes that the probabilities πS are independent of the particular characteristic function υ. If πS depends on υ, the linearity of Eπ is no longer guaranteed.
The BOLTZMANN value (to be discussed in Section 9 below) is a random value that is not linear in the sense of (63) because the associated probability distribution depends on the characteristic function.
8.2.1. The value of BANZHAF
As an example, let us assume that a player i joins any of the 2n−1 coalitions S ⊆ N \ {i} with equal likelihood, i.e., with probability
Consider the unanimity game 
and observe that ∂iυT(S) = 0 holds if i ∉ T. On the other hand, if i ∈ T, then one has
So the number of coalitions S with ∂iυT(S) = 1 equals
Hence we conclude
which means that the random value EπB is identical with the BANZHAF power index. The probabilistic approach yields the explicit formula
8.2.2.Marginal vectors and the SHAPLEY value
Let us imagine that the members of N build up the “grand coalition” N in a certain order
and hence join in the sequence of coalitions
where 
for k = 1, . . . , n. Given the game (N, υ), σ gives rise to the marginal vector21 ∂σ(υ) ∈ ℝN with components
Notice that υ ↦ ∂σ(υ) is a linear value by itself. We can randomize this value by picking the order σ from the set ΣN of all orders of N according to a probability distribution π. Then the expected marginal vector
represents, of course, also a linear value on .
EX. 8.22. Show that the value υ ↦ ∂π(υ) is linear and efficient. (Hint: Recall the discussion of the greedy algorithm for network connection games.)
THEOREM 8.6. The SHAPLEY value results as the expected marginal vector relative to the uniform probability distribution on ΣN, where all orders are equally likely:
(Recall from combinatorics that there are n! = |ΣN| ordered arrangements of N.)
Proof. Because of linearity, it suffices to prove the Proposition for unanimity games . For any order σ = i1 . . . in ∈ ΣN and element ik ∈ N \ T, we have ∂ik (υT) = 0 and hence
On the other hand, the uniform distribution treats all members i ∈ T equally and thus distributes the value υT(N) = 1 equally and efficiently among the members of T:
which is exactly the concept of the SHAPLEY value.
COROLLARY 8.2. The SHAPLEY value ΦSh satisfies:
| (1) | ΦSh(υ) ∈ core(υ) if υ is supermodular. |
| (2) | ΦSh(υ) ∈ core*(υ) if υ is submodular. |
Proof. A marginal vector is a primal MONGE vector relative to the zero vector c = O ∈ ℝN. So all marginal vector lie in core(υ) if υ is supermodular. Since core(υ) is a convex set and ΦSh(υ) a convex linear combination of marginal vectors, ΦSh(υ) ∈ core(υ) follows.
We may interpret the SHAPLEY value within the framework of random values initially introduced. To this end, we assume that an order σ ∈ ΣN is chosen with probability 1/n! and consider a coalition S ⊆ N \{i}. We ask:
•What is the probability 
that i would join S?
Letting k − 1 = |S| be the size of S, the number of sequences σ where i would be added to S is
This is so because:
| (1) | The first k − 1 elements must be chosen from S in any of the (k − 1)! possible orders. |
| (2) | The remaining n − k elements must be from N \ (S ∪ {i}). |
So one concludes
and obtains another explicit formula for the SHAPLEY VALUE:
EX. 8.23. Consider a voting/threshold game (cf. Section 3.4) with four players of weights w1 = 3, w2 = 2, w3 = 2, w4 = 1. Compute the BANZHAF and the SHAPLEY values for each of the players for the threshold w = 4.
9.Boltzmann values
The probabilistic analysis of the previous section shows that the value assessment concepts of the BANZHAF power index and the SHAPLEY value, for example, implicitly assume that players just join — but never leave — an existing coalition in a cooperative game (N, υ).
In contrast, the model of the present section assumes an underlying probability distribution π on the set 2N of all coalitions of N and assigns to player i ∈ N its expected marginal value
EX. 8.24. Let π be the uniform distribution on :
one has
So the expected marginal value of any particular player is zero, if all coalitions are equally likely.
We further do allow π to depend on the particular characteristic function v under consideration. It follows that the functional υ ↦ Ei(υ, π) is not guaranteed to be linear.
The idea of the BOLTZMANN value is based on the fact that one expects the characteristic value
if the players agree on a coalition S ∈ with probability πS. So we may associate with μ its BOLTZMANN temperature T and define the corresponding BOLTZMANN values
for the players i in the cooperative game (N, υ) with expected characteristic value μ.
10.Coalition formation
In the cooperative game (N, υ) it may not be clear in advance which coalition S ⊆ N will form to play the game and produce the value υ(S). The idea behind the theory coalition formation is the viewpoint of a dynamic process in which players join and part in discrete time steps until a final coalition is likely to have emerged.
If this coalition formation process has BOLTZMANN temperature T > 0, the METROPOLIS process suggests the model where, at the moment of a current coalition S ⊆ N, a randomly determined player i ∈ N considers to enact a possible transition
by either becoming inactive or active. The transition is made with probability
In this case, the coalition formation process converges to the corresponding BOLTZMANN distribution on the family of coalitions in the limit.
Cost games. If (N, c) is a cost game, a player’s gain from the transition S → SΔ{i} is the negative marginal cost
So the transition S → SΔ{i} in the METROPOLIS process would be enacted with probability
10.1.Individual greediness and public welfare
Let us assume that N is a society whose common welfare is expressed by the potential υ on the family of all possible coalitions: If the members of N decide to join in a coalition S ⊆ N, then the value υ(S) will be produced.
If all members of N act purely greedily, an i ∈ N has an incentive to change its decision with respect to the current coalition S depending on its marginal value ∂iυ(S) being positive or negative. This behavior, however, will not guarantee a high public welfare.
The METROPOLIS process suggests that the public welfare can be steered if an incentive is provided such that i enacts a move S → SΔ{i} (i.e., changes its decision) with a non-zero probability
If the control parameter T > 0 is sufficiently small, the behavior of an i ∈ N is “almost purely greedy” in the sense
Moreover, a small temperature T > 0 in the coalition formation process allows us to expect a high public welfare.
10.2.Equilibria in cooperative games
In many cooperative games, the grand coalition offers an obvious equilibrium if the players’ utilities are assessed by their marginal values:
LEMMA 8.5. Let (N, υ) be a cooperative game. Then the two statements are equivalent:
| (1) | N is a gain equilibrium with respect to the individual utility functions ui(S) = ∂iυ(S). |
| (2) | υ(N) ≥ υ(N \ i) for all i ∈ N. |
In general, we may view (N, υ) as an n-person matrix game with individual utilities
Hence we know from NASH’s Theorem 6.1 that the randomization of (N, υ) admits an equilibrium.
REMARK 8.15. The randomization of (N, υ) means that each i ∈ N selects a probability 0 ≤ wi ≤ 1 for the probability to become active. The coalition S is thus formed with probability
The expected value of υ is thus
The randomization of (N, υ) essentially is a fuzzy game (see Ex. 6.2) with potential function
Observe, in contrast to the above:
•The BOLTZMANN coalition formation model does not admit coalition equilibria at temperature T ≠ 0, unless υ is constant,
but implies high public welfare if the temperature is small.
Many value concepts (like SHAPLEY and BANZHAF, for example), are based on marginal gains with respect to having joined a coalition as fundamental criteria for the individual utility assessment of a player.
So let us consider the cooperative game (N, υ) and take into account that the game will eventually split N into a group S ⊆ N and the complementary group Sc = N \ S. Suppose a player i ∈ N evaluates its utility relative to the partition (S, Sc) of N by
EX. 8.25. Assume that (N, υ) is a supermodular game. Then one has for all players i ≠ j,
Consequently, the grand coalition N represents a gain equilibrium relative to the utilities υi.
EX. 8.26. Assume that (N, c) is a zero-normalized submodular game and that the players i have the utilities
Show: The grand coalition N is a cost equilibrium relative to the utilities ci.
_____________________
2A.F. MÖBIUS (1790–1868).
4See also Ex. 8.1.
5Core allocations are studied more generally in Section 5.
6Like electricity or water, etc.
7Game theorists disagree on “the best” network cost allocation scheme.
8Also known as a threshold game.
9Also known as a packing.
10cf. Theorem 3.4.
11Here we assume again that υ represents a gain. For a cost potential c, feasibility of an allocation x ∈ ℝN means x(N) ≥ c(N).
12Further game-theoretic implications are studied in, e.g., FAIGLE and KERN [15].
13Related solution concepts are studied in MASCHLER et al. [28].
15To keep the discussion simple — the general case can be analyzed in the same spirit.
16G. MONGE (1746–1818).
17cf. Section 5 of the Appendix.
18L.S. SHAPLEY (1923–2016).
19See, e.g., S. FUJISHIGE [20].
20cf. FAIGLE and GRABISCH [13].
21The marginal vectors are precisely the primal MONGE vectors.
