Misplaced Pages

Bondareva–Shapley theorem

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

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

The core of ( N , v ) {\displaystyle (N,v)} is non-empty if and only if for every function α : 2 N ∖ { ∅ } → [ 0 , 1 ] {\displaystyle \alpha :2^{N}\setminus \{\emptyset \}\to } where

∀ i ∈ N : ∑ S ∈ 2 N : i ∈ S α ( S ) = 1 {\displaystyle \forall i\in N:\sum _{S\in 2^{N}:\;i\in S}\alpha (S)=1}
the following condition holds:

∑ S ∈ 2 N ∖ { ∅ } α ( S ) v ( S ) ≤ v ( N ) . {\displaystyle \sum _{S\in 2^{N}\setminus \{\emptyset \}}\alpha (S)v(S)\leq v(N).}

References

Categories: