Skip to content

tucoopy.solutions.shapley

Shapley value and semivalues.

This module implements the Shapley value, weighted Shapley variants, Monte Carlo approximation, and a generic semivalue helper.

semivalue 

semivalue(game, *, weights_by_k, normalize=False)

Compute a semivalue for a TU cooperative game.

A semivalue is defined by weights \(p_k\) for coalition sizes \(k=0,\ldots,n-1\):

\[ \phi_i = \sum_{S \subseteq N \setminus \{i\}} p_{|S|} \big( v(S \cup \{i\}) - v(S) \big). \]

The standard semivalue normalization is:

\[ \sum_{k=0}^{n-1} \binom{n-1}{k} \, p_k = 1. \]

Parameters:

Name Type Description Default
game GameProtocol

TU game.

 required
weights_by_k Sequence[float]

Sequence of length n_players where entry k is \(p_k\).

 required
normalize bool

If True, rescale \(p_k\) to satisfy the semivalue normalization.

 False

Returns:

Type Description
list[float]

Allocation vector of length n_players.

Raises:

Type Description
InvalidParameterError

If weights_by_k has the wrong length, or normalization is requested with all-zero weights.
Notes
  • The Shapley value is a special case of a semivalue with \(p_k = \frac{k!(n-k-1)!}{n!}\).
  • Complexity is \(O(n 2^n)\) due to coalition enumeration.

Examples:

>>> # Example: choose p_k proportional to 1/(n * C(n-1,k)) and normalize
>>> phi = semivalue(g, weights_by_k=[1.0]*g.n_players, normalize=True)
>>> len(phi) == g.n_players
True

shapley_value 

shapley_value(game)

Compute the Shapley value for a TU cooperative game.

The Shapley value assigns to each player their expected marginal contribution under a uniformly random permutation of players.

Formally:

\[ \phi_i = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|! (n-|S|-1)!}{n!} \bigl( v(S \cup \{i\}) - v(S) \bigr). \]

Parameters:

Name Type Description Default
game Game

TU cooperative game.

 required

Returns:

Type Description
list[float]

Shapley value allocation (length n_players).
Notes
  • Complexity is \(O(n 2^n)\).
  • Exact and deterministic; suitable for small to medium n.

Examples:

>>> g = Game.from_value_function(n_players=3, value_fn=lambda S: float(len(S)))
>>> shapley_value(g)
[1.0, 1.0, 1.0]

shapley_value_fast 

shapley_value_fast(game, *, backend='auto')

Fast exact Shapley value via Harsanyi dividends (Möbius transform).

Using Harsanyi dividends d(S) (unanimity coordinates), the Shapley value admits the closed form:

\[ \phi_i(v) = \sum_{S \ni i} \frac{d(S)}{|S|}. \]

This implementation computes dividends via a fast Möbius transform and then aggregates contributions across coalitions.

Parameters:

Name Type Description Default
game Game

TU game.

 required
backend ('auto', 'numpy', 'python')

Backend for the Möbius transform: - "auto": try NumPy, fall back to Python - "numpy": force NumPy (raises ImportError if unavailable) - "python": pure-Python

 "auto"

Returns:

Type Description
list[float]

The Shapley value allocation (length n_players).
Notes
  • Complexity is \(O(n 2^n)\), like the classic formula, but with substantially better constants when the Möbius transform uses NumPy.
  • This is an exact method (not Monte Carlo).
  • Conceptually, it decomposes the game into unanimity games and distributes each dividend equally among players in the coalition.

Examples:

>>> phi = shapley_value_fast(g, backend="auto")
>>> len(phi) == g.n_players
True

shapley_value_sample 

shapley_value_sample(game, *, n_samples, seed=None)

Monte Carlo estimate of the Shapley value using random permutations.

For each sampled permutation, the marginal contribution vector is computed. The estimator returns the sample mean and an estimated per-player standard error.

Parameters:

Name Type Description Default
game Game

TU cooperative game.

 required
n_samples int

Number of random permutations to sample.

 required
seed int | None

Random seed for reproducibility.

 None

Returns:

Type Description
(phi_hat, stderr)

Estimated Shapley value and per-player standard error.
Notes
  • Complexity is \(O(n \cdot n_{samples})\).
  • Suitable for large n when exact computation is infeasible.

Examples:

>>> phi_hat, stderr = shapley_value_sample(g, n_samples=1000)

shapley_value_sample_stratified 

shapley_value_sample_stratified(
    game, *, samples_per_k, seed=None
)

Stratified Monte Carlo estimate of the Shapley value by coalition size.

This estimator samples random coalitions \(S\) of each size \(k = 0 \ldots n-1\) from \(N \setminus \{i\}\) and averages the marginal contributions:

\[\Delta_i(S) = v(S \cup \{i\}) - v(S)\]

weighted by the Shapley coefficient:

\[w_k = \frac{k!(n-k-1)!}{n!}.\]

Compared to permutation sampling, this can reduce variance in games where marginal contributions depend strongly on coalition size.

Parameters:

Name Type Description Default
game Game

TU game.

 required
samples_per_k int

Number of sampled coalitions per coalition size k, for each player. Must be >= 1.

 required
seed int | None

RNG seed.

 None

Returns:

Type Description
(phi_hat, stderr)

phi_hat is the estimated Shapley value and stderr is an estimated per-player standard error (based on sample variance across draws).
Notes
  • Total samples scale as O(n^2 * samples_per_k) because we sample for each player and each k.
  • This is still much cheaper than O(n 2^n) when n is moderate/large.
  • stderr here is an empirical standard error from the stratified samples.

Examples:

>>> phi_hat, se = shapley_value_sample_stratified(g, samples_per_k=200, seed=0)
>>> len(phi_hat) == g.n_players
True

weighted_shapley_value 

weighted_shapley_value(game, *, weights)

Compute the weighted Shapley value (Shapley value with weighted symmetry).

Using Harsanyi dividends \(d(S)\), the weighted Shapley value is:

\[ \phi_i = \sum_{S \ni i} d(S) \frac{w_i}{\sum_{j \in S} w_j}. \]

Parameters:

Name Type Description Default
game GameProtocol

TU game.

 required
weights Sequence[float]

Positive player weights (length n_players).

 required

Returns:

Type Description
list[float]

Allocation vector of length n_players.

Raises:

Type Description
InvalidParameterError

If the weights are non-positive or have the wrong length.
Notes
  • This uses Harsanyi dividends internally, so the overall cost is dominated by computing the Möbius transform (typically \(O(n2^n)\)).
  • Setting all weights equal reduces to the standard Shapley value.

Examples:

>>> phi_w = weighted_shapley_value(g, weights=[2.0, 1.0, 1.0])
>>> len(phi_w) == g.n_players
True