Kern (Spieltheorie)

Als Kern (teilweise auch direkt aus dem Englischen: Core) bezeichnet man in der kooperativen Spieltheorie ein Konzept zur Lösung eines kooperativen Spiels. „Im“ Kern befinden sich all diejenigen Zuteilungen von Gütern an die Spieler, die koalitionsrational sind, das heißt, die keinem Spieler einen Anreiz geben, sich mit anderen Spielern zusammenzutun, sondern und nur die Interessen der Koalition zu verfolgen. Dies deshalb, weil im Kern der Gesamtwert einer jeden Koalition niemals größer ist als der Teil der Zuteilung, den die Koalitionsmitglieder ohne einen Zusammenschluss erhalten würden.

Eine bedeutsame Anwendung des Konzepts findet sich im Bereich der Mikroökonomik in der Theorie des allgemeinen Gleichgewichts.

Definition

Kooperative Spiele mit transferierbarem Nutzen lassen sich durch die Menge der Spieler und eine Koalitionsfunktion vollständig beschreiben. Eine Koalitionsfunktion ist eine (reellwertige) Funktion, die für jede mögliche Kombination von Spielern – man spricht von „Koalitionen“ – den Wert dieser Koalition liefert. Dies ähnelt dem Konzept der Nutzenfunktion; die Koalitionsfunktion gibt für jede Koalition den (Gesamt)wert dieser Koalition an, was zugleich die weitere Annahme impliziert, dass der Wert einer Koalition nicht vom Verhalten solcher Spieler abhängig ist, die kein Mitglied der Koalition sind. Der Wert des Spiels für jeden einzelnen der $n$ Spieler (im Folgenden: Payoff) wird durch einen n-Vektor (Zustand) beschrieben, den man – insbesondere mit Blick auf ökonomische Anwendungen – auch als Allokation bezeichnet.

Bedingung (1) (Effizienzbedingung, auch: Pareto-Optimalitäts-Bedingung oder Erfordernis kollektiver Rationalität) besagt, dass, wenn sich alle Spieler zu einer einzigen großen Koalition zusammenschließen, ihr aggregierter Payoff dem Wert der Koalition entspricht. Um einzusehen, warum diese Annahme vernünftig ist, kann zunächst festgehalten werden, dass der aggregierte Payoff der Koalitionsmitglieder jedenfalls niemals über dem Wert der Koalition liegen kann. Er könnte nur darunter liegen. Dies aber wäre offensichtlich ineffizient; der nicht zugeteilte Anteil des Koalitionswertes könnte verteilt und damit wenigstens ein Koalitionsmitglied strikt bessergestellt werden, ohne zugleich ein anderes Koalitionsmitglied schlechterzustellen. Die Bedingung (2) formalisiert das Erfordernis individueller Rationalität. Sie schließt Allokationen aus, in denen ein Spieler weniger erzielt, als wenn er der Koalition fernbleibt und alleine spielt. Dies liegt intuitiv nahe: Damit sich ein Einzelner an einer Koalition beteiligt, wird ihm diese zumindest einen schwachen Payoff-Anreiz bieten müssen.

Spezifische Voraussetzung für eine Kernallokation ist Bedingung (3), die koalitionsrationale Payoff-Konfigurationen fordert. Sie besagt, dass in jeder erdenklichen Koalition der Gesamtbetrag, den die Mitglieder gemäß der Zuteilung erhalten, mindestens so hoch wie der Wert der Koalition ist. Offensichtlich impliziert (3) auch (2), aber nicht umgekehrt. Es ist $𝒞(N,v)\subseteq ℐ(N,v)$, wobei $ℐ(N,v)$ die Menge der Zuteilungen von $(N,v)$ ist.

Beispiel

Koalitionsfunktion des (Bei-)Spiels

$S$	$\mathrm{\varnothing }$	$\{A\}$	$\{B\}$	$\{C\}$	$\{A,B\}$	$\{A,C\}$	$\{B,C\}$	$\{A,B,C\}$
$v(S)$	$0$	$200$	$200$	$200$	$700$	$500$	$500$	$1200$

Die folgenden Ungleichungen beschreiben den Kern des (Bei-)Spiels:

$\begin{array}{ccccc}{x}_A,x_B,x_C& \ge & 200& & \text{individuelle Rationalität}\\ x_A+x_B+x_C& =& 1200& & \text{kollektive Rationalität}\\ x_A+x_B& \ge & 700& \\ x_A+x_C& \ge & 500& \\ x_B+x_C& \ge & 500& \end{array}$

