Cooperative Games

When players can form coalitions and make binding agreements, the key question shifts from what strategy to play to how to share the resulting surplus fairly. This chapter studies cooperative games through the characteristic function and develops the Shapley value as a principled allocation scheme.

Motivating Example: Dividing the loot after a D&D battle¶

After a climactic boss fight, a party of adventurers must divide a hoard of
1,000 gold coins recovered after fighting a dragon.

The party includes:

• Ren the fighter, who absorbed the dragon’s attacks.

• Azel the wizard, who cast a decisive spell at the turning point.

• Quinn the bard, who provided support and distracted the dragon
  with an improvised limerick.

Each character played a crucial role, but in very different ways. How can they
divide the treasure fairly?

Based on past encounters, the party has a sense of how much gold they might
have secured without the full team:

• $\{\text{Ren}\} = 0$ (they can’t get past the dragon alone)

• $\{\text{Azel}\} = 0$ (powerful spells, but too vulnerable on their own)

• $\{\text{Quinn}\} = 0$ (charming, but not a serious threat)

• $\{\text{Ren}, \text{Azel}\} = 900$ (they can defeat the dragon, but with great effort)

• $\{\text{Ren}, \text{Quinn}\} = 400$ (they can stall the dragon,
  but not defeat it)

• $\{\text{Azel}, \text{Quinn}\} = 600$ (Azel can burn the dragon while
  Quinn keeps it distracted)

• $\{\text{Ren}, \text{Azel}, \text{Quinn}\} = 1000$ (the full party defeats
  the dragon smoothly and decisively)

This is a classic example of a cooperative game, and understanding how to
allocate resources fairly in such settings is the focus of this chapter.

Theory¶

Definition: characteristic function game¶

A characteristic function game $G$ is given by a pair
$(N, v)$ where $N$ is the number of players and
$v: 2^{[N]} \to \mathbb{R}$ is a characteristic function which
maps every coalition of players to a payoff.

Example: The characteristic function game of the D&D battle¶

For the D&D battle, we have $N = 3$ and the
characteristic function $v$ is given by:

Definition: Monotone characteristic function game¶

A characteristic function game $G = (N, v)$ is called monotone if it satisfies
$v(C_2) \geq v(C_1)$ for all $C_1 \subseteq C_2$.

Example: The D&D battle is a monotone characteristic function game¶

The function defined in (1) is monotone.
However, the following game is not:

Indeed, Ren and Azel receive more without Quinn than with them, violating monotonicity.

Definition: superadditive characteristic function game¶

A characteristic function game $G = (N, v)$ is called superadditive if it satisfies
$v(C_1 \cup C_2) \geq v(C_1) + v(C_2)$ for all disjoint coalitions
$C_1 \cap C_2 = \emptyset$.

Example: The D&D battle is not a superadditive characteristic function game¶

The function defined in (1) is superadditive.
However, the following game is not:

Indeed:

so the game violates superadditivity.

Definition: Payoff vector¶

When we talk about a solution to a characteristic function game, we mean a
payoff vector $\lambda \in \mathbb{R}_{\geq 0}^N$ that allocates the value of
the grand coalition among the players. In particular, $\lambda$ must satisfy:

Example: A possible payoff vector:¶

One possible payoff vector for (1) is:

This would seem unfair as Quinn gets 450 of the gold. To find a “fair” distribution of the grand coalition we must define what is meant by “fair”. We require four desirable properties:

• Efficiency;

• Null player;

• Symmetry;

• Additivity.

Definition: Efficiency¶

Given a game $G = (N, v)$, a payoff vector $\lambda$ is efficient if:

Example: An efficient Payoff Vector for the D&D Battle¶

An efficient payoff vector is one that shares all 1,000 gold coins like the one in (6).

Definition: Null Player Property¶

Given a game $G = (N, v)$, a payoff vector $\lambda$ satisfies the null player property if, for a player $i$:

If $v(C \cup i) = v(C)$ for all coalitions $C \subseteq \Omega$, then:

Example: The Null Player Property in the D&D Battle¶

In Motivating Example: Dividing the loot after a D&D battle, Quinn contributes very little, yet still adds value to each coalition he joins. For instance, without Quinn, the grand coalition would only obtain 900 coins. If, however, a member of the party made no difference to the value of any coalition, the null player property dictates that this player should receive a payoff of 0.

Definition: Symmetry Property¶

Given a game $G = (N, v)$, a payoff vector $\lambda$ satisfies the symmetry property if, for any pair of players $i, j$:

If $v(C \cup i) = v(C \cup j)$ for all coalitions $C \subseteq \Omega \setminus \{i, j\}$, then:

Example: The Symmetry Property in the D&D Battle¶

