Seminarausarbeitung:
Konzepte und Umsetzung von
strategischen Spielen
Markus Knödler, 45478
Michael Mader, 45633
Nico Meier, 41828
Stefan Wehrenberg, 42261
Sommersemester 2015
Inhaltsverzeichnis
1 Einführung in strategische Spiele
1.1 Geschichte strategischer Spiele . . . . . . . . . . . . . . . . . .
1.2 Grundlegender Aufbau eines Spiels in Normalform . . . . . . .
1.3 Grundlegende graphische Darstellung von strategischen Spielen
1.3.1 Darstellung als Spielbaum . . . . . . . . . . . . . . . .
1.3.2 Darstellung als Auszahlungsmatrix . . . . . . . . . . .
.
.
.
.
.
1
1
1
4
5
5
2 Beschreibung von strategischen Spielen
2.1 Beschreibung der Form . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 Beschreibung als Normalform . . . . . . . . . . . . . . . . . . . .
2.1.1.1 Nullsummenspiel . . . . . . . . . . . . . . . . . . . . . .
2.1.2 Beschreibung als Extensivform . . . . . . . . . . . . . . . . . . . .
2.1.2.1 Zufall in Spielen der Extensivform . . . . . . . . . . . .
2.1.2.2 Vollkommene Information / unvollkommene Information
2.1.2.3 Vorteile und Nachteile des ersten Zuges . . . . . . . . . .
2.1.2.4 Beeinflussung der anderen Spieler . . . . . . . . . . . . .
7
7
7
8
9
12
14
16
17
3 Analyse und Lösung von strategischen Spielen
3.1 Dominante und dominierte Strategien . . . .
3.1.1 Beste Antwort . . . . . . . . . . . . .
3.2 Nash-Gleichgewicht . . . . . . . . . . . . . .
3.2.1 Rückwärts-Induktion . . . . . . . . .
3.3 Weitere Strategien . . . . . . . . . . . . . .
3.3.1 Max-Min-Strategie . . . . . . . . . .
3.3.2 Min-Max-Strategie . . . . . . . . . .
3.3.3 Min-Max-Theorem . . . . . . . . . .
.
.
.
.
.
.
.
.
18
18
20
21
23
26
26
27
28
.
.
.
.
.
29
32
32
34
35
35
4 Anwendung von strategischen Spielen
4.1 Anwendung in der Informatik . . .
4.2 Anwendung in der Biologie . . . . .
4.3 Anwendung in der Wirtschaft . . .
4.3.1 Verhandlungstheorie . . . .
4.3.2 Marktwirtschaft . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Abbildungsverzeichnis
i
Tabellenverzeichnis
ii
Literatur
iii
1 Einführung in strategische Spiele
Schon seit dem 18. Jahrhundert werden unter dem Konzept der Spieltheorie sogenannte
strategische Spiele dazu benutzt, bestimmte ökonomische Entscheidungssituationen
mit einem Spiel abzubilden, um so mathematisch den Erfolg einzelner Handlungsarten
der einzelnen Akteure zu betrachten. Spieltheorie kann man deswegen auch als »Mehrpersonenentscheidungstheorie« bezeichnen.
1.1 Geschichte strategischer Spiele
Diese mathematische Herangehensweise an ökonomische Probleme wurde nachweislich
zum ersten Mal im Jahre 1787 vom damaligen politischen Theoretiker und späterem
Präsident der vereinigten Staaten James Madison verwendet, um die Auswirkungen
verschiedener Steuersysteme auf die einzelnen Staaten der USA und deren Reaktion zu
untersuchen.[Mad87]
Auch wenn es schon früher - wie im Falle des James Madison - dazu kam, dass spieltheoretisch an bestimmte Probleme herangegangen wurde, so prägte erst der österreichungarische Mathematiker John von Neumann in seinem Aufsatz »Zur Theorie der
Gesellschaftsspiele«[Neu28] von 1928 und später in seinem 1944 erschienenen, auf der
Forschung von 1928 basierenden Buch »Theory of Games and Economic Behavior«[NM44]
den Begriff der Spieltheorie.
Wie in dem genannten Buch klar wird, wurde der Begriff der »Spieltheorie« davon abgeleitet, dass damit - als der Begriff geprägt wurde - Gesellschaftsspiele untersucht worden
sind. Daraus folgend werden die behandelten Entscheidungssituationen schlichtweg als
»Spiele« bezeichnet.
Die Betrachtungsweisen der Spieltheorie fußen darauf, dass es zahlreiche Gemeinsamkeiten zwischen Strategiespielen wie beispielsweise Schach, Mühle, Poker, ... und
Entscheidungsproblemen in der Ökonomie gibt; darunter die Tatsache, dass es wenige
Entscheidungsträger (»Spieler«) gibt, die aufgrund ihrer eigenen Entscheidungen sowie
der Entscheidungen anderer einen bestimmten Nutzen ziehen; diese Art von Interessenkonflikt wird von der Spieltheorie abgebildet.
1.2 Grundlegender Aufbau eines Spiels in Normalform
Ein strategisches Spiel besteht in seiner Normalform aus folgenden Elementen:
• Einer endlichen Menge von Akteuren/Entscheidungsträgern, Spieler genannt
• Für jeden Spieler eine Menge der zu wählenden Strategien (Strategiemenge), die
jeweils aus einzelnen Spielzügen besteht.
• Das Resultat der Strategiewahl aller Spieler, genannt Strategiekombination
• Eine bestimmte Auszahlfunktion, die den Nutzen für jeden Spieler anhand einer
Strategiekombination angibt.
1
Kennzeichen eines sogenannten nichtkooperativen Spieles ist es, dass alle Spieler ihre Strategie gleichzeitig ohne Kenntnis der Strategie des anderen wählen müssen; d.h.
kein Spieler kennt eine der gewählten Strategien der anderen Spieler. Weiterhin muss
ein kardinales Nutzenkonzept existieren, d.h. die einzelnen Auszahlungen müssen
zueinander in Relation gestellt werden können, um so Auszahlungen gegeneinander abzuwägen und eine »Ordnung« der einzelnen Auszahlungen herstellen zu können.
Diese Definition eines strategischen Spiels kann auch mathematisch anstatt in Umgangssprache erfolgen[BEG10, S. 11-13]:
Definition 1.1 Ein strategisches Spiel in Normalform wird definiert
über einen Tupel
G = (Σ1 . . . Σn ; H1 . . . Hn ; I)
+
wobei n ∈ N die Anzahl der Spieler,
I die Menge aller Spieler,
Σi die Strategiemenge des Spielers i,
Hi die Auszahlungsfunktion von Spieler i und
σi ∈ Σi eine bestimmte vom Spieler i wählbare Strategie darstellt.
Die Strategiekombination aller Strategien wird mit σ bezeichnet;
mit Hi (σ) berechnet sich der Nutzen für Spieler i.
Bei einem sogenannten nichtkooperativen strategischen Spiel gilt zusätzlich:
Definition 1.2 Die gewählten Strategien werden in einem nichtkooperativen strategischen Spiel simultan bekanntgegeben;
Dies bedeutet, dass ein Spieler i keine der gewählten Strategien σj ∈
V
Σj für j ∈ N+ i 6= j kennt.
Um diese abstrakten Definitionen eines strategischen Spieles zu verdeutlichen, bietet es
sich an, ein konkretes, einfaches Beispiel zu wählen, anhand welchem der Zweck der
einzelnen Komponenten leicht ersichtlich ist.
Beispiel 1.1 »Gefangenen-Dilemma«[Tuc83]
Ein sehr bekanntes Beispiel aus der Spieltheorie ist das sogenannte
»Gefangenen-Dilemma«:
Zwei Gefangene (Spieler 1 und Spieler 2) haben zusammen ein
Verbrechen begangen und werden getrennt verhört. Jeder Gefangene
hat zwei mögliche Strategien, aus denen er wählen kann:
Strategie V, in der er seinen Partner verrät oder
Strategie S, in welcher er schweigt und seinen Partner deckt.
Die Höchststrafe beträgt 6 Jahre. Schweigen beide, wird jeder nur
wegen geringerer Vergehen für jeweils 2 Jahre bestraft; verrät einer
2
den anderen, bekommt er selbst nur eine einjährige Gefängnisstrafe,
der andere dafür die Höchststrafe. Verraten sich beide gegenseitig,
erhalten Beide eine Strafe von 4 Jahren.
Es gilt also: GGD = (Σ1 , Σ2 , H1 , H2 , I), wobei
I = {Spieler 1,Spieler 2}
Σ1 = Σ2 = {V, S}
Es ist leicht zu erkennen, dass es genau vier Strategiekombinationen
geben muss:
σV,V ≡ (σ1 = V ∧ σ2 = V ) (Beide wählen »Verrat«)
σS,S ≡ (σ1 = S ∧ σ2 = S) (Beide wählen »Schweigen«)
σV,S ≡ (σ1 = V ∧ σ2 = S) (Spieler 1 verrät Spieler 2)
σS,V ≡ (σ1 = S ∧ σ2 = V ) (Spieler 2 verrät Spieler 1)
Hierbei lautet die Auszahlungsfunktion wie folgt:
H1 (σV,V ) = H2 (σV,V ) = −4 (4 Jahre »negativer« Nutzen)
H1 (σS,S ) = H2 (σS,S ) = −2
H1 (σV,S ) = −1 sowie H2 (σV,S ) = −6
H1 (σS,V ) = −6 sowie H2 (σS,V ) = −1
Anhand dieses Beispiels ist zu sehen, dass eine Entscheidungsfindung respektive die Wahl
der besten Strategie nicht einfach ist.
Für außenstehende Betrachter ist es leicht, die beste Strategie zu finden: Der Gesamtnutzen ist am Höchsten für alle Spieler (nämlich -4), wenn beide Spieler sich dazu
entschließen, sich gegenseitig nicht zu verraten - da man jedoch in einem nichtkooperativen Spiel als Spieler die Entscheidungen der anderen Spieler nicht kennt, ist es als
individuelle Strategie am besten, den anderen Spieler zu verraten - hiermit erhöht man
den eigenen Nutzen auf jeden Fall auf -4, wenn der andere Spieler schweigt sogar auf -1.
So wird klar, was konkret unter dem Begriff Interessenkonflikt verstanden werden
muss und welche Auswirkungen er konkret auf die Entscheidungsfindung hat - auch bei
einem derart simplen Beispiel wie dem Gefangenendilemma. Dazu noch ein weiteres Beispiel, welches eng mit dem Gefangenendilemma verwandt ist und diesen Aspekt genauer
beleuchtet:
Beispiel 1.2 »Kampf der Geschlechter«-Variation
Zwei Studenten (Spieler 1 und Spieler 2) sind sich nicht einig, ob
sie morgens die Vorlesung in der Hochschule besuchen oder zuhause
bleiben möchten. Der faule Student 1 bevorzugt hierbei die Variante,
zuhause zu bleiben (Strategie A) der fleißige Student 2 den Besuch
3
der Vorlesung. (Strategie B).
Sie müssen sich, ohne zu wissen wofür sich der andere entscheidet,
eine Strategie wählen, da sie vergessen haben, sich abzusprechen. Es
besteht für beide Studenten ein »kleiner« Nutzen, wenn sie die gleiche
Entscheidung getroffen haben, und ein »großer« Nutzen, wenn sich
beide in der jeweiligen Präferenz treffen. Ansonsten ist der Nutzen 0.
Es gilt also: GKDG∗ = (Σ1 , Σ2 , H1 , H2 , I), wobei
I = {Spieler 1,Spieler 2}
Σ1 = Σ2 = {A, B}
Auch hier gibt es wieder genau vier Strategiekombinationen:
σA,A ≡ (σ1 = A ∧ σ2 = A) (Beide bleiben zuhause)
σB,B ≡ (σ1 = B ∧ σ2 = B) (Beide besuchen die Vorlesung)
σA,B ≡ (σ1 = A ∧ σ2 = B) (Spieler 1 bleibt zuhause)
σB,A ≡ (σ1 = B ∧ σ2 = A) (Spieler 2 bleibt zuhause)
Hierbei lautet die Auszahlungsfunktion für die Studenten wie folgt:
H1 (σA,A ) = 3 sowie H2 (σA,A ) = 1
H1 (σB,B ) = 1 sowie H2 (σB,B ) = 3
H1 (σA,B ) = H2 (σA,B ) = 0
H1 (σB,A ) = H2 (σB,A ) = 0
Hier ist es im Vergleich zum Gefangenen-Dilemma deutlich schwieriger eine vernünftige
Lösungsstrategie zu finden, da bei jeder Strategie, welche gewählt werden kann, eine
Chance von 12 besteht, bei der Strategiekombination einen Nutzen von 0 zu erhalten.
Es ist daher völlig egal, welche Strategie die einzelnen Studenten wählen, weswegen
eine zufallsbasierte Entscheidung in diesem Entscheidungsproblem das Richtige wäre.
Man spricht auch davon, dass es in diesem Problem keine sogenannte dominante Lösungsstrategie gibt. Bei strategischen Spielen in der Art wie hier dargestellt spricht
man auch von einem sogenannten Nash-Gleichgewicht, dazu jedoch mehr in den folgenden Kapiteln.
1.3 Grundlegende graphische Darstellung von strategischen Spielen
Wie an den Darstellungen der simplen Beispiele erkannt werden kann, ist eine Beschreibung als Text und in mathematischer Form insbesondere bei den vorliegenden Strategiekombinationen und der Auszahlungsfunktion mitunter sehr unübersichtlich.
Aufgrund dessen haben sich andere Darstellungsformen durchgesetzt, die eine einfachere,
genauere und selbsterklärende Darstellung der einzelnen strategischen Spiele erlauben
- darunter die Matrixdarstellung der Auszahlungen (»Auszahlungsmatrix«) und der
Spielbaum oder auch »Entscheidungsbaum«.
4
1.3.1 Darstellung als Spielbaum
Die Darstellung als Spielbaum bietet einige
Vorteile gegenüber der Darstellung in reiner
mathematischer oder schriftlicher Form.
Spieler 1
V
S
Spieler 2
V
S
V
S
(-4, -4) (-1, -6) (-6, -1) (-2, -2)
So kann man hier ohne Probleme erkennen, wie
viele Strategiekonfigurationen es gibt und anhand der Einträge an den Blättern des Baumes
auch sehr leicht die zugehörige Auszahlungsfunktion, die aufgrund dieser Konstellation entsteht.
Abbildung 1: Spielbaumdarstellung
von GGD
Nachteile der Darstellung als Spielbaum ist die
Tatsache, dass der Eindruck erweckt wird, dass
das Spiel nacheinander anstatt simultan gespielt wird - dies ist jedoch auch die größte Stärke der Darstellung als Spielbaum, da so
auch Spiele modelliert werden können, die nicht simultan ablaufen.
Spieler 1
A
B
Spieler 2
A
B
A
B
(3, 1)
(0, 0)
(0, 0)
(1, 3)
Die zwei hier dargestellten Spielbäume stellen eine Visualisierung der vorangegangenen Beispiel dar, wobei durch die Darstellung als Spielbaum hier noch einmal klarer
gemacht wird, wie ähnlich sich beide angeführten strategischen Spiele sind respektive wie
stark beide Probleme miteinander verwandt
sind.
Abbildung 2: GKDG∗ als Spielbaum
1.3.2 Darstellung als Auszahlungsmatrix
Eine andere Möglichkeit der Darstellung von strategischen Spielen ist die sogenannte
Auszahlungsmatrix oder auch Bimatrix.
Diese vereinfacht ebenfalls die Darstellung, hat allerdings den Nachteil, dass sie nur
bei Spielen mit genau zwei Spielern möglich ist. Hier werden Spieler 1 die Spalten und
Spieler 2 die Zeilen der Matrix zugeordnet; die Anzahl der Zeilen und Spalten orientiert
sich an den wählbaren Strategien der einzelnen Spieler. Wie bei der Spielbaumdarstellung üblich werden auch hier die Auszahlungen als Tupel notiert.
5
Spieler 2
S
V
Die Matrixdarstellung ist die Darstellung der Wahl bei einfachen, nichtkooperativen und sogenannten One-ShotSpielen, die nicht nacheinander, sondern
simultan »auf einen Zug« gespielt werden.
Spieler 1
S
V
(-2, -2) (-1, -6)
(-6, -1) (-4, -4)
Tabelle 1: Matrixdarstellung von GGD
Spieler 2
Durch die Tatsache, dass die einzelnen
Strategiemöglichkeiten der Spieler durch Spalten und Zeilen in der Matrix dargestellt
werden, wird die Matrixdarstellung schnell sehr unübersichtlich, wenn sehr viele Strategien existieren. Aus diesem Grund wird daher in einem solchen Fall auf eine andere
Darstellungsmethode ausgewichen.
A
B
Spieler 1
A
B
(3, 1) (0, 0)
(0, 0) (1, 3)
Tabelle 2: Matrixdarstellung von GKDG∗
6
2 Beschreibung von strategischen Spielen
Strategische Spiele werden - je nachdem wie die Entscheidungsproblematik aufgebaut
ist, die dem Spiel zu Grunde liegt - in verschiedenen Formen beschrieben, die je nach
Form abhängig verschiedene Eigenheiten aufweisen.
Darüber hinaus haben strategische Spiele auch spezielle Eigenschaften und je nach
Form und Eigenschaft auch verschiedene Lösungsansätze beziehungsweise Lösungsstrategien.
2.1 Beschreibung der Form
2.1.1 Beschreibung als Normalform
In Kapitel 1.2 »Grundlegender Aufbau eines Spiels in Normalform« wurde bereits der
grundlegende Aufbau eines Spiels in Normalform beschrieben, der genaue mathematische Aufbau findet sich in Definition 1.1.
Zur Verdeutlichung der Normalform kann hier nochmal ein simples Beispiel gewählt
werden, um noch einmal zu verdeutlichen, wie die Normalform eines Spieles aufgebaut
ist.
Beispiel 2.1 »Elfmeter-Schießen«
Ein bekanntes Beispiel aus der Spieltheorie ist die theoretische Betrachtung des Elfmeterschießens beim Fußball:
Zwei Fußballer (Spieler 1, der Torwart und Spieler 2, der Schütze) stehen sich beim Elfmeter-Schießen gegenüber und stehen jeweils
vor den gleichen Entscheidungsmöglichkeiten:
Strategie L, in denen der Torwart nach links hechtet / der Spieler
links schießt oder
Strategie R, in denen der Torwart nach rechts hechtet / der Spieler
rechts schießt.
Ganz simpel betrachtet geht man nur von den folgenden Fällen aus:
Wählen Torwart und Schütze die gleiche Strategie, wird der Ball
gehalten und kein Tor fällt; wählen Torwart und Schütze verschiedene Strategien, fällt ein Tor.
Es gilt also: GElf meter = (Σ1 , Σ2 , H1 , H2 , I), wobei
I = {Spieler 1,Spieler 2}
Σ1 = Σ2 = {L, R}
7
Spieler 2
Die Darstellung sieht also folgendermaßen aus:
Spieler 1
L
R
(1, -1) (-1, 1)
(-1, 1) (1, -1)
L
R
Tabelle 3: Matrixdarstellung von GElf meter
Spieler 1
L
R
Spieler 2
L
R
L
R
(1, -1)
(-1, 1)
(-1, 1)
(1, -1)
Abbildung 3: Spielbaumdarstellung von GElf meter
Spiele wie hier beim Elfmeterschießen nennt man auch »Nullsummenspiele« (ZeroSum).
2.1.1.1 Nullsummenspiel
Ein »Nullsummenspiel« (oder auch Zero-Sum-Spiel) beschreibt ein Spiel, indem es
- umgangssprachlich ausgedrückt - nur einen Gewinner (mit Auszahlung a) und einen
Verlierer (mit Auszahlung -a) gibt; es gibt in einem solchen Spiel daher nur zwei Fälle:
Entweder einer der Spieler gewinnt, oder beide einigen sich auf Unentschieden (Auszahlung 0).
In dem hier vorliegenden Spiel GElf meter entspricht der Verlust eines Spielers exakt
dem Gewinn des anderen - das erkennt man daran, dass die Auszahlungsmengen in
ihrer Summe immer 0 ergeben; daher auch der Begriff »Nullsummenspiel«
Eine Unterart des Nullsummenspiels ist ein sogenanntes »Konstantsummenspiel«,
bei dem sich die Auszahlungen immer zu der gleichen Summe ergänzen; es handelt sich
jedoch hierbei nur um einen Spezialfall des Nullsummenspieles, wobei die Auszahlungen
alle um den gleichen Betrag größer oder kleiner gemacht wurden.
Definition 2.1 In einem strategischen Konstantsummenspiel in
Normalform muss gelten:
P
∀ σ : i0 Hi (σ) = a.
Und nochmal spezifischer für Nullsummenspiele:
8
Definition 2.2 In einem strategischen Nullsummenspiel gilt Definition 2.1, wobei a = 0.
2.1.2 Beschreibung als Extensivform
Im Vergleich zu einem Spiel in Normalform, bei dem Spieler sich simultan für eine
Strategie entscheiden, die sie das komplette Spiel über »verfolgen« wird bei einem Spiel,
welches in Extensivform beschrieben wird sequentiell, d.h. Schritt für Schritt eine Strategie gewählt.
Die Beschreibung eines Spiels in Normalform ist sehr abstrakt und für viele Alltagssituationen nicht brauchbar, da sich diese damit nicht oder nur sehr kompliziert abbilden
lassen. Das gilt sowohl für die klassischen Gesellschaftsspiele wie Mühle, Schach oder
andere als auch für ökonomische Entscheidungssituationen, in welcher mehrere Schritte
nacheinander ablaufen.
Allgemein betrachtet ist jedes Spiel in Normalform gleichzeitig auch ein Spiel in Extensivform; die simultane Entscheidung ist ein Sonderfall der sequentiellen Entscheidung
- wie auch jedes Spiel in Extensivform zu einer Normalformdarstellung umgewandelt
werden kann, wobei jedoch meistens die Abfolge der Spielzüge verloren geht. Zur Darstellung eines Spieles in Extensivform wird gemeinhin die Spielbaum-Darstellung wie
in Kapitel 1.3.1 benutzt.
Ein Strategiespiel in Extensivform besteht im Allgemeinen aus folgenden Elementen:
• Einer endlichen Menge von Akteuren/Entscheidungsträgern, Spieler genannt
• Für jeden Punkt im Spielverlauf die Information, wer gerade »am Zug« ist
• Für jeden Punkt im Spielverlauf die möglichen »Folgezüge«
• Der Sachverhalt, welcher Information sich der Spieler sich der Spieler bei seinem
Zug bedienen kann (vollständige Information / unvollständige Information)
• Für die Endpunkte des Spiels die Auszahlungen für die einzelnen Spieler
Auch hier muss natürlich - wie bei der Normalform auch - ein kardinales Nutzenkonzept existieren, welches die Auszahlungen / den Nutzen zueinander in Bezug setzt.
Auch die Definition eines Spiels in Extensivform kann mathematisch und nicht in der
Umgangssprache erfolgen.
Mathematisch gesehen verwendet man für die Darstellung einen Graphen bzw. Spielbaum K mit einer bestimmten Knoten- und Kantenmenge:
9
Definition 2.3
Ein Spielbaum K ist ein zusammenhängender, gerichteter Graph
mit einem bestimmten Startknoten v0 .
1. Die Knoten V repräsentieren dabei die Punkte im Spielverlauf.
2. Die Partition oder Spielerzerlegung P = {P1 , P2 , . . .} unterteilt die Knoten in Partitionsmengen für die einzelnen Spieler.
3. Die Knoten sind in Endknoten Z und in Entscheidungsknoten X unterteilt, wobei gilt: Z ∪ X := V .
4. Die Informationspartition Ui = {ui1 , . . . , uiKi } unterteilt
die Partition Pi in Informationsmengen. Die uik repräsentieren die
Informationen von Spieler i an den Punkten, an denen er am Zug
ist. Ist uik einelementig, hat der Spieler vollständige Information ist sie mehrelementig, kennt der Spieler nicht alle Informationen.
Die Informationszustände aller Spieler findet man in U =
{U1 , . . . , Ui }.
5. Eine Aktionsmenge C, die als Menge {Cu } mit u ∈ Ui alle
Aktionen des Spielers i an seinen Informationsmengen u enthält diese bilden die Kanten des Spielbaums.
6. Eine Auszahlfunktion Π : Z → Rn , die jedem Endknoten
z ∈ Z ein n-Tupel an Auszahlungen zuordnet.
Aus dieser Definition leitet sich die - jetzt triviale - Definition eines strategischen Spiels
in Extensivform ab:
Definition 2.4 [BEG10, S. 91-96]
Ein strategisches Spiel in Extensivform wird definiert über einen Tupel
Γ = (I, K, Z, P, U, C, Π)
wobei I die Menge aller Spieler,
K die Knotenmenge,
Z die Endknotenmenge,
P die Partitionsmenge,
U die Informationsmenge,
C die Aktionsmenge und
Π die Auszahlfunktion darstellt.
Da die Definition eines Spiels in Extensivform ziemlich komplex erscheint, kann man
ein Beispiel zur Verdeutlichung wählen. Während Spiele wie das Elfmeter-Schießen aus
Beispiel 2.1 nicht zur Extensivform mit vollkommener Information überführt werden
können (würde der Torwart bekanntgeben, in welche Ecke er springen wird, wäre das
Elfmeterschießen sinnlos), so ist dies bei der »Kampf der Geschlechter (Variation)«
aus Beispiel 1.2 mit ein paar Änderungen ohne Weiteres möglich.
10
Beispiel 2.2 »Kampf der Geschlechter«-Variation (als extensives Spiel)
Zwei Studenten (Spieler 1 und Spieler 2) sind sich nicht
einig, ob sie morgens die Vorlesung in der Hochschule besuchen oder
zuhause bleiben möchten. Der faule Student 1 bevorzugt hierbei die
Variante, zuhause zu bleiben (Strategie A) der fleißige Student 2
den Besuch der Vorlesung. (Strategie B).
Hier wählt Student 1 seine Entscheidung als Erstes, wobei Student
2 die Entscheidung von Student 1 bedenken und seine Strategie
danach ausrichten kann.
Es besteht für beide Studenten ein »kleiner« Nutzen, wenn sie die
gleiche Entscheidung getroffen haben, und ein »großer« Nutzen,
wenn sich beide in der jeweiligen Präferenz treffen. Ansonsten ist
der Nutzen 0.
Das Aufstellen des zugehörigen Spielbaumes ist trivial:
x1
x2
A
A
x4
(3, 1)
B
B
x3
A
x5
x6
(0, 0)
(0, 0)
B
x7
(1, 3)
Abbildung 4: Spielbaumdarstellung von ΓKDG∗
Es gilt also: ΓKDG∗ = (I, K, Z, P, U, C, Π), wobei:
I = {Spieler 1,Spieler 2}
K = {x1 , x2 , x3 , x4 , x5 , x6 , x7 }
Z = {x4 , x5 , x6 , x7 }
P = {P1 , P2 } mit P1 = {x1 } und P2 = {x2 , x3 } (Bei x1 ist Spieler 1
am Zug, bei x2 , x3 Spieler 2)
U = {U1 , U2 } mit U1 = {u11 } und U2 = {u21 , u22 } (Aufteilung der
Informationsmenge)
u11 = {x1 }, u21 = {x2 }, u22 = {x3 } (Spieler 2 ist komplett über die
Aktionen von Spieler 1 informiert.)
C = {Cu11 , Cu21 , Cu22 } mit Cu11 = {A, B}, Cu21 = {A, B},
Cu22 = {A, B}
11
Die Auszahlfunktion Π hat vier verschiedene Parameter, für jeden
Knoten x ∈ Z eine:
Π(x4 ) = (3, 1)
Π(x5 ) = (0, 0)
Π(x6 ) = (0, 0)
Π(x7 ) = (1, 3)
2.1.2.1 Zufall in Spielen der Extensivform
Die Extensivform wird auch dazu benutzt, zufällige Spielzüge zu modellieren - einerseits mit einer Art »Zufallsspieler«, der beispielsweise in ein Ergebnis eingreifen kann
(»mit einer Wahrscheinlichkeit von 20% erhöht sich der Gewinn um das Doppelte!«) als
auch mit einem Zufallszug, wie beispielsweise beim Würfeln oder bei anderen Spielen
üblich.
Hierzu ein kleines Beispiel:
Beispiel 2.3 »Würfelwurf« (mit Zufall)
Spieler 1 wirft einen sechsäugigen, sechsseitigen Würfel. Bei
geraden Zahlen gewinnt er einen Euro, bei ungeraden Zahlen verliert
er zwei Euro.
Der zugehörige Spielbaum:
x1
1
3
4
6
2
x2
x3
5
x4
x5
x6
x7
Abbildung 5: Spielbaumdarstellung von ΓW ürf el
Es gilt also: ΓW ürf el = (I, K, Z, P, U, C, Π, P r), wobei:
I = {Spieler 1}
K = {x1 , x2 , x3 , x4 , x5 , x6 , x7 }
Z = {x2 , x3 , x4 , x5 , x6 , x7 }
P = {P0 , P1 } mit P0 = {x2 , x3 , x4 , x5 , x6 , x7 } und P1 = {x1 } (Der
»Zufall« erhält die Partition mit der Nummer 0)
U = {U1 } mit U1 = {u11 } (Aufteilung der Informationsmenge)
u11 = {x1 } (Es gibt nur Spieler 1)
C = {Cu11 } mit Cu11 = {1, 2, 3, 4, 5, 6}
12
Die Auszahlfunktion Π hat sechs verschiedene Parameter, für jeden
Knoten x ∈ Z eine:
Π(x2 ) = (-2)
Π(x3 ) = (1)
Π(x4 ) = (-2)
Π(x5 ) = (1)
Π(x6 ) = (-2)
Π(x7 ) = (1)
Was neu hinzugekommen ist, ist die Menge der Wahrscheinlichkeitsverteilungen Pr in der oberen Definition; diese enthält die
unterschiedlichen Wahrscheinlichkeiten, mit denen die Ergebnisse
eintreten:
P r = {px2 , px3 , px4 , px5 , px6 , px7 }
Hier tritt ein Sonderfall auf, denn:
px2 = px3 = px4 = px5 = px6 = px7 = 16
Die Ereignisse treten daher alle mit einer Wahrscheinlichkeit von 16
auf.
Auch andere Arten des Zufalls, wie Beispielsweise die Verteilung von Karten in Kartenspielen, die Wahrscheinlichkeit eines Treffers beim Roulette oder zahlreiche andere
Dinge können so mit in die Definition des strategischen Spieles miteinfließen.
In vielen ökonomischen Beispiel ist die Reaktion von Angebot und Nachfrage bzw. die
Reaktion des Marktes oft mit bestimmten Zufällen verbunden, die so im Spiel modellierbar sind.
Als Definition:
Definition 2.5 Ein strategisches Spiel in Extensivform mit Zufallszügen wird definiert über einen Tupel
Γ = (I, K, Z, P, U, C, Π, P r)
wobei:
I die Menge aller Spieler,
K die Knotenmenge,
Z die Endknotenmenge,
P die Partitionsmenge,
U die Informationsmenge,
C die Aktionsmenge,
Π die Auszahlfunktion und
P r die Menge der Wahrscheinlichkeitsverteilungen darstellt.
Auf diese Art und Weise ist es möglich und modellierbar, dass ein Spieler zufällige
Entscheidungen trifft beziehungsweise zufällige Strategien wählt.
Während man bei den bisher vorhandenen Strategien von sogenannten »reinen Stra-
13
tegien« spricht, zwischen denen der Spieler sich entscheidet, so wählt er bei einer sogenannten »gemischten Strategie« eine zufällige reine Strategie mit einem bestimmten
Zufallsalgorithmus.
Eine gemischte Strategie wird in Extensivspielen üblicherweise mit der Menge der
Wahrscheinlichkeitsverteilungen Pr definiert, kann aber auch mit einer Matrix p
definiert werden, welche an Stelle pi,j den Wahrscheinlichkeitswert der Strategie j des
Spielers i enthält. Damit die zufällige Wahl funktioniert, müssen sich alle wählbaren reinen Strategien auf den Wahrscheinlichkeitswert von 11 ergänzen, wie es beispielsweise
im Beispiel 2.3 der Fall gewesen ist.
2.1.2.2 Vollkommene Information / unvollkommene Information
Während bei den bisher dargestellten Spielen in Extensivform davon ausgegangen wird,
dass alle Spieler über alle Entscheidungen aller Spieler Bescheid wissen (sogenannte
»vollkommene Information«), so ist das in vielen Alltagssituationen wie auch ökonomischen Formen nicht der Fall.
Schon bei der Betrachtung von Gesellschafts- und Glücksspielen wie Poker, Siebzehnund-Vier oder »Uno« wird klar, dass die Spieler nur sehr begrenzen Einblick in die
Entscheidungen der anderen Spieler haben - es handelt sich hier um Spiele mit unvollkommener Information. Reale Beispiele aus der Ökonomie können beispielsweise
Investitionsentscheidungen von Unternehmen oder Verhandlungssituationen sein, bei denen den einzelnen Spielern nicht alle Entscheidungen der anderen Spieler offenliegen.
Bei der Betrachtung anderer Gesellschaftsspiele, beispielsweise »Mensch-ärgere-dichnicht«, »Monopoly«, Schach oder Mühle handelt es sich um Spiele mit vollkommener
Information, da jedem Spieler zu jedem Zeitpunkt alle getroffenen Entscheidungen der
anderen Spieler bekannt sind (wenn man von der Komplexität absieht.)
Auch bei den in Kapitel 2.1.2.1 dargestellten Spielen mit Zufallszügen kann es sich
sowohl um Spiele mit unvollkommener Information als auch um Spiele mit vollkommener Information handeln; je nachdem ob die Züge des »Spielers 0« (der Natur) den
anderen Spielern bekannt sind oder nicht.
Das Beispiel 2.2 kann leicht modifiziert werden, um es zu einem Spiel mit
unvollkommener Information zu machen:
Beispiel 2.4 »Kampf der Geschlechter«-Variation (als extensives Spiel mit unvollkommener Information)
Zwei Studenten (Spieler 1 und Spieler 2) sind sich nicht einig, ob
sie morgens die Vorlesung in der Hochschule besuchen oder zuhause
bleiben möchten. Der faule Student 1 bevorzugt hierbei die Variante,
14
zuhause zu bleiben (Strategie A) der fleißige Student 2 den Besuch
der Vorlesung. (Strategie B).
Hier wählt Student 1 seine Entscheidung als Erstes, wobei Student
2 die Entscheidung von Student 1 nicht bekannt ist, da Student 1 ihn nicht darüber informiert.
Es besteht für beide Studenten ein »kleiner« Nutzen, wenn sie die
gleiche Entscheidung getroffen haben, und ein »großer« Nutzen, wenn
sich beide in der jeweiligen Präferenz treffen. Ansonsten ist der Nutzen 0.
Es gilt also: ΓKDG2∗ = (I, K, Z, P, U, C, Π), wobei:
I = {Spieler 1,Spieler 2}
K = {x1 , x2 , x3 , x4 , x5 , x6 , x7 }
Z = {x4 , x5 , x6 , x7 }
P = {P1 , P2 } mit P1 = {x1 } und P2 = {x2 , x3 } (Bei x1 ist Spieler
1 am Zug, bei x2 , x3 Spieler 2)
U = {U1 , U2 } mit U1 = {u11 } und U2 = {u21 , u22 } (Aufteilung der
Informationsmenge)
u11 = {x1 }, u21 = {x2 , x3 }, u22 = {x2 , x3 } (Spieler 2 weiß an
den Punkten u21 und u22 nicht, ob er sich bei x2 oder x3 befindet.)
C = {Cu11 , Cu21 , Cu22 } mit Cu11 = {A, B}, Cu21 = {A, B},
Cu22 = {A, B}
Die Auszahlfunktion Π hat vier verschiedene Parameter, für jeden
Knoten x ∈ Z eine:
Π(x4 ) = (3, 1)
Π(x5 ) = (0, 0)
Π(x6 ) = (0, 0)
Π(x7 ) = (1, 3)
Der Unterschied zu ΓKDG∗ findet sich in der Definition von
u21 und u22 - diese zwei Parameter legen fest, dass der Spieler sich
im Moment sowohl bei x2 als auch x3 befinden kann.
Aufgrund dieses Beispiels lässt sich leicht die Definition eines unvollkommenen bzw.
vollkommenen Spieles ableiten:
Definition 2.6 In einem strategischen Spiel in Extensivform mit
vollkommener Information muss gelten:
∀ uiKi ∈ Ui ∈ U : |uiKi | = 1.
Alle Informationsmengen müssen einelementig und damit eindeutig
sein.
15
Analog gilt daher:
Definition 2.7 In einem strategischen Spiel in Extensivform mit
unvollkommener Information muss gelten:
∃ uiKi ∈ Ui ∈ U : |uiKi | =
6 1.
Es gibt eine Informationsmenge, die nicht einelementig ist → Es gibt
mindestens einen Spielpunkt, bei dem ein Spieler keine vollkommene
Information besitzt.
2.1.2.3 Vorteile und Nachteile des ersten Zuges
Während es bei Spielen in Normalform (und auch bei Spielen in Extensivform mit derart unvollkommener Information, dass keiner der Spieler weiß, was der andere macht)
völlig egal ist, in welcher »Reihenfolge« die Spieler ihre Züge machen; so ist bei einem Spiel mit vollkommener Information respektive bei jedem Spiel, in dem der Spieler
Kenntnis über die Strategiewahl des anderen hat die Reihenfolge nicht zu unterschätzen.
Ein sogenannter »Vorteil des ersten Zuges«[LM88] kann bei vielen Spielen ausgenutzt werden; so gibt es beispielsweise bei manchen Gesellschaftsspielen Gewinnstrategien, die nur funktionieren, wenn der Spieler als erstes beginnt (»Tic-Tac-Toe«) sowie
bestimmte Schacheröffnungen, die nur als erster Zug durchgeführt werden können.
Auch bei ökonomischen Situationen ist es oft von Vorteil, »als Erster zu ziehen« - solch
ein Vorteil tritt beispielsweise bei technischen Innovationen auf, die der entwickelnden und veröffentlichenden Partei aufgrund des technischen Vorsprungs einen Vorteil
verschafft. Aufgrund des Durchbruchs kann eine Führungsrolle am Markt eingenommen werden, was bei den Parteien, die erst »später am Zug« sind zu Beschwerlichkeiten
führt - die Kunden müssen das System wechseln (mit teilweise hohen bis sehr hohen
Wechselkosten, je nach Branche) und es muss Geld darin investiert werden, die Kunden
vom ersten Produkt wegzuleiten.
Es kann in einem Strategischen Spiel jedoch nicht nur von Vorteil, sondern sogar von
Nachteil sein, den ersten Zug zu machen - dieser »Nachteil des ersten Zuges«[LM88]
kann sich beispielsweise darin äußern, dass man - in einer ökonomischen Situation die Reaktion des Spielers »Kunde« falsch eingeschätzt hat; aufgrund der Reaktion dieses Spielers können nachfolgende Spieler bessere Entscheidungen treffen (sogenanntes
»Cherry-Picking«) und müssen auch nicht mehr die Akzeptanz des Spielers »Kunde«
für die neuartigen Entwicklungen abwarten.
Auch in anderen Beispielen kann der erste Zug manchmal die schlechtere Wahl sein,
beispielsweise beim Elfmeter-Schießen, wo weder der Torwart noch der Schütze dem
Gegenüber die Richtung, in die geschossen / gesprungen wird preisgeben sollte.
16
2.1.2.4 Beeinflussung der anderen Spieler
In einem extensiven sequenziellen Spiel kann durch das eigene Verhalten direkt in die
Entscheidungsfindung des anderen eingegriffen werden; der Spieler kann somit sowohl
durch Drohungen als auch durch Versprechen andere Spieler zu einer bestimmten
Handlung nötigen oder sie zu einer bestimmten Handlung überreden.
Eine Drohung ist schon bei alltäglichen Situationen gegeben, wie beispielsweise der
Aufforderung einer Mutter an ihr Kind, das Zimmer aufzuräumen, da ansonsten das
Taschengeld gestrichen wird (sogenannte »erzwingende Drohung«) sowie auch bei
Situationen in Gesellschaftsspielen (Das Schachsetzen des Königs, was einen Zug erzwingt) oder als sogenannte »abschreckende Drohung« auch im Sinne der Aussage
des Professors an den Student, dass er in der Prüfung nicht schummeln soll, da er ansonsten durchfällt, wenn er erwischt wird.
Ein Versprechen im spieltheoretischen Sinne ist genauso auch bei alltäglichen Situationen vorhanden (generell bei Situationen mit sogenannter positiver Bestärkung oder
positiver Konditionierung als »erzwingendes Versprechen«), beziehungsweise auch
in anderen Situationen so - so könnten sich die Gefangenen vor dem Gefangenendilemma
gegenseitig versprechen zu schweigen, da so Beiden kein starker Verlust droht.
Ein »abschreckendes Versprechen« wäre im gleichen Zuge die Aussage eines Professors, der seinen Studenten Bonuspunkte in der Klausur verspricht, wenn sie regelmäßig
zu seiner Vorlesung erscheinen - um die Studenten von dem Fernbleiben der Vorlesung
abzuschrecken.
17
3 Analyse und Lösung von strategischen Spielen
Während bisher die Beschreibung der Form, d.h. des Problems und der Fragestellung
eines ökonomischen Entscheidungsproblems respektive eines strategischen Spiels im Mittelpunkt stand, so kommt jedoch der Analyse beziehungsweise der Findung der besten
Strategie, der »Lösung« des strategischen Spiels und der »Antwort« auf die Fragestellung gleichfalls große - wenn nicht sogar die größte - Bedeutung zu.
Wie einfache Beispiele in vergangenen Kapiteln gezeigt haben, gibt es nicht in jedem
Spiel immer eine optimale Strategie, bei der man immer gewinnt - besonders, weil das
Verhalten der anderen Spieler schwer kalkulierbar und manchmal (extensive Form beim
Nachteil des ersten Zuges; Normalform) gar nicht bekannt ist.
In einem Spiel mit einem Spieler ist die beste Lösungsstrategie leicht zu finden - sie ist
immer die Strategie mit dem höchst möglichsten Gewinn für diesen Spieler. Bei einem
Spiel mit mehreren Spielern jedoch müssen deren Entscheidungen und mögliche Strategien bei einer Entscheidungsfindung und Lösungsfindung gleichfalls betrachtet werden.
3.1 Dominante und dominierte Strategien
Ungeachtet der Entscheidungen der anderen Spieler geht es bei einer sogannten »dominanten Strategie« darum, dass ein Spieler die jeweils beste Strategie für sich selbst
findet, ohne dabei auf die anderen Mitspieler achten. Eine Strategie wird als »dominante
Strategie« bezeichnet, wenn sie bei allen möglichen Entscheidungen der anderen Spieler
immer den höheren Nutzen aufweist.
Beim Gefangenendilemma ist es für beide Spieler beispielsweise (aufgrund der Tatsache, dass sie von der Entscheidung des anderen nichts wissen) eine dominante Strategie,
zu kooperieren und seinen Mitspieler zu verraten - auf diese Art und Weise erhält man
immer eine Strafmilderung, die entweder stark ausfällt (wenn der Mittäter schweigt)
oder schwach ausfällt (wenn der Mittäter seinerseits kooperiert).
Definition 3.1 Eine Strategie σi∗ ∈ Σi des Spielers i gilt als schwach
dominant, wenn gilt:
∀σi ∈ Σi ∧ σ-i ∈ Σ-i : Hi (σi∗ ∪ σ-i ) ≥ Hi (σi ∪ σ-i )
wobei σ-i = σ \ σi .
In anderen Worten: Die Auszahlung der Strategiemenge mit der
dominanten Strategie ist größergleich aller anderen Strategiekombinationen, für jede beliebige Wahl der anderen Mitspieler σ-i und für
jede eigene Alternative σi ∈ Σi .
18
Bei einer sogenannten »strikt dominanten Strategie« gilt das Gleiche; hier muss
die Strategie jedoch strikt größer sein. Es gilt also:
Definition 3.2 Eine Strategie σi∗ ∈ Σi des Spielers i gilt als strikt
dominant, wenn gilt:
∀σi ∈ Σi ∧ σ-i ∈ Σ-i : Hi (σi∗ ∪ σ-i ) > Hi (σi ∪ σ-i )
wobei σ-i = σ \ σi .
Die Auszahlung der Strategiemenge mit der dominanten Strategie
ist größer aller anderen Strategiekombinationen, für jede beliebige Wahl der anderen Mitspieler σj6= i und für jede eigene Alternative
σi ∈ Σi .
Das Gegenteil der hier angesprochenen strikt-dominanten Strategie ist eine sogenannte
»dominierte Strategie«, die - ungeachtet der Wahl der Mitspieler - niemals besser ist
als eine andere Strategie.
Wie die Beschreibung schon aussagt, sollte es stets vermieden werden, sogenannte dominierte Strategien zu benutzen. Das Wichtige ist es, solche domierten Strategien in
einem strategischen Spiel zu erkennen, identifizieren und dann als Wahlmöglichkeit in
Σi zu streichen.
Dieses Konzept der dominanten und dominierten Strategien kann man sehr gut verdeutlichen, wenn man das klassische »Schere, Stein, Papier«-Spiel betrachtet.
In seiner Urform mit den drei Symbolen Schere, Stein und Papier hat jedes Symbol ein
anderes Symbol, welches es schlägt; ein Symbol, von welchem es geschlagen wird und
sich selbst, was keins von Beidem zur Folge hat. Hier existieren weder dominante noch
dominierte Strategie.
Erweitert man das »Schere, Stein, Papier«-Spiel jedoch um ein viertes Symbol (Häufig
gewählt ist beispielsweise das Symbol »Brunnen«) wird dieses Gleichgewicht aufgehoben:[Rie15]
Beispiel 3.1 »Schere, Stein, Papier«-Variation
Bei der Variation von »Schere, Stein, Papier« mit vier Symbolen
(d.h. dem zusätzlichen Symbol »Brunnen«) sieht die Matrix ungefähr
so aus:
Schere Stein Papier Brunnen
Schere
(0,0)
(-1,1)
(1,-1)
(-1,1)
Stein
(1,-1)
(0,0)
(-1,1)
(-1,1)
Papier
(-1,1)
(1,-1)
(0,0)
(1,-1)
Brunnen (1,-1)
(1,-1)
(-1,1)
(0,0)
Tabelle 4: Matrixdarstellung der »Schere, Stein, Papier«-Variation
19
Bei der Betrachtung wird schnell klar, dass Schere und Stein jetzt
zweimal verlieren, während Brunnen zweimal gewinnt.
Wenn Spieler 1 für »Stein« und »Brunnen« die einzelnen Fälle
betrachtet, so wird klar, dass bei »Papier« und »Schere« Brunnen
und Stein völlig gleich sind, bei »Stein« oder »Brunnen« es jedoch
für Spieler 1 besser ist, Brunnen statt Stein zu wählen.
Stein ist daher immer eine schlechtere Strategie als die anderen
Wahlmöglichkeiten; Stein wird daher hier zu einer dominierten Strategie. Es gilt für Spieler 1:
∀σ1 ∈ Σ1 ∧ σ2 ∈ Σ2 : H1 (σ1∗ ∪ σ2 ) < H1 (σ1 ∪ σ2 )
für σ1∗ = {Stein}.
Wie bereits erwähnt, können dominierte Strategien bei der Analyse
eines Spiels gestrichen werden - da es um ökonomische Entscheidungssituationen geht ist die Wahl einer Möglichkeit welche allen
anderen Strategien immer unterlegen ist unsinnig. Es ergibt sich:
Schere
Papier
Brunnen
Schere
(0,0)
(-1,1)
(1,-1)
Papier
(1,-1)
(0,0)
(-1,1)
Brunnen
(-1,1)
(1,-1)
(0,0)
Tabelle 5: Matrixdarstellung der »Schere, Stein, Papier«-Variation
ohne Stein
Wie man hier sieht, hat sich die Ausgangssituation von »Schere, Stein, Papier« wiederhergestellt - nur mit dem Unterschied, dass
Stein durch Brunnen ersetzt wurde.
Durch wiederholte Streichung dominierter Strategien (sogenannter »iterierter Elimination«) wird das Spiel vereinfacht; nur die sinnvollen Entscheidungsmöglichkeiten bleiben übrig, was die Zahl der möglichen Strategiekombinationen deutlich reduzieren kann.
Bleiben durch wiederholtes iteriertes Eliminieren nur noch dominante Strategien übrig,
so spricht man bei diesen Strategien vom sogenannten Nash-Gleichgewicht.
3.1.1 Beste Antwort
Das größte Problem bei einem Mehrpersonenentscheidungsproblem (d.h. einem strategischen Spiel) ist die Unkenntnis darüber, wie sich die anderen Spieler verhalten werden.
Die sogenannte »beste Antwort« (oder auch »best reponse«) ist ein Verfahren, bei
dem zu jeder denkbaren Entscheidung der Mitspieler σj6= i das optimale Verhalten bestimmt wird; eine dominante Strategie ist immer die beste Antwort. Im Gegensatz zur
20
dominanten Strategie bezieht sich die beste Antwort nicht auf alle, sondern auf eine
Strategiekombination der Mitspieler.
3.2 Nash-Gleichgewicht
Zusammen mit der Definition der »besten Antwort« und der Definition der dominanten
Strategie ist es ziemlich einfach das sogenannte »Nash-Gleichgewicht« (respektive
»Nash-equilibrum«) zu definieren:
Definition 3.3 [LBS08] Eine Strategiekombination σ = (σ1 , . . . , σn )
ist ein sogenanntes schwaches »Nash-Gleichgewicht«, wenn gilt:
∀i ∈ I ∧ σi 6= σi0 : Hi (σi ∪ σ-i ) ≥ Hi (σi0 ∪ σ-i )
d.h., dass für alle Spieler i die Strategie σi die beste Antwort auf die
Strategien σ-i ist, wobei σ-1 = σ \ σi .
Auch hier gibt es wieder ein sogenanntes striktes Nash-Gleichgewicht, bei dem der
Operator anders ist:
Definition 3.4 [LBS08] Eine Strategiekombination σ = (σ1 , . . . , σn )
ist ein sogenanntes striktes Nash-Gleichgewicht, wenn gilt:
∀i ∈ I ∧ σi 6= σi0 : Hi (σi ∪ σ-i ) > Hi (σi0 ∪ σ-i )
Das Nash-Gleichgewicht wird »Gleichgewicht« genannt, da - wenn alle Spieler den Strategievorschlag des Nash-Gleichgewichts wählen - keiner der Spieler alleine ein besseres
Ergebnis für sich selbst erreichen kann; kein Spieler hat daher Interesse daran, an diesem Gewicht abzuweichen. Das Nash-Gleichgewicht ist daher eine vernünftige
Lösungsstrategie für alle Spieler.
Auch in vielen der bereits besprochenen Beispiele bestehen Nash-Gleichgewichte:
Beispiel 3.2 Gefangenen-Dilemma: Nash-Gleichgewicht
Wie bereits im Kapitel zu dominierten / dominanten Strategien erwähnt ist es für beide Spieler jeweils besser, den anderen zu verraten,
da bei Beiden somit die Gefängnisstrafe zumindest reduziert wird.
Wenn sich beide Spieler an dieses Nash-Gleichgewicht halten, dann
muss für die Strategie »Verraten« (V) folgendes gelten:
∀σ2 ∈ Σ2 : H1 ({V } ∪ σ2 ) ≥ H1 ({S} ∪ σ2 )
∀σ2 ∈ Σ2 : H2 ({V } ∪ σ1 ) ≥ H2 ({S} ∪ σ1 )
21
Wenn man die Werte durchrechnet, gilt:
H1 (σV,S ) ≥ H1 (σS,S ) ⇒ −1 ≥ −2
H1 (σV,V ) ≥ H1 (σS,V ) ⇒ −4 ≥ −6
√
√
Für H2 gilt analog das Gleiche → σV,V ist das Nash-Gleichgewicht
des Gefangenendilemmas.
Es gibt auch in der abgewandelten »Battle-of-Sexes«-Variation Nash-Gleichgewichte:
Beispiel 3.3 Battle-of-Sexes-Variation: Nash-Gleichgewicht
Im Battle-of-Sexes-Spiel mit den Studenten gibt es sogar zwei NashGleichgewichte - jeweils ein Student passt sich dem anderen an, während der Student seiner eigenen Vorliebe nachgeht - dies ist auch für
beide Spieler ein solches Gleichgewicht, von dem jeder nur verlieren
kann, wenn man davon abweicht.
Wenn sich beide Spieler an diese Nash-Gleichgewichte halten, dann
muss Folgendes gelten:
H1 (σA,A ) ≥ H1 (σA,B ) ≥ H1 (σB,A )
(1)
H1 (σB,B ) ≥ H1 (σB,A ) ≥ H1 (σA,B )
(2)
H2 (σB,B ) ≥ H2 (σB,A ) ≥ H2 (σA,B )
(3)
H2 (σA,A ) ≥ H2 (σA,B ) ≥ H2 (σB,A )
(4)
Mit den Auszahlungswerten:
√
3 ≥ 0 ≥ 0 bei (1) √
1 ≥ 0 ≥ 0 bei (2) √
3 ≥ 0 ≥ 0 bei (3) √
1 ≥ 0 ≥ 0 bei (4)
Auch hier stimmt die Überlegung: σB,B und σA,A sind
Nash-Gleichgewichte.
Es ist jedoch kein Zufall, dass bei beiden Beispielen ein Nash-Gleichgewicht besteht. Zu
genau diesem Problem findet sich in der Abhandlung von Nash aus dem Jahre 1951
Folgendes (sinngemäß):
Theorem 3.1 Jedes Spiel mit einer endlichen Anzahl Spielern und
Strategien hat mindestens ein Nash-Gleichgewicht. [Nas15]
22
Ein mathematischer Beweis dieses Theorems findet sich bspw. in einem Technical Report von Prof. Xiang und Prof. Brown der University of British Columbia[JLB15], geht
aber weit über den Umfang dieses Berichtes hinaus, weswegen dieses Theorem einfach
als gegeben hingenommen wird.
Eine große Einschränkung des Nash-Gleichgewichts ist natürlich die Annahme, dass alle
Spieler sich dazu rational verhalten müssen, d.h. sich gewinnorientiert verhalten - hier
werden weder Drohungen, Versprechen oder andere psychologische Beeinflussungen des
Gegners berücksichtigt.
Eine weitere Einschränkung des hier definierten Nash-Gleichgewichts ist es, dass es nur
bei reinen Strategien (siehe 2.1.2.1 auf Seite 13) funktioniert, auf diese Art und Weise
eine Lösung zu finden.
3.2.1 Rückwärts-Induktion
In den bisherigen Beispielen wurden die Nash-Gleichgewichte durch logisches Überlegen
identifiziert und über Rechnungen bestätigt - dies ist aber nicht immer möglich, insbesondere bei komplexeren Spielen. Hier ist es wichtig, über die Analyse des Spieles das
Spiel auf die Strategiemöglichkeiten der einzelnen Spieler zu reduzieren, die zu einem
Nash-Gleichgewicht führen - dieses Verfahren, welches nur bei Spielen in Extensivform
durchgeführt werden kann, nennt man Rückwärts-Induktion.[NM44]
Wie der Name schon sagt, geht man rückwärts an das Spiel heran - die letzten Entscheidungen d.h. die Entscheidungen zum Schluss des Spieles werden untersucht - und
jeweils die Aktion, die den Gewinn maximiert, gewählt - die andere entfernt. Hierzu wird
das Spiel in sogenannte Teilspiele zerlegt.
Bei der Rückwärtsinduktion geht man folgendermaßen vor:
1. Das Spiel wird in sogenannte Teilspiele zerlegt, die jeweils aus einem Entscheidungsknoten und den dazugehörigen Entscheidungen bestehen.
2. Das Teilspiel, welches zeitlich als Letztes gespielt wird wird ausgewählt.
3. In diesem Teilspiel wird die für einen bestimmten Spieler i beste Strategie gewählt, welche die höchste Auszahlung für i liefert und alle anderen Strategien
gestrichen. → Der Entscheidungsknoten von i nimmt den Wert der höchsten Auszahlung an, die Verästelung wird entfernt.
4. Man wählt das Teilspiel, welches zeitlich von einem Spieler j als Vorletztes gespielt wird und streicht - unter Berücksichtigung der vorherigen Punkte - wiederum
alle Strategien, die nicht die höchste Auszahlung für j 6= i liefern.
5. Das wird solange durchgeführt, bis man keine Strategie mehr streichen kann.
(Schleifenende)
23
Die so übrigen Strategiemengen sind Nash-Gleichgewichte - unter der Berücksichtigung,
dass sich alle Spieler rational verhalten. Dies kann auch grafisch dargestellt werden:
Beispiel 3.4 Auch hierzu kann man die extensive Version von der
»Kampf der Geschlechter«-Variation aus Beispiel 2.2 herangezogen
werden:
x1
x2
A
A
x4
B
B
A
x5
(3, 1)
x3
x6
(0, 0)
B
x7
(0, 0)
(1, 3)
Abbildung 6: Schritt 1: Spielbaum von ΓKDG∗
Hier wird das tiefste Teilspiel von links ausgewählt, welches Spieler
2 spielt (Entscheidungsknoten x2 ) und betrachten die Auszahlungsmengen für Spieler 2: 1 und 0.
x1
x2
A
A
x4
(3, 1)
B
B
x3
A
x5
x6
(0, 0)
(0, 0)
B
x7
(1, 3)
Abbildung 7: Schritt 2: Teilbaum x2 selektiert
Als nächstes sucht man die höchste Auszahlung für Spieler 2 (in diesem Fall 1) und reduziert den Knoten x2 auf seine Auszahlfunktion.
Hier wird das tiefste Teilspiel von links ausgewählt, welches Spieler
2 spielt (Entscheidungsknoten x2 ) und betrachten die Auszahlungsmengen für Spieler 2: 1 und 0.
24
x1
A
x2
B
(3, 1)
x3
A
B
x6
x7
(0, 0)
(1, 3)
Abbildung 8: Schritt 3: Teilbaum x2 ersetzt
Nachdem dieser Teilbaum direkt durch das Anfügen des Auszahlungswertes an x2 aufgelöst wurde, wird diesmal der Teilbaum x3 selektiert:
x1
A
x2
B
(3, 1)
x3
A
B
x6
x7
(0, 0)
(1, 3)
Abbildung 9: Schritt 4: Teilbaum x3 selektiert
Auch hier ist es für Spieler 2 nur sinnvoll, die Option B zu wählen (mit einer Auszahlung von 3), weswegen die Auswahloption A entfernt und an den Entscheidungsknoten
die
Auszahlungsmenge
gesetzt
wird:
x1
x2
A
B
(3, 1)
x3
(1, 3)
Abbildung 10: Schritt 5: Teilbaum x3 ersetzt
Für Spieler 1 ist die Entscheidung klar; die höhere Auszahlung
erhält er, wenn er A wählt, weswegen B gestrichen werden kann.
Aus der Rückwärtsinduktion ergibt sich, dass σA,B mit σ1 = {A} und
σ2 = {B} das Nash-Gleichgewicht ist, wenn Spieler 1 beginnt.
Durch Überlegung sieht man, dass es ein zweites Nash-
25
Gleichgewicht σB,A gibt, wenn Spieler 2 beginnt - die Rückwärtsinduktion deckt sich also mit der Vorhersage, die auf Basis des Spiels
in Normalform getroffen wurde.
3.3 Weitere Strategien
Bei einem Nash-Gleichgewicht wird bei jedem Spieler davon ausgegangen, dass rational
gedacht wird und gleichzeitig mit in die Entscheidung einbezogen wird, dass auch alle
anderen Spieler rational denken.
Meistens ist dies aber nicht der Fall. So gibt es in Spielen sowohl Versprechungen und Drohungen als auch »Strafen« für bestimmtes Verhalten durch andere Spieler
oder »Belohnungen« für ein bestimmtes Verhalten (was oft bei mehr als zwei Spielern
auftritt).
3.3.1 Max-Min-Strategie
Eine aus der Wirtschaft sehr bekannte Strategie ist die sogenannte »Max-Min-Strategie«.
Hier geht es darum, die beste Auszahlung (Max) bei schlechtesten Bedingungen (Min)
zu erzielen.[LBS08]
Diese Strategie wird beispielsweise von Spielern in Situationen angewendet, bei denen
alle Mitspieler eine Strategie spielen, die für diesen Spieler eine möglichst niedrige Auszahlung garantieren; hier hat der Spieler selbstverständliches großes Interesse daran,
seinen Schaden zu minimieren, d.h. die höchste Auszahlung zu erreichen.
Definition 3.5 Als σi± wird die Strategie bezeichnet, die höchste
Auszahlung bei schlechtesten Bedingungen erzielt.
Für alle anderen Spieler j ∈ I, j 6= i gilt:
∀σj ∈ Σj ∧ σi ∈ Σi ∧ σj 6= σj0 : Hi (σj ∪ σ-j ) ≤ Hi (σj0 ∪ σ-j )
(1)
Daraus folgt:
∀σi± ∈ Σi ∧ σ-i ∈ Σ-i : Hi (σi± ∪ σ-i ) ≥ Hi (σi ∪ σ-i ) und σi 6= σi± (2)
Aus (1) folgt, dass die gewählten Strategien aller anderen Spieler die
jeweils schlechteste Auszahlung für i liefern (Min).
Aus (2) folgt, dass die Funktion höchste Auszahlung liefert (Max).
Die Max-Min-Strategie kann damit als Funktion definiert werden:
MAXMIN(i) = return Hi (σi± ∪ σ-i )
26
Der Vorteil dieser Strategie liegt - auch wenn es vermutlich nur sehr wenige Situationen gibt, in denen es allen Spielern nicht um ihren eigenen Gewinn, sondern um den
größtmöglichen Schaden für i geht - darin, dass die Auszahlung für i, wenn er die MaxMin-Strategie anwendet, niemals unter den Wert MAXMIN(i) fallen wird.
Wenn MAXMIN(i) signifikant größer als die geringste Auszahlung von i im ganzen
Spiel ist, kann damit das Risiko für i deutlich minimiert werden - i arbeitet mit dieser Strategie nicht mehr auf den größten Gewinn, sondern auf den kleinsten Verlust
hin.
Beispiel 3.5
Beim Gefangenendilemma muss für Spieler 1 laut (1) beispielsweise
folgendes gelten:
∀σ1 ∈ Σ1 : H1 (σ1 ∪ σ2 ) ≤ H1 (σ1 ∪ σ20 )
Schon aus der Beschreibung des Spiels ergibt sich, dass σ2 = {V },
d.h. »Verraten« ist, da Spieler 1 so bei allen seiner möglichen Strategien der meiste Schaden zugefügt wird. Daher gilt:
∀σ1± ∈ Σ1 : H1 (σ1± ∪ {V }) ≥ Hi (σ1 ∪ {V })
Auch hier erschließt sich aus dem Spiel, dass σ1± = {V } sein muss,
da die Auszahlung von i in diesem Fall −4, im Fall von σ1 = {S}
aber −6 beträgt.
MAXMIN(1) ist damit hier −4.
3.3.2 Min-Max-Strategie
Analog dazu gibt es eine sogenannte »Min-Max-Strategie«, die der Spieler i beispielsweise als Strafe für ein vorheriges Spiel wählt - hier geht es darum, dass Spieler i die
Strategie wählt, die die höchste Auszahlung des anderen Spieler j minimalisiert.
Diese angestrebte minimale höchste Auszahlung des Spielers j ist - wie bereits oben
berechnet - MAXMIN(j).
Definition 3.6 Für σi∓ als Min-Max-Strategie gilt für σi∓ 6= σi :
∀σj+ ∈ Σj : Hj (σj+ ∪ σ-j ) ≥ Hj (σj ∪ σ-j )
(1)
wobei σj+ die höchste Auszahlung für j unter gegebenem σ-j darstellt.
∀σi , σi∓ ∈ Σi : Hj (σi∓ ∪ σj+ ∪ σ-i-j ) ≤ Hj (σi ∪ σj+ ∪ σ-i-j )
27
(2)
Aus (1) wird σj+ als unter Berücksichtigung der Strategien der anderen Spieler höchstmögliche Auszahlung von j definiert.
Aus (2) folgt, dass die Strategie σi∓ aus allen eigenen und Strategien
des Spielers j das minimale σj+ bewirkt, d.h. die minimale Maximalauszahlung für j liefert.
Auch diese Strategie kann als Funktion definiert werden:
MINMAX(i) = return Hi (σi∓ ∪ σj+ ∪ σ-i-j )
3.3.3 Min-Max-Theorem
Hier steht nicht - wie beim Nash-Gleichgewicht - die rationale und gewinnorientierte
Handlung aller Spieler im Vordergrund, sondern die Maximierung der eigenen Auszahlung bei schlechtesten Bedingungen aller Spieler (→ Max-Min-Strategie) sowie die Minimierung eben dieser Auszahlung anderer Spieler (→ Min-Max-Strategie).
John von Neumann sagt in seinem Werk von 1928 sinngemäß Folgendes[Neu28]:
Theorem 3.2 In jedem endlichen Nullsummenspiel mit zwei Spielern erhält jeder Spieler in einem Nash-Gleichgewicht eine Auszahlung, die gleich seinem MAXMIN und MINMAX-Wert ist.
Das kann leicht durch ein Beispiel nachgeprüft werden.
Beispiel 3.6 Wie im Abschnitt zum Nash-Gleichgewicht bewiesen
wurde, liegt das Nash-Gleichgewicht für das Gefangenendilemma bei
σV,V = (-4, -4). In Beispiel 3.5 wurde berechnet, dass sowohl MAXMIN(1) als auch analog MAXMIN(2) bei -4 liegen.
Durch Überlegung kann der Spieler 1 im Gefangenendilemma die
höchste Auszahlung des Gegners von −1 auf −4 minimalisieren, indem er ihn verrät ({V}); das Gleiche gilt auch für Spieler 2; daher
liegen sowohl MINMAX(1) als auch MINMAX(2) bei −4.
Für beide Spieler sind MAXMIN und MINMAX-Werte identisch
und liefern das Nash-Gleichgewicht σV,V = (-4, -4).
Damit bestätigt sich das Theorem für das Gefangenendilemma.
28
4 Anwendung von strategischen Spielen
Strategische Spiele werden - wie in der Einführung erwähnt - generell in verschiedensten sogenannten Mehrpersonenentscheidungsproblemen angewendet; diese treten
in verschiedensten Umfeldern auf. Strategische Spiele werden sowohl in der Ökonomie,
der Politik, der Biologie als auch in der Informatik zum Lösen von Entscheidungsproblemen benutzt.
Wie in vorherigen Kapiteln genannt, ist es hier wichtig, aus der konkreten Situation ein Modell zu erstellen, welches den nötigen Abstraktionsgrad aufweist, um in
ein Spiel in einer bestimmten Form umgewandelt werden zu können.
Bei der Konzeption eines Spiels müssen daher notwendigerweise mindestens folgende
Schritte durchgeführt werden:
1. Welche relevanten Entscheidungsträger gibt es in dem vorliegenden Mehrentscheidungsproblem?
2. Welches Problem ist konkret die Fragestellung?
3. Welche Entscheidungen können die einzelnen Entscheidungsträger konkret treffen?
4. Welcher Nutzen ist für die einzelnen Entscheidungsträger und die Entscheidungen
zu erwarten?
5. Wie kann dieser Nutzen geordnet und kardinalisiert werden, um miteinander
verglichen werden zu können?
6. Wie ist der zeitliche Ablauf der Entscheidungen? Gibt es einen Ablauf, oder
wird gleichzeitig entschieden?
7. Wissen die einzelnen Entscheidungsträger von den Entscheidungen anderer, oder
sind die Informationen nicht öffentlich?
8. Gibt es Ereignisse, die nicht von den Entscheidungen der Spieler abhängig sind,
sondern unter bestimmten Zufallswerten auftreten?
9. Treffen die Entscheidungsträger rein gewinnorientierte, d.h. rationale Entscheidungen oder ist es möglich, dass verschiedene Entscheidungsträger kooperieren?
Wie man schnell sieht, führen die einzelnen Fragen schnell zu den abstrahierten Werten,
die man für ein strategisches Spiel benötigt - aus Frage (1) ergeben sich die Spieler
des strategischen Spiels, aus Frage (2), (4) und (5) ergeben sich die jeweiligen Auszahlungsfunktionswerte der einzelnen Spieler.
29
Aus (2) und (3) werden die einzelnen Strategien der Spieler gebildet, die dann den
erzeugten Auszahlungsfunktionswerten mit Hilfe von (4) und (5) zugeordnet werden. Bei
Frage (6) wird die Form des Spiels bestimmt, d.h. es wird festgelegt ob es sich um
ein Spiel in Extensiv- oder Normalform handelt; bei Frage (7) wird danach gefragt, ob
es sich um ein Spiel mit vollkommener oder unvollkommener Information handelt.
Bei den Fragen (8) und (9) handelt es sich um Fragen danach, ob es gemischte Strategien gibt bzw. ein Spieler 0 (»Zufall«) existiert, der zufällig eingreift - beziehungsweise
ob Spieler kooperativ spielen (mit Drohungen, Versprechungen, Strafen, Belohnungen,
...) oder ob mehrheitlich rational, d.h. nur auf den eigenen Gewinn orientiert gespielt
wird.
Aus all diesen Werten und Antworten ist es nun möglich, ein strategisches Spiel zu
konstruieren. Das Ganze kann auch an einem trivialen Beispiel erklärt werden:
Beispiel 4.1 Zwei Studenten aus einer Studenten-WG, Kevin und
Bernd, haben zufällig an einem Sonntagabend beide Lust auf ein
Bier, stellen aber fest, dass im Kühlschrank nur noch eine Flasche
steht.
Dabei hat Bernd eine überragende Idee: Er schlägt vor, dass einfach
jeder einmal mit einem normalen, sechsseitigen Würfel würfelt und
derjenige, der die höhere Augenzahl gewürfelt hat, das Bier trinken
darf. Sollten Beide die gleiche Zahl würfeln, wird das Bier brüderlich
geteilt.
Hier kann nach der Form von oben ein strategisches Spiel
erstellt werden:
1. Es existieren zwei Entscheidungsträger: Spieler Bernd und Spieler Kevin.
2. Das Problem lässt sich mit der Frage umschreiben: »Wer bekommt das Bier?«
3. Die einzelnen Entscheidungsträger würfeln, und fällen somit
beide [zufallsbasiert] die Entscheidungen 1,2,3,4,5 oder
6.
4. Der Nutzen ist entweder ein Bier, kein Bier oder ein halbes
Bier.
5. Der Nutzen kann problemlos mit den Zahlen 0,
dinalisiert und geordnet werden.
6. Beide Spieler würfeln gleichzeitig.
30
1
2
und 1 kar-
7. Da gleichzeitig gewürfelt wird, weiß kein Spieler die Augen des
Gegners.
8. Der Würfelwurf ist zufällig und jede Augenzahl kommt mit
einer Wahrscheinlichkeit von 16 vor.
9. Den Entscheidungsträgern geht es hier um das Bier - es geht
hier daher um rationale Entscheidungen.
Aufgrund dieser Informationen wird definiert:
GBier = (Σ1 , Σ2 , H1 , H2 , I), wobei
I = {Spieler Bernd, Spieler Kevin}
Σ1 = Σ2 = {1, 2, 3, 4, 5, 6}
Man kann leicht feststellen, dass es 62 mögliche Strategiekombinationen von σ1,1 bis σ6,6 geben muss.
Die Auszahlungsfunktion lautet:

