View
219
Download
0
Category
Preview:
Citation preview
Kriterien für PermanenzReplikator-Netzwerke
Kriterien für Permanenz -Replikator-Netzwerke
Eliseu Radecke
20. Dezember 2011
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Gliederung
1 Kriterien für PermanenzPermanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
2 Replikator-NetzwerkeEin periodischer Attraktor für n = 4Permanenz und IrreduzibilitätPermanenz für katalytische Netzwerke
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Permanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
Gliederung
1 Kriterien für PermanenzPermanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
2 Replikator-NetzwerkeEin periodischer Attraktor für n = 4Permanenz und IrreduzibilitätPermanenz für katalytische Netzwerke
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Permanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
Gleichungen
Die Replikator-Gleichung lautet
xi = xi(fi(x)− f ), auf Sn, (1)
wobei f (x) =∑n
j=1 xj fj(x).
In der Ökologie tauchen Gleichungen der Form
xi = xi(fi(x)), auf Rn+ (2)
auf.
Überleben alle Spezies dieser Systeme für jedes t > 0?
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Permanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
Das System (1) heißt permanent, wenn ein KompaktumK ⊂ int(Sn) gibt, für das gilt: jeder Orbit in Sn endet in K .Genauer: Falls xi(0) > 0,
∃δ > 0 : lim inft→∞
xi(t) > δ, i = 1, ...,n .
Für (2) wird noch verlangt: Falls x ∈ int(Rn+),
∃D > 0 : lim supt→∞
xi(t) ≤ D, i = 1, ...,n .
So heißen ihre Orbits gleichmäßig beschränkt.Die Permanenz von (1) wurde bewiesen. Derselbe Beweisgilt für (2), falls gleichmäßige Beschränktheit vorliegt.
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Permanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
Brouwerscher Abbildungsgrad
Sei U ⊂ Rn offen und beschränkt, f ein Vektorfeld auf einerUmgebung von U.
x ∈ U ist regulär, falls det Dxf 6= 0.y ∈ Rn ist ein regulärer Wert, falls alle x ∈ U mit f(x) = yregulär sind.
DefinitionDer Brouwersche Abbildungsgrad von f zu einem regulärenWert y ∈ Rn \ f(∂U) ist definiert als
deg(f,y) :=∑
f(x)=y
sgn det Dxf .
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Permanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
Die Nullstellen von f sind die stationären Punkte desSystems x = f(x). Wir definieren den Grad der Abbildungf als deg(f,0).
Seien f, g : U → Rn zwei Abbildungen, jede mit Grad 6= 0auf dem Rand ∂U. Falls f und g auf ∂U nicht inentgegengesetzten Richtungen zeigen, so gilt
deg(f,0) = deg(g,0).
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Permanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
Satz(Fixpunktsatz von Brouwer) Jede stetige Abbildung h von dern-dimensionalen Einheitskugel
D = {x ∈ Rn : ‖x‖ ≤ 1}
in sich selbst besitzt mindestens einen Fixpunkt, d.h.
∃x ∈ D : h(x) = x.
Beweis.Siehe Anhang.
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Permanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
Poincaré-Index
DefinitionSei x ein isolierter stationärer Punkt vom System x = f(x). DerPoincaré-Index von x bzgl. des Vektorfeldes f ist definiert als
i(x) = deg(f,0).
Folgerung
Ist x regulär, so entspricht i(x) dem Vorzeichen von det Dxf.Also gilt
i(x) = (−1)σ ,
wobei σ die Anzahl von negativen Eigenwerten bezeichnet.
Beispiel:i(Quelle) = 1, i(Senke) = 1, i(Sattelpunkt) = −1.
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Permanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
Satz(Poincaré-Hopf) Sei M eine kompakte Mannigfaltigkeit mit Randund f ein Vektorfeld auf M, das auf dem Rand nach aussenzeigt. Falls f nur endlich viele Fixpunkte besitzt, dann gilt dieBeziehung ∑
x∈FP
i(x) = χ(M) ,
wobei FP die Menge aller Fixpunkte in M und χ dieEuler-Charakteristik bezeichnet.
Die Euler-Charakteristik ist eine Verallgemeinerung deseulerschen Polyedersatz E − K + F = 2. Es giltχ(Kreis) = 1 ,
χ(Sphäre)= 2.
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Permanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
Beispiel: Sei B ⊂ R2 der Einheitskreis und f ein Vektorfeld, sodass gilt:
1) Es entsteht eine geschlossene Trajektorie γ und f ist überallauf int(γ) definiert.2) Auf der geschlossenen Trajektorie γ zeigt f nach aussen.
Dann folgt mit dem Satz von Poincaré-Hopf, dass esmindestens einen kritischen Punkt in int(γ) gibt:∑
x∈FP
i(x) = χ(B) = 1.
Wenn alle kritischen Punkte regulär sind, dann muss ihreAnzahl ungerade sein, 2n + 1, und davon müssen genau nSattelpunkte sein.
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Permanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
Ein Index-Satz für permanente Systeme
Satz
Sei U eine beschränkte Menge mit U ⊆ int(Rn+), die alle
ω-Limesmengen und ihre Inneren enthält, und sei g einVektorfeld auf einer Umgebung von U. Falls das System
xi = xi(fi(x)), auf Rn+
permanent ist, dann gilt
deg(g,0) = (−1)n .
Insbesondere existiert ein stationärer Punkt in int(Rn+).
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Permanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
Gesättigter stationärer Punkt
DefinitionEin stationärer Punkt p von
xi = xi(fi(x)) , ( bzw. xi = xi(fi(x)− f ) )
heißt gesättigt, wenn aus pi = 0
fi(p) ≤ 0 , ( bzw. fi(p) ≤ f (p) )
folgt.
Jeder innere stationäre Punkt ist gesättigt.
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Permanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
SatzDie Replikator-Gleichung
xi = xi(fi(x)− f )
besitzt mindestens einen gesättigten stationären Punkt. Fallsalle gesättigten stationären Punkte regulär sind, so beträgt dieSumme ihrer Indizes (−1)n−1.
Bem. Bei der speziellen Replikator-Gleichung
xi = xi((Ax)i − xAx)
ist der stationäre Punkt p gesättigt, falls aus pi = 0,(Ap)i ≤ p · Ap folgt. Somit enspricht p dem symmetrischenNash-Gleichgewicht für das Spiel mit einer Payoff-Matrix A :
x · Ap ≤ p · Ap, ∀x ∈ Sn.
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Permanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
DefinitionDie Replikator-Gleichung
xi = xi(fi(x)− f ), auf Sn (3)
heißt stark persistent, wenn es trotz kleiner Störungen in fipermanent bleibt.
Satz1) Wenn das System (3) stark persistent ist, dann besitzt eseinen inneren stationären Punkt.
2) Sei U eine offene Menge, U ⊆ int(Sn), die alle innerenstationären Punkte enthält. Dann beträgt der Grad desVektorfeldes
(−1)n−1 .
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Permanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
Gliederung
1 Kriterien für PermanenzPermanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
2 Replikator-NetzwerkeEin periodischer Attraktor für n = 4Permanenz und IrreduzibilitätPermanenz für katalytische Netzwerke
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Permanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
Wir betrachten zunächst die spezielle Replikator-Gleichung
xi = xi((Ax)i − xAx), auf Sn (4)
bzw. die Lotka-Volterra-Gleichung
xi = xi(ri + (Ax)i), auf Rn+. (5)
SatzWenn das System (4) oder (5) permanent ist, dann existiertgenau ein innerer stationäre Punkt p. Ferner gilt für jedes x ausdem Inneren des Zustandsraums
limT→∞
1T
T∫0
x(t)dt = p .
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Permanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
Satz1) Wenn (5) permanent ist, dann gilt
(−1)n det(D) > 0 ,tr(D) > 0 ,
(−1)n det(A) > 0 ,
hierbei bezeichnet D die zugehörige Jacobi-Matrix an deminneren stationären Punkt p.2) Wenn (4) mit aii = 0 und innerem stationären Punkt p,permanent ist, dann gilt
p · Ap > 0
sowie(−1)n−1 det A > 0.
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Permanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
Gliederung
1 Kriterien für PermanenzPermanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
2 Replikator-NetzwerkeEin periodischer Attraktor für n = 4Permanenz und IrreduzibilitätPermanenz für katalytische Netzwerke
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Permanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
SatzDas Replikator-System (4) ist permanent, wenn es einen Punkty ∈ int(Sn) gibt, so dass
y · Ax > x · Ax
für alle stationären Punkte x ∈ ∂Sn gilt.
Bem. Es sei hier betont, dass auf ∂Sn nur stationäre Punktevorkommen dürfen (keine ω−Limesmenge).
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Permanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
SatzMan betrachtet das Lotka-Volterra-System
xi = xi(ri + (Ax)i), auf Rn+
mit gleichmäßig beschränkten Orbits:
∃k > 0 : lim supt→∞
xi(t) ≤ k .
Wenn die Menge
D ={
x ∈ Rn+ : r + Ax ≤ 0
}und die konvexe Hülle C von allen Fixpunkten im Rand desZustandsraums disjunkt sind, so ist dieses System permanent.
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Permanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
Beispiel: Das Lotka-Volterra-System mit n = 2. Existiertein stationärer Punkt im Inneren des Zustandsraums, sosind für dieses System zwei Arten von Verhältnissenmöglich:
1 globale Stabilität (und somit Permanenz): falls der innerestationäre Punkt oberhalb der Geraden, die durch beideein-speziesche stationäre Punkte läuft, liegt.
2 Bistabilität (eine Spezies stirbt aus): falls der innerestationäre Punkt unterhalb der Geraden liegt.
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Ein periodischer Attraktor für n = 4Permanenz und IrreduzibilitätPermanenz für katalytische Netzwerke
Gliederung
1 Kriterien für PermanenzPermanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
2 Replikator-NetzwerkeEin periodischer Attraktor für n = 4Permanenz und IrreduzibilitätPermanenz für katalytische Netzwerke
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Ein periodischer Attraktor für n = 4Permanenz und IrreduzibilitätPermanenz für katalytische Netzwerke
Für n = 2 besitzt das Lotka-Volterra-System keineω-Limesmenge. Wie sieht es aus für n = 3?Erinnerung: Der n-speziesche Replikator
xi = xi((Ax)i − x · Ax) , auf Sn (6)
ist äquivalent zu dem (n − 1)-spezieschen LV-System.Wir zeigen für n = 4, dass (6) eine ω-Limesmenge besitzt.Dafür benutzen wir die Matrix
A =
0 0 −µ 11 0 0 −µ−µ 1 0 00 −µ 1 0
.
Ein kritischer Punkt von (6) ist m = (14 ,
14 ,
14 ,
14).
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Ein periodischer Attraktor für n = 4Permanenz und IrreduzibilitätPermanenz für katalytische Netzwerke
Die Jacobi-Matrix D aus (6) ist zyklisch. Ihre erste Zeilelautet
−1 + µ
8,−1 + µ
8,−1− µ
8,
1 + µ
8.
Ihre Eigenwerte lauten
γ0 =−1 + µ
4, γ1 =
µ− i4
, γ2 =−1− µ
4, γ3 =
µ+ i4
.
Zu γ0 gehört der Eigenvektor 1, orthogonal zu S4. Da unsdie Einschränkung von (6) auf S4 interessiert, werden wirdiesen Eigenwert nicht mehr betrachten.
Wenn µ von −12 bis 1
2 variiert, so wird γ2 negativ, währendγ1 und γ3 von links nach rechts die imaginäre Achse beiµ = 0 überqueren.
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Ein periodischer Attraktor für n = 4Permanenz und IrreduzibilitätPermanenz für katalytische Netzwerke
Für µ < 0 ist der stationäre Punkt m eine Senke und fürµ < 0 ist er instabil. Für µ = 0 beschreibt die Matrix A denHyperzyklus (n = 4) mit m assymptotisch stabil.
Alle Bedingungen für Hopf-Bifurkationen sind erfüllt: Esgibt einen periodischen Attraktor in einer Umgebung von m.
Abbildung: Der Replikator (6) besitzt einen Attraktor für n = 4.Quelle: [EVO] S.172
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Ein periodischer Attraktor für n = 4Permanenz und IrreduzibilitätPermanenz für katalytische Netzwerke
Gliederung
1 Kriterien für PermanenzPermanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
2 Replikator-NetzwerkeEin periodischer Attraktor für n = 4Permanenz und IrreduzibilitätPermanenz für katalytische Netzwerke
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Ein periodischer Attraktor für n = 4Permanenz und IrreduzibilitätPermanenz für katalytische Netzwerke
Wir assoziieren die Replikator-Gleichung
xi = xi((Ax)i − x · Ax) , auf Sn, aij ≥ 0, ∀i , jmit einem direkten Graphen, dessen Knoten den Indizes ientsprechen: ein Pfeil von i nach j bedeutet aij > 0.
Abbildung: Matrix A mit entsprechendem direkten Graph.
Ein direkter Graph heißt irreduzibel, falls zu jedem Knoten-paar (i , j) einen orientierten Pfad gibt, der sie verbindet.
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Ein periodischer Attraktor für n = 4Permanenz und IrreduzibilitätPermanenz für katalytische Netzwerke
SatzFalls der Replikator (6) mit aij ≥ 0 permanent ist, dann ist seinGraph irreduzibel.
Die Hyperzyklus-Gleichung mit
A =
0 0 0 11 0 0 00 1 0 00 0 1 0
entspricht tatsächlich einem irreduziblen Graphen.
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Ein periodischer Attraktor für n = 4Permanenz und IrreduzibilitätPermanenz für katalytische Netzwerke
Gliederung
1 Kriterien für PermanenzPermanenz für die Replikator-GleichungenNotwendige Bedingungen für PermanenzHinreichende Bedingungen für Permanenz
2 Replikator-NetzwerkeEin periodischer Attraktor für n = 4Permanenz und IrreduzibilitätPermanenz für katalytische Netzwerke
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Ein periodischer Attraktor für n = 4Permanenz und IrreduzibilitätPermanenz für katalytische Netzwerke
Die Replikator-Gleichung (6) mit aij ≥ 0 und aij = 0 heißtkatalytisches Netzwerk. Hyperzyklen sind einfacheBeispiele davon.
Ein direkter Graph heißt hamiltonisch, falls er einen Pfadbesitzt, der durch alle Knoten genau einmal durchläuft.
Satz1) Für n ≤ 5 ist der Graph eines permanenten katalytischenNetzwerkes hamiltonisch.
2) Ein katalytisches Netzwerk für n = 4 ist genau dannpermanent, wenn es einen inneren stationären Punkt gibt undzusätzlich det(A) < 0 gilt.
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Ein periodischer Attraktor für n = 4Permanenz und IrreduzibilitätPermanenz für katalytische Netzwerke
Anhang
Satz(Brouwerscher Fixpunktsatz) Jede stetige Abbildung h von dern-dimensionalen Einheitskugel in sich selbst besitztmindestens einen Fixpunkt.
Beweis.Angenommen, h(x) 6= x für alle x ∈ D, so zeigt das Vektorfeldf(x) := h(x)− x für jedes x ∈ ∂D nach innen. Da f undg(x) := −x nie in entgegengesetzte Richtungen zeigen, giltdeg(f,0) = deg(g,0) = (−1)n 6= 0, aber dann gibt es ein x ∈ Dmit f(x) = 0. Widerspruch zur Annahme.
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Kriterien für PermanenzReplikator-Netzwerke
Ein periodischer Attraktor für n = 4Permanenz und IrreduzibilitätPermanenz für katalytische Netzwerke
Literatur
[EVO] Josef Hofbauer and Karl Sigmund: EvolutionaryGames and Population Dynamics, Cambridge.
Spieltheorie Kriterien für Permanenz - Replikator-Netzwerke
Recommended