Bimatrix-Spiele
Sarah Hidlmayer
13.12.2011
Literatur: Josef Hofbauer and Karl Sigmund: EvolutionaryGames and Population Dynamics (Ch. 11), Cambridge.
Bimatrix-Spiele
1 Dynamik für Bimatrix-Spiele
2 Partnerschaftsspiele und Nullsummenspiele
3 Volumenerhaltung
4 Nash-Pareto-Paare
5 Spiel-Dynamik und Nash-Pareto-Paare
Ziel des Vortrags
• Es gibt Alternativen für die Dynamik von asymmetrischenSpielen.
• Wir werden neu skalierte Partnerschaftsspiele undNullsummenspiele betrachten.
• Die normale Replikatordynamik ist volumenerhaltend,wohingegen eine Modifikation kleiner wird.
• Abschließend werden wir Nash-Pareto-Strategienbehandeln, die einen Ersatz für gemischte ESS imasymmetrischen Fall liefern.
Dynamik für Bimatrix-Spiele
Gleichungen für Replikatordynamik im asymmetrischen Spiel(Vergleich mit symmetrischem Spiel)
xi = xi((Ay)i − x · Ay)yj = yj((Bx)j − y · Bx)
(1)
Miteinbeziehen der Normalisierung durch den Erwartungswertdes Erfolgs:
xi = xi(Ay)i − x · Ay
x · Ay
yj = yi(Bx)j − y · Bx
y · Bx
(2)
• Motiviert durch das diskrete Zeit-Modell• Frequenz x ′i der Ei -Spieler in der nächsten Generation
proportional zu den xi(Ax)i
Dynamik für Bimatrix-Spiele
•∑
x ′i = 1• Multiplikationsrate von einer Generation zur nächsten
durch den Erwartungswert des Erfolgs normalisieren:
x ′i = xi(Ay)i
x · Ay
y ′j = yj(Bx)j
y · Bx
(3)
Dynamik für Bimatrix-Spiele
• (2) folgt aus linearer Approximation x ′i − xi ∼ xi
• (2) kann nicht zu (1) reduziert werden (außer fürPartnerschaftsspiele).
• Werden sehen: Unterschiedliches qualitatives Verhaltenvon (1) und (2)
• (2) und (3) auf Sn ×Sm wohldefiniert, vorausgesetzt aij undbji positiv
• Diese Einschränkung wird für (1) nicht gebraucht.
Dynamik für Bimatrix-Spiele
Grund: unterschiedliche Erwartungswerte des Erfolgs
• In (3) werden die aij als Multiplikationsraten von einer zurnächsten Generation verstanden.
• In (1) hingegen messen die aij nur die Veränderungen derFitness, die durch das Spiel verursacht werden.
Dynamik für Bimatrix-Spiele
Besseres Verständnis:
• Große Konstante C hinzufügen, die allgemeineHintergrundfitness von Individuen zu den aij und bji in (2)und (3) misst.
• Einfach zu sehen: (1) Grenzwert von (2) für C −→∞
Dies deutet an, dass die Dynamik von (1) etwas einfacher seinsollte als die der beiden anderen Gleichungen.
Partnerschaftsspiele und Nullsummenspiele
• (1) nicht nur einfacher als die anderen beiden Gleichungen,• auch immun gegenüber Reskalierungen des Erfolgs bei
der Addition beliebiger Konstanten zu den Spalten derErfolgsmatrizen A und B.
Allgemeiner nennt man ein Spiel (A′,B′) eine Reskalierung von(A,B), wenn Konstanten cj und di und α > 0, β > 0 existieren,sodass:
a′ij = αaij + cj ,
b′ji = βbji + di .
Wir schreiben dann: (A,B) ∼ (A′,B′).
Partnerschaftsspiele und Nullsummenspiele
Reskalierungen sind von besonderem Interesse
• für Partnerschaftsspiele, wo der Gewinn gleichmäßigzwischen den zwei Spielern aufgeteilt wird.
• für Nullsummenspiele, wo der Gewinn des Einen derVerlust des Anderen ist.
Partnerschaftsspiele und Nullsummenspiele
(A,B)
• reskaliertes Partnerschaftsspiel, wenn (A,B) ∼ (C,Ct)
• reskaliertes Nullsummenspiel, wenn (A,B) ∼ (−C,Ct)
für eine passende n ×m - Matrix C.
Partnerschaftsspiele und Nullsummenspiele
Genauer:
(A,B) c-Partnerschafts-/Nullsummenspiel (mit c > 0 bzw.c < 0), wenn passende cij , cj und di existieren, sodass für alle iund j :
aij = cij + cj ,
bji = ccij + di .
Partnerschaftsspiele und Nullsummenspiele
• c-Partnerschaftsspiele entsprechen bestimmtenGradienten-Systemen.
• Tangentialraum in Punkt (x , y) ∈ int Sn × Sm besteht ausVektoren (ξ, η) mit ξ ∈ Rn
0 und η ∈ Rm0 .
• Definiere inneres Produkt im Tangentialraum:
⟨(ξ, η), (ξ′, η′)
⟩(x ,y) =
∑ ξiξ′i
xi+
1c
∑ ηjη′j
yj
• Zugehörigen Gradienten nennt man c-Gradient.
Partnerschaftsspiele und Nullsummenspiele
Die folgenden Aussagen sind äquivalent:
• (A,B) ist ein c-Partnerschaftsspiel.• (1) ist ein c-Gradient.• cξ · Aη = η · Bξ• Für alle i , k zwischen 1 und n und für alle j , l zwischen 1
und m gilt:
c(aij − ail − akj + akl) = bji − bli − bjk + blk (4)
Partnerschaftsspiele und Nullsummenspiele
Außerdem gilt:• Wenn (A.B) Partnerschaftsspiel, dann x · Cy
durchschnittlicher Gewinn, der bei jeder Runde anwächst.• Wenn (A,B) c-Partnerschaftsspiel, dann (2) Gradient.• In einem Nullsummenspiel konvergiert die
durchschnittliche Zeit pro innerer Runde gegen (p,q).• Kampf der Geschlechter ist reskaliertes Nullsummenspiel.• (A,B) nur dann c-Nullsummenspiel, wenn (4) erfüllt.
Partnerschaftsspiele und Nullsummenspiele
(4) kann interpretiert werden als Population von Spielern, diegemischte Strategien spielen.
Annahme:• N gemischte Strategien pi ∈ Sn in Position I mit Frequenz
xi (i = 1, ..,N) gespielt werden• M gemischte Strategien qj ∈ Sm in Position II mit Frequenz
yj (j = 1, ...,M) gespielt werden.• Hauptstrategie in I: p =
∑xipi
• Hauptstrategie in II: q =∑
yjqj
Partnerschaftsspiele und Nullsummenspiele
Da Gewinn für pi : pi · Aq und für qj : qj · Bp, istReplikatorgleichung für Spiel mit gemischten Strategien:
xi = xi((Ay)i − x · Ay)yj = yj((Bx)j − y · Bx)
wobei aij = pi · Aqj und bji = qj · Bpi .
Partnerschaftsspiele und Nullsummenspiele
Also• A = PAQt ,• B = QBP t
mit• P stochastische N × n - Matrix mit Zeilen pi ,• Q stochastische M ×m - Matrix mit Zeilen qj .
(Jede Zeile einer nichtnegativen Matrix addiert sich zu 1.)
Partnerschaftsspiele und Nullsummenspiele
Es gilt folgendes:
• Wenn (A,B) c-Partnerschafts-/c-Nullsummenspiel, dannsind alle Spiele mit gemischten Strategien (PAQt ,QBP t)für alle stochastischen N × n - Matrizen P und allestochastischen M ×m - Matrizen Q.
• (A,B) nur dann c-Partnerschafts-/Nullsummenspiel, wennSpiele mit gemischten Strategien (PAQt ,QBP t)c-Partnerschafts-/Nullsummenspiele sind für alle2× n-Matrizen P mit Zeilen aus Basisvektoren ei und ekaus Rn und alle 2×m-Matrizen Q mit Zeilen ausBasisvektoren fj und fl aus Rm.
Partnerschaftsspiele und Nullsummenspiele
Außerdem:
• Dynamisches Verhalten der modifiziertenReplikatorgleichung (2) für allgemeine reskalierteNullsummenspiele nicht bekannt.
• Generell: 2× 2 - Spiel weder reskaliertes Nullsummenspielnoch reskaliertes Partnerschaftsspiel.
Volumenerhaltung
In höheren Dimensionen braucht die Replikatorengleichung (1)keine Geschwindigkeitskonstante, aber sie wird immer nochVolumen erhalten.
Liouville-Formel:• x = f (x) auf offener Menge U in Rn
• G als Teilmenge von U mit Volumen V• Volumen V (t) von G(t) = {y = x(t), x ∈ G}:
V (t) =∫
G(t)divf (x)d(x1, ..., xn)
Volumenerhaltung
• Teile Vektorfelder (1) und (2) durch positive FunktionP =
∏ni=1 xi
∏mj=1 yj .
• Nenne diese (I) und (II).• Berechne ihre Divergenzen.
Divergenz von (I) in int Rn × Rm:
div(I) = − 1P(x · Ay + y · Bx) (5)
Volumenerhaltung
• Divergenz div0 innerhalb des Zustandsraumes int Sn × Sm−→ Eigenwerte der Jacobimatrix subtrahieren, dieorthogonal zu Sn und Sm
•∑
xi = (1−∑
xi)x · Ay−→ −x · Ay und −y · Bx beiden Eigenwerte für (1)
• Berücksichtige Faktor 1P
−→ aus (5) folgt, dass Replikatordynamik (1) divergenzfrei:div0(I) = 0
Aus Liouvilles Formel ergibt sich, dass (I) Volumen erhält.
Volumenerhaltung
Analoge Berechnung für Modifikation (II) von (2):
div(II) = − 1P
n∑i=1
xi(Ay)2
i(x · Ay)2 +
m∑j=1
yj(Bx)2
j
(y · Bx)2
Beide zu Sn und Sm orthogonale Eigenwerte -1. Also:
div0(II) = div(II) +2P
Volumenerhaltung
• div0(II) < 0 auf int Sn × Sm, Liouvilles Formel−→ (2) verkleinert Volumen
• Verkürzungsrate entspricht Varianz der Vektorfelder, strebtgegen 0 nahe inneren stationären Punkten.
−→ Spiegelt Fakt wieder, dass (1) und (2) gleicheLinearisierung in der Nähe von stationären Punkten haben.
Volumenerhaltung
Wir wollen dieses Ergebnis nun benutzen, um die Diskussionvon 2-Strategien-Spielen (n = m = 2) zu komplettieren.Fehlt: Verhalten der modifizierten Replikatorgleichung (2) fürreskalierte Nullsummenspiele.
Betrachte Kampf der Geschlechter:
A =
(α b + β
a + α β
), B =
(c + γ δγ d + δ
)mit a,b, c,d > 0 und α, β, γ, δ ≥ 0.Für (1) können wir die Konstanten α, β, γ, δ streichen undinneres Nash-Gleichgewicht ausrechnen:
Volumenerhaltung
p =d
c + d
q =b
a + b
• Für (2) zeigt Formel von div0(II), dass P−1 Dulac-Funktionund zyklische Runden unmöglich.
• Bereich abnehmend −→ Innerer stationärer Punkt (p,q)global asymptotisch stabil.
• Obwohl gemischte Strategie (p,q) kein ESS, ist esAttraktor für (2).
Nash-Pareto-Paare
• Gesehen: Im Kampf der Geschlechter mit der Dynamik (2)ist gemischtes Nash-Gleichgewicht stabil.−→ Gemischte Strategien bei evolutionärenBestimmungen von Relevanz, obwohl sie nicht evolutionärstabil sein können.
• Dies spricht das Problem des geschwächten Begriffs desESS an, der sehr eng für asymmetrische Wettbewerbe ist,sodass es gemischte Strategien enthalten kann.
Nash-Pareto-Paare
• Annahme: 2 Populationen befinden sich in Lage(p,q) ∈ Sn × Sm.
• Dieser wird zweifellos nicht stabil sein, wenn Status (x , y)in der Nähe von (p,q) existiert, sodass beide Populationendurchschnittlichen Gewinn erhöhen können, indem sie zuihm wechseln.
Nash-Pareto-Paare
Paar von Strategien (p,q) Nash-Pareto-Paar für einasymmetrisches Spiel mit Gewinnen A und B, wenn:• Gleichgewichtsbedingung:
p · Aq ≥ x · Aq und q · Bp ≥ y · Bp für alle (x , y) ∈ Sn × Sm−→ (p,q) Nash-Gleichgewicht-Paar
• Stabilitätsbedingung:Für alle Zustände (x , y) ∈ Sn × Sm, für die Gleichheit in (I)gilt, gilt:Wenn x · Ay > p · Ay , dann y · Bx < q · Bx .Wenn y · Bx > q · Bx , dann x · Ay < p · Ay .−→ Unmöglich, dass beide Spieler zum gleichen Zeitpunkteinen Vorteil durch Abweichung vom Gleichgewicht (p,q)erhalten können.
Nash-Pareto-Paare
Dies deckt sich mit dem Konzept der Pareto-Optimalität oderEffizienz in der klassischen Spieltheorie.
Beachte:
• In der Stabilitätsbedingung essentiell, beiden Populationenzu erlauben, gleichzeitig abzuweichen.
• Wenn p durch x ersetzt wird und y gleich zu q bleibt−→ Stabilitätsbedingung leer.
Merke:• Nash-Gleichgewicht des Geschlechterkampf-Spiels ist
Nash-Pareto-Paar.• Für A = B = 0 ist jeder Zustand Nash-Pareto.
Wir wollen nun Nash-Pareto-Paare charakterisieren.
Nash-Pareto-Paare
(p,q) ∈ int Sn × Sm nur dann Nash-Pareto-Paar desBimatrix-Spiels (A,B), falls Konstante c existiert, sodass
(x − p) · Ay + c(y − q) · Bx = 0
für alle (x , y) ∈ Sn × Sm, d.h. nur wenn das Spiel reskaliertesNullsummenspiel ist.Solch ein Nash-Pareto-Paar ist stabil für die Replikatordynamik(1).
−→ Gleichgewichts- und Stabilitätsbedingung (rein qualitativeBehauptungen, die nur Ungleichungen enthalten) bedeuten,dass Gewinnmatrizen gleich sind.
Nash-Pareto-Paare
Es ist sehr aufschlussreich, dies mit dem Gedanken derevolutionären Stabilität für symmetrische Probleme zuvergleichen.
Bereits gesehen:p ∈ int Sn nur dann evolutionär stabil, wenn P(x) =
∏xpi
i striktglobale Lyapunov-Funktion: P(x) > 0 für x 6= p.
Nash-Pareto-Paare
Für asymmetrische Wettstreite zeigt Letzteres:
• (p,q) ∈ int Sn × Sm nur dann Nash-Pareto-Paar, wenn:• P(x , y) =
∏xpi
i∏
ycqjj globale Lyapunov-Funktion (und
Bewegungskonstante) für Replikatorgleichung (1):• P(x , y) ≥ 0 für (x , y) nahe (p,q).
P(x , y) strikte Lyapunov-Funktion für (1)−→ (p,q) striktes Nash-Gleichgewicht.−→ p und q reine Strategien.
Nash-Pareto-Paare
• Symmetrische Spiele: Evolutionärer, stabiler Zustandallgemein robust gegenüber kleinen Störungen in denGewinnen.
• Bei asymmetrischen Fällen ist dies anders.
Ein Nash-Pareto-Paar (p,q) für ein Bimatrix-Spiel (A,B) heißtrobust, wenn jedes Spiel (A, B) in einer passenden Umgebungvon (A,B) ein Nash-Pareto-Paar (p, q) nahe (p,q) hat.
• Robustes Nash-Pareto-Paar Mix aus maximal 2 Strategienpro Population.
• Also: Wenn (p,q) komplett gemischt und robust, dannn,m ≤ 2.
Nash-Pareto-Paare
−→ 2 Möglichkeiten für robustes Nash-Pareto-Paar:• Es besteht aus reinen Strategien (und ist somit ein striktes
Nash-Gleichgewicht).• Es ist das Nash-Gleichgewicht eines Unterspiels des Typs:
A =
(α b + β
a + α β
)B =
(c + γ δγ d + δ
)Außerdem:
Wenn ein inneres Gleichgewicht isoliert und stabil für (1) ist,dann ist es ein Nash-Pareto-Paar.
Spiel-Dynamik und Nash-Pareto-Paare
Wir haben bereits die ESS Bedingungen in spieldynamischenBezeichnungen interpretiert.
Wir wollen dies nun auch für Nash-Pareto-Paare tun:• In welcher Art und Weise sind diese immun gegen mutierte
Strategien?
Dazu:• Annahme: Beide Populationen homogen, p- und q-Spieler.• Lassen nun kleine Anzahl an x- und y -Spielern einfallen.
(Jeweilige Häufigkeiten, mit denen sie auftreten: x und y .)
Spiel-Dynamik und Nash-Pareto-Paare
Dynamik (1) dieses Spiels:
x = x(1− x)(b − (a + b)y)y = y(1− y)(d − (c + d)x)
auf [0,1]× [0,1] mit
a = (p − x) · Ay , b = (x − p) · Aq,c = (q − y) · Bx , d = (y − q) · Bq.
(p,q) nur dann Nash-Gleichgewicht, wenn b < 0 und d < 0 füralle x und y .
Spiel-Dynamik und Nash-Pareto-Paare
Stabil gegenüber (x , y) im Sinne davon, dass die Ecke (p,q)nur dann ein Attraktor ist, wenn b < 0 und d < 0d.h. nur dann, wenn:
p · Aq > x · Aq und q · Bp > y · Bp für alle x 6= p und y 6= q
−→ Exakte Definition eines strikten Nash-Gleichgewichts fürein asymmetrisches Spiel.
Spiel-Dynamik und Nash-Pareto-Paare
• Keine zweite Bedingung im Sinne von ESS, dawenn b = 0, d.h. wenn p · Aq = x · Aq für x 6= pdann entsteht Linie aus stationären Punkten.
• p kann von x-Mutanten aufgrund stochastischerSchwankungen überfallen werden.
−→ Gleichung im strikten Fall nicht vereinbar mit evolutionärerStabilität.
Spiel-Dynamik und Nash-Pareto-Paare
Andererseits:• Einführung eines y -Mutanten, der a > 0 und d < 0 erfüllt
also wenn gilt: p · Ay > x · Ay und q · By > y · Bp• in eine Population von Spielern in Position II.
−→ Zurückführen zu einem Punkt, der näher an (p,q) ist.
Spiel-Dynamik und Nash-Pareto-Paare
Somit kann das folgende Konzept eines schwachen ESS immernoch eine evolutionäre Stabilität garantieren:b ≤ 0 mit a > 0 wenn b = 0 und d ≤ 0 mit c > 0 wenn d = 0:
p · Aq ≥ x · Aq für alle x , bei Gleichheit : p · Ay > x · Ayq · Bp ≥ y · Bp für alle y , bei Gleichheit : q · Bx > y · Bx
−→ p und q pure Strategien
Spiel-Dynamik und Nash-Pareto-Paare
Für gemischte Strategien p und q• gelten Gleichheiten b = 0 (p · Aq = x · Aq) und d = 0
(q · Bp = y · Bp) für viele x , y• und Ränder mit stationären Punkten sind nicht vermeidbar.
Müssen verhindern:• a < 0 (x ·Ay > p ·Ay ) und c < 0 (y ·Bx > q ·Bx) für einige(x , y).
• (x , y) würde (p,q) überfallen.
Spiel-Dynamik und Nash-Pareto-Paare
Asymmetrie des Spiels −→ Zwischenmöglichkeit(Die im symmetrischen Fall keine Analogie hat.)
Dies ist genau unser Konzept des Nash-Pareto-Paars:b ≤ 0 und d ≤ 0, wenn b = 0 und d = 0, dann ac < 0.
Spiel-Dynamik und Nash-Pareto-Paare
Abschließend:
• Evolution wird Distanz der Abweichung einesNash-Pareto-Paars (p,q) nicht durch eine Mutationbedingt erhöhen.
• Hängt von aktueller Dynamik und Stärke desstochastischen Effekts ab, ob diese Distanz gegen 0 strebtund der Mutant emiliniert wird.
• Dies wird zuletzt für die modifiziertenReplikator-Dynamiken (2) vermutet.
Fazit
Wir haben
• eine alternative Dynamik kennengelernt,• uns mit Partnerschafts- und Nullsummenspielen
beschäftigt,• verschiedene Volumenbetrachtungen angestellt und• Nash-Pareto-Strategien behandelt.