Core (game theory)

In cooperative game theory, the core is the set of feasible allocations or imputations where no coalition of agents can benefit by breaking away from the grand coalition. One can think of the core corresponding to situations where it is possible to sustain cooperation among all agents. A coalition is said to improve upon or block a feasible allocation if the members of that coalition can generate more value among themselves than they are allocated in the original allocation. As such, that coalition is not incentivized to stay with the grand coalition.

An allocation is said 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 Edgeworth (1881), at the time referred to as the contract curve.^[1] Even though von Neumann and Morgenstern considered it an interesting concept, they only worked with zero-sum games where the core is always empty. The modern definition of the core is due to Gillies.^[2]

Definition

Consider a transferable utility cooperative game $(N,v)$ where $N$ denotes the set of players and $v$ is the characteristic function. An imputation $x\in \mathbb {R} ^{N}$ is dominated by another imputation $y$ if there exists a coalition $C$ , such that each player in $C$ weakly-prefers $y$ ( $x_{i}\leq y_{i}$ for all $i\in C$ ) and there exists $i\in C$ that strictly-prefers $y$ ( $x_{i}<y_{i}$ ), and $C$ can enforce $y$ by threatening to leave the grand coalition to form $C$ ( $\sum _{i\in C}y_{i}\leq v(C)$ ). The core is the set of imputations that are not dominated by any other imputation.^[3]

Weak core

An imputation $x\in \mathbb {R} ^{N}$ is strongly-dominated by another imputation $y$ if there exists a coalition $C$ , such that each player in $C$ strictly-prefers $y$ ( $x_{i}<y_{i}$ for all $i\in C$ ). The weak core is the set of imputations that are not strongly-dominated.^[4]

Properties

Another definition, equivalent to the one above, states that the core is a set of payoff allocations $x\in \mathbb {R} ^{N}$ satisfying

Efficiency: $\sum _{i\in N}x_{i}=v(N)$ ,
Coalitional rationality: $\sum _{i\in C}x_{i}\geq v(C)$ for all subsets (coalitions) $C\subseteq N$ .

The core is always well-defined, but can be empty.
The core is a set which satisfies a system of weak linear inequalities. Hence the core is closed and convex.
The Bondareva–Shapley theorem: the core of a game is nonempty if and only if the game is "balanced".^[5]^[6]
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

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

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 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 $x$ in favor of another alternative $y$ . 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.

References

^ Kannai, Y. (1992). "The core and balancedness". In Aumann, Robert J.; Hart, Sergiu (eds.). Handbook of Game Theory with Economic Applications. Vol. I. Amsterdam: Elsevier. pp. 355–395. ISBN 978-0-444-88098-7.
^ Gillies, D. B. (1959). "Solutions to general non-zero-sum games". In Tucker, A. W.; Luce, R. D. (eds.). Contributions to the Theory of Games IV. Annals of Mathematics Studies. Vol. 40. Princeton: Princeton University Press. pp. 47–85.
^ As noted by Shapley, L. S.; Shubik, M. (1969). "On Market Games". Journal of Economic Theory. 1 (1): 9–25. doi:10.1016/0022-0531(69)90008-8. S2CID 153498438. due to the contribution of Mr. E. Kohlberg
^ Yu, Chaowen (8 December 2020). "A note on the weak core of simple games with ordinary preferences and uncountable alternatives". SSRN Electronic Journal. doi:10.2139/ssrn.3225500.
^ Bondareva, Olga N. (1963). "Some applications of linear programming methods to the theory of cooperative games (In Russian)". Problemy Kybernetiki. 10: 119–139.
^ 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.

Works cited

Edgeworth, Francis Ysidro (1881). Mathematical Psychics: An Essay on the Application of Mathematics to the Moral Sciences. London: C. K. Paul.

v t e Topics of game theory
Definitions	Congestion game Cooperative game Determinacy Escalation of commitment Extensive-form game First-player and second-player win Game complexity Graphical game Hierarchy of beliefs Information set Normal-form game Preference Sequential game Simultaneous game Simultaneous action selection Solved game Succinct game Mechanism design
Equilibrium concepts	Bayes correlated equilibrium Bayesian Nash equilibrium Berge equilibrium Core Correlated equilibrium Coalition-proof Nash equilibrium Epsilon-equilibrium Evolutionarily stable strategy Gibbs equilibrium Mertens-stable equilibrium Markov perfect equilibrium Nash equilibrium Pareto efficiency Perfect Bayesian equilibrium Proper equilibrium Quantal response equilibrium Quasi-perfect equilibrium Risk dominance Satisfaction equilibrium Self-confirming equilibrium Sequential equilibrium Shapley value Strong Nash equilibrium Subgame perfection Trembling hand equilibrium
Strategies	Appeasement Backward induction Bid shading Collusion Cheap talk De-escalation Deterrence Escalation Forward induction Grim trigger Markov strategy Pairing strategy Dominant strategies Pure strategy Mixed strategy Strategy-stealing argument Tit for tat
Classes of games	Auction Bargaining problem Global game Intransitive game Mean-field game n-player game Perfect information Large Poisson game Potential game Repeated game Screening game Signaling game Strictly determined game Stochastic game Symmetric game Zero-sum game
Games	Go Chess Infinite chess Checkers All-pay auction Prisoner's dilemma Gift-exchange game Optional prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Lewis signaling game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Electronic mail game Rock paper scissors Pirate game Dictator game Public goods game Blotto game War of attrition El Farol Bar problem Fair division Fair cake-cutting Bertrand competition Cournot competition Stackelberg competition Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Induction puzzles Trust game Princess and monster game Rendezvous problem
Theorems	Aumann's agreement theorem Folk theorem Minimax theorem Nash's theorem Negamax theorem Purification theorem Revelation principle Sprague–Grundy theorem Zermelo's theorem
Key figures	Albert W. Tucker Amos Tversky Antoine Augustin Cournot Ariel Rubinstein Claude Shannon Daniel Kahneman David K. Levine David M. Kreps Donald B. Gillies Drew Fudenberg Eric Maskin Harold W. Kuhn Herbert Simon Hervé Moulin John Conway Jean Tirole Jean-François Mertens Jennifer Tour Chayes John Harsanyi John Maynard Smith John Nash John von Neumann Kenneth Arrow Kenneth Binmore Leonid Hurwicz Lloyd Shapley Melvin Dresher Merrill M. Flood Olga Bondareva Oskar Morgenstern Paul Milgrom Peyton Young Reinhard Selten Robert Axelrod Robert Aumann Robert B. Wilson Roger Myerson Samuel Bowles Suzanne Scotchmer Thomas Schelling William Vickrey
Search optimizations	Alpha–beta pruning Aspiration window Principal variation search max^n algorithm Paranoid algorithm Lazy SMP
Miscellaneous	Bounded rationality Combinatorial game theory Confrontation analysis Coopetition Evolutionary game theory Glossary of game theory List of game theorists List of games in game theory No-win situation Topological game Tragedy of the commons