Core (game theory)

In cooperative game theory, a concept for solving a cooperative game is referred to as a core (sometimes also directly from English: core ) . "At the core" are all those allocations of goods to the players that are coalition-rational, that is, which give no player an incentive to join forces with other players and only pursue the interests of the coalition instead of cooperating with the rest of the players . This is because, in essence, the total value of any coalition is never greater than the portion of the allocation that the coalition members would receive without a merger.

A significant application of the concept can be found in the field of microeconomics in the theory of general equilibrium .

definition

Cooperative games with transferable benefits can be fully described by the number of players and a coalition function. A coalition function is a (real-valued) function that delivers the value of this coalition for every possible combination of players - one speaks of "coalitions". This is similar to the concept of utility function ; The coalition function indicates the (total) value of a coalition for the whole of the coalition, which also implies the further assumption that the value of a coalition does not depend on the behavior of players who are not members of the coalition. The value of the game for each individual player (in the following: payoff) is described by an n- vector (state), which is also referred to as an allocation, particularly with a view to economic applications. ${\displaystyle n}$

Definition: Be a cooperative game with transferierbarem benefits, with the amount of players called and the coalition function . An allocation is an allocation ( english imputation ) if: ${\displaystyle (N,v)}$ ${\displaystyle N=\{1,\ldots ,n\}}$ ${\textstyle v:2^{N}\rightarrow \mathbb {R} }$ ${\displaystyle v(\emptyset )=0}$ ${\displaystyle \mathbf {x} =(x_{1},\ldots ,x_{n})}$

1. ${\displaystyle \sum _{i\in N}x_{i}=v(N)}$ and
2. ${\displaystyle x_{i}\geq v(\{i\})}$for everyone . ${\displaystyle i\in N}$

An allocation is a core allocation if

3. ${\displaystyle \sum _{i\in S}x_{i}\geq v(S)}$for all coalitions . ${\displaystyle S\subseteq N}$

The set of core allocations of is called the core of the game . In short: ${\displaystyle (N,v)}$ ${\displaystyle {\mathcal {C}}(N,v)}$

${\displaystyle {\mathcal {C}}(N,v):=\left\{\mathbf {x} \in \mathbb {R} ^{n}\left|\sum _{i\in N}x_{i}=v(N)\quad \mathrm {\&} \quad \sum _{i\in S}x_{i}\geq v(S)\mathrm {,} \;\forall S\subseteq N\right.\right\}}$

Condition (1) ( efficiency condition, also: Pareto optimality condition or requirement of collective rationality ) states that if all players form a single grand coalition, their aggregated payoff corresponds to the value of the coalition. In order to understand why this assumption is reasonable, it can first be stated that the aggregate payoff of the coalition members can never exceed the value of the coalition. It could only be below that. Obviously, this would be inefficient; the unallocated portion of the coalition value could be distributed and thus at least one coalition member could be placed in a strictly better position without putting another coalition member at a disadvantage at the same time. Condition (2) formalizes the requirement of individual rationality . It excludes allocations in which a player scores less than if he stayed away from the coalition and played alone. This is intuitively obvious: in order for an individual to participate in a coalition, it will have to offer at least a weak payoff incentive.

A specific prerequisite for a core allocation is condition (3), which calls for coalition-rational payoff configurations. It states that in any imaginable coalition, the total amount that members will receive under the allocation will be at least as high as the coalition's value. Obviously, (3) also implies (2), but not vice versa, and is related to the set of allotments of . ${\displaystyle {\mathcal {C}}(N,v)\subseteq {\mathcal {I}}(N,v)}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle (N,v)}$

properties

agreement

There are three standard definitions and notational agreements:

