Nicht-kooperative Spiele und das Nash-Gleichgewicht

Inhaltsverzeichnis

1 Einleitung

2 Terminologie und Definitionen

3 Existenz eines Gleichgewichts
3.1 Existenzbeweis unter Verwendung des Fixpunktsatzes von Brouwer
3.2 Existenzbeweis unter Verwendung des Fixpunktsatzes von Kaku-tani

4 Nash-Equilibrium in streng kompetitiven Spielen

5 Einblick in kooperative Spiele

6 Schlusswort und Ausblick

1 Einleitung

Die Spieltheorie (engl. game theory) ist ein Teilgebiet der Mathematik, das sich mit der Modellierung und Untersuchung von Gesellschaftsspielen, von im wei­testen Sinn gesellschaftsspielähnlichen Interaktionssystemen sowie mit den in solchen Systemen eingesetzten Strategien beschäftigt. Dabei ist die Spieltheo­rie weniger eine zusammenhängende Theorie als vielmehr ein Instrument zur Analyse von strategischen Entscheidungssituationen. Lösungen von Spielen, die sich dadurch auszeichnen, dass die Spieler ihre Strategieentscheidungen nicht revidieren wollen wenn ihnen die Lösung empfohlen wird, werden als Gleichge­wicht bezeichnet. Im Rahmen dieser Arbeit soll insbesondere auf ein allgemein akzeptiertes Konzept zur Lösung von nicht-kooperativen Spielen eingegangen werden, das Nash-Gleichgewicht. In einem weiteren Schritt wird genauer auf ei­ne oft verwendete Art von Spielen, die sogenannten streng kompetitiven Spiele oder auch Nullsummenspiele, eingegangen und kurz angedeutet, wie die Theorie der nicht-kooperativen Spiele auf jene der kooperativen erweitert werden kann.

2 Terminologie und Definitionen

Wir präsentieren hier die Basiskonzepte wie auch die notwendigen Definitionen zum allgemeinen Verständnis der Spieltheorie. Die Herleitung der Idee und der Lösung von nicht-kooperativen Spielen folgen daraus implizit.

Definition 1 Ein strategisches n-Personen Spiel G kann als Tripel

Abbildung in dieser Leseprobe nicht enthalten

geschrieben werden. Dabei setzt sich das Spiel aus n Spielern zusammen, wobei jeder Spieler i über eine endliche Anzahl von reinen Strategien nia 2 Hi verfügt а — 1, 2,m. Die nia können in einer Menge Hi C Rm, der Strategiemenge des Spielers i, zusammengefasst werden. Wir notieren mit Xi2nHi — Hi x H2 x ... x Hn die entsprechende Produktmenge beziehungsweise das kartesische Produkt aus den Strategiemengen der einzelnen Spieler. Weiters wird jedem Spieler i eine stetige, quasikonkave¹ Auszahlungsfunktion ai : Xi2nHi ! R zugeordnet, welche die n -Tupel der Strategien nach R abbildet.²

Implizit wird in dieser Definition angenommen, dass sich die gewählten Strate­gien in Spielausgängen niederschlagen, die dann zu verschiedenen Auszahlungen führen. Für eine explizite Modellierung kann der direkte Einbau von Spielaus­gängen hilfreich sein.

Definition 2 (gemischte Strategie oder Randomisierung) Eine gemisch­te Strategie Si eines Spielers i ist eine Kombination seiner reinen Strategien Wia 2 Di und wird ebenfalls als ein Element von D betrachtet. Wir schreiben Si = ΣCiaría 2 Di mit βία > 0 und Σcia = 1. Die gemischten Strategien si können also als Linearkombinationen angesehen werden. Wir unterstellen von nun an, dass die Menge Di der Si eine nicht-leere, kompakte und konvexe Teil­menge des Euklidischen Raumes ist.³

Bemerkung 3 Wir bemerken, dass eine pure Strategie Wia auch immer als eine gemische Strategie Si geschrieben werden kann.

Beispiel 4 Ein Unternehmen i kann als Output die Menge жц = 0 und Wi2 = M produzieren sowie jede Menge zwischen 0 und M: 0 6 Si 6 M. Die Strategie­menge Di = [0, M] ist konvex, weil jede konvexe Kombination zwischen 0 und M, das heisst AM + (1 — λ)0 = AM mit 0 6 λ 6 1, produziert werden kann. Da die Menge nach oben und unten beschränkt ist und 0 und M enthalten sind, ist Di auch kompakt.

Die allgemeine Formulierung und die hohe Abstraktion erlauben es, diese Defini­tion in einer Reihe von Situationen anzuwenden. Ein Spieler kann ein Individu­um sein oder eine beliebige andere Entscheidungseinheit, wie zum Beispiel eine Regierung, ein Verwaltungsrat, eine marxistische Revolutionsarmee, ja sogar so­gar eine Blume oder ein Tier. Allerdings sind die Anwendungsmöglichkeiten da­durch beschränkt, dass jedem Spieler eine Auszahlungsfunktion zugeordnet wer­den muss. Als Auszahlungsfunktionen oder Präferenzrelationen können jedoch bereits die einfachen Gefühle eines Spieler bezüglich verschiedener Endzustände oder im Falle eines nicht-menschlichen Organismus die Wahrscheinlichkeit des reproduktiven Erfolgs verwendet werden.

Selbstverständlich bevorzugt Spieler i Strategie Wi1 gegenüber Wis falls

Abbildung in dieser Leseprobe nicht enthalten