Die letzten drei Bedingungen (Nicht-Blockierbarkeit) können zusammengefasst werden zu:

$\begin{array}{ccccc}{\displaystyle }& 2\cdot (x_A+x_B+x_C)& \ge & 1700& \\ \iff & x_A+x_B+x_C& \ge & 850& \end{array}$.

Anhand dieses (Bei-)Spiels wird ersichtlich, dass der Kern durch eine Menge an möglichen Auszahlungsvektoren beschrieben wird.

Eigenschaften

Vereinbarungen

Vorangestellt seien drei definitorische bzw. notationelle Standardvereinbarungen:

• Die Menge ${𝒢}^N$ ist die Menge der Koalitionsfunktionen für kooperative Spiele mit transferierbarem Nutzen und der Spielermenge $N$.
• Für eine Koalition $S$ ist der ${ℝ}^S$ definiert als der $|S|$-dimensionale euklidische Raum, der durch die an $S$ partizipierenden Spieler aufgespannt wird.
• Sei $X\subseteq {ℝ}^N$ eine Menge, $\alpha$ ein Skalar und $\mathit{\beta }\in {ℝ}^N$. Dann ist die Menge $\alpha X$ definiert durch $\alpha X:=\{\alpha 𝐱|𝐱\in X\}$ und die Menge $X+\mathit{\beta }$ durch $X+\mathit{\beta }:=\{𝐱+\mathit{\beta }|𝐱\in X\}$.

Grundlegende Beschaffenheit

Sei $𝒞(N,v)$ der Kern eines Spiels $(N,v)$, $v\in {𝒢}^N$.

a) Der Kern ist konvex und kompakt.

b) Sei $𝒞(N,w)$ der Kern eines von $(N,v)$ verschiedenen Spiels $(N,w)$, $w\in {𝒢}^N$, das zu $(N,v)$ strategisch äquivalent ist. Dann geht der Kern wie folgt aus dem Kern des anderen Spiels hervor:

$𝒞(N,w)=\alpha 𝒞(N,v)+\mathit{\beta }$

mit geeignetem $\alpha ,\mathit{\beta }$.

c) Kernlösungen sind anonym, symmetrisch, Pareto-optimal und superadditiv.

Die Eigenschaft (a) folgt bereits aus der Definition über schwache Ungleichungen. Die Bedeutung von (b) ergibt sich aus der Anwendung strategisch äquivalenter Spiele. Formal bezeichnet man zwei Spiele $(N,v)$ und $(N,w)$ als strategisch äquivalent, wenn es eine Konstante $\alpha >0$ und einen Vektor $\mathit{\beta }\in {ℝ}^N$ gibt, sodass für jede Koalition $S\subseteq 2^N\mathrm{\setminus }\{\mathrm{\varnothing }\}$ gilt, dass $w(S)=\alpha v(S)+\sum _{i\in S}{\beta }_i$, das heißt, die Koalitionsfunktion des einen Spiels durch positive affine Transformation aus der Koalitionsfunktion des anderen Spiels hervorgeht. Man kann sich vorstellen, dass sich strategisch äquivalente Spiele nur dadurch unterscheiden, dass jeder Spieler unabhängig vom Spielergebnis einen fixen Betrag erhält (${\beta }_i>0$) bzw. fixe Kosten hat (${\beta }_i<0$) und dass sich die Einheit ändert, in der der Payoff ausbezahlt wird ($\alpha =0,01$ könnte beispielsweise den Übergang von Cent zu Euro widerspiegeln). Beim Übergang von einem Spiel zu einem strategisch äquivalenten Spiel ändert sich der Kern, so die Aussage des Satzes (b), also gewissermaßen im Gleichschritt mit den Änderungen der Koalitionsfunktion.

Existenz

Das von Olga Bondareva und Lloyd Shapley unabhängig voneinander bewiesene Theorem baut maßgeblich auf dem Konzept der Ausgewogenheit (Balanciertheit) eines Mengensystems (also einer Menge von Mengen, die jeweils Teilmengen ein und derselben Grundmenge – hier: $N$ – sind) auf. Ein solches Mengensystem von Koalitionen, welches auch Koalitionsfamilie genannt wird, (hier: $\{S_1,\dots ,S_k\}\subseteq 2^N\setminus \mathrm{\varnothing }$) bezeichnet man als ausgewogen, wenn es strikt positive Gewichtungsfaktoren (hier: ${\lambda }_1,\dots ,{\lambda }_k$) gibt, sodass für jeden Spieler $i\in N$ gilt, dass