• The amount is the amount of coalition functions for cooperative games with transferable benefits and the amount of players . ${\displaystyle {\mathcal {G}}^{N}}$ ${\displaystyle N}$
• For a coalition, it is defined as the -dimensional Euclidean space that is spanned by the participating players. ${\displaystyle S}$ ${\displaystyle \mathbb {R} ^{S}}$ ${\displaystyle |S|}$ ${\displaystyle S}$
• Be a crowd, a scalar and . Then the set is defined by and the set by . ${\displaystyle X\subseteq \mathbb {R} ^{N}}$ ${\displaystyle \alpha }$ ${\displaystyle {\boldsymbol {\beta }}\in \mathbb {R} ^{X}}$ ${\displaystyle \alpha X}$ ${\displaystyle \alpha X:=\{\alpha \mathbf {x} |\mathbf {x} \in X\}}$ ${\displaystyle X+{\boldsymbol {\beta }}}$ ${\displaystyle X+{\boldsymbol {\beta }}:=\{\mathbf {x} +{\boldsymbol {\beta }}|\mathbf {x} \in X\}}$

Basic texture

Be the core of a game , . ${\textstyle {\mathcal {C}}(N,v)}$ ${\textstyle (N,v)}$ ${\textstyle v\in {\mathcal {G}}^{N}}$

a) The core is convex and compact .

b) Let the core of a different game , which too is strategically equivalent. Then the core emerges from the core of the other game as follows: ${\textstyle {\mathcal {C}}(N,w)}$ ${\textstyle (N,v)}$ ${\textstyle (N,w)}$ ${\textstyle w\in {\mathcal {G}}^{N}}$ ${\textstyle (N,v)}$

${\displaystyle {\mathcal {C}}(N,w)=\alpha {\mathcal {C}}(N,v)+{\boldsymbol {\beta }}}$

with suitable . ${\textstyle \alpha ,{\boldsymbol {\beta }}}$

c) Core solutions are anonymous, symmetrical, Pareto-optimal and superadditive.

Property (a) already follows from the definition of weak inequalities. The meaning of (b) results from the application of strategically equivalent games. Formally, one describes two games and as strategically equivalent, if there is a constant and a vector , so that for every coalition it applies that , that is, the coalition function of one game results from the coalition function of the other game through positive affine transformation. One can imagine that strategically equivalent games only differ in that each player receives a fixed amount ( ) or has fixed costs ( ) regardless of the game result and that the unit in which the payoff is paid out changes ( for example, the Reflect transition from cents to euros). In the transition from one game to a strategically equivalent game, the core changes, so the statement of sentence (b), so to a certain extent in step with the changes in the coalition function. ${\textstyle (N,v)}$ ${\textstyle (N,w)}$ ${\displaystyle \alpha >0}$ ${\textstyle {\boldsymbol {\beta }}\in \mathbb {R} ^{N}}$ ${\textstyle S\subseteq 2^{N}\backslash \{\emptyset \}}$ ${\textstyle w(S)=\alpha v(S)+\sum _{i\in S}\beta _{i}}$ ${\textstyle \beta _{i}>0}$ ${\textstyle \beta _{i}<0}$ ${\textstyle \alpha =0{,}01}$

existence

Set of Bondareva and Shapley (Bondareva 1963, Shapley 1967): Be a cooperative game . Then the following statements are equivalent: ${\displaystyle (N,v)}$ ${\textstyle v\in {\mathcal {G}}^{N}}$

1. ${\displaystyle {\mathcal {C}}(N,v)}$ is not empty.
2. ${\displaystyle (N,v)}$is a balanced (balanced) game, that is, for every balanced (balanced) set of coalitions with the associated weighting factors , the inequality applies ${\displaystyle \{S_{1},\ldots ,S_{k}\}}$ ${\displaystyle N}$ ${\displaystyle \lambda _{1},\ldots ,\lambda _{k}}$

${\displaystyle \sum _{j=1}^{k}\lambda _{j}v(S_{j})\leq v(N)}$.

The theorem, independently proven by Olga Bondareva and Lloyd Shapley, is largely based on the concept of the equilibrium of a set system (i.e. a set of sets that are subsets of the same basic set - here: -). Such a set system of coalitions (here:) is called balanced if there are strictly positive weighting factors (here:) so that it applies to every player that ${\displaystyle N}$ ${\displaystyle \{S_{1},\ldots ,S_{k}\}}$ ${\displaystyle \lambda _{1},\ldots ,\lambda _{k}}$ ${\displaystyle i\in N}$

${\displaystyle \sum _{j=1,\ldots ,k:i\in S_{j}}\lambda _{j}=1}$,

