Bondareva–Shapley theorem

Overview

The Bondareva–Shapley theorem is a central result in cooperative game theory that characterizes when the core of a transferable-utility (TU) game is nonempty. The core is the set of payoff allocations to players that are feasible (sum to the grand coalition’s value) and stable against deviations by any coalition (no subset of players can guarantee themselves more by breaking away). The theorem says: a TU game has a nonempty core if and only if it is balanced, meaning every “fractional” way to cover players with coalitions cannot create more value than the grand coalition. This matters for executives evaluating joint ventures, cost-sharing, or alliance structures: it provides a precise test for whether a stable profit-sharing or cost allocation exists given coalition values.

Origins and Credit

Olga N. Bondareva (1963) first proved the result in Russian; Lloyd S. Shapley (1967) provided an independent proof and popularized it in English. The theorem connects stability to linear programming duality and complements Shapley’s other contributions, such as the Shapley value for fair division.

Core Idea and Mechanics

Consider a set of players N. For each coalition S ⊆ N, v(S) is the value (profit or cost saving) they can generate together, and utility is transferable (players can make side payments). An allocation x = (x_i) is in the core if:

• Efficiency: ∑_i∈N x_i = v(N).
• Coalitional rationality: for all S ⊆ N, ∑_i∈S x_i ≥ v(S).

Define a balanced collection as nonnegative weights λ(S) for coalitions S such that each player is covered exactly once in total: for every i ∈ N, ∑_S∋i λ(S) = 1. Intuitively, the weights describe a “time-sharing” or fractional partition of players among coalitions.

Bondareva–Shapley theorem. The core of a TU game is nonempty if and only if for every balanced collection λ(·), the balancedness inequality holds:

∑_S⊆N λ(S) v(S) ≤ v(N).

Economic intuition: no matter how one fractionally assigns players to coalitions, the weighted sum of what those coalitions can achieve should never exceed what the grand coalition can achieve. If some balanced collection yields a weighted sum larger than v(N), then some combination of coalitions can collectively “demand” more than any feasible allocation can give them, so the core must be empty.

The proof exploits linear programming. The core constraints are a feasibility system; if infeasible, Farkas’ lemma/duality yields a certificate in the form of a violating balanced collection. Conversely, if all balancedness inequalities hold, one can construct an allocation satisfying all core constraints.

Key Assumptions and Conditions

• Transferable utility: payoffs can be freely redistributed via side payments.
• Characteristic function form: v(S) is well defined for every coalition S and does not depend on what outsiders do (no externalities across coalitions).
• Complete information about v(S) for all coalitions (or at least enough structure to verify balancedness).
• No restrictions on v beyond those above; superadditivity (v(S∪T) ≥ v(S)+v(T)) often holds in applications but is not required by the theorem itself.

Implications

• Stability test: The theorem gives necessary and sufficient conditions for the existence of stable profit-sharing or cost allocations. If the game is unbalanced, any proposed split can be blocked by some coalition.
• Design guidance: To achieve a stable grand coalition, structure technology, contracts, or exclusivity so that no balanced collection of sub-coalitions can create more value per “unit of player coverage” than the whole coalition.
• Links to sufficient conditions: Classes of games—such as convex (supermodular) games—are automatically balanced, guaranteeing a nonempty core. This covers many cost-subadditive sharing and increasing-returns collaboration settings.
• Algorithmic lens: Checking balancedness translates to linear programs. Practically, firms use sufficient conditions (convexity, superadditivity) or scenario-specific structure rather than enumerate all coalitions.
• Policy relevance: In regulated cost allocation (e.g., networks, joint infrastructure), the theorem underpins whether stable, coalition-proof tariffs exist without subsidies.

Example in Practice

Three-firm alliance with strong pair synergies. Firms A, B, and C consider a platform alliance. Coalition values (in $M of incremental profit): v({i}) = 0 for singletons; any pair can make 6; all three together make 8 (coordination costs or congestion dilute value).

Is there a stable split x with x_A + x_B + x_C = 8 and each pair getting at least 6? Summing the three pair constraints yields 2(x_A + x_B + x_C) ≥ 18 ⇒ 16 ≥ 18, a contradiction. So the core is empty: no allocation avoids being blocked by some pair.

Bondareva–Shapley explains why. Consider the balanced collection with weights λ({AB}) = λ({BC}) = λ({AC}) = 1/2 (each player appears in exactly two pairs, so coverage sums to 1). The weighted sum is 0.5·6 + 0.5·6 + 0.5·6 = 9, which exceeds v({ABC}) = 8, violating balancedness. Business implication: without additional instruments—exclusivity, side contracts, or extra value creation—the three-way alliance is inherently unstable; bilateral deals will unravel the grand coalition.

Limitations and Common Misunderstandings

• Existence, not construction: The theorem says when the core is nonempty; it does not identify a specific allocation. Selection may use other concepts (e.g., the Shapley value), which need not lie in the core.
• Transferability and no externalities: Real alliances may have nontransferable utilities (private benefits, risk exposures) or externalities across coalitions; the result does not apply directly in those cases.
• Verification burden: Testing balancedness can be computationally demanding because it involves many coalitions; practitioners rely on structure (convexity/supermodularity) or linear-programming formulations.
• Empty core ≠ impossibility of cooperation: An empty core means no allocation is immune to blocking, not that cooperation cannot occur. Long-term contracts, penalties for exit, repeated interaction, or platform governance can sustain outcomes outside the core.
• Stability vs. fairness: The core concerns coalition stability, not fairness. Fair division rules (like the Shapley value) may conflict with stability in some games.

Related Concepts

Core (cooperative games); Balanced collections; Convex (supermodular) games; Shapley value; Least core and ε-core; Linear programming duality; Characteristic function form.