A primer on cooperative game theory and power indices

Shane Chu

A primer on cooperative game theory and power indices

Cooperative game theory studies what happens when players form coalitions and produce value together, and asks how that value should be attributed back to the individual players. This is a plain reference for the standard definitions: cooperative games, the Shapley value and its axioms, the Banzhaf index, and the weighted-marginal-contribution form that contains both as special cases. Nothing here is new; for a full treatment see Maschler et al. (2013).

Cooperative games

A cooperative game is a pair $(\mathcal N, v)$ , where $\mathcal N = \{1, \dots, n\}$ is a finite set of players and

v : 2^{\mathcal N} \rightarrow \mathbb R, \qquad v(\emptyset) = 0

is a characteristic function (or payoff function) that assigns a real value to every coalition $\mathcal S \subseteq \mathcal N$ . The full set $\mathcal N$ is the grand coalition.

The value $v(\mathcal S)$ is the payoff the players in $\mathcal S$ can secure by cooperating among themselves. A few standard restrictions on $v$ :

Monotone: $v(\mathcal S) \leq v(\mathcal T)$ whenever $\mathcal S \subseteq \mathcal T$ .
Superadditive: $v(\mathcal S \cup \mathcal T) \geq v(\mathcal S) + v(\mathcal T)$ whenever $\mathcal S \cap \mathcal T = \emptyset$ .
Simple: $v$ is monotone and takes values in $\{0, 1\}$ with $v(\mathcal N) = 1$ . These model voting; a coalition with $v(\mathcal S) = 1$ is winning.

Marginal contributions

The marginal contribution of player $i$ to a coalition $\mathcal S \subseteq \mathcal N \setminus \{i\}$ is

\mathcal M_i(\mathcal S) = v(\mathcal S \cup \{i\}) - v(\mathcal S).

Every index below is a weighted average of marginal contributions; the indices differ only in the weights.

The Shapley value

The Shapley value of player $i$ in the game $(\mathcal N, v)$ is

\phi_i(v) = \sum_{\mathcal S \subseteq \mathcal N \setminus \{i\}} \frac{|\mathcal S|! \, (n - |\mathcal S| - 1)!}{n!} \, \mathcal M_i(\mathcal S).

Equivalently, averaging marginal contributions over all $n!$ orderings of the players,

\phi_i(v) = \frac{1}{n!} \sum_{\pi} \mathcal M_i\big(P_i^{\pi}\big),

where the sum runs over all permutations $\pi$ of $\mathcal N$ and $P_i^{\pi}$ is the set of players preceding $i$ in $\pi$ . The intuition is the random-arrival picture: the players show up one at a time in a random order, each is credited with what it adds to those already present, and the Shapley value is a player's expected credit under a uniformly random order. The two forms are equal because exactly $|\mathcal S|! \, (n - |\mathcal S| - 1)!$ orderings place the set $\mathcal S$ before $i$ and the rest after.

The Shapley value is characterized by four axioms (Shapley, 1953). State $\phi$ as a map from games to payoff vectors in $\mathbb R^n$ .

Efficiency. $\sum_{i \in \mathcal N} \phi_i(v) = v(\mathcal N)$ . The whole value of the grand coalition is divided among the players, with nothing left over.
Null player. If $\mathcal M_i(\mathcal S) = 0$ for all $\mathcal S \subseteq \mathcal N \setminus \{i\}$ , then $\phi_i(v) = 0$ .
Symmetry. If $\mathcal M_i(\mathcal S) = \mathcal M_j(\mathcal S)$ for all $\mathcal S \subseteq \mathcal N \setminus \{i, j\}$ , then $\phi_i(v) = \phi_j(v)$ .
Additivity. $\phi_i(v + w) = \phi_i(v) + \phi_i(w)$ , where $(v + w)(\mathcal S) = v(\mathcal S) + w(\mathcal S)$ .

Theorem (Shapley, 1953). The Shapley value is the unique map

\phi

satisfying efficiency, the null-player property, symmetry, and additivity.

An alternative characterization replaces additivity with marginality: a player's payoff depends only on its own marginal contributions.

