The Shapley value — fair division of cooperative surplus

Derive the Shapley value axiomatically, implement it for arbitrary coalitional games in R, and visualize marginal contributions and fairness properties with interactive examples.

Keywords

Shapley value, cooperative game theory, fair division, marginal contribution, coalitional game, axiomatic

Introduction & motivation

When a group of players cooperate and generate surplus, how should that surplus be divided? Lloyd Shapley proved in 1953 that there is exactly one division rule satisfying four fairness axioms: the Shapley value. Each player’s share equals their average marginal contribution across all possible orderings in which the coalition could form. The Shapley value is the most widely used solution concept in cooperative game theory, with applications ranging from cost allocation in shared infrastructure to profit division in joint ventures, from computing feature importance in machine learning (SHAP values) to allocating airport runway costs among airlines of different sizes. Its appeal is that it provides a unique, axiomatically justified answer to the question “who deserves what?” — a question that arises whenever multiple agents collaborate and must divide the proceeds. This tutorial implements the Shapley value for arbitrary coalitional games in R, demonstrates it on classic examples (glove game, airport game, voting power), and visualizes the marginal contribution structure that determines each player’s fair share.

Mathematical formulation

A coalitional game \((N, v)\) consists of a finite player set \(N = \{1, \ldots, n\}\) and a characteristic function \(v: 2^N \to \mathbb{R}\) with \(v(\emptyset) = 0\), where \(v(S)\) is the worth of coalition \(S\).

The Shapley value of player \(i\) is:

\[ \phi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|! \, (n - |S| - 1)!}{n!} \left[ v(S \cup \{i\}) - v(S) \right] \]

The term \(v(S \cup \{i\}) - v(S)\) is \(i\)’s marginal contribution to coalition \(S\). The coefficient is the probability that \(S\) is exactly the set of players who arrived before \(i\) in a uniformly random ordering.

Shapley’s axioms: The unique function \(\phi\) satisfying:

1. Efficiency: \(\sum_i \phi_i = v(N)\)
2. Symmetry: If \(i\) and \(j\) contribute identically, \(\phi_i = \phi_j\)
3. Null player: If \(i\)’s marginal contribution is always 0, then \(\phi_i = 0\)
4. Additivity: \(\phi(v + w) = \phi(v) + \phi(w)\)

R implementation

# Compute Shapley value for a coalitional game
# v_func: function mapping a set of player indices to coalition value
shapley_value <- function(n, v_func) {
  players <- 1:n
  phi <- numeric(n)

  # Generate all permutations (feasible for n ≤ 8)
  if (n <= 8) {
    # Use all orderings approach
    perms <- combinat::permn(players)
    for (perm in perms) {
      for (pos in 1:n) {
        i <- perm[pos]
        predecessors <- if (pos > 1) perm[1:(pos-1)] else integer(0)
        mc <- v_func(c(predecessors, i)) - v_func(predecessors)
        phi[i] <- phi[i] + mc
      }
    }
    phi <- phi / factorial(n)
  } else {
    # Monte Carlo approximation for large games
    n_samples <- 10000
    for (s in 1:n_samples) {
      perm <- sample(players)
      for (pos in 1:n) {
        i <- perm[pos]
        predecessors <- if (pos > 1) perm[1:(pos-1)] else integer(0)
        mc <- v_func(c(predecessors, i)) - v_func(predecessors)
        phi[i] <- phi[i] + mc
      }
    }
    phi <- phi / n_samples
  }

  phi
}

# --- Example 1: Glove game (L, L, R) ---
# 3 players: two have left gloves, one has right glove
# v(S) = min(left gloves in S, right gloves in S)
cat("=== Glove Game: Players 1,2 have left gloves, Player 3 has right glove ===\n")

=== Glove Game: Players 1,2 have left gloves, Player 3 has right glove ===

v_glove <- function(S) {
  if (length(S) == 0) return(0)
  left <- sum(S %in% c(1, 2))
  right <- sum(S %in% c(3))
  min(left, right)
}

phi_glove <- shapley_value(3, v_glove)

Error in `loadNamespace()`:
! there is no package called 'combinat'

cat(sprintf("Shapley values: P1=%.3f, P2=%.3f, P3=%.3f (sum=%.3f)\n",
            phi_glove[1], phi_glove[2], phi_glove[3], sum(phi_glove)))

Error:
! object 'phi_glove' not found

cat("(The scarce right-glove owner gets the largest share)\n\n")

(The scarce right-glove owner gets the largest share)

# --- Example 2: Airport game ---
cat("=== Airport Game: 3 airlines need runways of length 1, 2, 3 ===\n")

=== Airport Game: 3 airlines need runways of length 1, 2, 3 ===

# Cost = max runway length needed by coalition members
v_airport <- function(S) {
  if (length(S) == 0) return(0)
  max(S)  # player i needs runway of length i
}

phi_airport <- shapley_value(3, v_airport)

Error in `loadNamespace()`:
! there is no package called 'combinat'

cat(sprintf("Cost allocation: Small=%.3f, Medium=%.3f, Large=%.3f (total=%.3f)\n",
            phi_airport[1], phi_airport[2], phi_airport[3], sum(phi_airport)))

Error:
! object 'phi_airport' not found

cat("(Larger planes pay more but benefit from cost sharing)\n\n")

(Larger planes pay more but benefit from cost sharing)

# --- Example 3: Majority voting (weighted) ---
cat("=== Weighted Voting: weights = (4, 3, 2, 1), quota = 6 ===\n")

