Core (game theory)

In game theory, the core is the set of feasible allocations that cannot be improved upon by a subset (a coalition) of the economy's consumers. A coalition is said to improve upon or block a feasible allocation if the members of that coalition are better off under another feasible allocation that is identical to the first except that every member of the coalition has a different consumption bundle that is part of an aggregate consumption bundle that can be constructed from publicly available technology and the initial endowments of each consumer in the coalition.

An allocation is said to have the core property if there is no coalition that can improve upon it. The core is the set of all feasible allocations with the core property.

Origin

The idea of the core already appeared in the writings of Edgeworth (1881), at the time referred to as the contract curve (Kannai 1992). Even if 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 1959).

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$ prefers $y$ , formally: $x_i\leq y_i$ for all $i\in C$ and there exists $i\in C$ such that $x_i<y_i$ and $C$ can enforce $y$ (by threatening to leave the grand coalition to form $C$ ), formally: $\sum_{i\in C}y_i\geq v(C)$ . An imputation $x$ is dominated if there exists an imputation $y$ dominating it.

When the core exists and is not empty, it is the set of imputations that are not dominated.^[1]

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 iff the game is "balanced" (Bondareva 1963,Shapley 1967).
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

Mrs A and Mrs 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 lady 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 lady) are the only non-trivial coalitions of the game all possible distributions of this sum belong to the core, provided both ladies 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 1, 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

↑ As noted by Shapley, L.S. and Shubik, M. (On Market Games, Journal of Economic Theory, 1, 9-25, 1969) due to the contribution of Mr. E. Kohlberg

Bondareva, Olga N. (1963). "Some applications of linear programming methods to the theory of cooperative games (In Russian)". Problemy Kybernetiki 10: 119–139.
Edgeworth, F. Y. (1881). Mathematical Psychics: An essay on the mathematics to the moral sciences. London: Kegan Paul.
Gillies, D. B. (1959). "Solutions to general non-zero-sum games". In Tucker, A. W.; Luce, R. D. Contributions to the Theory of Games IV. (Annals of Mathematics Studies 40). Princeton: Princeton University Press. pp. 47–85.
Kannai, Y (1992). "The core and balancedness". In Aumann, Robert J.; Hart, Sergiu. Handbook of Game Theory with Economic Applications, Volume I. Amsterdam: Elsevier. pp. 355–395. ISBN 978-0-444-88098-7.
Leyton-Brown, Kevin; Shoham, Yoav (2008). Essentials of Game Theory: A Concise, Multidisciplinary Introduction. San Rafael, CA: Morgan & Claypool Publishers. ISBN 978-1-59829-593-1.
Osborne, Martin J. Rubinstein, Ariel. A Course in Game Theory. The MIT Press (1994)
Peleg, B (1992). "Axiomatizations of the Core". In Aumann, Robert J.; Hart, Sergiu. Handbook of Game Theory with Economic Applications, Volume I. Amsterdam: Elsevier. pp. 397–412. ISBN 978-0-444-88098-7.
Shapley, Lloyd S. (1967). "On balanced sets and cores". Naval Research Logistics Quarterly 14: 453–460. doi:10.1002/nav.3800140404.
Shoham, Yoav; Leyton-Brown, Kevin (2009). Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. New York: Cambridge University Press. ISBN 978-0-521-89943-7.
Telser, Lester G. (1994). "The Usefulness of Core Theory in Economics". The Journal of Economic Perspectives 8 (2): 151–164. doi:10.1257/jep.8.2.151.

Topics in game theory

Definitions	Normal-form game Extensive-form game Graphical game Cooperative game Succinct game Information set Hierarchy of beliefs Preference

Equilibrium concepts	Nash equilibrium Subgame perfection Mertens-stable equilibrium Bayesian-Nash Perfect Bayesian Trembling hand Proper equilibrium Epsilon-equilibrium Correlated equilibrium Sequential equilibrium Quasi-perfect equilibrium Evolutionarily stable strategy Risk dominance Core Shapley value Pareto efficiency Quantal response equilibrium Self-confirming equilibrium Strong Nash equilibrium Markov perfect equilibrium

Strategies	Dominant strategies Pure strategy Mixed strategy Tit for tat Grim trigger Collusion Backward induction Forward induction Markov strategy

Classes of games	Symmetric game Perfect information Simultaneous game Sequential game Repeated game Signaling game Cheap talk Zero-sum game Mechanism design Bargaining problem Stochastic game n-player game Large Poisson game Nontransitive game Global games Strictly determined game

Games	Prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Rock-paper-scissors Pirate game Dictator game Public goods game Blotto games War of attrition El Farol Bar problem Cake cutting Cournot game Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Screening game Prisoners and hats puzzle Trust game Princess and monster game Monty Hall problem Rendezvous problem

Theorems	Minimax theorem Nash's theorem Purification theorem Folk theorem Revelation principle Arrow's impossibility theorem

Key figures	Kenneth Arrow Robert Aumann Kenneth Binmore Samuel Bowles Melvin Dresher Merrill M. Flood Drew Fudenberg Donald B. Gillies John Harsanyi Leonid Hurwicz David K. Levine Daniel Kahneman David M. Kreps Harold W. Kuhn Eric Maskin Jean-François Mertens Paul Milgrom Oskar Morgenstern Roger Myerson John Nash John von Neumann Ariel Rubinstein Thomas Schelling Reinhard Selten Herbert Simon Lloyd Shapley John Maynard Smith Jean Tirole Albert W. Tucker Amos Tversky William Vickrey Robert B. Wilson Peyton Young

See also	Tragedy of the commons Tyranny of small decisions All-pay auction List of games in game theory Confrontation analysis List of game theorists Combinatorial game theory Alpha–beta pruning Bertrand paradox Bounded rationality No-win situation