$\sum _{j=1,\dots ,k:i\in S_j}{\lambda }_j=1$,

das heißt: Ein Mengensystem von Koalitionen ist dann ausgewogen, wenn für jeden Spieler gilt, dass sich die Gewichtungsfaktoren sämtlicher Koalitionen des Mengensystems, denen er selbst angehört, zu eins aufsummieren. Eine Interpretationsmöglichkeit hierfür besteht darin, sich die Gewichtungsfaktoren als Anteile am verfügbaren Zeitbudget vorzustellen; Wiese (2005) bezeichnet sie deshalb etwa auch als „Teilzeitfaktoren“. Man nehme an, dass jeder Spieler seine Zeit auf verschiedene Koalitionen aufteilen kann. Das Mengensystem ist in dieser Vorstellung gerade dann ausgewogen, wenn kein Spieler „Zeit verschenkt“ ($\sum _{j=1,\dots ,k:i\in S_j}{\lambda }_j<1$) oder mehr Zeit aufwendet, als ihm zur Verfügung steht ($\sum _{j=1,\dots ,k:i\in S_j}{\lambda }_j>1$), sondern sein gesamtes Zeitbudget auf die Koalitionen des Mengensystems aufteilt, denen er angehört. Es handelt sich mithin um eine Art Budgetrestriktion für das Zeitbudget. Damit nun eine Koalition $S_j$ für einen Zeitanteil ${\lambda }_j$ aktiv ist, müssen alle Mitglieder von $S_j$ aktiv sein. Sind sie dies, so rentiert die Koalition einen Payoff (Auszahlung) in Höhe von ${\lambda }_{j}v(S_j)$. Ein Spiel ist, mit anderen Worten, also gerade dann ausgewogen, dass die Spieler über keine alternative zulässige Zeitaufteilung verfügen, die ihnen einen höheren Gesamtpayoff als $v(N)$ einbringen würde.

Darüber hinaus beschreibt eine minimal balancierte Koalitionsfamilie ${𝔅}_{𝔪𝔦𝔫}$ eine balancierte Koalitionsfamilie $𝔅:=\{S_1,\dots ,S_k\}\subseteq 2^N\setminus \mathrm{\varnothing }$, in der keine echte Teilmenge balanciert ist. Eine minimal balancierte Koalitionsfamilie hat eindeutig bestimmte Gewichtungsfaktoren. Analog zum balancierten Spiel nennt man $(N,v)$ ein minimal balancierte Spiel, sofern für alle ${𝔅}_{𝔪𝔦𝔫}:=\{M_1,\dots ,M_l\}\subseteq 2^N\setminus \mathrm{\varnothing }$:

$\sum _{j=1}^l{\lambda }_{j}v(M_j)\le v(N)$ erfüllt ist.

Theorie des allgemeinen Gleichgewichts

Grundlagen

Betrachtet sei eine Ökonomie mit $n$ Gütern, in der es keinerlei Externalitäten gibt. Die Preise für diese Güter werden in einem Preisvektor $𝐩=(p_1,\dots ,p_n)$ zusammengefasst, wobei $𝐩\ne \mathrm{𝟎}$. In der Ökonomie gebe es weiter $I$ Konsumenten und $J$ Firmen, wobei für diese beiden Gruppen entsprechend die Indexmengen $ℐ=\{1,\dots ,I\}$ (die Menge aller Konsumenten) bzw. $𝒥=\{1,\dots ,J\}$ (die Menge aller Produzenten) definiert werden. Produzenten wie Konsumenten sind jeweils Preisnehmer. Betrachtet werden nun nacheinander Konsumenten und Produzenten, danach die anfängliche Ausstattung der Ökonomie:

