Cooperative Game Theory

Coalitional Games

Transferable Utility (TU) Games

A cooperative game with transferable utility is defined by (N, v) where:

• N = {1, ..., n}: set of players
• v: 2^N -> R: characteristic function mapping each coalition S to its value v(S), with v(empty) = 0

The characteristic function captures what each coalition can achieve independently. TU assumes utility is freely transferable among coalition members (e.g., money).

Key Properties of v

• Monotonicity: S subset of T implies v(S) <= v(T)
• Superadditivity: v(S union T) >= v(S) + v(T) for disjoint S, T (cooperation never hurts)
• Convexity (supermodularity): v(S union T) + v(S intersect T) >= v(S) + v(T) for all S, T. Stronger than superadditivity; implies marginal contributions increase with coalition size.
• Subadditivity: v(S union T) <= v(S) + v(T) (cost games, where cooperation reduces cost)

Imputations

An imputation is a payoff vector x in R^n satisfying:

• Efficiency: sum_i x_i = v(N) (the grand coalition's value is fully distributed)
• Individual rationality: x_i >= v({i}) for all i (no player receives less than they can get alone)

The set of imputations is the feasible set for solution concepts.

The Core

Definition

The core is the set of imputations that no coalition can block:

Core(v) = {x in R^n : sum_i x_i = v(N) and sum_{i in S} x_i >= v(S) for all S subset N}

An allocation in the core gives every coalition at least its standalone value, so no group has incentive to break away from the grand coalition.

Properties

• The core is a convex polytope (intersection of halfspaces)
• The core may be empty (e.g., simple majority games with n >= 3)
• Bondareva-Shapley theorem: The core is non-empty if and only if the game is balanced. A game is balanced if for every balanced collection of coalitions (with weights summing to 1 for each player), the weighted sum of coalition values does not exceed v(N). Checking balancedness is equivalent to solving a linear program.
• Convex games: If v is convex, the core is non-empty and equals the convex hull of all marginal contribution vectors (one per permutation). The Shapley value is the centroid of the core.

Computational Aspects

• Core membership: Given x, checking whether x is in the core requires verifying 2^n - 1 constraints. For specific game classes (flow games, matching games), this can be done in polynomial time.
• Core non-emptiness: Equivalent to LP feasibility; polynomial in the number of constraints, but the number of constraints is exponential. For structured games, compact LP formulations exist.

Shapley Value

Definition

The Shapley value assigns to each player their expected marginal contribution over all orderings of players:

phi_i(v) = sum_{S subset N \ {i}} (|S|! (n - |S| - 1)! / n!) * (v(S union {i}) - v(S))

Equivalently, the average over all permutations pi of N of player i's marginal contribution when they join the coalition of players preceding them in pi.

Axioms

The Shapley value is the unique function satisfying:

1. Efficiency: sum_i phi_i(v) = v(N)
2. Symmetry: If players i and j are interchangeable (v(S union {i}) = v(S union {j}) for all S not containing i or j), then phi_i = phi_j
3. Null player: If v(S union {i}) = v(S) for all S, then phi_i = 0
4. Additivity (linearity): phi_i(v + w) = phi_i(v) + phi_i(w)

Alternative axiomatization (Young): Efficiency, symmetry, and strong monotonicity (if player i's marginal contributions weakly increase in game w compared to v, then phi_i(w) >= phi_i(v)) uniquely characterize the Shapley value.

Computation

Exact computation requires summing over 2^n coalitions or n! permutations: exponential in general.

Efficient computation for specific games:

• Weighted voting games: Pseudo-polynomial dynamic programming in O(n * sum_w) where sum_w is the sum of weights
• Graph games: Polynomial for tree-structured games
• Marginal contribution nets: Compact representation allowing polynomial Shapley computation

Approximation: Monte Carlo sampling of random permutations. Sample m permutations uniformly; average marginal contributions. By Hoeffding's bound, O(1/epsilon^2 * log(n/delta)) samples suffice for epsilon-additive approximation with probability 1-delta.

Machine learning applications: SHAP (SHapley Additive exPlanations) uses the Shapley value to attribute model predictions to features. Kernel SHAP, Tree SHAP provide efficient computation for specific model classes.

Properties

• In the core for convex games: The Shapley value lies in the core when the game is convex
• Marginal contributions: Can be negative (a player may hurt coalitions)
• Computational hardness: Computing the exact Shapley value is #P-hard for weighted voting games (Deng-Papadimitriou)

Banzhaf Index (Power Index)

Definition

The Banzhaf index measures a player's power as the fraction of coalitions where they are pivotal (swing voter):

beta_i(v) = (1/2^{n-1}) * sum_{S subset N \ {i}} [v(S union {i}) - v(S)]

The normalized Banzhaf index divides by sum_j beta_j to sum to 1.

Comparison with Shapley

| Property | Shapley | Banzhaf | |---|---|---| | Efficiency | Yes (sums to v(N)) | No (must normalize) | | Symmetry | Yes | Yes | | Null player | Yes | Yes | | Additivity | Yes | No (satisfies transfer property) | | Probabilistic interpretation | Uniform over orderings | Uniform over coalitions |

The Banzhaf index is particularly natural for voting games where the question is "how often is player i decisive?" without concern for the order of coalition formation.

Nucleolus

Definition

The nucleolus minimizes the maximum dissatisfaction of any coalition. For an imputation x, the excess of coalition S is:

e(S, x) = v(S) - sum_{i in S} x_i

The excess measures how unhappy coalition S is with allocation x (positive excess means S receives less than its value).

The nucleolus is the unique imputation that lexicographically minimizes the sorted vector of excesses:

nu(v) = argmin_x (sort descending {e(S, x) : S subset N})

Properties

• Unique: The nucleolus is always a single point (unlike the core, which is a set)
• In the core: If the core is non-empty, the nucleolus lies in the core
• Computation: Solvable by a sequence of LPs (at most n LPs), but each LP has exponentially many constraints. For specific game classes, polynomial algorithms exist.
• Kernel: The nucleolus is in the kernel (a set of balanced imputations)

Interpretation

The nucleolus is the "egalitarian" solution: it makes the most unhappy coalition as happy as possible, then the second-most, and so on. It can be viewed as a fairness-maximizing solution with a Rawlsian flavor.

Cost Sharing

Cost Sharing Games

A cost game (N, c) has a cost function c: 2^N -> R (with c(empty) = 0) where c(S) is the cost of serving coalition S. The goal is to divide c(N) among agents.

Subadditivity (c(S union T) <= c(S) + c(T)) ensures the grand coalition is efficient. The core conditions become: sum_{i in S} x_i <= c(S) for all S (no coalition overpays relative to going alone).

Shapley Cost Sharing

Apply the Shapley value to the cost game: each player pays their expected marginal cost contribution. Satisfies efficiency, symmetry, additivity, and dummy axioms.

Moulin Mechanisms

Cross-monotonic cost sharing: A cost-sharing method where adding a player never increases other players' cost shares. Enables group-strategyproof mechanisms. Not always achievable for all cost games.

Budget balance vs. efficiency trade-off: Moulin's impossibility results show tension between group strategyproofness, budget balance, and economic efficiency in cost sharing.

Voting Games

Simple Games

A simple game assigns v(S) in {0, 1} (losing or winning coalition). A coalition S is winning if v(S) = 1. Properties: v(N) = 1, v(empty) = 0, monotonicity (supersets of winning coalitions are winning).

Weighted Voting Games

Represented as [q; w_1, ..., w_n]: coalition S wins iff sum_{i in S} w_i >= q (quota). Not all simple games are weighted voting games (the 6-player game with minimum winning coalitions {1,2,3}, {1,4,5}, {2,4,6}, {3,5,6} is not representable as weighted voting).

Power Indices for Voting

The Shapley-Shubik index (Shapley value of the simple game) and Banzhaf index measure voting power:

• Shapley-Shubik: Fraction of permutations where player i is pivotal (turns a losing coalition into winning)
• Banzhaf: Fraction of coalitions (not orderings) where player i is a swing voter

Example (UN Security Council): 5 permanent members (veto power), 10 non-permanent. Under Shapley-Shubik, each permanent member has ~19.6% power, each non-permanent ~0.19%. The formal voting weight (1 each) vastly understates the power asymmetry.

Computational Complexity

• Computing Shapley-Shubik and Banzhaf indices for weighted voting games is #P-hard
• Checking whether a simple game is weighted is coNP-complete
• Pseudo-polynomial algorithms exist for integer-weighted games

Additional Solution Concepts

Bargaining Solutions

Nash Bargaining Solution: Maximizes the product of players' gains over the disagreement point. Axiomatically characterized by invariance to affine transformations, symmetry, Pareto efficiency, and independence of irrelevant alternatives.

Kalai-Smorodinsky Solution: Requires that the ratio of players' gains is proportional to their maximum possible gains. Replaces IIA with individual monotonicity.

Stable Sets (von Neumann-Morgenstern)

A set of imputations V is stable if: (1) no element of V dominates another (internal stability), and (2) every imputation outside V is dominated by some element of V (external stability). May not exist; may not be unique.

Market Games

A coalitional game derived from an exchange economy. Shapley-Shubik showed that market games are exactly the totally balanced games (core is non-empty for every subgame). Competitive equilibrium payoffs lie in the core.

Applications

• Airport cost sharing: Dividing runway construction costs among airlines with different aircraft sizes (Littlechild-Thompson)
• Telecommunications: Cost sharing for network infrastructure
• Data valuation: Shapley value for valuing data points in machine learning (Data Shapley)
• Coalition formation: Which coalitions form endogenously? Core stability predicts the grand coalition; non-empty core ensures no group wants to deviate