Bimatrix-Spiele Bimatrix-Spiele Sarah Hidlmayer 13.12.2011 Literatur: Josef Hofbauer and Karl...

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


•∑

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)


• (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.


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.


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′).


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.


(A,B)

• reskaliertes Partnerschaftsspiel, wenn (A,B) ∼ (C,Ct)

• reskaliertes Nullsummenspiel, wenn (A,B) ∼ (−C,Ct)

für eine passende n ×m - Matrix C.


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 .


• 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.


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)


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.


(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


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 .


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.)


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.


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 .)


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 .


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.


• 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.


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.


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


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.


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.


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.

Date post:	06-Aug-2019
Category:	Documents
Upload:	doannhan
View:	215 times
Download:	0 times

Bimatrix-Spiele Bimatrix-Spiele Sarah Hidlmayer 13.12.2011 Literatur: Josef Hofbauer and Karl...

Documents