Einführung, Spieldynamik und soziales Lernen - num.uni-sb… Inhalt 1 Einführung Das Gefangenendilemma TFT Künstliche Gesellschaft Die Dritten Vertrauensspiel Ultimatumexperement

Einführung, Spieldynamik und sozialesLernen

Vsevolod Shashkov

25.10.2011

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.


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

)


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 .


• 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


• 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


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


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.


• 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


• 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


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.


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


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


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.


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


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


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


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


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 ]


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)


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


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

Documents

Einführung, Spieldynamik und soziales Lernen - num.uni-sb… Inhalt 1 Einführung Das Gefangenendilemma TFT Künstliche Gesellschaft Die Dritten Vertrauensspiel Ultimatumexperement