Bondareva–Shapley theorem

The Bondareva–Shapley theorem, in game theory, describes a necessary and sufficient condition for the non-emptiness of the core of a cooperative game in characteristic function form. Specifically, the game's core is non-empty if and only if the game is balanced. The Bondareva–Shapley theorem implies that market games and convex games have non-empty cores. The theorem was formulated independently by Olga Bondareva and Lloyd Shapley in the 1960s.

Theorem

Let the pair $⟨N,v⟩$ be a cooperative game in characteristic function form, where $N$ is the set of players and where the value function $v:2^N\to \mathbb{ℝ}$ is defined on $N$'s power set (the set of all subsets of $N$).

The core of $⟨N,v⟩$ is non-empty if and only if for every function $\alpha :2^N\setminus \{\mathrm{\varnothing }\}\to [0,1]$ where

$\mathrm{\forall }i\in N:\sum _{S\in 2^N:i\in S}\alpha (S)=1$
the following condition holds:

$\sum _{S\in 2^N\setminus \{\mathrm{\varnothing }\}}\alpha (S)v(S)\le v(N).$

References

• Bondareva, Olga N. (1963). "Some applications of linear programming methods to the theory of cooperative games (In Russian)". Problemy Kybernetiki 10: 119–139. http://www.princeton.edu/~erp/ERParchives/archivepdfs/WP0.pdf#page=82. 
• Kannai, Y (1992), "The core and balancedness", Handbook of Game Theory with Economic Applications, Volume I., Amsterdam: Elsevier, pp. 355–395, ISBN 978-0-444-88098-7 
• Shapley, Lloyd S. (1967). "On balanced sets and cores". Naval Research Logistics Quarterly 14 (4): 453–460. doi:10.1002/nav.3800140404.