View source for Core (game theory)

{{Short description|Set in game theory}}
{{Technical|date=February 2024}}
In [[cooperative game theory]], the '''core'''  is the [[Set (mathematics)|set]] of [[Feasible region|feasible]] allocations or [[Imputation (game theory)|imputations]] where no coalition of agents can benefit by breaking away from the grand coalition.

An allocation is said{{by whom|date=June 2025}} to be in the ''core'' of a game if there is no coalition that can improve upon it. The core is then the set of all feasible allocations.

==Origin==
The idea of the core already appeared in the writings of {{harvtxt|Edgeworth|1881}}, at the time referred to as the ''contract curve''.<ref name="Kannai 1992">{{Cite book
  | last =Kannai
  | first = Y.
  | editor-last =Aumann |editor-first=Robert J. |editor-link=Robert J. Aumann
  | editor2-last=Hart |editor2-first=Sergiu|editor2-link=Sergiu Hart
  | contribution=The core and balancedness
  | title =Handbook of Game Theory with Economic Applications |volume=I
  | publisher =Elsevier
  | date =1992
  | location =Amsterdam
  | pages =355–395
  | isbn = 978-0-444-88098-7
  }}</ref> Even though [[John von Neumann|von Neumann]] and [[Oskar Morgenstern|Morgenstern]] considered it an interesting concept, they only worked with [[zero-sum game]]s where the core is always [[Empty set|empty]]. The modern definition of the core is due to [[Donald B. Gillies|Gillies]].<ref>{{Cite book
  | last =Gillies
  | first =D. B.
  | editor-last =Tucker |editor-first=A. W.  |editor-link=Albert W. Tucker
  | editor2-last=Luce |editor2-first=R. D. |editor2-link=R. Duncan Luce
  | contribution=Solutions to general non-zero-sum games
  | title =Contributions to the Theory of Games IV |series=[[Annals of Mathematics]] Studies |volume=40
  | publisher =[[Princeton University Press]]
  | date =1959
  | location =Princeton
  | pages =47–85
  }}</ref>

