Inhalt1 Einführung
Das GefangenendilemmaTFTKünstliche GesellschaftDie DrittenVertrauensspielUltimatumexperementPublic Goods Games
2 Spieldynamik und soziales LernenSpieleGemischte StrategienNash’sche GleichgewichtPopulationsspieleSymmetrierung eines SpielsPopulationsdynamik trifft SpieltheorieImmitationsdynamikenGrundeigenschaften der ReplikatorgleichungNGe, gesättigte Restpunkte und Existenz von NGSperner’s Lemma
Einführung
Soziales Tier• Aristotle• Städten und Länder wurden mit Ameisenhaufen
vergliechen• Methologischer Individualismus
Die unsichtbare Hand• Thomas Hobbes• Adam Smith• Voltaire - lettres philosophiques
Einführung
DAS GEFANGENENDILEMMA (engl. Prisoners Dilemma)
Beispiel:
• Spender spendet 5 euro => Empfänger kriegt 15 euro• Spender spendet nicht => Empfänger kriegt nichts
Spieler 2spendet nicht
Spieler 1spendet 10 -5
nicht 15 0
Einführung
DAS GEFANGENENDILEMMA (engl. Prisoners Dilemma)
Notation:• C - Spieler macht ein Zug• D - Spieler passt
Spieler 2C D
Spieler 1C R SD T P
T > R > P > S
Einführung
Widerholtes Gefangenendilemma(engl. Repeated Prisoners Dilemma)
• Backward Induction• Welche Strategie sollte man wählen?• Robert Alexrod
TFT - Tit for Tat
• Man fängt mit C an• Widerholt die züge vom Gegner
Einführung
Künstliche Gesellschaft
• Fiktive Personen• Vorprogrammierte Strategien• Sie traten gegeneinander auf• Bessere verbreiten sich
Beispiel: 2 Strategien TFT und AllD, 6 Runden
GegnerTFT AllD
IchTFT 60 -5AllD 15 0
Falls mehr als 10% TFT spieler sind, werden sie dominieren
Einführung
Die Menschen sind die Sieger der Gegenseitigkeit
• Einzige Tiere die auf andere Achten• In der Lage sich in die Schuhen des anderen zu versetzen• Sympatisieren mit den Fremden
Eintretten zu den Dritten (engl. Third Party)
• Dies sind sogenante zuschauer• Ich tue was für dich, weil du was für die anderen getan hast• Indirekte Gegenseitigkeit• Ausbeuter• Sie unterscheiden sich in 2 Gruppen: die einige helfen
allen inkl. Ausbeutern und andere nicht• Reputation
Einführung
VERTRAUENSSPIEL
• auf dem Prinzip der Spendespielen gebaut• Spender kann an Empfänger 1 euro spenden dabei kriegt
der Empfänger das 3- fache• danach kann der der Empfänger an Spender 1 euro
zurückgeben• im reeellen Leben gibt es sehr viele Elemente des
Vertauensspiels
ULTIMATUMEXPERIMENT
• 2 Spieler: Proposer und Responder• Proposer kriegt 10 euro und darf sie teilen• Responder kann entweder das Angebot annehmen oder
ablehnen, dabei kriegen die beiden nichts
Einführung
• Offensichtlich dass als Responder muss man immerannehmen sobald die Anteil grösser 0 ist und als Proposersollte man wenig anbieten. Experemintell wurde abermeistens um die 50% angeboten, und die Angeboteweniger als 20 % wurden fast immer abgelehnt.
• Menschliche Gehirn besteht aus 2 Teilen: das eine ist fürrationales Denken zuständig und das andere für gefühle
• Mensch hat sich betrogen gefühlt
Einführung
Gerechtigkeitsnormen
• viele Nutzen das Ultimatumexperement um dieGerechtigkeitsnormen zu studieren ’
• Woher kommen die Normen?• Reputation
PUBLIC GOODS GAMES
Alle Spiele die wir bisher betrachtet haben handelten von 2Personen. Viele ökonomische Vorgehen bestehen aber ausmehr wie 2 Personen. Was soll man dann machen wennsowohl ein passer als auch ein nichtpasser dabei sind?
Einführung
Ein typischer Muster solches Experements:
• 6 Spieler haben jeweils 10 euro• Sie können das Geld auf ein gemeinsames Konto legen
dabei wird es verdreifacht, durch 6 geteilt undzurückbezahlt
Fals alle investieren kriegt jeder am schluss 30 euro, aber fallseiner nicht mitmacht kriegt jeder 25 euro, also wird der eine 35haben - 10 euro mehr als die anderen Die meisten investierenaber mehr als die hälfte.Falls wir das Experiment widerholen wird es mit jedem Versuchimmer weniger
Einführung
PUNISH OR PERISH?
• Bestrafung = man bezahlt 1 euro und es werden 3 eurovom Konto des anderen abgezogen
• Mit Bestrafung investieren die Menschen mehr• Man möchte dass die Person sich verbessert, deshalb
bezahlt man• Man hat gemerkt, dass viele, obwohl sie genau wissen,
dass sie nie wider mit gegen unfairen Spieler auftretten,neigen dafür ihn zu bestraffen
• Wieso?!?! - Aus Prinzip und wegen den Dritten!
Spieldynamik und soziales Lernen
SPIELE
Beispiel:
• 2 Personen zeigen gleichzeitig 1 oder 2 Finger ’• Falls die Summe ungerade ist gewinnt der 1 Spieler, wenn
die Summe gerade ist gewinnt der 2 Spieler
Formalisierung:
• Angenommen Spieler 1 muss sich zwischen n Strategienentscheiden e1 . . . en und Spieler 2 zwischen m Strategienf1 . . . fm.
• Falls der 1 Spieler sich für ei und der 2 Spieler Für fjentscheiden kriegt der 1 Spieler aij und der 2 Spieler bijausgezahlt.
Spieldynamik und soziales Lernen
• Also kann das Spiel durch 2 Matrizen A und B beschriebenwerden, bzw durch die Matrix ( aij , bij ).
• Also in unserem Beispiel: Angenommen man setzt 1 euroein, e1 = f1 = gerade, e2 = f2 = ungerade. DieAuszahlungsmatrix ist dann:(
(−1,1) (1,−1)(1,−1) (−1,1)
)
Spieldynamik und soziales Lernen
GEMISCHTE STRATEGIEN
• Für beide seiten ist es wichtig dass der Gegner die Zügenicht kennt. Lösung - zufällig entscheiden.
• Angenommen, der Spieler 1 entscheidet sich mit einerWahrscheinlichkeit xi für Strategie ei . Diese gemischteStrategie für Spieler 1 ist dann gegeben durchx = (x1 . . . xn), wobei
xi ≥ 0 ∀i ∈ {1 . . . n} undn∑
i=1xi = 1
Sei Sn die Menge aller solche Strategien. Sn ist einSimplex (n - dimensionales Polytop) in Rn gespannt vonder Einheitsvektoren ei .
Spieldynamik und soziales Lernen
• Analog, die gemischte Strategie für Spieler 2 ist einElement y von Simplex Sm.
• Falls Spieler 1 eine einfache Strategie ei benutzt undSpieler 2 Strategie y , dann ist das Ergebnis für Spieler 1
(Ay)i =n∑
j=1aijyj
• Angenommen, Spieler 1 hat eine gemischte Strategie xund Spieler 2 eine gemischte Strategie y . Für den 1Spieler ergibt sich dann:
x · Ay =∑
ixi(Ay)i =
∑i,j
aijxiyj
Spieldynamik und soziales Lernen
• Für Spieler 2:
x · By =∑i,j
bijxiyj
• Falls man die Strategie y vom 2 Spieler kennt, sollteSpieler 1 die am besten passende Strategie benutzen. DieMenger solcher Strategien ist eine Menge
BR(y) = arg maxx
x · Ay
d.h. die Menge solcher x ∈ Sn so, dass
z · Ay ≤ x · Ay für alle z ∈ Sn
Spieldynamik und soziales Lernen
• Die Funktion z → z · Ay ist stetig. Da Sn kompakt ist dieMenge nicht Leer. Die Menge ist konvex. Mehr als das, fallsx ∈ BR(y) dann sind auch alle ei ∈ BR(y) für die xi > 0 .
In der Tat, für alle i gilt: (Ay)i = ei · Ay ≤ x · Ayfalls für ein i mit xi die Ungleichung streng kleiner wäre,gälte dann xi(Ay)i < xi(x · Ay)
n∑i=1
xi(Ay)i <n∑
i=1xi(x · Ay)
Dies ist ein Widerspruch. Daraus folgt dass BR(y) eineUnterraum von Sn ist, gespannt von Einfachstrategien vonBR(y)
Spieldynamik und soziales Lernen
NASH’SCHE GLEICHGEWICHT (engl. Nash Equilibrium)
• 2 Strategien befinden sich in einer Nash’scheGleichgewicht, wenn x ∈ BR(y) und y ∈ BR(x)
• Äquivalent :z · Ay ≤ x · Ay für alle z ∈ Sn und x · Bw ≤ x · By für allew ∈ Sm
• Später wird bewiesen dass für alle Spiele (A,B) existiert soein Paar.
Spieldynamik und soziales Lernen
• Wir betrachten jetzt eine bevölkerung, jedes Mitglied hateine Strategie
• Um es zu vereinfachen, betrachten wir zuerst nursymmetrische Spiele
• Dabei ist n = m, ej = fj∀j , aijbji oder mit anderen WortenB = AT
• Ein Symmetrisches Spiel ist also durch (A, AT ) gegeben,also durch eine einzige Matrix A
Spieldynamik und soziales Lernen
• Interessant ist sogenante symmetrische Nash’scheGleichgewicht (engl. symmetric Nash equilibrium), d.h. einTupel (x,y) mit x=y.
• x ist dann die beste Strategie zu sich selbst, x ∈ BR(x) Mitanderen Wortenz · Ax < x · Ax für alle z 6= x
Spieldynamik und soziales Lernen
SYMMETRIERUNG EINES SPIELS
• Es gibt ein einfacher weg das nicht symmetrische Spiel(A,B) zu symmetrisieren.
• Einfach zufällig Spieler 1 aussuchen• Strategie dieses symmetrisches Spiels muss aber die
Strategie von beider enthalten. Eine Strategie ist danngegeben durch ein Paar (ei , fj).
• Eine gemischte Strategie ist dann gegeben durch einElement z = zij ∈ Smn, wobei zij beschreibt dieWahrscheinlichkeit von ei bei dem 1 Spieler und fj bei dem2 Spieler.
Spieldynamik und soziales Lernen
• Die Rände der Wahrscheinlichkeitsverteilung z sindxi =
∑j
zij und yj =∑
izij
• Die Vektoren x = (xi) und y = (yj) liegen in Sn und Sm
• Es ist klar, dass für alle x und y existiert so ein z ∈ Snm,so dass x und y die Rände sind, z.B. zij = xiyj
• Das ergebnis für einen Spieler (ei , fj) gegen einen Spieler(ek , fl) hängt von dem Münzenwurf ab und ist gegebendurchcij,kl = 1
2ail + 12bkj
• Wir nehmen an, dass jedes symmetrisches Spiel einNash’schen Gleichgewichtzustand besitzt. Dann besitztauch das nicht- symetrisches Spiel ein NG.
Spieldynamik und soziales Lernen
• Beweis:
Sei z ∈ Snm ein NG für symmetriezierbares Spiel (C,CT ).Es gilt also:
z · Cz ≤ z · Cz für alle z ∈ Snm
Sei nun x und y die Rände von z und x , y von z. Dann gilt:
z · Cz =∑ijkl
zijcij,kl zkl = 12∑ijkl
zijail zkl + 12∑ijkl
zijbkj zkl =
12∑il
xiail yl + 12∑jk
yjbkj xk = 12x · Ay + 1
2y · BT x
Da z ein symmetrisches NG ist, folgt:x · Ay + x · By ≤ x · Ay + x · By
Für x = x und y = y ist dann (x , y) NG für (A,B)
Spieldynamik und soziales Lernen
POPULATIONSDYNAMIK TRIFFT SPIELTHEORIE
Jetzt betrachten wir ein symmetrisches Spiel mitErgebnismatrix A in einer Menge.
• Die Fraktion xi hat eine Strategie ei . Der Zustand derMenge wird durch ein Vektor x ∈ Sn gegeben. Ein Spielermit Strategie ei erwartet also
(Ax)i =∑
jaijxj
• Für die die gesamte Menge also
x · Ax =∑
ixi(Ax)i
• Wichtig: x steht jetzt für den Zustand der Menge und nichtfür die gemischte Strategie wie vorher.
Spieldynamik und soziales Lernen
• Der Zustand x hängt von der Zeit ab .• Uns interessiert die Grösse
xi = dxidt
der Frequenzen von den Strategien• Frage: Inwiefern spielen sie eine Rolle?• Wir nehmen an, dass der Zustand der Menge nach der so
genannten Replikatorgleichung (engl. replicator equation)xi = xi [(Ax)i − x · Ax ]
• Entsprechend, ob die Strategie ei sich verbreitet oderverschwindet hängt von dem Durchschnitt ab.
Spieldynamik und soziales Lernen
• Dies liefert ein deterministisches Modell für den Zustandder Menge.
• In der Tat, die DGL x = F (x) wobei F glatt ist, hat eineeindeutige Lösung für jeden x
• Die rechte Seite der Gleichung können wir als ein VRintepretieren x 7→ F (x)
Spieldynamik und soziales Lernen
IMMITATIONSDYNAMIKEN (engl. immitation dynamics)
• Wenn wir annehmen dass die Personen sich immitieren,treffen wir auch die Replikatorgleichung
• Angenommen, eine zufällig gewälte Person ändert seineStrategie.Die Wahrscheinlichkeit, dass während eines Zeitraums ∆tdie Person seine Strategie von ej zu ei wechselt ist xi fij∆t .
• Die entsprechende Gleichung istxi(t + ∆t)− xi(t) =
∑fijxixj∆t −
∑fjixixj∆t
• Für ∆t → 0 gilt:xi = xi
∑(fij − fji)xj
Spieldynamik und soziales Lernen
• Meistens hängt fij von Zustand x ab. z.B können wirannehmen, dassfij = [(Ax)i − (Ax)j ]+ (Input - Output - Gleichung)
• Das heisst, dass ein ej Spieler beim vergleichen mit einemei Spieler, seine Strategie nur dann ändern wird, wenn esbesser für ihn ist. Und natürlich ist die Wahrscheinlichkeitgenau dann grösser wenn die differenz grösser ist.Und in diesem Fall, da fij − f ji = (Ax)i − (Ax)j liefert unsdie IO Gleichung:xi =
∑j
[(Ax)i − (Ax)j ]xj = xi [(Ax)i − x · Ax ]
Dies ist nichts anderes als Replikatorgleichung.
Spieldynamik und soziales Lernen
GRUNDEIGENSCHAFTEN DER REPLIKATORGLEICHUNG
• Wir können eine belibige Funktion f (x) zu allenErgebnissen (Ax)i dazuaddieren, dabei bleibt dieReplikatorgleichung unverändert: was wir zu demErgebniss dazuaddieren, wird auch zu demDurchschnittsergebnis dazuaddirt, da
∑xi = 1 und es
kürzt sich bei Differenz weg.• Dies impliziert, wir können zu j- ten Spalte von A einfach
eine konstante cj dazuaddieren, ohne dabei die Dyamik zuverändern.
• QuotientenregelFals xj > 0 gilt:
( ˙xixj
) = (xixj
)[(Ax)i − (Ax)j ]
Spieldynamik und soziales Lernen
NASH’SCHE GLEICHGEWICHTE, GESÄTTIGTE RESTPUNKTE
UND DIE EXISTENZ VON NASH’SCHEN GLEICHGEWICHT
• Betrachten wir ein symmetrisches n × n Spiel (A,AT ) mitsymmetrischen Nash’schen Gleichgewicht z. d.h.x · Az ≤ z · Az für alle z ∈ Sn
• Wenn x = ei gilt(Az)i ≤ z · Az
• Wie wir schon wissen muss für alle i , s.d zi > 0 dieungleichheit gelten. Dann ist z ein gesättigter Restpunkt(d.h.: falls zi = 0, dann gilt(Az)i − z · Az ≤ 0 )
• Es gilt Äquivalenz (jeder gesättigter Restpunkt ist NG)
Spieldynamik und soziales Lernen
• Um die Existenz der NG zu beweisen, können wir dieExistenz ger gesätteten Restpunkten derReplikatorgleichung zeigen.
• Wir addieren ε > 0 zur jede Komponente der rechten Seiteund substrahieren nε, damit die Summe
∑xi = 0 stimmt.
xi = xi [(Ax)i − x · Ax − nε] + ε
• Es gibt mindestens ein Restpunkt, der die Gleichung erfült,nennen wir ihn z. Es gilt:(Azε)i − zε · Azε = ε(n − 1
(zε)i)
• wenn wir zu den Grenzwerten übergehn, kriegen wir dassz ein gesättigter Restpunkt ist.
Spieldynamik und soziales Lernen
SPERNER’S LEMMA
• Betrachte n-1 dim. Simplex S (eine geschlossene“Hülle“von n Punkten y1, . . . yn , s.d. yi − yn unabhänig sind.
• eine nicht-triviale Teilmenge spannt Untersimplex.• Zerlegung besteht aus n-1 dim. disjunkten Simplexen, s.d
die Vereinigung S ergibt• Wir bemalen die Eckpunkten mit n Farben, angenommen
yi hat Farbe i• In jedem Untersimplex werden nur die Farben der
Eckpunkte, von welchen er gespannt wird benutzt• Spernener’s Lemma: Es gibt nur gerade Anzahl von
Untersimlexen so dass die Ecken unterschiedlich gefärbtsind.
• Beweis geht mit Hilfe der Induktion