That means: A set system of coalitions is balanced if it applies to every player that the weighting factors of all coalitions of the set system to which he belongs add up to one. One way of interpreting this is to imagine the weighting factors as proportions of the available time budget; Wiese (2005) therefore describes them as “part-time factors”. Assume that each player can divide his time between different coalitions. In this conception, the quantity system is balanced when no player "wastes time" ( ) or spends more time than he has available ( ), but divides his entire time budget over the coalitions of the quantity system to which he belongs. It is therefore a kind of budget restriction for the time budget. For a coalition to be active for a certain amount of time , all members of must be active. If they are, the coalition pays off a payoff of . In other words, a game is balanced precisely in that the players do not have any alternative permissible time division that would bring them a higher total payoff than . ${\textstyle \sum _{j=1,\ldots ,k:i\in S_{j}}\lambda _{j}<1}$ ${\textstyle \sum _{j=1,\ldots ,k:i\in S_{j}}\lambda _{j}>1}$ ${\displaystyle S_{j}}$ ${\displaystyle \lambda _{j}}$ ${\displaystyle S_{j}}$ ${\displaystyle \lambda _{j}v(S_{j})}$ ${\displaystyle v(N)}$

General equilibrium theory

Basics

Consider an economy with goods in which there are no externalities . The prices for these goods are summarized in a price vector , where . In economics there are also consumers and companies, whereby the index quantities (the quantity of all consumers) and (the quantity of all producers) are defined for these two groups . Producers and consumers alike are price takers. Consumers and producers are now considered one after the other, then the initial equipment of the economy: ${\textstyle n}$ ${\textstyle \mathbf {p} =(p_{1},\ldots ,p_{n})}$ ${\textstyle \mathbf {p} \neq \mathbf {0} }$ ${\textstyle I}$ ${\textstyle J}$ ${\textstyle {\mathcal {I}}=\{1,\ldots ,I\}}$ ${\textstyle {\mathcal {J}}=\{1,\ldots ,J\}}$

• A person's consumption profile is - it provides information on how much a person consumes of each of the goods. The amount covers all possible consumption profiles of (consumption possibilities amount of ). The preference structure of each individual is in turn expressed in its utility function . ${\textstyle i\in {\mathcal {I}}}$ ${\textstyle \mathbf {x} ^{i}=(x_{1}^{i},\ldots ,x_{n}^{i})\in \mathbb {R} _{+}^{n}}$ ${\textstyle i}$ ${\textstyle n}$ ${\textstyle X_{i}\subset \mathbb {R} _{+}^{n}}$ ${\textstyle i}$ ${\textstyle i}$ ${\textstyle i\in {\mathcal {I}}}$ ${\textstyle u^{i}=u^{i}(\mathbf {x} ^{i})\in \mathbb {R} }$
• The production of every company is given by the production vector; it indicates how much company produces of each of the goods. However, due to technological restrictions, only those production plans are possible that are contained in a quantity (production possibility quantity of ). ${\textstyle j\in {\mathcal {J}}}$ ${\textstyle \mathbf {y} ^{j}=(y_{1}^{j},\ldots ,y_{n}^{j})\in \mathbb {R} ^{n}}$ ${\textstyle j}$ ${\textstyle n}$ ${\textstyle Y_{j}\subset \mathbb {R} ^{J}}$ ${\textstyle j}$
• The initial stocks of the respective goods are given by an equipment vector. ${\textstyle \mathbf {e} =(e_{1},\ldots ,e_{n})\in \mathbb {R} _{+}^{n}}$

With the agreed definitions regarding the preference structure of the individuals, the technological capacities of the producers and the resource stocks, an economy can be defined by the tuple

${\displaystyle \mathbf {\mathcal {E}} =\left[\left(X_{i},u^{i}\right)_{i\in {\mathcal {I}}},\left(Y_{j}\right)_{j\in {\mathcal {J}}},\mathbf {e} \right]}$

characterize. In a competitive economy, both the initial equipment and the companies are owned by the consumers. One agrees accordingly as the equipment of a person (with regard to all goods). Let the share in the profits of any company be held by consumers . According to the requirements is and . ${\textstyle \mathbf {e} ^{i}=(e_{1}^{i},\ldots ,e_{n}^{i})\in \mathbb {R} _{+}^{n}}$ ${\textstyle i\in {\mathcal {I}}}$ ${\textstyle i}$ ${\textstyle {\boldsymbol {\theta }}^{i}=(\theta _{1}^{i},\ldots ,\theta _{J}^{i})\in \mathbb {R} ^{J}}$ ${\textstyle \mathbf {e} =\sum _{i\in {\mathcal {I}}}\mathbf {e} ^{i}}$ ${\textstyle \sum _{i\in {\mathcal {I}}}{\boldsymbol {\theta }}^{i}=\mathbf {1} }$

Consider a competitive economy. Then a tuple is called the Walrasian equilibrium of this economy if: ${\textstyle \left[\left(\mathbf {x} ^{i*}\right)_{i\in {\mathcal {I}}},\left(\mathbf {y} ^{j*}\right)_{j\in {\mathcal {J}}},\mathbf {p} ^{*}\right]}$

1. (Profit maximization :) Given the equilibrium market prices, every company maximizes its profit, which means that applies to all : for all . ${\displaystyle j\in {\mathcal {J}}}$ ${\displaystyle \mathbf {p} ^{*}\cdot \mathbf {y} ^{j}\leq \mathbf {p} ^{*}\cdot \mathbf {y} ^{j*}}$ ${\displaystyle \mathbf {y} ^{j}}$
2. (Benefit maximization :) Every consumer maximizes his benefit, that is, it applies to all that the benefit function maximizes while maintaining the budget condition . ${\textstyle i\in {\mathcal {I}}}$ ${\textstyle \mathbf {x} ^{i*}}$ ${\textstyle u^{i}(\mathbf {x} ^{i})}$ ${\textstyle \mathbf {p} ^{*}\cdot \mathbf {x} ^{i}\leq \mathbf {p} ^{*}\cdot \mathbf {e} ^{i}+\sum _{j=1}^{J}\theta _{j}^{i}(\mathbf {p} ^{*}\cdot \mathbf {y} ^{j*})}$
3. (Market clearing :) For each good applies: . ${\textstyle k}$ ${\textstyle \sum _{i=1}^{I}x_{k}^{i*}=e_{k}+\sum _{j=1}^{J}y_{k}^{j*}}$

If, instead of a competitive economy, one considers a pure exchange economy (in which there is no production, but the initial equipment is only redistributed through exchange), then there is a Walrasian equilibrium if the following applies:

1. (Benefit maximization :) Every consumer maximizes his benefit, that is, it applies to all that the benefit function maximizes while maintaining the budget condition . ${\textstyle i\in {\mathcal {I}}}$ ${\textstyle \mathbf {x} ^{i*}}$ ${\textstyle u^{i}(\mathbf {x} ^{i})}$ ${\textstyle \mathbf {p} ^{*}\cdot \mathbf {x} ^{i}\leq \mathbf {p} ^{*}\cdot \mathbf {e} ^{i}}$
2. (Market clearance :) The following applies to every good : ${\textstyle k}$ ${\textstyle \sum _{i=1}^{I}x_{k}^{i*}=e_{k}}$

Core of an economy

The game theory concept of the kernel can be applied in the theory of general equilibrium. A given (consumption) allocation can be blocked if there is a coalition of consumers who can force an alternative allocation through which - compared to the initial allocation - no member of the coalition is worse off and at least one is strictly better off. The set of all non-blockable (consumption) allocations is called the core of the economy. Core allocations are allocations with the property that no group of consumers can profitably "split off" from the economy in order to only trade among themselves from now on.

Formal: In the simplest case, be a pure exchange economy. Then there is an allocation that is in turn called permissible (in ) if . Continue to be any coalition. Define now as the set of all coalition-internal consumption profiles with the property that the coalition members do not consume more of any good than they have brought into the coalition as equipment: ${\textstyle \mathbf {\mathcal {E}} }$ ${\textstyle \left(\mathbf {x} ^{i}\right)_{i\in {\mathcal {I}}}}$ ${\textstyle \mathbf {\mathcal {E}} }$ ${\textstyle \sum _{i\in {\mathcal {I}}}\mathbf {x} ^{i}\leq \mathbf {e} }$ ${\textstyle S\subseteq {\mathcal {I}}}$ ${\textstyle X^{S}}$