• Das Konsumprofil einer Person $i\in ℐ$ ist ${𝐱}^i=(x_1^i,\dots ,x_n^i)\in {ℝ}_{+}^n$ – es gibt Auskunft, welche Menge Person $i$ von jedem der $n$ Güter konsumiert. Die Menge $X_i\subset {ℝ}_{+}^n$ erfasst alle möglichen Konsumprofile von $i$ (Konsummöglichkeitenmenge von $i$). Die Präferenzstruktur eines jeden Individuums $i\in ℐ$ findet wiederum in seiner Nutzenfunktion $u^i=u^i({𝐱}^i)\in ℝ$ Ausdruck.
• Die Produktion eines jeden Unternehmens $j\in 𝒥$ ist durch den Produktionsvektor ${𝐲}^j=(y_1^j,\dots ,y_n^j)\in {ℝ}^n$ gegeben; er gibt an, wie viel Unternehmen $j$ von jedem der $n$ Güter produziert. Durch technologische Beschränkungen sind allerdings nur solche Produktionspläne möglich, die in einer Menge $Y_j\subset {ℝ}^J$ enthalten sind (Produktionsmöglichkeitenmenge von $j$).
• Die anfänglichen Bestände an den jeweiligen Gütern sind durch einen Ausstattungsvektor $𝐞=(e_1,\dots ,e_n)\in {ℝ}_{+}^n$ gegeben.

Mit den vereinbarten Definitionen hinsichtlich der Präferenzstruktur der Individuen, der technologischen Kapazitäten der Produzenten und der Ressourcenbestände lässt sich eine Ökonomie durch das Tupel

$ℰ=[{(X_i,u^i)}_{i\in ℐ},{\left(Y_j\right)}_{j\in 𝒥},𝐞]$

charakterisieren. In einer Wettbewerbsökonomie stehen sowohl die Anfangsausstattung als auch die Unternehmen im Eigentum der Konsumenten. Man vereinbart entsprechend ${𝐞}^i=(e_1^i,\dots ,e_n^i)\in {ℝ}_{+}^n$ als die Ausstattung einer Person $i\in ℐ$ (bezüglich aller Güter). Der von Konsument $i$ gehaltene Anteil an den Gewinnen eines jeden Unternehmens betrage ${\mathit{\theta }}^i=({\theta }_1^i,\dots ,{\theta }_J^i)\in {ℝ}^J$. Entsprechend den Voraussetzungen ist $𝐞=\sum _{i\in ℐ}{𝐞}^i$ und $\sum _{i\in ℐ}{\mathit{\theta }}^i=\mathrm{𝟏}$.

Betrachte man eine Wettbewerbsökonomie. Dann bezeichnet man ein Tupel $[{\left({𝐱}^{i*}\right)}_{i\in ℐ},{\left({𝐲}^{j*}\right)}_{j\in 𝒥},{𝐩}^{*}]$ als Walrasianisches Gleichgewicht dieser Ökonomie, wenn gilt:

1. (Gewinnmaximierung:) Jedes Unternehmen maximiert, gegeben die gleichgewichtigen Marktpreise, seinen Gewinn, das heißt für alle $j\in 𝒥$ gilt: ${𝐩}^{*}\cdot {𝐲}^j\le {𝐩}^{*}\cdot {𝐲}^{j*}$ für alle ${𝐲}^j$.
2. (Nutzenmaximierung:) Jeder Konsument maximiert seinen Nutzen, das heißt für alle $i\in ℐ$ gilt, dass ${𝐱}^{i*}$ die Nutzenfunktion $u^i({𝐱}^i)$ unter Wahrung der Budgetbedingung ${𝐩}^{*}\cdot {𝐱}^i\le {𝐩}^{*}\cdot {𝐞}^i+{\sum }_{j=1}^J{\theta }_j^i({𝐩}^{*}\cdot {𝐲}^{j*})$ maximiert.
3. (Markträumung:) Für jedes Gut $k$ gilt: ${\sum }_{i=1}^I{x}_k^{i*}=e_k+{\sum }_{j=1}^J{y}_k^{j*}$.

Betrachtet man statt einer Wettbewerbsökonomie eine reine Tauschwirtschaft (in der es keine Produktion gibt, sondern nur durch Tausch die Anfangsausstattung umverteilt wird), so liegt dort ein Walrasianisches Gleichgewicht vor, wenn gilt:

1. (Nutzenmaximierung:) Jeder Konsument maximiert seinen Nutzen, das heißt für alle $i\in ℐ$ gilt, dass ${𝐱}^{i*}$ die Nutzenfunktion $u^i({𝐱}^i)$ unter Wahrung der Budgetbedingung ${𝐩}^{*}\cdot {𝐱}^i\le {𝐩}^{*}\cdot {𝐞}^i$ maximiert.
2. (Markträumung:) Für jedes Gut $k$ gilt: ${\sum }_{i=1}^I{x}_k^{i*}=e_k$

Kern einer Ökonomie

