GAME THEORY
COOPERATIVE GAMES
Department of Economics
1. Definitions
A coalitional (or cooperative) game is a model of interacting decision-makers that focuses
on the behavior of groups of players.
N denotes the set of players. A coalition is a group of players S ⊂ N . We refer to N as
the grand coalition. Every coalition S has a set of available actions AS .
An outcome consists of a partition of N (coalition structure) and one action associated
with each coalition in the partition,
6 k, ∪k Sk = N, ak ∈ ASk .
(Sk , ak )k=1,...,k̄ with Sj ∩ Sk = ∅, ∀j =
Each agent i has preferences over the set of all outcomes represented by a utility function
ui . We restrict attention to settings without externalities. Agent i cares only about the
action of the coalition he belongs to, i.e., ∃Ui : ∪S3i AS → R s.t.
ui ((Sk , ak )k=1,...,k̄ ) = Ui (aj ) if i ∈ Sj .
Example 1 (Three-player majority game). Three agents have access to a unit of output.
Any majority—coalition of two or three agents—may control the allocation of the output.
The output may be shared among the members of the winning coalition any way they wish.
No agent can produce any output by himself. Each agent only cares about the amount of
output he receives (prefers more to less). Actions for each coalition? Feasible outcomes?
Example 2 (Firm and workers). Consider a firm and n potential workers. The firm generates
profit f (k) from hiring k workers, where f is some exogenously given function. Any coalition
consisting only of workers produces profit 0. Each agent only cares about his own share of
the profit. Actions for each coalition? Feasible outcomes?
,2
Example 3 (Marriage market). A group of men and a group of women can be matched
in pairs. A matching of a coalition of men and women is a partition of the coalition into
man-woman pairs and single individuals. Each person cares only about her partner (and
how she/he compares to being single). Actions for each coalition? Feasible outcomes?
Definition 1. A game is cohesive if for every outcome (Sk , ak )k=1,...,k¯ there exists an outcome
generated by the grand coalition which is at least as desirable as (Sk , ak )k=1,...,k¯ for every
player.
The solution concepts we consider assume that the grand coalition forms (rather than
outcomes involving a non-trivial coalition structure) and have attractive interpretations only
for cohesive games.
Definition 2. A game with transferable payoffs associates to any coalition S a real number
v(S), which is interpreted as the worth of the coalition S. We assume v(∅) = 0. The set of
actions available to coalition S consists of all possible divisions (xi )i∈S of v(S) among the
P
members of S, i∈S xi = v(S).
When is a game with transferable payoffs cohesive? Which of the games above have
transferable payoffs? What are the corresponding worth functions?
2. The Core
Which action may we expect the grand coalition to choose? We seek actions that withstand
the pressures imposed by the opportunities of each coalition. We define an action of the
grand coalition to be “stable” if no coalition can break away and choose an action that all
its members prefer. Formally, a coalition S blocks an action aN of the grad coalition if there
is an action aS ∈ AS that all members of S strictly prefer to aN . The set of all actions that
cannot be blocked forms the core.
Definition 3. The core of a coalitional game is the set of actions aN of the grand coalition
N that are not blocked by any coalition.
If a coalition S has an action that all its members prefer to an action aN of the grand
coalition, we say that S blocks aN .
, COOPERATIVE GAMES 3
For a game with transferable payoffs with payoff function v, a coalition S can block the
P
allocation (xi )i∈N iff xS < v(S), where xS = i∈S xi . Hence the allocation x is in the core
of the game iff xS ≥ v(S), ∀S ⊂ N .
Example 4 (Two-player split the dollar with outside options). v({1}) = p, v({2}) =
q, v({1, 2}) = 1. The core is given by the set of allocations
{(x1 , x2 )|x1 + x2 = 1, x1 ≥ p, x2 ≥ q}.
What happens for p = q = 0? What if p + q > 1?
Argue that the core of the three-player majority game is empty.
When is the core non-empty? A vector (λS )S∈2N of non-negative numbers is a balanced
collection of weights if
X
λS = 1, ∀i ∈ N.
{S⊂N |i∈S }
A payoff function v is balanced if
X
λS v(S) ≤ v(N ) for every balanced collection of weights λ.
S ⊂N
Interpretation: each player has a unit of time, which he needs to distribute among all his
coalitions. For coalition S to be active for λS time and generate payoff λS v(S), all its
members need to be active in S for this fraction of time λS . A game is balanced if there is no
allocation of time across coalitions that yields a total value greater than that of the grand
coalition.
Theorem 1 (Bondareva 1963; Shapley 1967). A coalitional game with transferable payoffs
has a non-empty core iff it is balanced.
Proof. Consider the linear program
X X
min xi s.t. xi ≥ v(S ), ∀S ⊂ N.
i∈N i∈S
The core is non-empty iff the minimized sum is not greater than v(N ).1 The dual of the
latter linear program is given by
X X
max λS v(S) s.t. λS ≥ 0, ∀S ⊂ N & λS ≤ 1, ∀i ∈ N .
S ∈2N S3i
1Actually, the optimal value needs to be exactly v(N ) in this case.
COOPERATIVE GAMES
Department of Economics
1. Definitions
A coalitional (or cooperative) game is a model of interacting decision-makers that focuses
on the behavior of groups of players.
N denotes the set of players. A coalition is a group of players S ⊂ N . We refer to N as
the grand coalition. Every coalition S has a set of available actions AS .
An outcome consists of a partition of N (coalition structure) and one action associated
with each coalition in the partition,
6 k, ∪k Sk = N, ak ∈ ASk .
(Sk , ak )k=1,...,k̄ with Sj ∩ Sk = ∅, ∀j =
Each agent i has preferences over the set of all outcomes represented by a utility function
ui . We restrict attention to settings without externalities. Agent i cares only about the
action of the coalition he belongs to, i.e., ∃Ui : ∪S3i AS → R s.t.
ui ((Sk , ak )k=1,...,k̄ ) = Ui (aj ) if i ∈ Sj .
Example 1 (Three-player majority game). Three agents have access to a unit of output.
Any majority—coalition of two or three agents—may control the allocation of the output.
The output may be shared among the members of the winning coalition any way they wish.
No agent can produce any output by himself. Each agent only cares about the amount of
output he receives (prefers more to less). Actions for each coalition? Feasible outcomes?
Example 2 (Firm and workers). Consider a firm and n potential workers. The firm generates
profit f (k) from hiring k workers, where f is some exogenously given function. Any coalition
consisting only of workers produces profit 0. Each agent only cares about his own share of
the profit. Actions for each coalition? Feasible outcomes?
,2
Example 3 (Marriage market). A group of men and a group of women can be matched
in pairs. A matching of a coalition of men and women is a partition of the coalition into
man-woman pairs and single individuals. Each person cares only about her partner (and
how she/he compares to being single). Actions for each coalition? Feasible outcomes?
Definition 1. A game is cohesive if for every outcome (Sk , ak )k=1,...,k¯ there exists an outcome
generated by the grand coalition which is at least as desirable as (Sk , ak )k=1,...,k¯ for every
player.
The solution concepts we consider assume that the grand coalition forms (rather than
outcomes involving a non-trivial coalition structure) and have attractive interpretations only
for cohesive games.
Definition 2. A game with transferable payoffs associates to any coalition S a real number
v(S), which is interpreted as the worth of the coalition S. We assume v(∅) = 0. The set of
actions available to coalition S consists of all possible divisions (xi )i∈S of v(S) among the
P
members of S, i∈S xi = v(S).
When is a game with transferable payoffs cohesive? Which of the games above have
transferable payoffs? What are the corresponding worth functions?
2. The Core
Which action may we expect the grand coalition to choose? We seek actions that withstand
the pressures imposed by the opportunities of each coalition. We define an action of the
grand coalition to be “stable” if no coalition can break away and choose an action that all
its members prefer. Formally, a coalition S blocks an action aN of the grad coalition if there
is an action aS ∈ AS that all members of S strictly prefer to aN . The set of all actions that
cannot be blocked forms the core.
Definition 3. The core of a coalitional game is the set of actions aN of the grand coalition
N that are not blocked by any coalition.
If a coalition S has an action that all its members prefer to an action aN of the grand
coalition, we say that S blocks aN .
, COOPERATIVE GAMES 3
For a game with transferable payoffs with payoff function v, a coalition S can block the
P
allocation (xi )i∈N iff xS < v(S), where xS = i∈S xi . Hence the allocation x is in the core
of the game iff xS ≥ v(S), ∀S ⊂ N .
Example 4 (Two-player split the dollar with outside options). v({1}) = p, v({2}) =
q, v({1, 2}) = 1. The core is given by the set of allocations
{(x1 , x2 )|x1 + x2 = 1, x1 ≥ p, x2 ≥ q}.
What happens for p = q = 0? What if p + q > 1?
Argue that the core of the three-player majority game is empty.
When is the core non-empty? A vector (λS )S∈2N of non-negative numbers is a balanced
collection of weights if
X
λS = 1, ∀i ∈ N.
{S⊂N |i∈S }
A payoff function v is balanced if
X
λS v(S) ≤ v(N ) for every balanced collection of weights λ.
S ⊂N
Interpretation: each player has a unit of time, which he needs to distribute among all his
coalitions. For coalition S to be active for λS time and generate payoff λS v(S), all its
members need to be active in S for this fraction of time λS . A game is balanced if there is no
allocation of time across coalitions that yields a total value greater than that of the grand
coalition.
Theorem 1 (Bondareva 1963; Shapley 1967). A coalitional game with transferable payoffs
has a non-empty core iff it is balanced.
Proof. Consider the linear program
X X
min xi s.t. xi ≥ v(S ), ∀S ⊂ N.
i∈N i∈S
The core is non-empty iff the minimized sum is not greater than v(N ).1 The dual of the
latter linear program is given by
X X
max λS v(S) s.t. λS ≥ 0, ∀S ⊂ N & λS ≤ 1, ∀i ∈ N .
S ∈2N S3i
1Actually, the optimal value needs to be exactly v(N ) in this case.