${\displaystyle X^{S}:=\left\{\left.\left(\mathbf {x} ^{s}\right)_{s\in S}\in \left(\mathbb {R} _{+}^{n}\right)^{|S|}\right|\sum _{s\in S}\mathbf {x} ^{s}\leq \sum _{s\in S}\mathbf {e} ^{s}\right\}}$

Definition: The core of an economy is the set of all allocations for which there is no coalition with an associated internal coalition allocation that has the following properties: ${\textstyle \left(\mathbf {x} ^{i}\right)_{i\in {\mathcal {I}}}}$ ${\textstyle S\subseteq {\mathcal {I}}}$ ${\textstyle \left({\tilde {\mathbf {x} }}^{s}\right)_{s\in S}}$

1. (Admissibility in :) ${\textstyle S}$ ${\textstyle \left({\tilde {\mathbf {x} }}^{s}\right)_{s\in S}\in X^{S}}$
2. (Pareto improvement for :) for all and for any one . ${\textstyle S}$ ${\textstyle u^{s}\left({\tilde {\mathbf {x} }}^{s}\right)\geq u^{s}\left(\mathbf {x} ^{s}\right)}$ ${\textstyle s\in S}$ ${\textstyle u^{s}\left({\tilde {\mathbf {x} }}^{s}\right)>u^{s}\left(\mathbf {x} ^{s}\right)}$ ${\textstyle s\in S}$

Walrasian balance and core

Theorem: Let a Walrasian equilibrium be a pure exchange economy and let the preferences of all consumers not be saturated locally (in the special case: let the utility functions of all consumers be strictly monotonous). Then lies at the core of . ${\textstyle (\mathbf {x} ,\mathbf {p} )}$ ${\textstyle \mathbf {\mathcal {E}} }$ ${\displaystyle i\in {\mathcal {I}}}$ ${\textstyle \mathbf {x} }$ ${\textstyle \mathbf {\mathcal {E}} }$

The reverse implication does not generally apply: Not every core allocation is also a Walrasian equilibrium allocation. However, it can be shown that this is the case for sufficiently large economies (i.e. those with a sufficiently large number of consumers) (Debreu-Scarf theorem).

Extensions

Definition: Be a cooperative game with transferierbarem benefits, with the amount of players called and the coalition function . Then one designates the amount ${\displaystyle (N,v)}$ ${\displaystyle N=\{1,\ldots ,n\}}$ ${\displaystyle v:2^{N}\rightarrow \mathbb {R} }$ ${\displaystyle v(\emptyset )=0}$

${\displaystyle {\mathcal {C}}_{\epsilon }(N,v):=\left\{\mathbf {x} \in \mathbb {R} ^{n}\left|\sum _{i\in N}x_{i}=v(N)\quad \mathrm {\&} \quad \sum _{i\in S}x_{i}\geq v(S)-\epsilon \mathrm {,} \;\forall S\notin \{N,\emptyset \}\right.\right\}}$

as a strict core. ${\displaystyle \epsilon }$

literature

• Rodica Branzei, Dinko Dimitrov and Stef Tijs: Models in Cooperative Game Theory. 2nd Edition. Springer, Berlin a. a. 2008, ISBN 978-3-540-77953-7 .
• Theo Driessen: Cooperative Games, Solutions and Applications. Kluwer, Dordrecht u. a. 1988, ISBN 90-277-2729-5 .
• Robert P. Gilles: The Cooperative Game Theory of Networks and Hierarchies. Springer, Berlin a. a. 2010, ISBN 978-3-642-05281-1 .
• Yakar Kannai: The Core and Balancedness. In: Robert J. Aumann and Sergiu Hart (Eds.): Handbook of Game Theory with Economic Applications. 1. Elsevier, Amsterdam 1992, ISBN 0-444-88098-4 , pp. 355-395, doi : 10.1016 / S1574-0005 (05) 80015-3 .
• Michael Maschler, Eilon Solan and Shmuel Zamir: Game Theory. Cambridge University Press, Cambridge u. a. 2013, ISBN 978-1-107-00548-8 .
• Vladimir Mazalov: Mathematical Game Theory and Applications. Wiley, Chicester 2014, ISBN 978-1-118-89962-5 .
• Bezalel Peleg and Peter Sudhölter: Introduction to The Theory of Cooperative Games. 2nd Edition. Springer, Berlin a. a. 2007, ISBN 978-3-540-72944-0 .
• Harald Wiese: Cooperative game theory. Oldenbourg, Munich 2005, ISBN 3-486-57745-X .