Das spieltheoretische Konzept des Kerns lässt sich in der Theorie des allgemeinen Gleichgewichts anwenden. Eine gegebene (Konsum)allokation ist blockierbar, wenn es eine Koalition von Konsumenten gibt, die eine Alternativallokation erzwingen kann, durch welche – im Vergleich zur Ausgangsallokation – kein Koalitionsmitglied schlechtergestellt und mindestens eines strikt bessergestellt wird. Die Menge aller nicht-blockierbaren (Konsum)allokationen bezeichnet man als Kern der Ökonomie. Kernallokationen sind also Allokationen mit der Eigenschaft, dass sich keine Gruppe von Konsumenten von der Ökonomie profitabel „abspalten“ kann, um fortan nur noch unter sich Handel zu treiben.

Formal: Sei im einfachsten Fall $ℰ$ eine reine Tauschwirtschaft. Dann ist ${\left({𝐱}^i\right)}_{i\in ℐ}$ eine Allokation, die man wiederum als zulässig (in $ℰ$) bezeichnet, wenn $\sum _{i\in ℐ}{𝐱}^i\le 𝐞$. Sei weiter $S\subseteq ℐ$ eine beliebige Koalition. Definiere nun $X^S$ als die Menge aller koalitionsinternen Konsumprofile mit der Eigenschaft, dass die Koalitionsmitglieder von keinem Gut mehr konsumieren als sie insgesamt als Ausstattung in die Koalition eingebracht haben:

$X^S:=\{{\left({𝐱}^s\right)}_{s\in S}\in {\left({ℝ}_{+}^n\right)}^{|S|}|\sum _{s\in S}{𝐱}^s\le \sum _{s\in S}{𝐞}^s\}$

Walrasianisches Gleichgewicht und Kern

Die umgekehrte Implikation gilt grundsätzlich nicht: Nicht jede Kernallokation ist auch eine Walrasianische Gleichgewichtsallokation. Allerdings kann man zeigen, dass dies für hinreichend große Ökonomien (das heißt solche mit hinreichend vielen Konsumenten) der Fall ist (Satz von Debreu-Scarf).

Literatur

• Rodica Branzei, Dinko Dimitrov und Stef Tijs: Models in Cooperative Game Theory. 2. Auflage. Springer, Berlin u. 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 u. a. 2010, ISBN 978-3-642-05281-1.
• Yakar Kannai: The Core and Balancedness. In: Robert J. Aumann und Sergiu Hart (Hrsg.): Handbook of Game Theory with Economic Applications. 1. Elsevier, Amsterdam 1992, ISBN 0-444-88098-4, S. 355–395, Vorlage:DOI.
• Michael Maschler, Eilon Solan, Shmuel Zamir: Game Theory, 2nd Edition. Cambridge University Press, Cambridge 2020, ISBN 978-1-108-49345-1.
• Vladimir Mazalov: Mathematical Game Theory and Applications. Wiley, Chicester 2014, ISBN 978-1-118-89962-5.
• David Müller: Investitionscontrolling: Entscheidungsfindung bei Investitionen II: Entscheidungstheorie. 3. Aufl. Springer Gabler, Berlin u. a. 2022, ISBN 978-3-658-36596-7.
• Bezalel Peleg und Peter Sudhölter: Introduction to The Theory of Cooperative Games. 2. Auflage. Springer, Berlin u. a. 2007, ISBN 978-3-540-72944-0.
• Hans Peters: Game Theory, A Multi-Leveled Approach, Second Edition. Springer, Berlin u. a. 2015, ISBN 3-662-46949-9.
• Lloyd S. Shapley: On balanced sets and cores. In: Naval Research Logistics Quarterly, Volume 14, Issue 4, 1967, Vorlage:DOI, S. 453–460.
• Harald Wiese: Kooperative Spieltheorie. Oldenbourg, München 2005, ISBN 3-486-57745-X, doi:10.1524/9783486837469.

Ökonomische Anwendung

• David M. Kreps: Microeconomic Foundations I. Choice and Competitive Markets. Princeton University Press, Princeton 2012, ISBN 978-0-691-15583-8. [Zum Kern: Kapitel 15]
• James C. Moore: General equilibrium and welfare economics. An introduction. Springer, Berlin u. a. 2007, ISBN 978-3-540-31407-3 (auch online: Vorlage:DOI). [Zum Kern: Kapitel 11]
• Lester G. Telser: The Core Theory in Economics. Problems and Solutions. Routledge, Oxon 2007, ISBN 978-0-415-70144-0.