Chapter 4: Cooperative games

Basic idea: players can form coalitions, and each coalition, for example let's call one $A$, is able to get for themselves a certain amount, denoted by $v(A)$.

The setting is the following: we have a (finite) set, denoted by $N$, which represents the set of the players. $A$ subset of $N$, say $A$, is called coalition.$|A|$ is the number of the players in $A$, and it can be denoted by $a$ (thus $n$ is the number of the players) . Denote also by $2^{N}$ the family of the coalitions of $N$.

Transferable utility function

Central concept of cooperative games: side payment cooperative game function (of transferable utility), it is like the utility/payoff function in non cooperative games. It is a function called $v$:

$v:2^{N}\rightarrow$

If $v(\emptyset)=0$, then we have a special kind of cooperative game called TU game, or transferable utility game.

Note that $2^N$ is the set of all subsets of $N$. If we call $V$ the set of aggregated utilities of players of all coalitions, we can denote a cooperative game by $(N, V : P(N) \rightarrow \R^n)$.

When $v(A) ∈ \{0, 1\}$, the game usually partitions the coalitions in two subsets: $v(A) = 1$ means that A is a winning coalition, while $v(A) = 0$ means that the coalition A is losing. In this case $v$ does not represent utilities or costs.

Cooperative games examples

Seller and buyers

Let's say that player 1 wants to sell a good for a quantity $a$, and that players 2 and 3 are buyers that value the good respectively $b$ and $c$. Assume that $a<b\le c$. The following is the associated cooperative game:

$$\begin{cases} n = 3 \\ v({1})=a, v({2})=v({3})=v({2, 3})=0, v({1, 2})=b, v({1, 3})=c, v({N})=c \end{cases}$$

And here is how to read the game: player 1 has the good, which means that his payoff is how much he values it, which is $a$. Players 2 and 3, alone or together, does not gain anything, since they've got nothing. The coalitions formed respectively by players 1 and 2, and 1 and 3 gain exactly how much player 1 and 2 offer, respectively. The total coalition has as side payment function result $c$, which means that the seller will sell the good to player 3, which is the one that is making the highest offer.

If instead we have two sellers (players 1 and 2), one buyer (player 3) and a indivisible good:

$v({1}) = v({2}) = v({3}) = v({1, 2})=0, v({1, 3}) = v({2, 3}) = v(N)=1.$

Lighter notation:

• $N = {1, 2, 3}$

