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