1 1


( 2 , 2 )
H1 (σx,y ) = H2 (σx,y ) = (1, 0)


(0, 1)
für x = y
für x > y
für x < y
Kevin
Die zugehörige 6 × 6-Matrix besitzt an der Hauptdiagonale jeweils
den Wert ( 12 , 21 ) und unterteilt die übrigen Felder in (1, 0) (rechte
obere Ecke) und (0, 1) (linke untere Ecke).
1
2
3
4
5
6
1
1 1
(2, 2)
(0, 1)
(0, 1)
(0, 1)
(0, 1)
(0, 1)
Bernd
2
3
(1, 0) (1, 0)
( 12 , 12 ) (1, 0)
(0, 1) ( 21 , 12 )
(0, 1) (0, 1)
(0, 1) (0, 1)
(0, 1) (0, 1)
4
(1, 0)
(1, 0)
(1, 0)
( 12 , 12 )
(0, 1)
(0, 1)
5
(1, 0)
(1, 0)
(1, 0)
(1, 0)
( 12 , 12 )
(0, 1)
6
(1, 0)
(1, 0)
(1, 0)
(1, 0)
(1, 0)
( 12 , 21 )
Tabelle 6: Matrixdarstellung von GBier
Entscheidend ist hier auch (8): Da es sich um gemischte Strategien
handelt, muss noch ein Vektor p für die
Wahrscheinlichkeitsverteilung angegeben werden (siehe Kapitel
2.1.2.1 auf Seite 13):
p1,1 = . . . = p1,6 = p2,1 = . . . = p2,6 = 16 .
31
Prinzipiell kann die Spieltheorie in jedem Gebiet angewendet werden, bei dem sich
Menschen gegenseitig beeinflussen und eine Entscheidungsfindung bei einer bestimmten
Problematik herbeigeführt werden muss. Im Kurzen wird genauer auf drei einzelne
Anwendungsbereiche eingegangen:
4.1 Anwendung in der Informatik
Der Bereich der Informatik ist vermutlich der Interessanteste, da es sich hier um das
eigene Fach handelt. Auch hier kommt die Spieletheorie zur Anwendung:
So wird bspw. beim »Secret Sharing« beispielsweise ein Geheimnis auf mehrere Personen aufgeteilt, dass jedoch nur alle Personen zusammen das Geheimnis rekonstruieren
können, aber keine Person einzeln. Hierzu gibt es Anwendungsfälle, wo die Spieltheorie dazu benutzt wird, bestimmte Nash-Gleichgewichte zu untersuchen, bei denen kein
Teilnehmer einer Koalition C einer Größe k alleine ein besseres Ergebnis erreichen kann,
was einer Modellierung des Secret-Sharing Problems entspricht[ADGH06]
Dieses - relativ abstrakte - Beispiel findet Anwendung bei der sogenannten »Secure
Multiparty Computation«, bei der es darum geht, den Abgleich von Daten zwischen
verschiedenen Systemen durchzuführen, ohne dabei alle Daten offenzulegen.[HT04] Dieses System kam 2008 erstmals in Dänemark sogar zur Anwendung.[BCD+ 09]
Etwas vereinfacht findet man das gleiche Szenario auch beim sogenannten »Millionärsproblem«, welches in [Yao82] formuliert wurde:
»Zwei Millionäre möchten müssen, welcher von Beiden reicher ist. Sie möchten allerdings
dem anderen nicht da genaue Vermögen verraten.«
Das Ganze ist an das »Secret-Sharing«-Problem angelehnt und bedient sich dem gleichen
Prinzip wie in [ADGH06] genannt. Eine algorithmische Lösung des Problems befindet
sich ebenfalls in [Yao82].
Ein anderes Spektrum von spieltheoretischen Problemen aus der Informatik bietet beispielsweise das Operations Research - hier wird die Spieltheorie beispielsweise dafür
benutzt, um eine Konfliktanalyse durchzuführen.
4.2 Anwendung in der Biologie
Auch wenn es abwegig klingt, so kommt die Spieltheorie auch in der Biologie zur Anwendung; insbesondere im Bereich der theoretischen Evolutionsbiologie.
Es gibt sehr einfache Modelle, die an die Beispiele aus vorherigen Kapiteln erinnern,
beispielsweise das sogenannte Falke-Taube-Spiel von Richard Dawkins[Daw78]:
32
Beispiel 4.2 Dawkins schreibt in [Daw78] Folgendes:
»Nehmen wir an, es gäbe in einer Population einer speziellen Art lediglich zwei Kampfstrategien, die als Falke
und Taube bezeichnet werden... Alle Bewohner unserer
hypothetischen Population sind entweder Falke oder Taube.«
Hiermit legt er die zwei Spieler fest (zwei Konkurrenten einer
bestimmten Art) sowie die wählbaren Strategiemöglichkeiten (Taube
und Falke).
Diese zwei Strategiemöglichkeiten werden so definiert, dass ein Falke sich eher aggressiv, eine Taube sich eher friedlich verhält.
Dies führt dazu, dass sich zwei Tauben ein Revier teilen, zwei
Falken sich jedoch zum gegenseitigen Nachteil bekämpfen - bei einer
Konfrontation Falke gegen Taube setzt sich der Falke durch und
die Taube muss auf ein schlechteres Revier ausweichen.
Konkurrent 2
Dies führt - wenn man den Nutzen kardinalisiert - zu folgender Matrix:
Konkurrent 1
Falke Taube
Falke (0, 0) (6, 2)
Taube (2, 6) (4, 4)
Tabelle 7: Matrixdarstellung von GF alkeT aube
Dieses Falke-Taube-Beispiel ist jedoch nur das einfachste Beispiel der Spieltheorie in
der Biologie.
Von höherem Interesse sind in der Biologie sogenannte »evolutionär stabile Strategien« nach John Maynard Smith[Smi82] - hier geht es darum, welches Verhalten man
langfristig erwarten kann, wenn die Spieler sich zwar nicht rational verhalten (wovon
man bei Tieren nicht ausgehen kann), aber erfolgreiches Verhalten vermehrt und nicht
erfolgreiches Verhalten vermindert wird.
Für diese Betrachtung kann man ebenfalls das Falke-Taube-Spiel heranziehen:
• In einer Population, in der es beispielsweise ausschließlich Tauben gibt, vermeh-
33
ren sich die Tauben stabil, da Tauben alle friedlich sind und in einem Revier
zusammenleben können.
• Sollte jedoch in diese Population ein Falke vordringen hat er aufgrund seines aggressiven Verhaltens keinerlei Problem, sich gegen die Tauben zu behaupten und
wird sich deswegen vermehren, wohingegen die Population der Tauben abnehmen
wird.
• Diese Vermehrung der Falken wird solange fortschreiten, bis der Falke durch sein
eigenes aggressives Verhalten gestört wird. In dieser Population können sich dann
Tauben - die sich bei einem Konflikt zurückziehen - sich wegen ihres friedlichen
Verhaltens stärker vermehren.
• An dem Punkt, wo sich diese Effekte einpendeln und aufheben, entsteht
eine stabile Population.
In der Evolutionsbiologie kommen interessante Aspekte und Effekte der Spieltheorie zum
Tragen.
So kann man beispielsweise längerfristig beobachten, dass dominante Strategien (siehe Definition 3.1 auf Seite 18) sich durchsetzen und dominierte Strategien aussterben.
Ebenfalls interessant ist die Tatsache, dass der stabile Zustand, der vom Anpassungsprozess her angestrebt wird, ein Nash-Gleichgewicht darstellt.
4.3 Anwendung in der Wirtschaft
Der wohl größte Anwendungsbereich der Spieltheorie ist die Wirtschaft mit Ihren einzelnen Entscheidungssituationen; sowohl in der Verhandlungstheorie, der Auktionstheorie als auch der Marktwirtschaft können strategische Spiele dazu benutzt werden,
bestimmte ökonomische Situationen zu beschreiben, Lösungsverfahren dafür zu bieten
und somit eine mathematische Hilfe zu sein.
Einfache Beispiele dafür lassen sich beispielsweise schon durch das Gefangenendilemma modellieren:
• Das bekannteste Reale-Welt-Beispiel für das Gefangenendilemma dürfte die Kartellregelung sein - in einem Kartell haben beispielsweise Unternehmen 1 und
Unternehmen 2 beide die Wahl, zu kooperieren und eine geringe Menge zu produzieren - kooperieren sie, erhalten Beide einen mittleren Gewinn, kooperiert ein
Unternehmen nicht, ist sein Gewinn sehr hoch; der Gewinn des anderen Unternehmens aber 0. Kooperieren beide nicht, ist der Gewinn für beide sehr niedrig.
• Ein weiteres Beispiel ist Beispielsweise die Rüstungspolitik der USA und UdSSR
während des kalten Krieges - hier haben beide Länder die Wahl, zu kooperieren
und abzurüsten, wo der Gewinn mittel ist; wenn ein Land kooperiert, das andere
aber nicht, ist das für das eine Land ein sehr hoher Gewinn, für das andere ein
hoher Verlust - Rüsten beide auf, ist der Gewinn für beide minimal.
34
Es gibt jedoch noch viel weitere Beispiele aus der Wirtschaft, bei denen die Spieltheorie
eingesetzt wird - darunter fallen wie bereits gesagt die Verhandlungstheorie und die
Marktwirtschaft:
4.3.1 Verhandlungstheorie
In der Verhandlungstheorie werden spieltheoretische Modelle dazu benutzt, Verhandlungssituationen zu lösen, ohne Informationen über die genauen Spielregeln (d.h. die
Strategien der einzelnen Spieler) zu besitzen.
In einem sogenannten Verhandlungsproblem geht es - wie der Name schon sagt - um
Verhandlungssituationen, wobei es hier sowohl um Verhandlungen zwischen Unternehmen, Lohnverhandlungen, Koalitionsverhandlungen als auch um die Verhandlung bei
einer Scheidung gehen kann.
Im Großen und Ganzen geht es in einem Verhandlungsspiel um einen bestimmten Gewinn, der verteilt werden soll. Eine Nicht-Einigkeit ist als Lösung eher inakzeptabel, es
wird eine Verteilung gesucht, bei der beide Partner eine Einigung erzielen können.
4.3.2 Marktwirtschaft
Ein weiterer sehr oft vorkommender Fall der Spieltheorie ist die Marktwirtschaft, bei
der es sowohl um das Zusammenspiel einzelner Unternehmen, aber vor allem auch um
das Zusammenspiel zwischen den Unternehmen und dem Kunden geht.
In Kapitel 2.1.2.3 auf Seite 16 wurde schon konkret angesprochen, welche Vor- und
Nachteile der erste Zug in solchen marktwirtschaftlichen Situationen haben kann.
Ein konkretes Beispiel für eine solche marktwirtschaftliche Situation ist beispielsweise
das klassische Markteintrittsspiel[BEG10, S. 108], bei dem es darum geht, dass eine
bestimmte Firma 1 überlegt, dem Markt beizutreten, an dem Schon eine Firma 2 agiert wenn Firma 1 zutritt, kann Firma 2 entweder aggressiv oder kooperativ reagieren.
Beispiel 4.3 »Markteintrittsspiel« Wie eingangs erklärt, handelt es sich um 2 Firmen: Firma 1, die sich überlegt, in den Markt
einzutreten; sowie Firma 2, welche eine Monopolstellung innehat.
Entschließt sich Firma 1 dazu, in den Markt nicht einzutreten, dann verdient Firma 2 weiterhin sehr hohe Profite; Firma
1 dagegen verdient weniger Geld als im neuen Markt.
Entschließt sich Firma 1 dazu, in den Markt einzutreten, dann
kann Firma 2 entweder aggressiv gegen Firma 1 vorgehen (wo
Firma 2 die Preise derartig drückt, dass Beide Firmen keinen
Gewinn machen) oder kooperativ mit Firma 1 umgehen (wobei
35
Beide dann einen mittleren Gewinn machen.)
In Spielbaumdarstellung sieht das folgendermaßen aus:
x1
x2
E
A
x4
(0, 0)
NE
K
x3
(1, 5)
x5
(2, 2)
Abbildung 11: Spielbaum von ΓM arkteintritt
Das Nash-Gleichgewicht dieses Markteintrittspieles liegt bei der Entscheidung, in den
Markt einzutreten, woraufhin kooperiert wird - Firma 2 würde sich sonst nur schaden;
die Drohung mit der Entscheidung »A« ist daher unglaubwürdig.
36
Abbildungsverzeichnis
1
2
3
4
5
6
7
8
9
10
11
Spielbaumdarstellung von GGD . .
Spielbaumdarstellung von GKDG∗ .
Spielbaumdarstellung von GElf meter
Spielbaumdarstellung von ΓKDG∗ .
Spielbaumdarstellung von ΓW ürf el .
Rückwärtsinduktion: Schritt 1 . . .
Rückwärtsinduktion: Schritt 2 . . .
Rückwärtsinduktion: Schritt 3 . . .
Rückwärtsinduktion: Schritt 4 . . .
Rückwärtsinduktion: Schritt 5 . . .
Spielbaum von ΓM arkteintritt . . . .
i
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5
5
8
11
12
24
24
25
25
25
36
Tabellenverzeichnis
1
2
3
4
5
6
7
Matrixdarstellung
Matrixdarstellung
Matrixdarstellung
Matrixdarstellung
Matrixdarstellung
Matrixdarstellung
Matrixdarstellung
von GGD . . . . . . . . . . . . . . .
von GKDG∗ . . . . . . . . . . . . . .
von GElf meter . . . . . . . . . . . . .
der »Schere, Stein, Papier«-Variation
der »Schere, Stein, Papier«-Variation
von GBier . . . . . . . . . . . . . . .
von GF alkeT aube . . . . . . . . . . . .
ii
. . .
. . .
. . .
. . .
ohne
. . .
. . .
. . . .
. . . .
. . . .
. . . .
Stein
. . . .
. . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6
6
8
19
20
31
33
Literatur
[ADGH06] Abraham, Ittai ; Dolev, Danny ; Gonen, Rica ; Halpern, Joe: Distributed computing meets game theory. In: Proceedings of the twenty-fifth annual
ACM symposium on Principles of distributed computing - PODC '06, ACM
Press, 2006, 53–62
[Axe80] Axelrod, Robert: Effective Choice in the Prisoner’s Dilemma. In: The
Journal of Conflict Resolution 24 (1980), Nr. 1. http://www.jstor.org/
stable/173932
[BCD+ 09] Bogetoft, Peter ; Christensen, Dan L. ; Damgård, Ivan ; Geisler,
Martin ; Jakobsen, Thomas ; Krøigaard, Mikkel ; Nielsen, Janus D.
; Nielsen, Jesper B. ; Nielsen, Kurt ; Pagter, Jakob ; Schwartzbach, Michael ; Toft, Tomas: Secure Multiparty Computation Goes Live.
Version: 2009. http://dx.doi.org/10.1007/978-3-642-03549-4_20. In:
Financial Cryptography and Data Security. Springer Science + Business
Media, 2009. – DOI 10.1007/978–3–642–03549–4_20, 325–343
[BEG10] Berninghaus, Siegfried K. ; Ehrhart, Karl-Martin ; Güth, Werner: Strategische Spiele. Springer Berlin Heidelberg, 2010. http://dx.
doi.org/10.1007/978-3-642-11651-3.
http://dx.doi.org/10.1007/
978-3-642-11651-3
[Daw78] Dawkins, Richard: Das egoistische GEN. Springer Berlin Heidelberg, 1978.
http://dx.doi.org/10.1007/978-3-642-66899-9. http://dx.doi.org/
10.1007/978-3-642-66899-9
[HT04] Halpern, Joseph ; Teague, Vanessa: Rational secret sharing and multiparty computation. In: Proceedings of the thirty-sixth annual ACM symposium
on Theory of computing - STOC '04, ACM Press, 2004, 623–632
[JLB15] Jiang, Albert X. ; Leyton-Brown, Kevin: A Tutorial on the Proof of the
Existence of Nash Equilibria. http://www.cs.ubc.ca/cgi-bin/tr/2007/
TR-2007-25.pdf. Version: 2007 (abgerufen am 17.06.2015)
[LBS08] Leyton-Brown, Kevin ; Shoham, Yoav: Essentials of Game Theory: A Concise Multidisciplinary Introduction. In: Synthesis Lectures on
Artificial Intelligence and Machine Learning 2 (2008), jan, Nr. 1, 1–
88. http://dx.doi.org/10.2200/s00108ed1v01y200802aim003. – DOI
10.2200/s00108ed1v01y200802aim003
[LM88] Lieberman, Marvin B. ; Montgomery, David B.: First-mover advantages.
In: Strat. Mgmt. J. 9 (1988), Nr. S1, 41–58. http://dx.doi.org/10.1002/
smj.4250090706. – DOI 10.1002/smj.4250090706
iii
[Mad87] Madison, James: Vices of the Political System of the United States. In:
The Founders’ Constitution Bd. 1. The University of Chicago Press, 1982
[1787], Kapitel 5
[Nas15] Nash, John: Non-Cooperative Games. In: Annals of Mathematics 54 (1951
(abgerufen am 17.06.2015)), sep, Nr. 2, 286–295. http://www.jstor.org/
stable/1969529?origin=JSTOR-pdf
[Neu28] Neumann, John von:
Zur Theorie der Gesellschaftsspiele.
In:
Mathematische Annalen 100 (1928), dec, Nr. 1, 295–320. http://dx.doi.
org/10.1007/bf01448847. – DOI 10.1007/bf01448847
[NM44] Neumann, John von ; Morgenstern, Oskar: Theory of games and
economic behavior. Princeton University Press, 1944
Schnick-Schnack-Schnuck
(Knobeln).
[Rie15] Rieck,
Christian:
http://www.spieltheorie.de/Spieltheorie_Grundlagen/
schnick-schnack-schnuck.htm, 2006 (abgerufen am 17.06.2015)
[Smi82] Smith, John M.: Evolution and the Theory of Games. Cambridge, UK :
Cambridge University Press, 1982
[Tuc83] Tucker, A. W.: The Mathematics of Tucker: A Sampler. In: The Two-Year
College Mathematics Journal 14 (1983), jun, Nr. 3, 228. http://dx.doi.
org/10.2307/3027092. – DOI 10.2307/3027092
[Yao82] Yao, Andrew C.:
Protocols for secure computations.
In: 2013
IEEE 54th Annual Symposium on Foundations of Computer
Science 0 (1982), S. 160–164.
http://dx.doi.org/http:
//doi.ieeecomputersociety.org/10.1109/SFCS.1982.88. –
DOI
http://doi.ieeecomputersociety.org/10.1109/SFCS.1982.88. – ISSN 0272–
5428
iv
Selbstständigkeitserklärung
Hiermit versichern wir, dass wir die vorliegende Seminararbeit selbstständig verfasst und
keine anderen als die angegebenen Quellen und Hilfsmittel benutzt haben.
Alle Ausführungen, die anderen veröffentlichten oder nicht veröffentlichten Schriften
wörtlich oder sinngemäß entnommen wurden, haben wir kenntlich gemacht.
Aalen, den
Knödler, Markus
Mader, Michael
Meier, Nico
Wehrenberg, Stefan
v

AUFWÄRMEN 1: Passen und Annehmen in offener Stellung

intraclub 2015 - Tennisclub Lerchenberg

Einladung Senioren-Blitz 2016

Circus Grandioso - Regelerweiterungen für Profis 1

KSM Unihockey - OSZ Hindelbank

SCHLUSSTEIL: Raute gegen 2-2-System

AUFWÄRMEN 1: Kasten-Passen

AUFWÄRMEN 2: Flotte Passstaffel

Ausschreibung - Hessische Schachjugend

3. offizielle „Ciao Sepp“ Weltmeisterschaft