Bondareva–Shapley theorem explained

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

\langle N, v\rangle be a cooperative game in characteristic function form, where N is the set of players and where the value function v: 2 ^{N} \to 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

• Bondareva . Olga N. . Olga Bondareva . Some applications of linear programming methods to the theory of cooperative games (In Russian) . Problemy Kybernetiki . 10 . 119–139 . 1963 .
  • Shapley . Lloyd S. . Lloyd S. Shapley . On balanced sets and cores . Naval Research Logistics Quarterly . 14 . 4 . 453–460 . 1967 . 10.1002/nav.3800140404 . 10338.dmlcz/135729 . free .