References:

• https://en.wikipedia.org/wiki/Cooperative_game_theory
• https://en.wikipedia.org/wiki/Shapley_value
• conversations with GPT-4

A cooperative game consists of a set of $N$ players, called the grand coalition, and a characteristic function $v: 2^N \to \mathbb{R}$, which specifies the payoff achieved by cooperation among any subset of the players. The characteristic function satisfies $v(\emptyset) = 0$, and is usually assumed to be superadditive, meaning that the union of disjoint coalitions has value at least as great as those coalitions individually: $v(S \cup T) \ge v(S) + v(T)$ for $S, T \subseteq N$ when $S \cap T = \emptyset$.

Superadditivity can be thought of as the assumption that cooperation is generally beneficial, perhaps due to economies of scale or synergies between players. It implies that the greatest possible value is realized when the set of all players (the grand coalition) works together.

I think that the mental model for thinking about cooperative game theory is that cooperation is the only possible interaction between the players: in the absence of a coalition, the players can all revert to collecting their individual payoffs. Under this assumption, superadditivity is the only incentive to cooperation, because plain old 'additive' payoffs are still available without cooperation. This would not be true if the underlying world in the absence of competition is actually competitive: if failing to form a coalition leaves the players in the situation of questing after some rivalrous good, so that the individual payoffs are not additive but perhaps even mutually exclusive.

A stronger condition than superadditivity is supermodularity: where the reward to joining a coalition increase with the size of the coalition, so that cooperation tends to 'snowball': $v(S \cup T) + v(S \cap T) \ge v(S) + v(T)$ for all $S, T \subseteq N$. A game with a supermodular characteristic function is called a convex game.

Solution concepts

In cooperative game theory the main task is to allocate the payoff for the grand coalition $v(N)$. Most solution concepts begin with the notation of an imputation. This is any vector allocating payoffs $x_i$ to individual players $i$ that satisfies the basic properties of

1. efficiency: summing to the total payoff, $\sum_{i \in N} x_i = v(N)$, and
2. individual rationality: giving each player at least as much as they would get on their own, $x_i \ge v({i})$.

Stable solutions and the core

We would ideally like a solution to have some notion of stability. A basic notion is that no subset of players can do better by breaking off on their own. The set of imputations satisfying this property is called the core. Formally, an imputation $x$ is in the core if $\sum_{i \in S} x_i \ge v(S)$ for all subsets $S \subseteq N$. We can think of the core as the set of all imputations under which players are incentivized to form the grand coalition.

Some properties of the core:

• It may be empty. For example, if there are three workers and a heavy load that requires only two workers to carry, then any two of the workers can split off and get the whole payoff to themselves. So there is no stable way to allocate payoff to all three workers.
  • We can of course just give worker 3 a payoff of zero, effectively cutting them out of the coalition: $(0.5, 0.5, 0)$ is a valid imputation. But is not stable, since worker 3 could counter-offer with something like $(0, 0.6, 0.4)$ to form the $\{2, 3\}$ coalition cutting out worker 1 , which worker 2 would accept. And so on. There would be a stable solution if we had one fewer worker, but there is no stable way to decide which worker to cut out.
• It is defined by a set of linear inequalities on payoff vectors, so it is always closed and convex. And it can be solved for as the solution to a set of linear inequalities (i.e., a linear programming problem with a constant objective).
• The Bondareva-Shapley theorem says that the core exists if and only if a game is balanced in a particular sense. I don't really understand if this is supposed to provide any extra intuition, or just add technical difficulty.

Shapley values and fair allocation

The core is a set of imputations which are stable, but as a concept it doesn't tell us which of these imputations bargainers will or 'should' converge on.

Some other properties we might hope for in a solution include:

• symmetry: players that provide identical value should receive identical value. Formally, if adding player $i$ to a coalition always leads to the same value as adding player $j$ (for all coalitions not already containing one of those players), then we should distribute payoffs equally, $x_i = x_j$.
• null player: a player that never adds value (formally, if $v(S \cup {i}) = v(S)$ for all coalitions $S$) should receive nothing.
• linearity: combining two separate games described by $v$ and $w$ into a new game with payoffs $v + w$ should lead to a distribution equal to the sum of the original distributions.

The Shapley value is the unique payoff rule that satisfies these properties (as well as various others). It is defined as the average value that a player adds when joining the coalition, taken over all possible orders (permutations of players) in which the grand coalition can be formed:

where $P(\sigma, i)$ is the set of predecessors of $i$ in the permutation $\sigma$ (for example, if $N = 5$ and $\sigma = (5, 2, 1, 4, 3)$, then $P(\sigma, 4) = \{5, 2, 1\}$ are the players that precede player 4 in this permutation).

Note that the Shapley value can be outside the core. In the example above where three workers are doing a task that only requires two workers, symmetry of the workers implies that the Shapley value is $(\frac{1}{3}, \frac{1}{3}, \frac{1}{3})$, even though this is not a stable distribution (and indeed, no stable distribution is possible).