Zusammenfassung

Eine dynamische Methode zur Berechnung von Nash-Gleichgewichten in nichtkooperativen n-Personen-Spielen. Zu diesem Zweck werden stetige Abbildungen auf dem kartesischen Produkt der Strategiemengen der Spieler in sich selbst konstruiert, so dass die Fixpunkte dieser Abbildungen Nash-Gleichgewichte sind. Dies f ¨ uhrt zu

einer Iterationsmethode zur Berechnung von Fixpunkten, die zu Nash-Gleichgewichten f ¨ uhrt, falls die Iteration konvergiert. Als Spezialf¨ alle werden Bi-Matrix- und Evolutions- Spiele betrachtet.

Inhaltsverzeichnis

1  Grundlegende Begriffe und Notationen  8

1.1  Einf uhrung  8

1.2  Notation  12

2  Nash-Gleichgewichte als Fixpunkte von Abbildungen  13

2.1  Konstruktion der Abbildung  13

2.2  spezielle Strategiemengen  21

3  Bi-Matrix-Spiele  25

3.1  Symmetrische Bi-Matrix-Spiele  31

4  Evolutionsspiele  36

4.1  Einf uhrung  36

4.2  Dynamische Behandlung  37

4.3  Evolutionsstabile Nash-Gleichgewichte  43

5  Appendix  46

5.1  Allgemeine Erl auterungen  46

5.2  Fixpunkts atze  47

5.3  Zur Stabilit atstheorie  48

5.4  Quellcode  49

Bibliogra  fie  51

5

Abbildungsverzeichnis   

1  Beispiel (2.3), Startpunkt (0 0)  16

2  Beispiel (2 3), Startpunkt (12 34)  18

6

Einf ¨ uhrung

Diese Diplomarbeit besch¨ aftigt sich mit der Berechnung von Nash-Gleichgewichten in nicht-kooperativen n-Personen-Spielen. Das Nash - Gleichgewicht ist ein zentraler Begriff in der mathematischen Spieltheorie. Es beschreibt in nicht kooperativen Spielen einen strategischen Gleichgewichtszustand, von dem ausgehend kein einzelner Spieler f ¨ ur sich einen Vorteil erzielen kann. Definition und Existenzbeweis des Nash-Gleichgewichtes gehen auf die 1950 ver ¨

Forbes Nash Jr. zur ¨ uck. Die eigentliche Spieltheorie begann im Jahr 1928 mit der Arbeit “Zur Theorie der Gesellschaftsspiele”von John von Neumann. Schnell erkannte John von Neumann die Anwendbarkeit seiner Ans¨ atze zur Analyse wirtschaftlicher Fragestellungen. Dies f ¨ uhrte, zusammen mit dem Wirtschaftswissenschaftler Oskar Morgenstern, zu dem Buch “Theory of Games and Economic Behavior”. Inzwischen findet sich die Spieltheorie in vielen Bereichen wieder. Besonders im Operations Research, den Wirtschaftswissenschaften, in Teilbereichen der Rechtswissenschaften, in der Politikwissenschaft, der Soziologie, der Psychologie, der Informatik und der Biologie findet die Spieltheorie Anwendung.

Im ersten Kapitel werden grundlegende Begriffe der Spieltheorie eingef ¨ uhrt und defi-

niert, sowie erste Resultate vorgestellt. Insbesondere wird hier auf die Definition des Nash - Gleichgewichtes eingegangen. Das Kapitel liefert alles Grundwissen, was zum Verst¨ andnis der folgenden Kapitel ben ¨

im sp¨ ateren Verlauf zur ¨ uckgegriffen wird.

Das zweite Kapitel besch¨ aftigt sich mit der eigentlichen dynamischen Berechnung von Nash-Gleichgewichten. Hier werden Abildungen definiert, deren Fixpunkte Nash-Gleichgewichte des Ausgangsspiels sind. Hierzu werden die Definition des Nash -Gleichgewichtes sowie Eigenschaften der Strategiemengen und der Auszahlungsfunktionen zu Hilfe genommen.

Im dritten Kapitel werden die Resultate aus dem zweiten Kapitel auf Bi-Matrix-Spiele angewendet, also auf bestimmte 2-Personen-Spiele. Hier werden Beispiele und bestimmte Eigenschaften der Strategiemengen betrachtet.

Im vierten Kapitel werden Evolutions-Spiele betrachtet. Diese lassen sich als 1-Personen-Spiele interpretieren und somit lassen sich die Resultate aus dem zweiten Kapitel auch hier anwenden. Außerdem wird der Begriff der Evolutions-Stabilit¨ at studiert.

7

Danksagung

An dieser Stelle m ¨ ochte ich gerne all jenen danken, die am Gelingen dieser Diplomarbeit maßgeblich beteiligt waren: Zuallererst Herrn Professor Werner Krabs, der nicht m ¨ ude wurde, meine vielen Fragen zu diskutieren und mir stets wertvolle Anregungen geben konnte. Insbesondere in der Schlussphase der Arbeit hat er sehr viel Zeit

