Core (game theory)

In cooperative game theory, the core is the set of feasible allocations that cannot be improved upon by a subset (a coalition) of the economy's agents. 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) harvtxt error: no target: CITEREFEdgeworth1881 (help), 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 ${\displaystyle (N,v)}$ where ${\displaystyle N}$ denotes the set of players and ${\displaystyle v}$ is the characteristic function. An imputation ${\displaystyle x\in \mathbb {R} ^{N}}$ is dominated by another imputation ${\displaystyle y}$ if there exists a coalition ${\displaystyle C}$, such that each player in ${\displaystyle C}$ prefers ${\displaystyle y}$, formally: ${\displaystyle x_{i}\leq y_{i}}$ for all ${\displaystyle i\in C}$ and there exists ${\displaystyle i\in C}$ such that ${\displaystyle x_{i}<y_{i}}$ and ${\displaystyle C}$ can enforce ${\displaystyle y}$ (by threatening to leave the grand coalition to form ${\displaystyle C}$), formally: ${\displaystyle \sum _{i\in C}y_{i}\leq v(C)}$. An imputation ${\displaystyle x}$ is dominated if there exists an imputation ${\displaystyle y}$ dominating it. fr The core is the set of imputations that are not dominated.^[3]

Properties

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

1. Efficiency: ${\displaystyle \sum _{i\in N}x_{i}=v(N)}$,
2. Coalitional rationality: ${\displaystyle \sum _{i\in C}x_{i}\geq v(C)}$ for all subsets (coalitions) ${\displaystyle 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".^[4][5]
• 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

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

광부가 2명 이상이고 광부 수가 짝수인 경우, 핵심은 각 광부가 1/2을 얻는 단일 보상으로 구성된다. 광부 수가 홀수일 경우 핵은 비어 있다.

예 2: 장갑

A씨와 B씨는 장갑을 뜨개질하고 있다. 장갑은 모두 한 벌이고, 장갑 두 개는 5유로짜리 한 켤레를 판다. 그들은 각각 3개의 장갑을 만들었다. 판매 수익금은 어떻게 분담할 것인가? 문제는 다음과 같은 특징적 기능을 가진 특징적 함수 형태 게임으로 설명할 수 있다. 각 남자는 3개의 장갑을 가지고 있는데, 그것은 시장가치가 5유로인 1쌍이다. 그들은 함께 6개의 장갑이나 3개의 쌍을 가지고 있으며, 시장가치는 15유로다. 싱글톤 연합(싱글맨으로 구성됨)은 게임의 유일한 비독점적 연합이므로, 이 합계의 가능한 모든 분포가 핵심에 속하며, 두 사람이 스스로 달성할 수 있는 양인 5유로 이상을 획득할 경우. 예를 들어 (7.5, 7.5)는 코어에 속하지만 (5, 10) 또는 (9, 6)도 코어에 속한다.

예 3: 신발

당분간 신발 사이즈는 무시하라: 한 켤레는 왼쪽과 오른쪽 신발로 구성되며, 그 신발은 10유로(약 1만 원)에 팔릴 수 있다. 2001년 선수들과의 경기를 생각해보자: 그들 중 1000명은 왼쪽 신발 1개를 가지고 있고, 1001명은 오른쪽 신발 1개를 가지고 있다. 이 게임의 핵심은 다소 놀랍다: 왼쪽 신발을 가진 사람에게는 10을 주고 오른쪽 신발을 가진 사람에게는 0을 주는 하나의 귀책자로 구성되어 있다. 어떤 연합도 이 결과를 막을 수 없다. 왜냐하면 어떤 왼쪽 신발 소유주도 10개 이하로 받아들이지 않을 것이고, 어떤 오른쪽 신발 소유주에게도 긍정적인 금액을 지불하는 어떤 귀책도 10,000개 이하로 지불해야 하기 때문이다. 그들은 스스로 10,000개를 얻을 수 있다. 그래서, 핵심에는 단 하나의 귀신이 있을 뿐이다.

왼쪽 신발이 더 무서운 한 숫자를 늘린다 해도 메시지는 그대로다. 코어는 한 유형의 선수의 공급 과잉에 매우 민감하다는 비판을 받아왔다.

일반 평형 이론의 핵심

일반적인 평형모델에서 거래소 경제의 왈라시아 평형주의는 요원들 간의 협력 게임의 핵심에 놓여질 것이다. 그래픽적으로는, 그리고 2-에이전트 경제에서 (에지워스 박스 참조) 핵심은 최초 기부금에서 정의된 각 에이전트의 무관심 곡선 사이에 놓여 있는 계약 곡선상의 포인트 세트(파레토 최적 배분 세트)이다.

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 ${\displaystyle x}$ in favor of another alternative ${\displaystyle 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.

See also

• Welfare economics
• Pareto efficiency
• Knaster–Kuratowski–Mazurkiewicz–Shapley theorem - instrumental in proving the non-emptiness of the core.

References

Further reading

• Ichiishi, Tatsuro (1983). "Cooperative Behavior and Stability". Game Theory for Economic Analysis. New York: Academic Press. pp. 77–117. ISBN 0-12-370180-5.
• Osborne, Martin J.; Rubinstein, Ariel (1994). A Course in Game Theory. The MIT Press.
• Peleg, B (1992). "Axiomatizations of the Core". In Aumann, Robert J.; Hart, Sergiu (eds.). Handbook of Game Theory with Economic Applications. I. Amsterdam: Elsevier. pp. 397–412. ISBN 978-0-444-88098-7.
• 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". Journal of Economic Perspectives. 8 (2): 151–164. doi:10.1257/jep.8.2.151.