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 {displaystyle langle N,vrangle } be a cooperative game in characteristic function form, where {displaystyle N} is the set of players and where the value function {displaystyle v:2^{N}to mathbb {R} } is defined on {displaystyle N} 's power set (the set of all subsets of {displaystyle N} ).

The core of {displaystyle langle N,vrangle } is non-empty if and only if for every function {displaystyle alpha :2^{N}setminus {emptyset }to [0,1]} where {displaystyle forall iin N:sum _{Sin 2^{N}:;iin S}alpha (S)=1} the following condition holds: {displaystyle sum _{Sin 2^{N}setminus {emptyset }}alpha (S)v(S)leq v(N).} References Bondareva, Olga N. (1963). "Some applications of linear programming methods to the theory of cooperative games (In Russian)" (PDF). Problemy Kybernetiki. 10: 119–139. Kannai, Y (1992), "The core and balancedness", in Aumann, Robert J.; Hart, Sergiu (eds.), 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. hdl:10338.dmlcz/135729. Categories: Game theoryEconomics theoremsCooperative gamesLloyd Shapley