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.
© Copyright 2025 ExpyDoc