Sharing the value: allocations and imputations¶

Now that we understand that a cooperative game is described by a function $v(S)$, a natural question arises:

How should we split the value generated by the grand coalition $N$?

We know how much each group can generate. But we have not yet said how that value is distributed among players.

This is where a new central object of the theory appears.

Allocations¶

One way to split value among players is via a vector

\[ x = (x_1, x_2, \dots, x_n) \in \mathbb{R}^n, \]

where $x_i$ represents what player $i$ receives.

This vector is called an allocation.

It no longer depends on coalitions. It describes only the final outcome of cooperation.

A first natural requirement: distribute all available value¶

If the players together can generate $v(N)$, it is reasonable to require that all of it is distributed:

\[ \sum_{i \in N} x_i = v(N). \]

If the sum is smaller, we are "throwing away" value. If it is larger, we are distributing something that does not exist.

This condition is called efficiency.

A second natural requirement: no one accepts less than acting alone¶

Each player knows what they can generate on their own: $v(\{i\})$.

So a division only makes sense if

\[ x_i \ge v(\{i\}), \quad \text{for all } i \in N. \]

Otherwise, the player would prefer to leave the cooperation.

This condition is called individual rationality.

Imputations¶

When an allocation satisfies these two properties -- efficiency and individual rationality -- it gets a special name.

We call such an allocation an imputation.

Mathematically, the set of all imputations is

\[ \left\{ x \in \mathbb{R}^n \,:\, \sum_{i \in N} x_i = v(N) \text{ and } x_i \ge v(\{i\}) \ \forall i \right\}. \]

This set is called the imputation set.

What does this mean intuitively?¶

An imputation is simply a way to split the total value that:

uses exactly everything that was generated, and
ensures nobody is worse off compared to acting alone.

We have not said anything about fairness yet. We have not said anything about stability yet. We have not said anything about power yet.

We are only describing the divisions that make sense to consider.

Visualizing it¶

Geometrically, imputations form a subset of a hyperplane in $\mathbb{R}^n$: all possible divisions of the total value, constrained by the requirement that each player must receive at least what they could get alone.

This is the "space" where all classic solutions will live.

Imputation set for the pipeline example: $ \{(x_1,x_2,x_3) \, : \, x_1+x_2+x_3 = 100,\; x_i \ge 0\} $

Why is this such an important step?¶

Because now we can restate all the theory's questions very clearly:

Among all imputations, which are stable?
Among all imputations, which are fair?
Among all imputations, which best reflect each player's power?

The concepts that come next -- core, Shapley value, least-core, kernel, power indices -- are nothing more than different ways of selecting points inside this set.

From here on, cooperative game theory becomes the art of selecting good imputations.