Economic application

• David M. Kreps: Microeconomic Foundations I. Choice and Competitive Markets. Princeton University Press, Princeton 2012, ISBN 978-0-691-15583-8 . [To the core: Chapter 15]
• James C. Moore: General equilibrium and welfare economics. An introduction. Springer, Berlin a. a. 2007, ISBN 978-3-540-31407-3 (also online: doi : 10.1007 / 978-3-540-32223-8 ). [To the core: Chapter 11]
• Lester G. Telser: The Core Theory in Economics. Problems and Solutions. Routledge, Oxon 2007, ISBN 978-0-415-70144-0 .

Remarks

1. ↑ See Maschler et al. 2013, pp. 674, 687; Peleg / Sudhölter 2007, p. 19 f .; Gilles 2010, pp. 19, 30; Driessen 1988, p. 13 f., 20.
2. ↑ The set is the power set of , i.e. the set of all subsets of . Note that the empty set ( ) is also a subset. ${\textstyle 2^{N}}$ ${\textstyle N}$ ${\textstyle N}$ ${\displaystyle \emptyset }$
3. ↑ See Wiese 2005, p. 144.
4. ↑ See Peleg / Sudhölter 2007, p. 20.
5. ↑ Cf., also for proof, Maschler et al. 2013, p. 687 f.
6. ↑ Cf., also for proof, Maschler et al. 2013, p. 690 f.
7. ↑ See Peleg / Sudhölter 2007, p. 20 f.
8. ↑ See for example Branzei et al. 2008, p. 8.
9. ↑ Olga N. Bondareva: Nekotoriye primeneniya metodov lineynogo programmirovaniya k teorii Kooperativnikh igr. In: Problemy Kybernetiki. 10, 1963, pp. 119-139 [in Russian]. English translation under the title Some applications of linear programming methods to the theory of cooperative games reprinted in Selected Russian Papers on Game Theory, 1959–1965. Princeton University, Princeton 1968, pp. 79–114, also princeton.edu (PDF; 3.3 MB).
10. ^ Lloyd S. Shapley : On balanced sets and cores. In: Naval Research Logistics Quarterly. 14, 1967, pp. 453-460, doi : 10.1002 / nav.3800140404 .
11. ↑ See, also for evidence, Kannai 1992, p. 359 f .; Maschler et al. 2013, p. 695 ff .; Peleg / Sudhölter 2007, p. 28 f.
12. ↑ See Gilles 2010, p. 37; Peleg / Sudhölter 2007, p. 28.
13. ↑ See Maschler et al. 2013, p. 694.
14. ^ Similar to Martin J. Osborne and Ariel Rubinstein: A course in game theory. MIT Press, Cambridge 1994, ISBN 0-262-65040-1 , p. 262.
15. ↑ See Martin J. Osborne and Ariel Rubinstein: A course in game theory. MIT Press, Cambridge 1994, ISBN 0-262-65040-1 , p. 262.
16. ↑ The structure of the economy summarized below follows largely Andreu Mas-Colell, Michael Whinston, Jerry Green: Microeconomic Theory. Oxford University Press, Oxford 1995, ISBN 0-195-07340-1 , in particular pp. 546 f. and partly Moore 2007, pp. 131 ff, 191 ff.
17. ↑ See e.g. Kreps 2012, p. 366 f.
18. ↑ See Kreps 2012, p. 366 ff.
19. ↑ One describes a preference order as locally unsaturated if there exists for any and every environment around one , for which applies: (see also preference order ). ${\displaystyle x_{a}\in X}$ ${\displaystyle \epsilon }$ ${\displaystyle U_{\epsilon }}$ ${\displaystyle x_{a}}$ ${\displaystyle z\in U_{\epsilon }}$ ${\displaystyle zPx_{a}}$
20. ↑ Cf. Kreps 2012, p. 370 ff.