Core, Shapley Value, and Cooperative Concepts

When Negotiation Matters More Than Strategy

In cooperative game theory, the question is different: not "how do players interact strategically," but "how do they share the jointly created payoff." It is assumed that players can make binding agreements—the main question is which distribution is "fair" and "stable."

Examples: profit allocation in a joint venture; sharing costs for construction of joint infrastructure; allocation of power in a political coalition.

Characteristic Function

TU-game (with transferable utility) is defined by the pair (N, v): N = {1, ..., n}—the players; v: 2^N → ℝ—the characteristic function (v(S)—the maximum joint payoff of coalition S). Usually v(∅) = 0.

Superadditivity: v(S∪T) ≥ v(S) + v(T) when S∩T = ∅. This is the condition "it is beneficial to unite"—standard for most economic applications.

Numerical example: N = {1, 2, 3}, v({1}) = 1, v({2}) = 2, v({3}) = 0, v({1,2}) = 4, v({1,3}) = 3, v({2,3}) = 3, v(N) = 6.

Core: Stable Allocation

Allocation (imputation) x = (x₁, x₂, x₃) satisfies: x₁+x₂+x₃ = 6 (efficiency); xᵢ ≥ v({i}) (individual rationality). Therefore: x₁≥1, x₂≥2, x₃≥0, Σxᵢ=6.

Core—the set of allocations that cannot be "blocked" by any coalition: x ∈ Core(v) if and only if for all S ⊆ N: Σᵢ∈S xᵢ ≥ v(S).

For our example, the core conditions: x₁+x₂ ≥ 4, x₁+x₃ ≥ 3, x₂+x₃ ≥ 3, and Σxᵢ = 6.

From x₁+x₂ ≥ 4 and x₁+x₂+x₃ = 6: x₃ ≤ 2. From x₂+x₃ ≥ 3 and x₃ ≤ 2: x₂ ≥ 1. Therefore x₂ ∈ [1, 3], x₃ ∈ [0, 2], x₁ = 6 − x₂ − x₃. The core is nonempty! For example: (2, 3, 1) ∈ Core.

Shapley Value: Fair Allocation

Shapley (1953) found the unique allocation satisfying four "reasonable" axioms.

Axioms: Efficiency: Σᵢ φᵢ(v) = v(N). Symmetry: interchangeable players receive equal amounts. Dummy player: a "zero" player (contributes nothing) receives 0. Additivity: φ(v+w) = φ(v) + φ(w).

Formula: φᵢ(v) = Σ_{S⊆N{i}} [|S|!(n−|S|−1)!/n!] · [v(S∪{i}) − v(S)]

Interpretation: imagine the players enter the grand coalition in random order. The marginal contribution of player i is v(S∪{i}) − v(S), where S is the random coalition already formed by his arrival. The Shapley value = expected marginal contribution under uniform random ordering.

Computation for the example (6 permutations of three players):

Orderings and marginal contributions i=1: (1,2,3): v({1})−0=1; (1,3,2): 1; (2,1,3): v({1,2})−v({2})=2; (2,3,1): v(N)−v({2,3})=3; (3,1,2): v({1,3})−v({3})=3; (3,2,1): v(N)−v({2,3})=3. φ₁ = (1+1+2+3+3+3)/6 = 13/6 ≈ 2.17.

Similarly: φ₂ ≈ 2.5, φ₃ ≈ 1.33. Check: 2.17+2.5+1.33 = 6 ✓.

Nucleolus: Minimization of Dissatisfaction

The nucleolus lexically minimizes the maximum excess e(S,x) = v(S) − Σᵢ∈S xᵢ. Excess = how much the coalition S is "aggrieved" by allocation x.

The nucleolus is unique. If the core is nonempty, the nucleolus lies inside it.

Applications

Cost allocation in infrastructure: Three cities (A, B, C) build an airport. The cost for each: v({A}) = 100, v({B}) = 150, v({C}) = 200, v({A,B}) = 180, v({A,C}) = 250, v({B,C}) = 290, v(N) = 350. The Shapley value gives each city a "fair" share of the costs based on its marginal contribution.

Share allocation in mergers: If companies A and B merge and create synergy (v(AB) > v(A)+v(B)), the Shapley value determines the "fair" exchange rate of shares.

Power index in politics: In parliament, coalitions need a minimum number of votes. The Shapley value (Shapley–Shubik index) shows how often the party is "pivotal"—changing the outcome of the vote. This is its real power.

Alternative power indices: The Banzhaf index—an alternative to Shapley–Shubik—is based on the number of "critical" participations: player i is critical for coalition S if S is winning but S {i} is not. The Banzhaf index does not assume equally likely order of joining and gives a different distribution of power. In the European Council, both indices are used to analyze the impact of member states under qualified majority.

Shapley Value in Corporate Governance and Political Economy

The Shapley value has found wide application beyond abstract theory. In corporate governance, it is used to evaluate the influence of shareholders in voting: if one shareholder owns 40% of the votes with a simple majority required, his Shapley–Shubik index significantly exceeds his vote share, since he is needed in any winning coalition. In political science, the Shapley value analyzes the strength of individual states in international organizations and votes in parliamentary coalitions. In infrastructure economics, it is used to allocate costs for the construction of a joint facility (an airport, reservoir) among several municipalities—it is a fair distribution based on each one’s marginal contribution. Nobel laureates Robert Aumann and Lloyd Shapley developed key results of cooperative game theory, including the axiomatization of the Shapley value (the axioms of efficiency, symmetry, dummy player, and additivity), giving it the status of a unique fair allocation. Modern explainable AI algorithms (SHAP—SHapley Additive exPlanations) directly use the Shapley value to explain the contribution of each feature to a machine learning model’s prediction.

In practice, the Shapley value is numerically calculated for large games via the Monte Carlo method: random permutations of players approximate the average marginal contribution with accuracy O(1/√N) for N samples. This is how SHAP computes feature importance in random forests and neural networks with thousands of parameters—the full enumeration of all 2ⁿ coalitions is impossible, but random sampling of permutations gives a good approximation in reasonable time.

Exercise: N = {1,2,3}: v({1}) = 1, v({2}) = 2, v({3}) = 0, v({1,2}) = 4, v({1,3}) = 3, v({2,3}) = 3, v(N) = 6. Find the Shapley value for each player. Is it inside the core?