2-PERSONEN-NULLSUMMENSPIELE

6 - 1
Teil 6 2-Personen-Nullsummenspiele, Bimatrixspiele
===================================================
Wir hatten in Teil 1 das folgende Matrixspiel untersucht:
I
II
links rechts
------------oben |
2
-2
|
|
|
unten | -1
1* |
-------------
Spielmatrix A
Gewinn für I
= Verlust für II
⇒ Nullsummenspiel
Wir hatten festgestellt, wie vorsichtige Spieler sich verhalten
werden: Spieler I wird unten ziehen, dort gewinnt er mindestens -1
(d.h. er verliert höchstens 1). Spieler II wird rechts ziehen,
auch er verliert dann höchstens 1. Als Spielergebnis kommt dann
also die untere rechte 1 heraus, und Spieler I gewinnt eine
Einheit.
Dieses Ergebnis ist jedoch problematisch, und zwar weniger in dem
Sinne, daß es ungerecht wäre, sondern in der Hinsicht, daß es
instabil ist.
Zwar wird Spieler I vermutlich zufrieden mit dem Ergebnis sein,
Abweichen von seiner Strategie nach oben würde ihm obendrein
schaden. Aber Spieler II wird mit dem Ergebnis unzufrieden sein.
Ihm würde Abweichen nach links nützen: Statt eine Einheit zu
verlieren, gewinnt er eine Einheit.
Wenn Spieler I das jedoch vorhersieht, wird er lieber oben ziehen,
was aber auch Spieler II sich denken kann, der dann...
Man sieht: Dieses Spiel hat, wenn man es häufiger spielt, alle
Anlagen zur Instabilität.
Es gibt Spielmatrizen, die in ihrer Struktur weniger kompliziert
sind:
II
--------| 1* , 2 |
I
|
|
| 0 , 3 |
--------Wenn die Spieler dieses Spiel einige Male spielen (und sich nicht
völlig irrational verhalten), so werden sie zweifellos ihre
6 - 2
jeweils erste Strategie spielen. Dies gilt auch für Spieler II,
obgleich der eine Einheit verliert, aber rechts verliert er mehr.
Dieses Spiel ist determiniert, eine Spieleigenschaft, die sich auf
zweifache Weise beschreiben läßt:
Ein vorsichtiger Spieler I wird oben spielen, denn dort gewinnt er
mindestens 1 (gegen 0, die unten resultieren könnte): Der untere
Spielwert dieses Spiels ist 1.
Ein vorsichtiger Spieler II wird links spielen, denn dort verliert
er höchstens 1 (gegen 3, die er rechts verlieren könnte), der
obere Spielwert dieses Spiels ist auch 1.
Bei diesem Spiel stimmen unterer und oberer Spielwert überein.
Betrachten wir andererseits das wahrscheinliche Spielergebnis, die
Position (1,1) der Spielmatrix: Das Matrixelement a11=1 ist das
Maximum der ersten Spalte und das Minimum der ersten Zeile. Dies
spiegelt die Tatsache wieder, daß beide Spieler sich nur schaden,
wenn sie von ihrer vorsichtigen Strategie abweichen.
Das Matrixposition (1,1) ist das, was man einen Sattelpunkt nennt:
Weichen wir vom Sattelpunkt in horizontaler Richtung ab, so
steigen die Einträge, weichen wir in vertikaler Richtung ab, so
fallen die Werte.
Was wir an diesem Beispiel beobachtet haben, wollen wir allgemein
festhalten:
Determinierte Matrixspiele
Ein 2-Personen-Nullsummenspiel ist durch eine Spielmatrix A gegeben, deren Einträge die Gewinnzahlen von Spieler I sind (negative
Einträge in A sind als Verluste von Spieler I zu verstehen).
Die Strategien von Spieler I entsprechen den Zeilen der Matrix.
Die Strategien von Spieler II entsprechen den Spalten der Matrix.
Diese Strategien sind die sogenannten reinen Strategien im Kontrast zu den gemischten Strategien, die wir später untersuchen
werden.
Der untere Spielwert (untere Garantiewert) c ist der Mindestgewinn
von I: Spieler I kann durch Einsatz eigener Strategien erreichen,
mindestens c zu bekommen.
Spieler I garantiert diesen unteren Spielwert durch Benutzen
seiner Maximin-Strategie: Er wählt die Zeile, für die das Minimum
maximal ist, also
c = max min aij
i
j
6 - 3
Der obere Spielwert (obere Garantiewert) C ist der Höchstverlust
von II: Spieler II kann durch Einsatz eigener Strategien
erreichen, daß er höchstens C verliert (daß also I höchstens C
gewinnt).
Spieler II garantiert den oberen Spielwert durch Benutzen seiner
Maximin-Strategie: Er wählt die Spalte, für die das Maximum minimal ist, also
C = min max aij
j
i
Offensichtlich gilt
----------| c ≤ C |
-----------
Das Spiel heißt determiniert (in reinen Strategien), falls
Beim ersten Beispiel war
Beim zweiten Beispiel war
c = C
c = -1 , C = 1
c = C = 1
Satz (Sattelpunkte)
Ein Matrixspiel ist determiniert genau dann, wenn es einen
Sattelpunkt hat, d.h. ein Strategienpaar (i0,j0) mit der Eigenschaft:
---------------------| aij0 ≤ ai0j0 ≤ ai0j |
---------------------für alle Strategien i und j.
Beweis:
i) Sei (i0,j0) Sattelpunkt der Matrix.
j0
---------------|
(-)
|
|
|
|
i0 |--(+)-- * --(+)-|
|
|
|
|
(-)
|
---------------Dann gilt (warum?):
c = max min aij = ai0j0
i
j
,
C = min max aij = ai0j0
j
i
Also gilt c = C , und das Spiel ist determiniert.
6 - 4
ii) Sei das Spiel determiniert: c = C
Dann gibt es i0 und j0 mit
min ai0j = c = C = max aij0
j
i
Nun ist einerseits
aij0 ≤ max aij0 = min ai0j ≤ ai0j0
i
j
andererseits
ai0j ≥ min ai0j = max aij0 ≥ ai0j0
j
i
woraus folgt
aij0
≤
ai0j0
≤
ai0j
d.h.(i0,j0) ist ein Sattelpunkt des Spiels.
//
------------------------------------------------------------Der letzte Satz beschreibt zur Zufriedenheit determinierte Spiele,
aber er hilft uns nicht bei unserem ersten Beispiel, einem Spiel,
das inhärent instabil ist und den Anschein hat, bei häufiger Wiederholung chaotische Ergebnisse zu produzieren.
I
II
q
1-q
-------------p |
2
-2
|
|
|
1-p | -1
1
|
--------------
Wir wollen ein Konzept vorstellen, mit der man auch Spiele dieser
Art rational handhaben kann: Wir stellen uns vor, die Spieler
wählen ihre Aktion bei jeder Spielpartie zufällig. Allerdings auch
nicht willkürlich, sondern gemäß gewisser Wahrscheinlichkeiten,
über die sich die Spieler vorher Gedanken machen.
Wählt beispielsweise Spieler I für sich die Wahrscheinlichkeit
p=1/3, so macht er damit Folgendes: Vor jeder Partie würfelt er
insgeheim für sich. Fällt 1 oder 2, so zieht er oben, fällt 3,4,5
oder 6, so zieht er unten. - Entsprechend wird Spieler II seine
Wahrscheinlichkeit q wählen, gemäß der er links oder rechts zieht.
Die Frage ist: Hat diese vorgeschlagene Zufallsspielerei Erfolgschancen gegen andere (Meta-)Strategien, die vielleicht nach psychologischen Gesichtspunkten oder noch anders gewählt werden, und
6 - 5
falls die zufallsgesteuerte Strategienwahl sinnvoll ist: Wie
sollten die Spieler ihre Wahrscheinlichkeiten wählen?
Wir prüfen das bei aktuellen Beispiel nach: Spieler I und II
wählen jeder ihre Wahrscheinlichkeit p bzw. q. Dann errechnet sich
der mittlere Gewinn für Spieler I:
p*[2q -2*(1-q)] + (1-p)*[-q + (1-q)] = 2p*(2q-1) + (1-p)*(1-2q)=
= (1-2q)*(1-3p)
Aus dem letzten Term folgt ganz klar: Spieler I wählt p=1/3.
Denn dann ist sein mittlerer Gewinn Null. Bei allen anderen p
könnte Spieler II sein q hingegen so einrichten, daß der mittlere
Gewinn von I negativ würde.
Mit einem analogen Argument wird Spieler II q=1/2 wählen.
Wenn also die Spieler zufällig nach dem vorgeschlagenen Wahrscheinlichkeitsprinzip spielen, dann sinnvollerweise so:
1/3
I
2/3
II
½
½
------------|
2
-2
|
|
|
| -1
1
|
-------------
Wenn die Spieler sich beide so verhalten, so hat jeder den
mittleren Gewinn Null zu erwarten. Dies ist ein Resultat, das für
jeden der beiden Spieler akzeptabel scheint.
Aber trotzdem bleibt die Frage: Ist dieses Resultat auch stabil,
oder könnte einer der beiden Spieler mit einer psychologisch
hinreichend raffinierten Strategie mehr für sich erwarten als
Null? - Die Antwort ist: Nein.
Nehmen wir an, Spieler I hält sich an sein Zufallsprinzip mit
p=1/3. Wenn nun Spieler II bei einer Partie aufgrund einer beliebig raffinierten Strategie links spielt, so bekommt Spieler I im
Mittel
1/3*2 + 2/3*(-1) = 0
also Null. Ebenso bekommt er Null, wenn Spieler II rechts spielt.
Also: Keine Metastrategie gibt Spieler II einen höheren mittleren
Gewinn als die Zufallsstrategie mit den von uns berechneten
Wahrscheinlichkeiten. Entsprechendes gilt für Spieler I.
Die hier erörterten Dinge wollen wir nun allgemein notieren.
6 - 6
Wir werden sehen, daß die Berechnung der Wahrscheinlichkeiten
dabei mit linearer Programmierung gemacht werden kann.
Definition (gemischte Strategien)
Sei gegeben eine (m,n)-Spielmatrix
die Spieler I und II sind Vektoren
(q1,...,qn) mit
m
pi ≥ 0 , ∑ pi = 1
i=1
A. Gemischte Strategien für
p = (p1,...,pm) und q =
n
qj ≥ 0 , ∑ qj = 1 .
j=1
und
Die Zahlen pi bzw. qj sind zu verstehen als Wahrscheinlichkeiten,
mit denen die Spieler I bzw. II bei einer Spielpartie ihre i-te
Zeile bzw. j-te Spalte wählen.
Wählen die Spieler gemischte Strategien p bzw. q, so errechnet
sich der mittlere Gewinn von Spieler I aus
m
n
∑ ∑ aij*pi*qj
i=1 j=1
Dieser Ausdruck kann mit Matrixnotation kompakt geschrieben werden:
-----------------------------|
m
n
|
T
|
∑ ∑
aij*pi*qj = p *A*q |
| i=1 j=1
|
-----------------------------[ Hier benutzen wir bei pT ausnahmsweise ein Transponiertzeichen,
um anzudeuten, daß die Vektoren p und q unterschiedlich orientiert
sind. ]
Genauso wie bei reinen Strategien definieren wir auch bei
gemischten Strategien den unteren und oberen Spielwert als Gewinn,
den die Spieler sich jeweils aus eigener Kraft garantieren können:
w = max min
p
q
Offenbar gilt
pT*A*q
W = min max
q
p
w
≤
pT*A*q
W
Nehmen wir die Garantiewerte c und C der reinen Strategien mit in
die Ungleichungskette, so gilt (warum?)
6 - 7
----------------------| c ≤ w ≤ W ≤ C |
----------------------Beim letzten Beispiel ist die mittlere Ungleichung dieser Kette
sogar eine Gleichung:
c
≤
w
≤
W
≤
C
-1 <
0
=
0
<
1
Dieses Spiel war in reinen Strategien nicht determiniert. Aber in
gemischten Strategien ist das Spiel determiniert: Was die Spieler
sich jeweils aus eigener Kraft sichern können, stimmt überein.
Insofern hat dieses Spiel in gemischten Strategien eine Lösung,
von der kein Spieler einen rationalen Grund hat abzuweichen.
Wir wollen zeigen, daß dies bei jedem Matrixspiel so ist.
Für die folgenden Überlegungen unterstellen wir, daß die Spielmatrix A nur positive Einträge hat:
A > 0
Wäre das nicht der Fall, so könnte man einfach auf alle Matrixfelder eine entsprechende einheitliche positive Zahl hinzuaddieren.
Denn diese Manipulation verschiebt zwar die Auszahlung zugunsten
von Spieler I, hat aber keinen Einfluß auf die optimalen Strategien beider Spieler (warum nicht?).
Wir untersuchen zunächst, was die Spieler mit gemischten Maximinstrategien erreichen können (was nicht die einzigen, aber die
nächstliegenden Metastrategien sind).
Nehmen wir an, Spieler I hat eine gemischte Strategie p gewählt.
Wir fragen uns, welcher Gewinn ist ihm damit garantiert ist.
Wir nennen diesen Gewinn für den Moment G(p), dieses G(p) werden
wir in mehreren Schritten ausrechnen:
G(p) =
min pT*A*q
q
=
m
n
min ∑
∑ aij*pi*qj
q i=1 j=1
n
= min ∑
q j=1
m
∑ aij*pi
i=1
* qj
Die Doppelsumme ist ein mit einem Wahrscheinlichkeitsvektor
gewichtetes inneres Produkt, welches zu minimieren ist.
Das Minimum erhalten wir, wenn wir die kleinste runde Klammer voll
(also mit Gewicht 1) gewichten (warum?).
6 - 8
Der Minimalwert ist dann der Wert der kleinsten Klammer. Also
G(p)
=
m
min ∑ aij*pi
j i=1
Spieler I sucht nun die gemischte Strategie p, die ihm seinen
Garantiegewinn G(p) maximiert:
|
|
|
|
|
|
max
G
|
m
|
G = min ∑ aij*pi
|
j i=1
|
|
p ist gemischte Strategie |
|
|
|
|
|
|
max
G
oder
G
≤
∑ aij*pi
i
alle j
∑ pi = 1 , pi ≥ 0
|
|
|
|
|
|
Und letzteres ist nichts anderes als ein lineares Programm für das
gesuchte p !
Dieses LP wollen wir noch in handlichere Form bringen. Wir setzen
-----------| xi = pi/G |
-----------Man beachte: Da wir positive Koeffizientenmatrix A unterstellt
haben, können wir sicher sein, daß der Garantiegewinn G für Spieler I positiv ist, daß wir also nicht durch 0 dividieren.
Aus der Substitution folgt:
-- m ------------|
∑ xi = 1/G |
- i=1 -----------Maximieren von G ist gleichbedeutend mit Minimieren von ∑ xi, also
6 - 9
(P):
----------------------------------|
m
|
|
min
∑ xi
|
|
i=1
|
|
m
|
|
∑ aij*xi ≥ 1 ; j=1,...,n
|
|
i=1
|
|
xi ≥ 0
|
-----------------------------------
Da A eine positive Matrix ist, hat das lineare Programm zulässige
Lösungen. Außerdem ist der Zielfunktionswert (durch 0) beschränkt.
Also hat (P) eine Optimallösung x.
Aus der Lösung x von (P) können wir die Maximin-Strategie und den
Garantiewert für den Spieler I rekonstruieren:
------------------------| pi = xi/∑ xi i=1,...,m |
|
|
|
w = 1/∑ xi
|
------------------------[ man beachte:
Maximinstrategie für Spieler I
Garantiewert für Spieler I
w = max G = 1/∑ xi ]
Wir haben nun die komplette Theorie für den Spieler I vorgeführt.
Die entsprechende Theorie für Spieler II führen wir nicht noch
einmal vor, wir geben einfach das Ergebnis an:
(D):
-------------------------------|
n
|
|
max
∑ yj
|
|
j=1
|
|
n
|
|
∑ aij*yj ≤ 1 i=1,...,m
|
|
j=1
|
|
yj ≥ 0
|
--------------------------------
Hier zeigt sich: Das lineare Programm (D) ist das zu (P) duale
Programm! Den Spielern sind also zueinander duale Programme zugeordnet.
Aus der Lösung y von (D) können wir die Maximin-Strategie und den
Garantiewert für den Spieler II ausrechnen:
6 - 10
-------------------------| qj = yj/∑ yj j=1,...,n |
|
|
|
W = 1/∑ yj
|
--------------------------
Maximinstrategie für Spieler II
Garantiewert für Spieler II
Wir betonen die Symmetrie der Theorie: Jeder der beiden Spieler
erhält seine (gemischte) Maximinstrategie als Optimallösung eines
linearen Programms. Die beiden linearen Programme bilden ein duales Paar.
Aus der Dualitätstheorie folgt, daß die Garantiewerte der Spieler
übereinstimmen:
----------------------| c ≤ w = W ≤ C |
----------------------[man beachte:
w = ∑ xi = ∑ yi = W ]
Hinsichtlich der Frage, ob es für die Spieler sinnvoll ist, nach
irgendwelchen raffinierten Metastrategien zu suchen, haben wir
jetzt Klarheit: Mehr als mit ihren Maximinstrategien können die
Spieler mir irgendeiner anderen Strategie auch nicht erreichen.
Unser zunächst willkürlich erscheinender Ansatz, gemischte Maximinstrategien zu untersuchen, ist im Nachhinein voll gerechtfertigt.
Ebenfalls hat sich unser anfänglicher Verdacht aufgelöst, Matrixspiele könnten instabil sein. Gemischte Maximinstrategien führen
bei rationalem Verhalten der Spieler zu einer absolut stabilen
Lösung.
Beispiel
Wir rechnen unser Beispiel
1/3
I
2/3
II
½
½
------------|
2
-2
|
|
|
| -1
1
|
-------------
mit der bereits gut bekannten Lösung ein weiteres mal unter
Benutzung unserer Theorie.
Wir haben die Wahl zwischen den linearen Programmen (P) und (D),
und wir entscheiden uns für (D), denn dort benötigen wir keine
erste Phase.
6 - 11
Die Spielmatrix A hat negative Einträge. Wir addieren die Zahl 2
zu allen Zahlen. Das macht die Matrix zwar nicht komplett positiv,
aber es sichert positiven Garantiewert für Spieler I, und die 0 im
Tableau vereinfacht die folgende Rechnung ein wenig:
4
0
1
3
A' =
Das Tableau des dualen Programms ist:
y0
y1
y2
s1
s2
---------------------------[1]
-1
-1
0
0 | [0]
4
0
[1]
0 | 1
1
3*
0
[1] | 1
----------------------------[3]
-2
0
0
1 | [1]
4*
0
[1]
0 | 1
1
[3]
0
1 | 1
----------------------------[6]
0
0
1
2 | [3]
[4]
0
1
0 | 1
0 [12] -1
4 | 3
optimal
Die Optimallösung von (D) ist:
y = (y1,y2) = (1/4,1/4)
Die Optimallösung von (P) erhalten wir aus der Zielfunktionszeile:
x = (x1,x2) = (1/6,2/6)
Die optimalen Strategien erhalten wir durch Normieren dieser
Lösungen auf 1:
---------------------------------------| q = (q1,q2) = (1/2,1/2) für Spieler II |
|
|
| p = (p1,p2) = (1/3,2/3) für Spieler I
|
---------------------------------------und dies sind die uns bereits bekannten Strategien.
Den (gemeinsamen) Garantiewert erhalten wir folgendermaßen. Es ist
∑ yi = 2/4 = 1/2
,
also
W' = 1/∑ yi = 2
6 - 12
Von W' müssen wir aber den Wert 2 abziehen, um die anfängliche
Addition zur Matrix A wieder zu kompensieren. Also erhalten wir
den uns für dieses Spiel bekannten Spielwert:
----------------| w = W = 0 |
-------------------------------------------------------------------------------Nullsummenspiele haben eine klare Regel: Das, was der andere
gewinnt, verliert man selbst. Manchmal ist die Wirklichkeit aber
komplizierter:
Beispiel (Gefangenendilemma)
Zwei Gefangene, die sich miteinander nicht verständigen können,
wissen:
Wenn sie beide gestehen, dann sitzen sie beide 6 Jahre.
Wenn genau einer gesteht, so kommt der (als Kronzeuge) frei, der
andere sitzt dann 10 Jahre.
Wenn beide leugnen, so müssen beide 2 Jahre sitzen (wegen unerlaubten Waffenbesitzes...). - Die Frage ist, wie die beiden sich
verhalten sollen.
Diese Situation können wir als Spiel interpretieren, aber offenbar
nicht mehr als Nullsummenspiel, das sich durch eine einzige Matrix
beschreiben ließe. Könnten die Gefangenen sich verständigen, so
würden sie sich möglicherweise darauf einigen, beide zu leugnen,
weil das die Kollektivstrafe minimieren würde.
Da die beiden sich aber nicht verständigen können, ist Leugnen
eine nicht ungefährliche Strategie. Jeder müßte befürchten, daß
der andere ihn verrät, um dann selber frei zu kommen.
Das Gefangenendilemma läßt sich in naheliegender Weise durch zwei
Matrizen beschreiben. Es handelt sich um ein Bimatrixspiel:
II
6 , 0
I
II
6 , 10
I
Verlustmatrizen
10 , 2
0 ,
A
B
A : Verlustmatrix von Spieler
B : Verlustmatrix von Spieler
I
II
2
6 - 13
Situationen, die wie dieses Gefangenendilemma mit Psychologie zu
tun haben, können wir natürlich mathematisch nicht vollständig
lösen. Wir können aber die gemischten Maximinstrategien für beide
Akteure angeben.
Das ist in diesem Falle sogar sehr einfach. Wenn jeder seine
Maximalstrafe minimieren will, so läuft es offenbar darauf hinaus,
daß beide gestehen. Das entspricht dem folgenden Bild:
g 1
g
l
1
0
(6,6) , (0,10)
l 0
(10,0) , (2,2)
(A,B)
g: gestehen
l: leugnen
Wir haben die beiden Matrizen A und B zu einer Matrix (A,B)
zusammengefaßt und die Strategien davor bzw. darüber notiert:
Gestehen entspricht dem Vektor (1,0).
Man beachte: Man wird diese beiderseitige Gestehen-Strategie
vielleicht nicht als gute Lösung für die beiden Gefangenen
ansehen. Eines wird man der Lösung aber nicht absprechen können:
Sie ist stabil in dem Sinne, daß Abweichen dem Abweichenden nur
schadet (er bekommt dann 10 Jahre anstatt 6).
Beispiel
Die Zahlen des folgenden Spiels wollen wir als Gewinne interpretieren:
II
(2,1) , (-1,-1)
I
(A,B) Gewinnmatrizen
(-1,-1) , (1,2)
Könnten die Spieler kooperieren, so könnten sie sich den maximalen
Gesamtgewinn 1+2=3 zu je 3/2 teilen. Wir unterstellen aber wieder
nichtkooperatives Verhalten. Was wir ausrechnen können, sind die
Maximinstrategien und die Garantiegewinne.
Wir machen das für den Spieler I (für den Spieler II argumentieren
wir dann mit Symmetrie)
2 , -1
A =
-1 ,
1
3 , 0
-->
+1
0 , 2
Wir haben +1 addiert, um die Matrix nichtnegativ zu machen.
Wir stellen das Tableau des (dualen) linearen Programms auf:
6 - 14
[1]
[6]
-1 -1
0
0 | [0]
|*6
3
0 [1]
0 | 1
|*2
0
2
0
[1] | 1
|*3
-------------------------0
0
2
3 | [5]
-->
[3] 0
1
0 | 1
0 [2] 0
1 | 1
optimal
x = (2/6, 3/6)
z = 5/6
Durch Normieren erhalten wir die Maximinstrategie für Spieler I .
Der Wert ist der (wieder um 1 verminderte) Kehrwert von z:
Maximinstrategie für
I: p=(2/5,3/5) , wI = 1/5
( = 6/5 - 1)
Maximinstrategie für II: q=(3/5,2/5) , wII = 1/5
Die Lösung für Spieler II folgt aus Symmetriegründen.
Man beachte: Die Werte wI und wII stimmen bei Bimatrixspielen (im
Kontrast zu Nullsummenspielen) normalerweise natürlich nicht
überein. Da jeder der Spieler seine eigene Spielmatrix hat, haben
die beiden Garantiegewinne im allgemeinen nichts miteinander zu
tun.
II
2/5
3/5
2/5
(2,1) , (-1,-1)
3/5
(-1,-1) , (1,2)
I
Maximinstrategien
Wir untersuchen diese Lösung wie die des letzten Beispiels
hinsichtlich Stabilität, und wir stellen einen Unterschied fest:
Wenn Spieler I bei seiner Strategie bleibt, so lohnt es sich für
Spieler II, seine Strategie (3/5, 2/5) zu verlassen und konsequent rechts, also q=(0,1) zu spielen. Dadurch bekommt er dann den
Gewinn wII = -2/5+6/5 = 4/5 . Und das ist mehr, als er bei seiner
Maximinstrategie erhält!
Für Spieler I gilt ähnliches: Er verbessert sich durch Abweichen
nach p=(1,0). Wenn aber beide Spieler wie beschrieben ihre Maximinstrategien verlassen, so landen sie bei der Auszahlung (-1,-1),
d.h. sie haben sich beide verschlechtert!
Diesem durch unsere beiden Beispiele aufgedeckten Phänomen der
(In-)Stabilität wollen wir einen Namen geben:
6 - 15
Definition (Gleichgewicht)
Ein Strategienpaar bildet einen Gleichgewichtspunkt, wenn Abweichen nur eines Spielers von seiner Strategie dem Betreffenden
höchstens schadet (seinen Gewinn jedenfalls nicht vergrößert).
Für das letzte Beispiel ist folgendes Paar von Strategien ein
Gleichgewichtspunkt:
3/5
II
2/5
3/5
(2,1) , (-1,-1)
I
Gleichgewichtspunkt
2/5
(-1,-1) , (1,2)
Kontrolle für Spieler I: Wenn Spieler I zur Strategie
abwandert, so erhält er
(p1,p2)
wI = p1*(4/5-3/5)+p2*(-2/5+3/5) = p1*1/5+p2*1/5 = (p1+p2)/5 = 1/5
Also der Spieler verbessert sich nicht (verschlechtert sich allerdings auch nicht).
Eine besonders befriedigende Lösung ist dieser Gleichgewichtspunkt nicht. Keiner der Spieler bekommt mehr als bei seiner
Maximin-Strategie und muß sich obendrein darauf verlassen, daß der
andere Spieler sich rational verhält (also bei seiner Strategie
aus dem Gleichgewichtspunkt bleibt).
Hinweis: Das zweite Spiel hat zwei weitere Gleichgewichtspunkte,
welche?
Bemerkungen
Für Nullsummenspiele bilden die Maximinstrategien einen Gleichgewichtspunkt, warum?
In einem späteren Abschnitt über Komplementarität werden wir
zeigen, daß Bimatrixspiele stets einen Gleichgewichtspunkt haben.
Es gibt Spiele ohne Gleichgewichtspunkt: "Zwei Spieler wählen
unabhängig voneinander eine Zahl. Der mit der größeren Zahl
gewinnt."
Bei diesem Spiel ist jedes Ergebnis instabil: Der Verlierer kann
sich durch eine größere Zahl stets verbessern. - Außer zum Nachweis der Existenz von Spielen ohne Gleichgewichtspunkte ist dieses
Spiel natürlich absolut uninteressant.
6 - 16
Aufgabe zur Spieltheorie
========================
Man bestimme gemischte Optimalstrategien für die Spieler I und II
für das angegebene Nullsummenspiel:
I
II
---------------| 4 -6
2
4 |
| 0 -2
1
5 |
| -3
2
1
4 |
----------------
Vor Starten des Algorithmus verkleinere man die Matrix so weit wie
möglich durch Dominanzargumente.

Download Report