Bondareva–Shapley theorem
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 <math>( N, v)</math> be a cooperative game in characteristic function form, where <math> N</math> is the set of players and where the value function <math> v: 2^N \to \mathbb{R} </math> is defined on <math>N</math>'s power set (the set of all subsets of <math>N</math>).
The core of <math>( N, v ) </math> is non-empty if and only if for every function <math>\alpha : 2^N \setminus \{\emptyset\} \to [0,1]</math> where <math>\forall i \in N : \sum_{S \in 2^N : \; i \in S} \alpha (S) = 1</math> the following condition holds: :<math>\sum_{S \in 2^N\setminus\{\emptyset\}} \alpha (S) v (S) \leq v (N).</math>