Theorem (Young, 1985). The Shapley value is the unique map satisfying efficiency, symmetry, and marginality.

Simple games and the Banzhaf index

In a simple game, $\mathcal M_i(\mathcal S) \in \{0, 1\}$ , and $\mathcal M_i(\mathcal S) = 1$ exactly when $i$ is a swing (or pivotal) player for $\mathcal S$ : the coalition $\mathcal S$ loses but $\mathcal S \cup \{i\}$ wins.

The (absolute) Banzhaf index of player $i$ is

\beta_i(v) = \frac{1}{2^{\,n-1}} \sum_{\mathcal S \subseteq \mathcal N \setminus \{i\}} \mathcal M_i(\mathcal S),

i.e. the fraction of coalitions for which $i$ is a swing player. The normalized Banzhaf index divides by $\sum_{j} \beta_j(v)$ so the values sum to one.

Where the Shapley value averages over arrival orders, the Banzhaf index (Banzhaf, 1965) ignores order entirely and simply asks how often a player turns a losing coalition into a winning one. Applying the Shapley value to a simple game gives the Shapley-Shubik index. Both measure voting power, and they generally disagree because they weight coalitions differently.

The Banzhaf index satisfies the null-player, symmetry, and additivity axioms but not efficiency.

Power indices as weighted marginal contributions

Both indices have the form

\rho_i(v) = \sum_{\mathcal S \subseteq \mathcal N \setminus \{i\}} \omega(|\mathcal S|) \, \mathcal M_i(\mathcal S),

differing only in the weight $\omega$ :

Shapley: $\;\omega(s) = \dfrac{s! \, (n - s - 1)!}{n!}$ ,
Banzhaf: $\;\omega(s) = \dfrac{1}{2^{\,n-1}}$ .

This common form is the class of semivalues (Weber, 1988).

A semivalue is any map $\rho_i(v) = \sum_{\mathcal S \subseteq \mathcal N \setminus \{i\}} p_{|\mathcal S|} \, \mathcal M_i(\mathcal S)$ whose weights $p_s \geq 0$ satisfy

\sum_{s=0}^{n-1} \binom{n-1}{s} \, p_s = 1.

The Shapley value is the unique efficient semivalue; the Banzhaf index is the semivalue with constant weights.

Values for groups of players

To score a coalition $\mathcal T \subseteq \mathcal N$ rather than a single player, treat $\mathcal T$ as one composite player and apply the same machinery. The general weighted form becomes

\rho(\mathcal T) = \sum_{\mathcal S \subseteq \mathcal N \setminus \mathcal T} \omega(\mathcal S) \, \big(v(\mathcal S \cup \mathcal T) - v(\mathcal S)\big),

with the Shapley weight generalizing to $\omega(\mathcal S) = \frac{|\mathcal S|! \, |\mathcal T|! \, (n - |\mathcal S| - |\mathcal T|)!}{n!}$ . Values tailored to group structure also exist, but the composite-player view covers the common case.

Computation

The exact formulas sum over $2^{\,n-1}$ subsets, so direct evaluation is exponential in $n$ . For weighted voting games, computing the Banzhaf and Shapley-Shubik indices is #P-hard / NP-hard (Deng and Papadimitriou, 1994), though dynamic programming over integer weights gives a pseudo-polynomial algorithm. In general, the permutation form is estimated by Monte Carlo sampling over orderings (Castro et al., 2009).

References

Lloyd S. Shapley, A value for n-person games, 1953.
H. Peyton Young, Monotonic solutions of cooperative games, 1985.
John F. Banzhaf, Weighted voting doesn't work: A mathematical analysis, 1965.
Robert J. Weber, Probabilistic values for games, 1988.
Xiaotie Deng, On the complexity of cooperative solution concepts, 1994.
Javier Castro, Polynomial calculation of the Shapley value based on sampling, 2009.
Michael Maschler, Game theory, 2013.

Contact me by E-mail | Github | Linkedin
This work is licensed under CC BY-SA 4.0. Last modified: June 14, 2026.
Website built with Franklin.jl and the Julia language.