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 Spieler (im Folgenden: Payoff) wird durch einen n-Vektor (Zustand) beschrieben, den man – insbesondere mit Blick auf ökonomische Anwendungen – auch als Allokation bezeichnet.

Definition: Sei ein kooperatives Spiel mit transferierbarem Nutzen, wobei die Menge der Spieler bezeichnet und die Koalitionsfunktion, . Eine Allokation ist eine Zuteilung (englisch imputation), wenn gilt:

1. und
2. für alle .

Eine Zuteilung ist eine Kernallokation, wenn

3. für alle Koalitionen .

Die Menge aller Kernallokationen von bezeichnet man als Kern des Spiels, . Kurzum:

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 , wobei die Menge der Zuteilungen von ist.

Beispiel

Koalitionsfunktion des (Bei-)Spiels

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

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

.

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 ist die Menge der Koalitionsfunktionen für kooperative Spiele mit transferierbarem Nutzen und der Spielermenge .
• Für eine Koalition ist der definiert als der -dimensionale euklidische Raum, der durch die an partizipierenden Spieler aufgespannt wird.
• Sei eine Menge, ein Skalar und . Dann ist die Menge definiert durch und die Menge durch .

Grundlegende Beschaffenheit

Sei der Kern eines Spiels , .

mit geeignetem .

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 und als strategisch äquivalent, wenn es eine Konstante und einen Vektor gibt, sodass für jede Koalition gilt, dass , 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 () bzw. fixe Kosten hat () und dass sich die Einheit ändert, in der der Payoff ausbezahlt wird ( 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

Satz von Bondareva und Shapley (Bondareva 1963, Shapley 1967): Sei ein kooperatives Spiel, . Dann sind die folgenden Aussagen äquivalent:

1. ist nichtleer.
2. ist ein ausgewogenes (balanciertes) Spiel, das heißt für jedes ausgewogene (balancierte) Mengensystem von Koalitionen aus mit den zugehörigen Gewichtungsfaktoren gilt die Ungleichung

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: – sind) auf. Ein solches Mengensystem von Koalitionen, welches auch Koalitionsfamilie genannt wird, (hier: ) bezeichnet man als ausgewogen, wenn es strikt positive Gewichtungsfaktoren (hier: ) gibt, sodass für jeden Spieler gilt, dass

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“ () oder mehr Zeit aufwendet, als ihm zur Verfügung steht (), 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 für einen Zeitanteil aktiv ist, müssen alle Mitglieder von aktiv sein. Sind sie dies, so rentiert die Koalition einen Payoff (Auszahlung) in Höhe von . 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 einbringen würde.

Darüber hinaus beschreibt eine minimal balancierte Koalitionsfamilie eine balancierte Koalitionsfamilie , in der keine echte Teilmenge balanciert ist. Eine minimal balancierte Koalitionsfamilie hat eindeutig bestimmte Gewichtungsfaktoren. Analog zum balancierten Spiel nennt man ein minimal balancierte Spiel, sofern für alle :

Theorie des allgemeinen Gleichgewichts

Grundlagen

Betrachtet sei eine Ökonomie mit Gütern, in der es keinerlei Externalitäten gibt. Die Preise für diese Güter werden in einem Preisvektor zusammengefasst, wobei . In der Ökonomie gebe es weiter Konsumenten und Firmen, wobei für diese beiden Gruppen entsprechend die Indexmengen (die Menge aller Konsumenten) bzw. (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 ist – es gibt Auskunft, welche Menge Person von jedem der Güter konsumiert. Die Menge erfasst alle möglichen Konsumprofile von (Konsummöglichkeitenmenge von ). Die Präferenzstruktur eines jeden Individuums findet wiederum in seiner Nutzenfunktion Ausdruck.
• Die Produktion eines jeden Unternehmens ist durch den Produktionsvektor gegeben; er gibt an, wie viel Unternehmen von jedem der Güter produziert. Durch technologische Beschränkungen sind allerdings nur solche Produktionspläne möglich, die in einer Menge enthalten sind (Produktionsmöglichkeitenmenge von ).
• Die anfänglichen Bestände an den jeweiligen Gütern sind durch einen Ausstattungsvektor 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

charakterisieren. In einer Wettbewerbsökonomie stehen sowohl die Anfangsausstattung als auch die Unternehmen im Eigentum der Konsumenten. Man vereinbart entsprechend als die Ausstattung einer Person (bezüglich aller Güter). Der von Konsument gehaltene Anteil an den Gewinnen eines jeden Unternehmens betrage . Entsprechend den Voraussetzungen ist und .

Betrachte man eine Wettbewerbsökonomie. Dann bezeichnet man ein Tupel als Walrasianisches Gleichgewicht dieser Ökonomie, wenn gilt:

1. (Gewinnmaximierung:) Jedes Unternehmen maximiert, gegeben die gleichgewichtigen Marktpreise, seinen Gewinn, das heißt für alle gilt: für alle .
2. (Nutzenmaximierung:) Jeder Konsument maximiert seinen Nutzen, das heißt für alle gilt, dass die Nutzenfunktion unter Wahrung der Budgetbedingung maximiert.
3. (Markträumung:) Für jedes Gut gilt: .

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 gilt, dass die Nutzenfunktion unter Wahrung der Budgetbedingung maximiert.
2. (Markträumung:) Für jedes Gut gilt:

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 eine Allokation, die man wiederum als zulässig (in ) bezeichnet, wenn . Sei weiter eine beliebige Koalition. Definiere nun 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:

Definition: Der Kern einer Ökonomie ist die Menge aller Allokationen , für die keine Koalition mit einer zugehörigen koalitionsinternen Allokation existiert, die die folgenden Eigenschaften aufweist:

1. (Zulässigkeit in :)
2. (Pareto-Verbesserung für :) für alle und für irgendein .

Walrasianisches Gleichgewicht und Kern

Theorem: Sei ein walrasianisches Gleichgewicht einer reinen Tauschwirtschaft und seien die Präferenzen aller Konsumenten lokal nicht gesättigt (im Spezialfall: seien die Nutzenfunktionen aller Konsumenten streng monoton). Dann liegt im Kern von .

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).

