Bondareva–Shapley theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

The Bondareva–Shapley theorem, in game theory, describes a necessary and sufficient condition for the non-emptiness of the core of a cooperative game. 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[edit]

Let the pair \; \langle N, v\rangle \; be a cooperative game, where \; \; N \; is the set of players and where the value function \; v: 2^N \to \mathbb{R} \; is defined on N's power set (the set of all subsets of N).
The core of \; \langle N, v \rangle \; is non-empty if and only if for every function \alpha : 2^N \setminus \{\emptyset\} \to [0,1] where
\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\{\emptyset\}} \alpha (S) v (S) \leq v (N).

References[edit]