Bondareva–Shapley Theorem
   HOME

TheInfoList



OR:

The Bondareva–Shapley theorem, in
game theory Game theory is the study of mathematical models of strategic interactions. It has applications in many fields of social science, and is used extensively in economics, logic, systems science and computer science. Initially, game theory addressed ...
, describes a
necessary and sufficient condition In logic and mathematics, necessity and sufficiency are terms used to describe a conditional or implicational relationship between two statements. For example, in the conditional statement: "If then ", is necessary for , because the truth of ...
for the non-emptiness of the
core Core or cores may refer to: Science and technology * Core (anatomy), everything except the appendages * Core (laboratory), a highly specialized shared research resource * Core (manufacturing), used in casting and molding * Core (optical fiber ...
of a cooperative game in characteristic function form. Specifically, the game's core is non-empty
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...
the game is ''balanced''. The Bondareva–Shapley theorem implies that
market game In economic theory, a strategic market game, also known as a market game, is a game explaining price formation through game theory, typically implementing a general equilibrium outcome as a Nash equilibrium. Fundamentally in a strategic market game ...
s and
convex Convex or convexity may refer to: Science and technology * Convex lens, in optics Mathematics * Convex set, containing the whole line segment that joins points ** Convex polygon, a polygon which encloses a convex set of points ** Convex polytop ...
games have non-empty cores. The theorem was formulated independently by
Olga Bondareva Olga Nikolaevna Bondareva (April 27, 1937 – December 9, 1991) was a distinguished USSR, Soviet mathematician and economist. She contributed to the fields of mathematical economics, especially game theory. Bondareva is best known as one of t ...
and
Lloyd Shapley Lloyd Stowell Shapley (; June 2, 1923 – March 12, 2016) was an American mathematician and Nobel Memorial Prize-winning economist. He contributed to the fields of mathematical economics and especially game theory. Shapley is generally conside ...
in the 1960s.


Theorem

Let the
pair Pair or PAIR or Pairing may refer to: Government and politics * Pair (parliamentary convention), matching of members unable to attend, so as not to change the voting margin * ''Pair'', a member of the Prussian House of Lords * ''Pair'', the Fren ...
( N, v) be a cooperative game in characteristic function form, where N is the set of players and where the ''value function'' v: 2^N \to \mathbb is defined on N's
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...
(the set of all subsets of N).
The core of ( N, v ) is non-empty if and only if for every function \alpha : 2^N \setminus \ \to ,1/math> where

\forall i \in N : \sum_ \alpha (S) = 1
the following condition holds: :\sum_ \alpha (S) v (S) \leq v (N).


References

* * * {{DEFAULTSORT:Bondareva-Shapley theorem Game theory equilibrium concepts Economics theorems Cooperative games Lloyd Shapley