In Motivating Example: Dividing the loot after a D&D battle, no two players contribute equally to every coalition they join. If there were such players, the symmetry property would guarantee that they each receive an equal share of the gold

Definition: Additivity Property¶

Given two games $G_1 = (N, v_1)$ and $G_2 = (N, v_2)$, define their sum $G^+ = (N, v^+)$ by:

A payoff vector $\lambda$ satisfies the additivity property if:

Example: The Additive Property in the D&D Battle¶

In Motivating Example: Dividing the loot after a D&D battle, if there were in fact two separate battles, the method for distributing the gold should
yield the same result as treating both battles as a single event with the
combined total reward.

Definition: Predecessors¶

Given a permutation $\pi$ of $[N]$, the set of predecessors of player $i$ in $\pi$ is denoted by $S_pi(i)$ and defined as:

Example: The predecessors for the D&D Battle¶

For Motivating Example: Dividing the loot after a D&D battle we have $N=3$ if we assume the ordering: $(\text{Ren}, \text{Azel}, \text{Quinn})$ Table 1 gives the predecessors of each individual for each of the $3!=6$ permutations of $[N]$.

Definition: Marginal Contribution¶

Given a permutation $\pi$ of $[N]$, the marginal contribution of player $i$ with respect to $\pi$ is defined as:

Example: Marginal Contributions in the D&D Battle¶

For Motivating Example: Dividing the loot after a D&D battle $(\text{Ren}, \text{Azel}, \text{Quinn})$, with $N = 3$. Table 2 shows the marginal contribution $\Delta_\pi^G(i)$ for each player $i$ in each permutation $\pi$ using (1).

We are now ready to define the Shapley value for any cooperative game $G=(N,v)$.

Definition: Shapley Value¶

Given a cooperative game $G=(N,v)$, the Shapley value of player $i$ is denoted by $\phi_i(G)$ and defined as:

Example: The Shapley Value for the D&D Battle¶

For Motivating Example: Dividing the loot after a D&D battle the Shapley value is the vector with entries corresponding to the average of each of the columnts of Table 2.

Giving: $\phi=(350, 450, 200)$

Exercises¶

Programming¶

The CoopGT library has functionality to verify properties of a characteristic function game and also compute the Shapley value.

Here let us define a characteristic function and check if it is valid:

import coopgt.characteristic_function_properties


characteristic_function = {
    (): 0,
    (1,): 0,
    (2,): 0,
    (3,): 0,
    (1, 2): 900,
    (1,3): 400,
    (2, 3): 600,
    (1, 2, 3): 1000,
}
is_valid = coopgt.characteristic_function_properties.is_valid(
    characteristic_function=characteristic_function
)
print(f"Characteristic function valid? {is_valid}")

Characteristic function valid? True

Here we can check if it is monotone:

is_monotone = coopgt.characteristic_function_properties.is_monotone(
    characteristic_function=characteristic_function
)
print(f"Characteristic function monotone? {is_monotone}")

Characteristic function monotone? True

Here we can check if it is supperadditive:

is_superadditive = coopgt.characteristic_function_properties.is_superadditive(
    characteristic_function=characteristic_function
)
print(f"Characteristic function superadditive? {is_superadditive}")

Characteristic function superadditive? True

Let us compute the Shapley value:

import coopgt.shapley_value

shapley_value = coopgt.shapley_value.calculate(
    characteristic_function=characteristic_function
)
print(f"Shapley value: {shapley_value}")

Shapley value: [350. 450. 200.]

Notable Research¶

The Shapley value was first introduced by Shapley in Shapley & others, 1953, a foundational paper in cooperative game theory. Although Shapley is best known for this concept, he was awarded the Nobel Prize in Economics for his later work on matching games.

In large games, the computational cost of calculating the Shapley value can be prohibitive. While not necessarily intractable in the formal sense, as shown in Deng & Papadimitriou, 1994, the number of permutations makes exact computation impractical. One of the earliest practical approaches to this challenge is Castro et al., 2009, which proposes Monte Carlo sampling of permutations as an efficient approximation method.

One of the most impactful application areas of the Shapley value in recent years has been in model explainability. As explored in Exercise 2, the Shapley value provides a principled way to attribute a model’s output to its input features. One of the first papers to formalise this idea was Strumbelj & Kononenko, 2010. This approach has since seen wide application, particularly in healthcare, where a comprehensive overview is provided in Jin et al., 2022.

Conclusion¶

In this chapter, we introduced the theory of cooperative games, where groups of players can form coalitions and share the resulting value. We focused on characteristic function games, where the value of each coalition is known, and explored how to fairly distribute this value using the Shapley value.

The four axioms (efficiency, null player, symmetry, and additivity) uniquely determine the Shapley value. We also saw applications to machine learning interpretability.

Table 3 gives a summary of the concepts of this chapter.

Solutions¶