==Definition==
Consider a [[transferable utility]] [[Cooperative game theory|cooperative game]] <math>(N,v)</math> where <math>N</math> denotes the set of players and <math>v</math> is the [[Game theory#Characteristic function form|characteristic function]]. An [[Imputation (game theory)|imputation]] <math>x\in\mathbb{R}^N</math> is ''dominated'' by another imputation <math>y</math> if there exists a coalition <math>C</math>, such that each player in <math>C</math> weakly-prefers <math>y</math> (<math>x_i\leq y_i</math> for all <math>i\in C</math>) and there exists <math>i\in C</math> that strictly-prefers <math>y</math> (<math>x_i<y_i</math>), and <math>C</math> can enforce <math>y</math> by threatening to leave the [[Glossary of game theory#Glossary|grand coalition]] to form <math>C</math> (<math>\sum_{i\in C}y_i\leq v(C)</math>). The '''core''' is the set of imputations that are not dominated by any other imputation.<ref>As noted by {{cite journal |last1=Shapley |first1=L. S. |last2=Shubik |first2=M. |title=On Market Games |journal=[[Journal of Economic Theory]] |volume=1 |issue=1 |pages=9–25 |year=1969 |doi=10.1016/0022-0531(69)90008-8 |s2cid=153498438 }} due to the contribution of Mr. E. Kohlberg</ref>

=== Weak core ===
An imputation <math>x\in\mathbb{R}^N</math> is ''strongly-dominated'' by another imputation <math>y</math> if there exists a coalition <math>C</math>, such that each player in <math>C</math> strictly-prefers <math>y</math> (<math>x_i < y_i</math> for all <math>i\in C</math>). The '''weak core''' is the set of imputations that are not strongly-dominated.<ref>{{cite journal |last1=Yu |first1=Chaowen |title=A note on the weak core of simple games with ordinary preferences and uncountable alternatives |journal=SSRN Electronic Journal |date=8 December 2020 |doi=10.2139/ssrn.3225500|doi-access=free}}</ref>

==Properties==
* Another definition, [[Logical equivalence|equivalent]] to the one above, states that the core is a set of payoff allocations <math>x\in\mathbb{R}^N</math> satisfying
#Efficiency: <math>\sum_{i\in N}x_i=v(N)</math>,
#Coalitional rationality: <math>\sum_{i\in C}x_i\geq v(C)</math> for all subsets (coalitions) <math>C\subseteq N</math>.
* The core is always well-defined, but can be [[empty set|empty]].
* The core is a set which satisfies a system of weak [[linear]] inequalities. Hence the core is [[Closed set|closed]] and [[Convex set|convex]].
* The [[Bondareva–Shapley theorem]]: the core of a game is nonempty [[if and only if]] the game is "balanced".<ref>{{cite journal
  | last =Bondareva
  | first =Olga N.
  | author-link = Olga Bondareva
  | title =Some applications of linear programming methods to the theory of cooperative games (In Russian)
  | journal =Problemy Kybernetiki
  | volume =10
  | pages =119–139
  | date =1963
  }}</ref><ref>{{cite journal
  | last = Shapley
  | first = Lloyd S.
  | author-link =Lloyd S. Shapley
  | title =On balanced sets and cores
  | journal =Naval Research Logistics Quarterly
  | volume =14
  | issue =4
  | pages =453–460
  | date =1967
  | doi =10.1002/nav.3800140404
  | hdl = 10338.dmlcz/135729
 | hdl-access =free
  }}</ref>
* Every [[Walrasian equilibrium]] has the core property, but not ''vice versa''. The [[Edgeworth conjecture]] states that, given additional assumptions, the limit of the core as the number of consumers goes to infinity is a set of Walrasian equilibria.
* Let there be ''n'' players, where ''n'' is odd. A game that proposes to divide one unit of a good among a coalition having at least (''n''+1)/2  members has an empty core. That is, no stable coalition exists.

==Example==

===Example 1: Miners===
Consider a group of ''n'' miners, who have discovered large bars of gold.  If two miners can carry one piece of gold, then the payoff of a coalition ''S'' is

:<math>v(S) = \begin{cases} |S|/2, & \text{if }|S|\text{ is even}; \\ (|S|-1)/2, & \text{if }|S|\text{ is odd}. \end{cases}</math>

If there are more than two miners and there is an even number of miners, then the core consists of the single payoff where each miner gets 1/2. If there is an odd number of miners, then the core is empty.

===Example 2: Gloves===
Mr A and Mr B are knitting gloves. The gloves are one-size-fits-all, and two gloves make a pair that they sell for €5. They have each made three gloves. How to share the proceeds from the sale? The problem can be described by a [[Game theory#Characteristic function form|characteristic function form]] game with the following characteristic function: Each man has three gloves, that is one pair with a market value of €5. Together, they have 6 gloves or 3 pair, having a market value of €15. Since the singleton coalitions (consisting of a single man) are the only non-trivial coalitions of the game all possible distributions of this sum belong to the core, provided both men get at least €5, the amount they can achieve on their own. For instance (7.5, 7.5) belongs to the core, but so does (5, 10) or (9, 6).

===Example 3: Shoes===
For the moment ignore shoe sizes: a pair consists of a left and a right shoe, which can then be sold for €10. Consider a game with 2001 players: 1000 of them have 1 left shoe, 1001 have 1 right shoe. The core of this game is somewhat surprising: it consists of a single imputation that gives 10 to those having a (scarce) left shoe, and 0 to those owning an (oversupplied) right shoe. No coalition can block this outcome, because no left shoe owner will accept less than 10, and any imputation that pays a positive amount to any right shoe owner must pay less than 10000 in total to the other players, who can get 10000 on their own. So, there is just one imputation in the core.

The message remains the same, even if we increase the numbers as long as left shoes are scarcer. The core has been criticized for being so extremely sensitive to oversupply of one type of player.

==The core in general equilibrium theory==
The Walrasian equilibria of an exchange economy in a general equilibrium model, will lie in the core of the cooperation game between the agents. Graphically, and in a two-agent economy (see Edgeworth Box), the core is the set of points on the contract curve (the set of Pareto optimal allocations) lying between each of the agents' indifference curves defined at the initial endowments.

==The core in voting theory==
When alternatives are allocations (list of consumption bundles), it is natural to assume that any nonempty subsets of individuals can block a given allocation.
When alternatives are public (such as the amount of a certain public good), however, it is more appropriate to assume that only the coalitions that are large enough can block a given alternative.  The collection of such large ("winning") coalitions is called a ''simple game''.
The ''core of a simple game with respect to a profile of preferences'' is based on the idea that only winning coalitions can reject an alternative <math>x</math> in favor of another alternative <math>y</math>.  A necessary and sufficient condition for the core to be nonempty for all profile of preferences, is provided in terms of the [[Nakamura number]] for the simple game.

==See also==
*[[Cooperative bargaining]]
*[[Welfare economics]]
*[[Pareto efficiency]]
*[[Knaster–Kuratowski–Mazurkiewicz lemma|Knaster–Kuratowski–Mazurkiewicz–Shapley theorem]] - instrumental in proving the non-emptiness of the core.

==References==
{{Reflist}}

===Works cited===
* {{cite book |last1=Edgeworth |first1=Francis Ysidro |title=Mathematical Psychics: An Essay on the Application of Mathematics to the Moral Sciences |date=1881 |publisher=C. K. Paul |location=London |url=https://onlinebooks.library.upenn.edu/webbin/book/lookupid?key=olbp34052 }}

==Further reading==
*{{cite book |last=Ichiishi |first=Tatsuro |title=Game Theory for Economic Analysis |chapter=Cooperative Behavior and Stability |location=New York |publisher=Academic Press |year=1983 |isbn=0-12-370180-5 |pages=77–117 |chapter-url=https://books.google.com/books?id=mMnNBQAAQBAJ&pg=PA77 }}
*{{cite book |last1=Osborne |first1=Martin J. |author-link2=Ariel Rubinstein |last2=Rubinstein |first2=Ariel |title=A Course in Game Theory |publisher=The MIT Press |year=1994 }}
*{{Cite book
  | last =Peleg
  | first =B
  | editor-last =Aumann |editor-first=Robert J. |editor-link=Robert J. Aumann
  | editor2-last=Hart |editor2-first=Sergiu|editor2-link=Sergiu Hart
  | contribution=Axiomatizations of the Core
  | title =Handbook of Game Theory with Economic Applications |volume=I
  | publisher =Elsevier
  | date =1992
  | location =Amsterdam
  | pages =397–412
  | isbn = 978-0-444-88098-7
  }}
* {{cite book 
  | last1=Shoham 
  | first1=Yoav 
  | last2=Leyton-Brown 
  | first2=Kevin 
  | title=Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations 
  | publisher=[[Cambridge University Press]] 
  | isbn=978-0-521-89943-7 
  | url=http://www.masfoundations.org 
  | year=2009 
  | location=New York}} 
* {{cite journal
  | last=Telser | first=Lester G. | author-link = Lester G. Telser
  | title = The Usefulness of Core Theory in Economics
  | journal = [[Journal of Economic Perspectives]]
  | year = 1994 | volume = 8 | issue = 2 | pages = 151–164
  | doi=10.1257/jep.8.2.151| doi-access = free }}

{{Game theory}}

[[Category:Cooperative games]]
[[Category:Game theory equilibrium concepts]]