Bondareva-Shapley theorem

From Wikipedia, the free encyclopedia

The Bondareva-Shapley theorem 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 1960's.

[edit] Theorem

Let the pair \; \langle N, v\rangle \; be a cooperative game (\; \; N \; is the set of players, and \; v: 2^N \to \mathbb{R} \; is the value function).
The core of \; \langle N, v \rangle \; is non-empty if and only if for every function \alpha : 2^N \to \mathbb{R}_+ where
\forall i \in N : \sum_{S \subseteq N : \; i \in S} \alpha (S) = 1
the following condition holds: \sum_{S \subseteq N} \alpha (S) v (S) \leq v (N)

[edit] References

  • Bondareva, Olga N. (1963). "Some applications of linear programming methods to the theory of cooperative games (In Russian)". Problemy Kybernetiki 10: 119–139. 
  • Kannai, Y (1992), “The core and balancedness”, in Aumann, Robert J. & Hart, Sergiu, 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: 453–460.