bei gegebenen Wja für j = 1, ...,i — 1,i + 1,...,n. Weiters ist es einfach ein­zusehen, dass ai problemlos auf gemischte Strategien erweitert werden kann. ai ist dann ebenfalls linear in den gemischten Strategien (vlg. Ritzberger, 2003). Abbildung in dieser Leseprobe nicht enthalten

dann ist Abbildung in dieser Leseprobe nicht enthalten

So ein n-Tupel s kann als Punkt in einem Vektorraum angesehen werden - dem Produktraum der Vektorräume, die die gemischten Strategien enthalten. Weiters führen wir die Substitutionsnotation

Abbildung in dieser Leseprobe nicht enthalten

ein. Nachfolgend geben wir mehrere verschiedene Kriterien für ein Gleichgewicht (vgl. Nash, 1951).

Definition 5 (Gleichgewicht) Ein n-Tupel s ist genau dann ein Gleichge­wicht von G —< n, (Πί) i2n, (ai)i2n > falls für alle Spieler i gilt:

Abbildung in dieser Leseprobe nicht enthalten

Wenn s — (s1, S2, ..., sn) und Si die pure Strategie nia benutzt, also a¡a > 0, sagen wir, dass s die pure Strategie nia benutzt. Wegen der Linearität von

ai(s1, s2, ..., sn) in si gilt:

Abbildung in dieser Leseprobe nicht enthalten

Definieren wir aia(s) : — ai(s;wia), so ergibt sich trivialerweise folgende notwen­dige und hinreichende Bedingung, dass s ein Equilibrium ist:

Abbildung in dieser Leseprobe nicht enthalten

Wenn s — (s1, S2, ..., sn) und Si — Σciaría, dann ist afis) —Σciaaia(s). Damit also die Formulierung (3) hält, muss a¡a — 0 sein, falls aia(s) < max(aiß(s)). Dies ist gleichbedeutend zu sagen, dass s die pure Strategie nia nicht benutzt, es sei denn, es handelt sich um eine optimale pure Strategie für Spieler i.Wir schreiben also

Abbildung in dieser Leseprobe nicht enthalten

Es handelt sich um eine weitere notwendige und hinreichende Bedingung für ein Gleichgewicht.

In Worten: Ein Gleichgewicht ist ein n-Tupel s so, dass die gewählte Strate­gie eines jeden Spielers seine Auszahlung maximiert bei gegebenen Strategi­en der anderen Spieler. Somit ist jede Strategie der Spieler optimal gegen die Strategien der anderen. Nochmals aus anderer Perspektive formuliert: Ausge­hend von einem Equilibrium, besteht für keinen Spieler ein Anreiz, von seiner Gleichgewichtsstrategie abzuweichen. Dieses fundamentale Konzept einer Spiel­lösung wird heute gemeinhin als Nash-Gleichgewicht, Nash-Equilibrium oder Nash-Lösung bezeichnet.

Eine gleichwertige Definition des Nash-Gleichgewichts, die gewöhnlicherweise in der neueren Literatur angeführt wird, lautet wie folgt:

Definition 6 Abbildung in dieser Leseprobe nicht enthalten ein strategisches Spiel. Wir de­finieren s-i als die Strategien der Spieler n\i und schreiben dementsprechend auch [Abbildung in dieser Leseprobe nicht enthalten] (Strategieraum ohne Strategien des Spielers i). Weiter sei

Abbildung in dieser Leseprobe nicht enthalten

die Menge der besten Strategien („Funktion der besten Antworten“) von Spieler i bei gegebenen s-i. Ein Nash-Equilibrium ist eine Strategie s* für welche

Abbildung in dieser Leseprobe nicht enthalten

Abbildung in dieser Leseprobe nicht enthalten

Definition (6) gibt eine (nicht notwendigerweise effiziente) Methode ein Nash- Gleichgewicht mit Hilfe der „Funktion der besten Antworten“ zu finden.

Beispiel 7 Wir betrachten zwei identische Unternehmen die ein homogenes Gut produzieren, sich um die Nachfrage konkurrieren und sich ihrer wechselsei­tigen Beziehung bewusst sind („Cournot-Duopol“). Das Gewinnoptimierungs­problem für i = 1, 2 laute

Abbildung in dieser Leseprobe nicht enthalten

wobei si Ausbringungsmengen⁴, p(.) die Preisfunktion am Markt und Ci (si) die

[...]

¹ Sei D C Rn konvex und f : D C Rn ! R. Wir sagen, dass f quasikonkav ist, falls die Menge fx £ D : f (x) > ag konvex ist für alle a £ R. f ist quasikonvex, falls fx G D : f (x) 6 ag konvex ist für alle a £ R.

² Anstelle von Auszahlungsfunktionen sprechen manche Autoren (vgl. ÜSBÜRNE UND Ru­BINSTEIN, 1994) auch von Präferenzrelationen. Präferenzrelationen können als eine Verallge­meinerung von Auszahlungsfunktionen angesehen werden.

³ Die Hauptidee der Einführung gemischter Strategien ist es, die diskreten puren Strategi­en zu „stetig“ zu machen. RlTZBERGER (2003) erwähnt ebenfalls, dass gemischte Strategien als Wahrscheinlichkeitsverteilungsfunktionen oder Verteilungsfunktion von puren Strategien verstanden werden können.

⁴ Betrachte Si zum Beispiel als gemischte Strategie der zwei reinen Strategien кц = lim s(p) n - 0 und Ki2 = lim s(p), wobei s(p) := p_1(s). n - -1