Erweiterungen

Definition: Sei ein kooperatives Spiel mit transferierbarem Nutzen, wobei die Menge der Spieler bezeichnet und die Koalitionsfunktion, . Dann bezeichnet man die Menge

als strikten -Kern.

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, doi:10.1016/S1574-0005(05)80015-3.
• 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, doi:10.1002/nav.3800140404, S. 453–460.
• Harald Wiese: Kooperative Spieltheorie. Oldenbourg, München 2005, ISBN 3-486-57745-X, doi:10.1524/9783486837469.

• 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: doi:10.1007/978-3-540-32223-8). [Zum Kern: Kapitel 11]
• Lester G. Telser: The Core Theory in Economics. Problems and Solutions. Routledge, Oxon 2007, ISBN 978-0-415-70144-0.

Anmerkungen

1. Vgl. Maschler et al. 2020, S. 724, 736; Müller 2022, S. 491; Peters 2015, S. 154; Peleg/Sudhölter 2007, S. 19 f.; Gilles 2010, S. 19, 30; Driessen 1988, S. 13 f., 20.
2. Die Menge ist die Potenzmenge von , also die Menge aller Teilmengen von . Beachte, dass die leere Menge () ebenfalls eine Teilmenge ist.
3. Vgl. Wiese 2005, S. 144.
4. Vgl. Peleg/Sudhölter 2007, S. 20.
5. Vgl. Müller 2022, S. 479.
6. Vgl. Müller 2022, S. 492.
7. Vgl., auch zum Beweis, Maschler et al. 2020, S. 736.
8. Vgl., auch zum Beweis, Maschler et al. 2020, S. 739.
9. Vgl. Peleg/Sudhölter 2007, S. 20 f.
10. Dazu siehe etwa Branzei et al. 2008, S. 8.
11. Olga N. Bondareva: Nekotoriye primeneniya metodov lineynogo programmirovaniya k teorii Kooperativnikh igr. In: Problemy Kybernetiki. 10, 1963, S. 119–139 [in russischer Sprache]. Englische Übersetzung unter dem Titel Some applications of linear programming methods to the theory of cooperative games abgedruckt in Selected Russian Papers on Game Theory, 1959–1965. Princeton University, Princeton 1968, S. 79–114, auch princeton.edu (PDF; 3,3 MB).
12. Lloyd S. Shapley: On balanced sets and cores. In: Naval Research Logistics Quarterly. 14, 1967, S. 453–460, doi:10.1002/nav.3800140404.
13. Vgl., jeweils auch zum Beweis, Kannai 1992, S. 359 f.; Maschler et al. 2020, S. 744 ff.; Peleg/Sudhölter 2007, S. 28 f.
14. Vgl. Gilles 2010, S. 37; Peleg/Sudhölter 2007, S. 28.
15. Vgl. Müller 2022, S. 494.
16. Vgl. Maschler et al. 2020, S. 742 f.
17. Ähnlich Martin J. Osborne und Ariel Rubinstein: A course in game theory. MIT Press, Cambridge 1994, ISBN 0-262-65040-1, S. 262.
18. Vgl. Martin J. Osborne und Ariel Rubinstein: A course in game theory. MIT Press, Cambridge 1994, ISBN 0-262-65040-1, S. 262.
19. Vgl. Müller 2022, S. 479; Shapley 1967, S. 453.
20. Der nachstehend summarisch wiedergegebene Aufbau der Ökonomie folgt weitgehend Andreu Mas-Colell, Michael Whinston, Jerry Green: Microeconomic Theory. Oxford University Press, Oxford 1995, ISBN 0-195-07340-1, insbesondere S. 546 f. und teilweise Moore 2007, S. 131 ff, 191 ff.
21. Vgl. etwa Kreps 2012, S. 366 f.
22. Vgl. Kreps 2012, S. 366 ff.
23. Man bezeichnet eine Präferenzordnung als lokal nicht gesättigt, wenn für beliebiges und für jede -Umgebung um ein existiert, für das gilt: (siehe auch Präferenzordnung).
24. Vgl. Kreps 2012, S. 370 ff.