investiert, um mir detailliert Feedback ¨ uber den Status der Arbeit zu geben und viele Vorschl¨ age zur Verbesserung der Darstellung gemacht, wof ¨ bin. Außerdem gilt Christiane Schulze, Tina Felber und Hannes Meinlschmidt mein Dank f ¨ ur ausf ¨ uhrliches Korrekturlesen, Hinweise zum Design und f ¨ ur ausf ¨ uhrliche fachliche Diskussionen.

Meinen Eltern danke ich daf ¨ dadurch erst erm ¨ oglicht haben.

Dank gilt auch den Betreibern und den Nutzern der Webseiten wikipedia.com und dict.leo.org, ohne die ich mir effizientes Arbeiten heute nicht mehr vorstellen k ¨ onnte.

1 Grundlegende Begriffe und Notationen

1.1 Einf ¨ uhrung

Hier wird mit Hilfe von [Kra04] eine Einf ¨ uhrung in die spieltheoretische Behandlung

von n-Personen Spielen gegeben. Außerdem werden Begriffe und Schreibweisen eingef ¨ uhrt, die in den n¨ achsten Kapiteln ben ¨ otigt werden.

Definition 1.1. Ein n-Personen Spiel Γ f ¨ ur n ≥ 2 besteht aus einem n-Tupel (S 1 , . . . , S n )

nichtleerer Mengen S i ⊆ R m i , i = 1 , . . . ,n den Strategiemengen, und einem n-Tupel (Φ 1 ,. . . , Φ n ) reellwertiger Funktionen Φ i : S → R, i = 1, . . . , n auf dem kartesischen Produkt S = S 1 × . . . × S n der Strategiemengen, den Auszahlungsfunktionen.

In dieser Definition interpretiert man die nichtleeren Mengen S i als Strategiemengen der Spieler i und Φ i (s 1 ,. . . , s n ) als Auszahlung an den Spieler i, wenn jeder Spieler j eine Strategie s j ∈ S j f ¨ ur j = 1, . . . , n w¨ ahlt. Rationale Spieler werden in jeder Situation

versuchen ihre Auszahlung Φ i (s 1 ,. . . , s n ) so groß wie m ¨ Regel aber nicht simultan m ¨ f ¨ ur alle Spieler in einem gewissen Sinne optimal ist.

Dies f ¨ uhrt zur folgenden Definition:

Definition 1.2. Ein Strategien-n-Tupel (ˆ s 1 , . . . , ˆ

ur alle i = 1, . . . , n und f ¨ ur alle s i ∈ S i gilt: wenn f ¨

Φ i (ˆ s 1 , . . . , ˆ s n ) ≥ Φ i (ˆ s 1 , . . . , ˆ s i−1 , s i , ˆ s i+1 , . . . , ˆ s n ) (1)

Ein Nash-Gleichgewicht ist ein Strategientupel derart, dass ein Abweichen eines Spielers von seiner Strategie, bei Festhalten der anderen Spieler an ihren Strategien, h ¨ ochstens

zu einer Verminderung der Auszahlung an den Abweichler f ¨ uhrt.

Unter folgenden zu¨ atzlichen Vorraussetzungen l¨ asst sich zeigen, dass ein n-Personenspiel immer ein Nash-Gleichgewicht besitzt:

ur i = 1, . . . , n konvexe und kompakte Teilmengen (i) Die Strategiemengen S i sind f ¨ von R m i .

(ii) Die Auszahlungsfunktionen Φ i : S 1 × . . . ×S n → R sind stetig.

Satz 1.3. Gilt zus¨ atzlich zu den Annahmen (i), (ii) noch die Annahme:

Zu jedem n-Tupel (s ^∗ , . . . , s ^∗ n ) ∈ S 1 × . . . ×S n und jedem i = 1, . . . , n gibt es genau ein ˜ s i ∈ S i

1

mit Φ i (s ^∗ 1 , . . . , s ^∗ s i , s ^∗ i+1 , . . . , s ^∗ n ) ≥ Φ i (s ^∗ 1 , . . . , s ^∗ i−1 , s i , s ^∗ i+1 , . . . , s ^∗ i−1 , ˜ ur alle s i ∈ S i , n ) f ¨ (2)

so existiert ein Nash-Gleichgewicht.

1. Grundlegende Begriffe und Notationen 9

Beweis. Siehe [Satz 1.10 in [Kra04]].

Zur Verdeutlichung der bisher eingef ¨

Cournot aus dem Jahr 1838 zur ¨ uckgeht.

Beispiel 1.4 (vgl. [Hel09]). Seien U 1 und U 2 zwei Unternehmen, die ein homogenes Gut produzieren, wobei keine Fixkosten entstehen. Zur Vereinfachung sei angenommen, dass beide Unternehmen identische Grenzkosten c = c 1 = c 2 haben. Der m ¨ ogliche

Gewinn der beiden Unternehmen ergibt sich aus der den Unternehmen bekannten inversen Nachfragefunktion

P(x) = a − bx

wobei x = x 1 + x 2 und x 1 , x 2 die gew¨ ahlten Mengen der Unternehmen sind, die sie auf den Markt bringen. Als Auszahlungsfunktion f ¨ ur die Unternehmen ergibt sich damit:

Φ i (x i , x j ) = (a − b(x i + x j ))x i − cx i f ¨ ur i, j = 1, 2.

Beide Unternehmen versuchen ihren Gewinn zu maximieren; allerdings geht die Produktion des anderen Unternehmens in die Auszahlungsfunktion ein. Nimmt man an, dass eine (zum Beispiel durch nur endliche Inputmengen induzierte) obere Schranke K f ¨ ur den Output x i existiert, so erh¨ alt man f ¨ ur die Strategiemengen die kompakte konvexe Menge [0, K].

Nach Satz (1.3) hat das so modellierte Spiel Γ = ([0, K], [0, K]; Φ 1 (x 1 , x 2 ), Φ 2 (x 1 , x 2 )) ein Nash-Gleichgwicht ((2) ist mit dem Satz von Weierstraß erf ¨ ullt).

Dieses Beispiel l¨ asst sich leicht auf n Spieler erweitern, indem man f ¨

U n den Output x =

i folgende Auszahlungsfunktion definiert:

Φ i (x) = (a − bx)x i − cx i

In vielen Spielen sind die Strategiemengen endliche Mengen und somit weder kompakt noch konvex. Um dies zu beheben, f ¨ uhrt man die gemischte Erweiterung einer endlichen Strategiemenge ein.

Definition 1.5. Sei M eine endliche Strategiemenge. Die Elemente m ∈ M heißen reine Strategien. Eine gemischte Strategie auf M ist eine reellwertige Funktion σ auf M mit

• σ(x) ≥ 0 f ¨ ur alle x ∈ M

• σ(x) = 0 f ¨ ur fast alle x ∈ M (d.h. alle, bis auf endlich viele)

• σ(x) = 1 x∈M

Die Menge aller gemischten Strategien auf M wird mit M bezeichnet.

1. Grundlegende Begriffe und Notationen 10

Die Zahl σ(x) kann man als Wahrscheinlichkeit interpretieren, mit der der Spieler die Strategie x w¨ ahlt. Die Mengen M i der reinen Strategien der Spieler i ∈ {1, . . . , n} lassen sich in die Mengen M i der gemischten Strategie isomorph einbetten verm ¨

bildungen s i → σ s i mit σ s i (s) = 1 und σ s i (s ^∗ ) = 0 f ¨ ur alle s ^∗ s.

Definiert man auf der Menge M 1 × · · · × ×M n Auszahlungsfunktionen

⎛ ⎞

so erh¨ alt man ein n-Personen Spiel, die sogenannte gemischte Erweiterung des Spiels.

Beispiel 1.6. Matching Pennies [vgl. [Osb93]]

Zwei Spieler w¨ ahlen simultan, ob sie Kopf oder Zahl einer M ¨ beide Spieler die gleiche Seite der M ¨ unze, so zahlt Spieler 2 an Spieler 1 einen Euro.

Zeigen die beiden Spieler unterschiedliche Seiten, so zahlt Spieler 1 an Spieler 2 einen Euro. Jedem Spieler geht es nur darum seinen eigenen Gewinn zu maximieren. Dies ist also ein Spiel mit endlichen Strategiemengen. Beide Spieler haben die gleiche Strategiemenge S 1 = S 2 = S = {Kopf, Zahl}. Dieses Spiel ist ein typisches Beispiel f ¨ ur ein Spiel

ohne Nash-Gleichgewicht in reinen Strategien. Die gemischte Erweiterung dieser Strategiemenge ist f ¨ ur Spieler 1

{(p, 1 − p), p ∈ [0, 1]}

und

{(q, 1 − q), q ∈ [0, 1]}

ur Spieler 2. Hierbei kann man p = σ(Kopf) als die Wahrscheinlichkeit interpretieren, f ¨

mit der Spieler 1 Kopf zeigt, und q = σ(Kopf) als die Wahrscheinlichkeit, dass Spieler 2 Kopf zeigt.

Die Auszahlungsfunktionen sehen dann wie folgt aus:

˜ Φ 1 (s 1 , s 2 ) =pq − p(1 − q) − (1 − p)q + (1 − p)(1 − q) = (4q − 2)p − 2q + 1 ˜ Φ 2 (s 1 , s 2 ) =p(1 − q) + (1 − p)q − pq − (1 − q)(1 − p) = (−4p + 2)q + 2p − 1.

Die Strategiemengen sind also konvex und kompakt und die Auszahlungsfunktionen stetig.

Zum besseren Verst¨ andnis f ¨ ur das Kapitel ¨ uber Bi-Matrix-Spiele wird hier noch eine kurze Einf ¨ uhrung in diesen Teilbereich der Spieltheorie gegeben.

Definition 1.7. Ein Bi-Matrix-Spiel oder auch (2-Personen-Matrix-Spiel) ist ein 2-Personen-Spiel mit endlichen Strategiemengen M und N, etwa M = (m 1 , . . . , m m ) und N = (n 1 , . . . , n n ).