• List of coalitions: $\{\{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{N\}\}$

• Vector of the game: $(0, 0, 0, 1, 1, 1, 1)$

Glove game

N players are have a glove each, some of them a right glove, some other a left glove. However only pair of gloves are useful. For example:

Player 1 and 2 have a right glove, player 3 has a left glove:

$$\begin{cases} v(\{1\})=v(\{2\})=v(\{3\})=v(\{1,2\})=0 \\ v(\{1,3\})=v(\{2,3\})=v(\{N\})=1 \\ \end{cases}$$

Children game

Three players must vote a name of one of them. If one of the players will get at least two votes, she will get 1000 Euros. They can make binding agreements about how to share the money. In case no one gets two nominations, the 1000 Euros are lost.

$$\left\{\begin{array}{ll} v(A)=1000 & \text { if }|A| \geq 2 \\ v(A)=0 & \text { otherwise. } \end{array}\right.$$

Peer games (also called OR games)

Let $N = \{1, . . . , n\}$ be the set of players and $T = (N, A)$ a directed rooted tree. Each agent $i$ has an individual potential $v_{i}$ which represents the gain that player $i$ can generate if all players at an upper level in the hierarchy cooperate with him.

$\forall(i \in N)$, we denote by $S(i)$ the set of all agents in the unique directed path connecting 1 to i, i.e. the set of superiors of $i$.

Example of peer game

Simple games

A game $v \in G$, where $G(N)$ is the set of all cooperative games having $N$ tas set of players, is called simple if:

1. $v(S) \in \{0,1\} \hspace{0.3em} \forall (S \ne \emptyset)$

2. $A \subseteq C \implies v(A) \le v(C)$ where $C$ is the core of the game (more on that later)

3. $v(N)=1$

A note on property 1: since $v(S)$ is either zero or one, it means that the coalitions are either winning or losing. The 2nd property is also called monotonic property:

A game $G = (N,v)$ is monotonic if $v(S) \le v(T), \forall S \subseteq T$.

Simple games are characterized by the list of all minimal winning coalitions.

Weighted majority games

Weighted majority games are simple games, and coalitions $A$ for which $v(A) = 1$ are the winning coalitions.

Weighted game example

$N = \{1, 2, 3\}$ and $v = [10; 3, 8, 5]$

It means that we have three players, 1, 2 and 3. The characteristic function of the game means that a winning coalitions needs a score of at least 10 to win, and each player weights respectively 3, 8 and 5. From this we can deduce:

• winning coalitions: $\{1, 2\}, \{2, 3\}, N$.

• core of the game: player 2 is a veto player, which means that the core is $(0, 1, 0)$. Both the core of the game and its behaviour in the case a veto player is present will be explained in a bit.

Solution of a cooperative game

A solution vector for the game $v \in \mathcal{G}(N)$ is a vector $x=\left(x_{1}, \ldots, x_{n}\right)$, which assings utility $x_i$ to player $i$. A solution concept (briefly, solution) for the game $v \in \mathcal{G}(N)$ is a multifunction which assigns to every game a set of solution vectors. The solution multifunction can be formulated as:

$$S: \mathcal{G}(N) \rightarrow \mathbb{R}^{n}$$

Minimal conditions that are to be met for any solution of a cooperative game:

$$\begin{cases} x_{i} \ge v(\{i\}), \forall i \\ \sum_{i=1}^{n} x_{i} = v(N) \end{cases}$$

Recall: $x_{i}$ is the amount assigned to the player $i$ by playing individually.

The first condition is pretty straightforward: it means that if a solution assigns to a player less than he is able to do by himself, clearly this player will not participate to the game, so that actually the set of the players is not the set N.

Regarding the second condition, it is actually a mix of two inequalities, a less or equal and a more or equal, which result in a equality relationship. $\sum_{i=1}^{n} x_{i} \le v(N)$means that the global payoff must be at least more or equal than the sum of the payoff of each individual player, since otherwise it would make no sense to cooperate. $\sum_{i=1}^{n} x_{i} \ge v(N)$ is an efficiency condition, it means that all of the payoff amount is distributed.

Additive, superadditive and convex games

1. A game is saif to be additive if:

   $v(A \cup B) = v(A)+v(B)$

2. A game is said to be superadditive if:

   $v(A \cup B) \ge v(A)+v(B)$

   Provided that $A$ and $B$ are disjointed. In other words, together is better than separate.

   Note that superadditivity means that every pair of coalitions has interest in forming a unique coalition, since the global utility increases. Convexity implies superadditivity.

3. A game is said to be convex if:

   $v(A \cup B) \ge v(A)+v(B) - v(A \cap B)$

   Which means that as the coalitions grow, so does the interest of the players in joining them. In this case $A$ and $B$ do not need to be disjointed.

Imputation

Given a game $v$, we call imputation any vector $x$ fulfilling the conditions of the solution for a cooperative game listed above. The set of imputations of a game is called $I(v)$. It is clear that an outcome of the game must be inside the imputations, but this is not enough to characterize a solution, or a solution set, since it is in general too large.

Some observations about imputations

• Efficiency is a mandatory requirement: it makes a real difference with the non cooperative case;

• The imputation set is nonempty if the game is superadditive;

• The imputation set reduces to a singleton if the game is additive.

• For any game $(N, v)$, the imputation set $I(v)$ is bounded and it is the smallest convex set containing a finite number of points in $\mathbb{R}^{n}$, i.e. it is a polytope

WTF is a polytope?

In elementary geometry, a polytope is a geometric object with "flat" sides. It is a generalization in any number of dimensions of the three-dimensional polyhedron.

The core

$C(v)$ is the set:

$$C(v)=\left\{x \in \mathbb{R}^{n}: \sum_{i=1}^{n} x_{i}=v(N) \quad \wedge \sum_{i \in S} x_{i} \geq v(S) \quad \forall S \subset N\right\}$$

The core is a subset of the set of imputations. Note that while imputations are efficient distributions of utilities accepted by all players individually, core vectors are efficient distributions of utilities accepted by all coalitions.

The core throws away all imputations rejected by at least one coalition.

Some notes about the core:

• The definition of core is not particularly meaningful for a two player game: all imputations belong to the core, and conversely.

• About the geometrical/topological structure of the core: it is easy to see that $\forall v$, $C(v)$ is a (possibly empty) convex closed bounded set. More precisely, the vectors in the core can be characterized as those vectors fulfilling a list of linear inequalities.

• When the core of the game $v$ is nonempty then it is a polytope.

Non emptyness of the core formulation

The core is non empty and is is equal to the set of solution of the following linear programming problem:

$$\begin{cases} min \sum_{i=1}^{n}x_{i} \\ \sum_{i \in S}x_{i} \ge v(S), \forall S \subseteq N \end{cases}$$

If and only if the optimal value of the problem is $v(N)$. Note that if the core is non empty, then its a polytope.

Example: core of the two musicians

$$\begin{cases} v(A)=100 \\ v(P)=150 \\ v(\{A, P\}) = v(N) = 400 \end{cases}$$

The core would be $(x_a, x_p)$. First we have to translate the game into a system using the solution of cooperative of the cores formulas:

$$\begin{cases} x_a \ge 100 \\ x_p \ge 150 \\ x_a+x_p = 400 \end{cases}$$

From the third equation we get:

$$x_p = 400 - x_a$$

Then we can substitute into the second one:

$$x_a \le 250 \rightarrow 100 \le x_a \le 250$$

And we construct $C(v)$ as:

$$C(v) = (x, 400 - x)$$

Where $x \ge 100$ and $x \le 250$.

About the core of convex games

If $v$ is a convex game, then $C(v) \neq 0$ and the Shapley values of the players are its core.

About the core of additive and superadditive games

The core can be empty for superadditive games, and it is a singleton for additive games:

$(v(\{1\}), ..., v(\{n\}))$

Note: In case of three players, the dual formulation allows concluding that, for superadditive games, the following condition becomes necessary and sufficient for nonemptyness of the core:

$v({1, 2}) + v({1, 3}) + v({2, 3}) ≤ 2v(N).$

About the core of simple games

Let $v$ be a simple game. Then $C(v)\ne \emptyset$ if and only if there is at least one veto player. When a veto player exists, the core is the closed convex polytope with extreme points the vectors $(0, . . . , 1, . . . , 0)$ where the 1 corresponds to a veto player.

#### About the core of glove games

Every glove game is superadditive.

Veto player

In a game $v$, a player $i$ is a veto player if $v(A)=0, \forall A$ such that $i \notin A$. In simpler terms, a veto player is a player that must be in a coalition in order for it to win, hence the name 'veto' player.

Condition of non emptyness of the core in simple game

If $v$ is a simple game, then $C(v) \neq 0 \iff$ there is at least a veto player. Moreover when a veto player exists, the core is a closed convex polytope with extreme points the vectors $(0, . . . , 1, . . . , 0)$ where the 1 corresponds to a veto player.

Nucleolus

For every TU game $v$ with nonempty imputation set, the nucleolus is a singleton. It is a one point solution.

If the core is not null, then the nucleolus is contained by it. This means that if the core is null, we cannot take a priori conclusions about the nucleolus.

Shapley value

Consider the following function $\sigma: \mathcal{G}(N) \rightarrow \mathbb{R}^{n}$:

$$\sigma_{i}(v)=\sum_{S \in 2^{N \backslash\{i\}}} \frac{s !(n-s-1) !}{n !}[v(S \cup\{i\})-v(S)]$$

Then $\sigma$, called Shapley value, is the only function $\phi$ fulfilling properties of efficiency, symmetry, null player and additivity. Thus the Shapley value is a weighted sum of all marginal contributions of the players.

Properties of the Shapley value

1. For every $v \in \mathcal{G}, \sum_{i \in N} \phi_{i}(v)=v(N)$

2. Let $v$ be a game with the following property, for players $i, j$ : for every $A$ not containing $i, j, v(A \cup\{i\})=v(A \cup\{j\})$. Then $\phi_{i}(v)=\phi_{j}(v)$

3. Let $v \in \mathcal{G}$ and $i \in N$ be such that $v(A)=v(A \cup\{i\})$ for all $A$. Then $\phi_{i}(v)=0$

4. for every $v, w \in \mathcal{G}, \phi(v+w)=\phi(v)+\phi(w)$.

The first axiom is simply efficiency and it is mandatory, as we already argued, talking about solutions in cooperative theory. The second one is symmetry: in the game $v$ the two players $i$, $j$ contribute to any coalition in exactly the same way, thus they must have the same utility (or power). The third one says that a null player, which is a player contributing nothing to any coalition, should have zero. More complicated is the interpretation of the fourth axiom, even if its mathematical meaning is quite simple and attracting: it says that $\phi$ acts additively (actually linearly, as we shall see) on the vector space $\mathcal{G}$.

Banzhaf value

$$\beta_{i}(v)=\sum_{S \in 2^{N \backslash\{i\}}} \frac{1}{2^{n-1}}(v(S \cup\{i\})-v(S))$$

Note that the Banzhaf values has the same properties of the Shapley value, except for efficiency.

Note about semivalues computation

In a three player game with two symmetric player (let's call them 1 and 2) the computation of Shapley values can be easily simplified by calculating the value of one of the symmetric player, and since they are symmetric, also the other player would have the same value ($\sigma_1=\sigma_2$). Then we can apply the efficiency property, which means that we'll compute the value of the third player (player 3) as follows: $\sigma_3 = v(N)-\sigma_1-\sigma_2$.

Note about semivalues in simple games

Both the Shapley and the Banzhaf value are called semivalues. In simple games, the Shapley value becomes:

$$\sigma_{i}(v)=\sum_{S \in \mathcal{S}_{i}} \frac{s !(n-s-1) !}{n !}$$

And the Banzhaf value becomes:

$$\beta_{i}(v)=\sum_{S \in 2^{N \backslash\{i\}}} \frac{1}{2^{n-1}}$$

Which means that every semivalue assigns zero to every null player.

Imputation, core and nucleolus properties recap

Both the Shapley values and the core belong to the imputation set, assuming that it is non empty. If also the core is non empty, then it contains the Shapley values and it is contained by the imputation set.

• If the game is additive:

  • Core and imputation set are singleton

• If the game is superadditive:

  • imputation set is non empty

  • core may be empty, and if $|A|\le3$, then $C(v) \ne 0 \iff v({1, 2}) + v({1, 3}) + v({2, 3}) ≤ 2v(N).$

• If the game is convex:

  • Core and imputation are non empty and the core is equal to the Shapley values of the players

• If the game is simple:

  • Then the core is non empty only if there is at least a veto player, and it is equal to all zero except for veto players, which are equal to one