Kern (Spieltheorie)

Konzept für kooperative Spiele

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

Bearbeiten

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:[1] Sei   ein kooperatives Spiel mit transferierbarem Nutzen, wobei   die Menge der Spieler bezeichnet und  [2] die Koalitionsfunktion,  . Eine Allokation   ist eine Zuteilung (englisch imputation), wenn gilt:

  1.   und
  2.   für alle  .

Eine Zuteilung ist eine Kernallokation, wenn

  1.   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[3]) 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.[4] 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

Bearbeiten
Koalitionsfunktion des (Bei-)Spiels[5]
                 
                 

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.[6]

Eigenschaften

Bearbeiten

Vereinbarungen

Bearbeiten

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

Bearbeiten

Sei   der Kern eines Spiels  ,  .

a) Der Kern ist konvex und kompakt.[7]
b) Sei   der Kern eines von   verschiedenen Spiels  ,  , das zu   strategisch äquivalent ist. Dann geht der Kern wie folgt aus dem Kern des anderen Spiels hervor:[8]
 
mit geeignetem  .
c) Kernlösungen sind anonym, symmetrisch, Pareto-optimal und superadditiv.[9]

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).[10] 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

Bearbeiten

Satz von Bondareva und Shapley (Bondareva 1963[11], Shapley 1967[12]):[13] 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[14] 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[15], (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;[16] 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.[17] 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.[18]

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  :

  erfüllt ist.[19]

Theorie des allgemeinen Gleichgewichts

Bearbeiten

Grundlagen

Bearbeiten

Betrachtet sei eine Ökonomie mit   Gütern, in der es keinerlei Externalitäten gibt.[20] 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

Bearbeiten

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:[21] 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

Bearbeiten

Theorem:[22] Sei   ein walrasianisches Gleichgewicht einer reinen Tauschwirtschaft   und seien die Präferenzen aller Konsumenten   lokal nicht gesättigt[23] (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).[24]

Erweiterungen

Bearbeiten

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

Bearbeiten
  • 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.
Ö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: 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

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