=== Weighted Voting: weights = (4, 3, 2, 1), quota = 6 ===

weights <- c(4, 3, 2, 1)
quota <- 6
v_vote <- function(S) {
  if (length(S) == 0) return(0)
  ifelse(sum(weights[S]) >= quota, 1, 0)
}

phi_vote <- shapley_value(4, v_vote)

Error in `loadNamespace()`:
! there is no package called 'combinat'

cat(sprintf("Shapley-Shubik power index: %.3f, %.3f, %.3f, %.3f\n",
            phi_vote[1], phi_vote[2], phi_vote[3], phi_vote[4]))

Error:
! object 'phi_vote' not found

cat("(Power is not proportional to weight — Player 4 may have zero power!)\n")

(Power is not proportional to weight — Player 4 may have zero power!)

Static publication-ready figure

shapley_df <- bind_rows(
  tibble(game = "Glove game", player = paste0("P", 1:3),
         value = phi_glove, type = c("Left", "Left", "Right")),
  tibble(game = "Airport costs", player = c("Small", "Medium", "Large"),
         value = phi_airport, type = c("Small", "Medium", "Large")),
  tibble(game = "Voting power", player = paste0("P", 1:4),
         value = phi_vote, type = paste0("w=", weights))
)

Error:
! object 'phi_glove' not found

shapley_df$game <- factor(shapley_df$game,
                           levels = c("Glove game", "Airport costs", "Voting power"))

Error:
! object 'shapley_df' not found

p_shapley <- ggplot(shapley_df, aes(x = player, y = value, fill = player)) +
  geom_col(show.legend = FALSE, width = 0.7) +
  geom_text(aes(label = round(value, 3)), vjust = -0.3, size = 3) +
  facet_wrap(~game, scales = "free") +
  scale_fill_manual(values = rep(okabe_ito[1:4], 2)) +
  labs(
    title = "Shapley values across three cooperative games",
    subtitle = "Fair allocation of surplus based on average marginal contributions",
    x = NULL, y = "Shapley value"
  ) +
  theme_publication() +
  theme(strip.text = element_text(face = "bold"))

Error:
! object 'shapley_df' not found

p_shapley

Error:
! object 'p_shapley' not found

Interactive figure

# Visualize all marginal contributions for the glove game
perms <- combinat::permn(1:3)

Error in `loadNamespace()`:
! there is no package called 'combinat'

mc_data <- lapply(seq_along(perms), function(k) {
  perm <- perms[[k]]
  mcs <- numeric(3)
  for (pos in 1:3) {
    i <- perm[pos]
    pred <- if (pos > 1) perm[1:(pos-1)] else integer(0)
    mcs[i] <- v_glove(c(pred, i)) - v_glove(pred)
  }
  tibble(ordering = paste(perm, collapse = "→"),
         player = paste0("P", 1:3),
         mc = mcs)
}) |> bind_rows()

Error:
! object 'perms' not found

mc_data$text <- paste0("Ordering: ", mc_data$ordering,
                        "\nPlayer: ", mc_data$player,
                        "\nMarginal contribution: ", mc_data$mc)

Error:
! object 'mc_data' not found

p_mc <- ggplot(mc_data, aes(x = ordering, y = mc, fill = player, text = text)) +
  geom_col(position = "dodge", width = 0.7) +
  scale_fill_manual(values = okabe_ito[1:3], name = "Player") +
  labs(
    title = "Marginal contributions across all orderings — Glove game",
    subtitle = "Shapley value = average MC across orderings; P3 (right glove) contributes in 4/6 orderings",
    x = "Arrival ordering", y = "Marginal contribution"
  ) +
  theme_publication() +
  theme(axis.text.x = element_text(angle = 45, hjust = 1, size = 9))

Error:
! object 'mc_data' not found

ggplotly(p_mc, tooltip = "text") |>
  config(displaylogo = FALSE,
         modeBarButtonsToRemove = c("select2d", "lasso2d"))

Error:
! object 'p_mc' not found

Interpretation

The Shapley value captures a deep notion of fairness: each player receives their expected marginal contribution to a randomly forming coalition. In the glove game, this means the scarce resource owner (the right-glove holder) receives 2/3 of the surplus — not because of any market power or negotiation skill, but because scarcity makes their contribution valuable in more coalition orderings. The airport game shows how cost sharing works: the large airline needs the longest runway (cost 3) but only pays about 1.83 because the smaller airlines also benefit from parts of that runway. The voting power example reveals the most counterintuitive result: in a weighted voting game, a player’s power (as measured by the Shapley-Shubik index) can be very different from their voting weight. Player 4 with weight 1 has almost no pivotal power because they can almost never change the outcome — the coalition either already has enough votes or doesn’t, and Player 4’s single vote rarely tips the balance. This disconnect between nominal weight and actual power is critical in political science (analysing the EU Council of Ministers, the UN Security Council, shareholder voting) and has been used to argue for voting weight reforms. The Shapley value’s modern renaissance comes from machine learning, where SHAP (SHapley Additive exPlanations) values use the same formula to fairly attribute a model’s prediction to individual features — showing that a 70-year-old cooperative game theory concept is now central to explainable AI.

Extensions & related tutorials

• Nash bargaining solution — the bilateral counterpart to Shapley’s multilateral solution.
• The core and stability in coalitional games — when is the Shapley value in the core?
• Voting power indices — Shapley-Shubik vs Banzhaf power.
• SHAP values for ML interpretability — the modern ML application.
• Airport and cost allocation games — deeper cost sharing analysis.

References