12. Evolutionäre Spiele in:

Thomas Riechmann

Spieltheorie, page 203 - 219

4. Edition 2013, ISBN print: 978-3-8006-4750-7, ISBN online: 978-3-8006-4751-4, https://doi.org/10.15358/9783800647514_203

Series: Vahlens Kurzlehrbücher

Bibliographic information
12. Evolutionäre Spiele 12.1 Das Hawk–Dove–Spiel und evolutionär stabile Zustände 12.1.1 Das Hawk–Dove–Spiel Zwei Wellensittiche teilen sich eine Weile lang einen Käfig. Im Käfig ist der Platz vor dem Spiegel besonders begehrenswert: Der Sittich, der dort sitzt, kann sich den ganzen Tag über kämmen, pudern, Pickel ausdrücken u.s.w., wodurch er für Wellensittichinnen extrem attraktiv wird. Attraktive Sittiche vermehren sich stärker als unattraktive Sittiche. Der Wert des Platzes vor dem Spiegel sei V = 2. Kommt es zwischen den Sittichen zum Kampf um diesen Platz, so trägt der Verlierer unschöne Narben davon, so dass er Kosten in Höhe von C = −4 tragen muss, um sich von einem Sittich–Schönheits– Chirurgen wiederherstellen zu lassen. Es gibt zwei Strategien, sich als Sittich in der Spiegel–Situation zu verhalten: 1. Hawk Ein Sittich, der Hawk spielt, tut so, als sei er ein Falke: Er kämpft in jedem Fall mit dem Gegner. 2. Dove Ein Sittich, der Dove spielt, ist ein echtes Weichei: Er flieht („macht den Sittich“), sobald er einen Hawk–spielenden Sittich sieht. Es resultiert ein Spiel mit simultanen Zügen. Treffen ein Hawk– und ein Dove–Spieler aufeinander, gewinnt der Hawk–Spieler den Platz vor dem Spiegel (π = 2), der Dove–Spieler bekommt nichts (π = 0). Treffen zwei Hawk–Spieler aufeinander, kämpfen sie miteinander. Die Chancen, diesen Kampf zu gewinnen, sind 12 für jeden, so dass die erwartete Auszahlung π = 12 ·V + 12 ·C = −1 beträgt. Treffen zwei Dove–Spieler aufeinander, teilen sie die Zeit vor dem Spiegel gleichmäßig untereinander auf, so dass jedem die Auszahlung π = 12V = 1 entsteht. Die Normalform des Spiels ist in Tab. 12.1 dargestellt. Hawk Dove Hawk -1, -1 2, 0 Dove 0, 2 1, 1 Tabelle 12.1: Hawk–Dove–Spiel. Normalform 196 12. Evolutionäre Spiele Die Struktur der Auszahlungen des Hawk–Dove–Spiels ist die gleiche wie im Chicken–Game (Abschnitte 3.6.2 und 6.4.2), die Höhe der Auszahlungen ist aber unterschiedlich. Es existieren drei Nash–Gleichgewichte: die Gleichgewichte in reinen Strategien bei (Hawk, Dove) und (Dove, Hawk) sowie das gemischte Gleichgewicht, in dem beide Spieler mit pH = 12 Hawk und mit (1− pH) = 12 Dove spielen. 12.1.2 Der evolutionäre Ansatz Die evolutionäre Spieltheorie wählt nun eine andere Herangehensweise an diese Art von Spielen. Es wird angenommen, es existiere eine große Anzahl von Wellensittichen, eine Population. Aus dieser Population werden nun wiederholt jeweils zwei Sittiche ausgewählt, die dann gegeneinander das Hawk–Dove–Spiel spielen. Dabei wird angenommen, dass die Spieler die Strategie spielen, die bei ihnen genetisch vorprogrammiert ist. Jeder Sittich spielt also entweder Hawk oder Dove, kann aber seine Strategie nicht wechseln, denn sie ist ihm von Geburt an vorgegeben. Die Auszahlungen aus dem Spiel geben nun an, wie viele Nachkommen der jeweilige Spieler haben wird. (Hier geht es um asexuelle Fortpflanzung!) Die Nachkommen erben die Strategie ihres Vorfahren. Die wichtigste Frage, die sich evolutionäre Spieltheoretiker stellen, ist die danach, wie die Zusammensetzung der Population langfristig sein wird. Wird auf lange Sicht die Population nur aus Hawk–Spielern, nur aus Dove–Spielern oder aus einer stabilen Mischung aus beidem bestehen? Die Antwort ist erstaunlich simpel. Angenommen, eine Population bestünde nur aus Hawk–Spielern. Würde nun ein einziger Dove–Spieler die Population „invadieren“, so würde sich dieser Dove–Spieler schneller vermehren als die Hawk–Spieler, denn die erwartete Auszahlung an einen Dove– Spieler in einer reinen Hawk–Population ist höher als die der Hawk–Spieler in dieser Population. Die erwartete Auszahlung eines Dove–Spielers, E (πD) errechnet sich allgemein als E (πD) = pHπHD +(1− pH)πDD , (12.1) wobei pH den Populationsanteil an Hawk–Spielern angibt, πDD die Auszahlung eines Dove–Spielers gegen einen Dove–Spieler und πHD die Auszahlung eines Dove–Spielers gegen einen Hawk–Spieler ist. Die einzelnen Auszahlungen sind in der Normalform Tab. 12.1 angegeben. Analog ergibt sich die erwartete Auszahlung an einen Hawk–Spieler als E (πH) = pHπHH +(1− pH)πDH . (12.2) 12.1 Das Hawk–Dove–Spiel und evolutionär stabile Zustände 197 Im Fall der Invasion einer reinen Hawk–Population durch einen Dove– Spieler ist pH = 1.1 Damit ergibt sich hier E (πD) = 0 , E (πH) = −1 . Entsprechend der Regel, dass sich der Spielertyp mit der höheren Auszahlung stärker vermehrt, d.h. im Laufe der Zeit in der Population ausbreitet, ist eine Population, die nur aus Hawk–Spielern besteht, nicht stabil. Die Invasion einer solchen Population durch einen Dove–Spieler wäre erfolgreich. Der Spielertyp „Dove“ würde sich in der Population ausbreiten. Auch eine reine Dove–Population, also eine Population mit pD = (1− pH) = 1 wäre instabil, d.h. nicht resistent gegen eine Invasion durch einen Hawk–Spieler. Hier lauten die Auszahlungen E (πD) = 1 , E (πH) = 2 . Insgesamt ist im Hawk–Dove–Spiel keine der homogenen Populationen stabil. Keine Population, die nur aus Spielern desselben Typs besteht, ist resistent gegen eine Invasion durch Spieler des jeweils anderen Typs. Es lässt sich aber zeigen, dass eine heterogene Population existiert, die stabil ist. Eine stabile heterogene Population ist eine Population, die über die Zeit ein unverändertes Mischungsverhältnis aus Spielern beiden Typs beibehält. Dieses stabile Mischungsverhältnis muss dadurch gekennzeichnet sein, dass die erwartete Auszahlung an einen Hawk–Spieler genau so hoch sein muss wie die an einen Dove–Spieler. Nur in diesem Fall vermehren sich die beiden Typen von Spielern gleich stark und halten sich anteilsmäßig in der Population die Waage. Das ausgewogene Mischungsverhältnis p⋆H lässt sich also aus dem Gedanken herleiten, dass die erwartete Auszahlung beider Strategien identisch sein muss: E (πH) = 2−3 p⋆H ! = 1− p⋆H = E (πD) p⋆H = 1 2 . Die eigentliche Stabilitätsanalyse stützt sich nun auf folgenden Gedanken: Ist der tatsächliche Anteil an Hawk–Spielern, pH , größer als der ausgewogene Anteil p⋆H = 1 2 , so ist die erwartete Auszahlung an Dove–Spieler höher als die an Hawk–Spieler: 1 Genauer: pH geht gegen Eins, wenn die Populationsgröße gegen unendlich geht. Es wird allerdings regelmäßig angenommen, die Populationen seien „sehr groß“. 198 12. Evolutionäre Spiele pH > 1 2 ⇔ E (πD) = 1− pH > 2−3 pH = E (πH) . Ist aber die Auszahlung an Dove–Spieler höher als an Hawk–Spieler, so steigt der Anteil der Dove–Spieler in der Population, d.h. πH sinkt. Dies geschieht genau so lange, bis die erwarteten Auszahlungen wieder gleich hoch sind, also genau bis pH = p⋆H = 1 2 . Analog lässt sich zeigen, dass für pH < p⋆H = 1 2 die erwartete Auszahlung an Hawk–Spieler höher ist als an Dove–Spieler und deshalb der Anteil an Hawk–Spielern steigt. Insgesamt ergibt sich also, dass eine heterogene Population mit dem Mischungsverhältnis p⋆H = 1 2 asymptotisch stabil ist: Wird von diesem Verhältnis abgewichen, so stellt es sich von selbst wieder her. 12.1.3 Evolutionär stabile Zustände (ESS) Definition. Gleichgewichtige Zustände einer Population wie der im vorigen Abschnitt beschriebene heißen evolutionär stabile Zustände (evolutionarily stable states, ESS). Sind solche Zustände dergestalt, dass jedes Mitglied der Population dieselbe Strategie spielt, so nennt man die gespielte Strategie eine evolutionär stabile Strategie (evolutionarily stable strategy, ebenfalls ESS). Auf den ersten Blick sieht es nun so aus, als sei der stabile Zustand im Hawk–Dove–Spiel kein evolutionär stabiler Zustand, in dem lediglich eine Strategie gespielt wird. Tatsächlich lässt sich der Zustand auch als ein Zustand der Population ansehen, in dem jedes Populationsmitglied eine gemischte Strategie aus Hawk und Dove spielt, bei der die Wahrscheinlichkeit Hawk zu spielen genau p⋆H = 1 2 beträgt. Damit ist der stabile Gleichgewichtszustand im Hawk–Dove–Spiel ein evolutionär stabiler Zustand, der durch eine gemeinsame evolutionär stabile Strategie gekennzeichnet wird. Eine solche evolutionär stabile Strategie lässt sich formal genauer charakterisieren: Eine Strategie s⋆ ist eine evolutionär stabile Strategie, wenn sie a) die streng beste Antwort auf sich selbst ist, oder b), falls sie nur eine schwache beste Antwort auf sich selbst ist, sie eine bessere Antwort auf alle anderen gleichfalls schwachen besten Antworten auf s⋆ ist als diese selbst: Definition 12.1.1 (evolutionär stabile Strategie). s⋆ ist eine evolutionär stabile Strategie, falls gilt, dass a) π (s⋆, s⋆) > π ( s′, s⋆ ) ∀ s′ ∈ S\ s⋆ , (12.3) oder b) falls ∃ s′ mit π (s⋆, s⋆) = π ( s′, s⋆ ) , 12.1 Das Hawk–Dove–Spiel und evolutionär stabile Zustände 199 dann π ( s⋆, s′ ) > π ( s′, s′ ) . (12.4) Falls Bedingung (12.3) hält, dann ist s⋆ deshalb eine stabile Strategie, weil sie besser ist als alle anderen Strategien, und so eine Invasion der Population durch andere Strategien abgewehrt werden kann. Falls es aber, wie in Bedingung (12.4) Strategien gibt, die genau so gut sind wie s⋆ wenn sie gegen s⋆ gespielt werden, dann wird eine Invasion deshalb abgewehrt, weil die invadierende Strategie s′ ab und zu auch gegen sich selbst spielen muss und dort schlechter abschneidet als s⋆ beim Spiel gegen s′. Verbindung zu Konzepten der klassischen Spieltheorie. In Worten der „normalen“ Spieltheorie: Ist s⋆ eine evolutionär stabile Strategie, so ist sie eine beste Antwort auf sich selbst (Bedingung (12.3)). Damit ist ein evolutionär stabiler Zustand (s⋆, s⋆) nach Bedingung (12.3) ein symmetrisches Nash–Gleichgewicht (allerdings unter Umständen in gemischten Strategien). Ist der Zustand (s⋆, s⋆) sogar ein strenges Nash–Gleichgewicht, so gilt auch der umgekehrte Zusammenhang: Ist (s⋆, s⋆) ein strenges Nash–Gleichgewicht, so ist s⋆ eine evolutionär stabile Strategie. Nach Bedingung (12.4) ist eine Strategie s⋆ ebenfalls dann eine ESS, falls sie nur eine schwache Nash–Strategie ist, aber von diesen schwachen Nash– Strategien eine, die eine beste Antwort auf sich selbst ist.2 Aus diesen Interpretationen ist zu erkennen, dass jeder evolutionär stabile Zustand ein symmetrisches Nash–Gleichgewicht ist, nicht aber jedes symmetrische Nash–Gleichgewicht auch ein evolutionär stabiler Zustand. Auffinden von ESS. Eine nützliche Hilfe zum Auffinden evolutionär stabiler Strategien resultiert aus der Eigenschaft (12.3), die besagt, dass ESS beste Antworten auf sich selbst sind. Gegeben die Auszahlungsmatrix des Zeilenspielers sind alle Strategien, deren Auszahlung auf der Hauptdiagonalen der Matrix die höchsten Auszahlungen ihrer Spalte sind, automatisch ESS. Dies lässt sich beispielhaft an der Matrix 12.2 zeigen, die nur die Auszahlungen an den Zeilenspieler darstellt. Hier sind sowohl a als auch b ESS. a b a 1 0 b 0 5 Tabelle 12.2: ESS–Finde–Spiel. Auszahlungen an Zeilenspieler 2 Auch nach Bedingung (12.3) ist die ESS, als strenge Nash–Strategie, natürlich eine beste Antwort auf sich selbst. 200 12. Evolutionäre Spiele 12.2 Evolutionäre Dynamik Der Gedanke der ESS basiert auf der Vorstellung einer Dynamik der Populationsanteile: Es wird angenommen, dass Strategien, die im Vergleich zu anderen erfolgreicher sind, d.h. zu höheren Auszahlungen gelangen, sich über die Zeit in der Population ausbreiten. Weniger erfolgreiche Strategien werden dagegen seltener in der Population. So folgt eine Population auf die andere. In jeder Population wird wieder das grundlegende Spiel gespielt. Hierbei werden die Auszahlungen festgestellt, die darüber bestimmen, aus welchen Anteilen welcher Strategien die nächste Population besteht u.s.w. Bei der Idee der evolutionären Dynamik handelt es sich also um eine Art wiederholter Spiele, wobei jede Stufe des wiederholten Spiels dadurch gekennzeichnet ist, dass sie von (möglicherweise) unterschiedlichen Populationsanteilen der verschiedenen Strategien gespielt wird. 12.2.1 Replikatordynamik in diskreter Zeit Es existieren verschiedene Möglichkeiten, solche Dynamiken explizit zur formulieren. Die wohl verbreitetste evolutionäre Dynamik ist die einfache Replikatordynamik. Dieser Dynamik liegt die Vorstellung zugrunde, dass die Mitglieder einer sehr großen Population in einer Zeitperiode paarweise gegeneinander jeweils ein Hawk–Dove–Spiel spielen und die ihren Strategien entsprechenden Auszahlungen erhalten. Diese Auszahlungen bestimmen nun über die Zusammensetzung der neuen Population, deren Mitglieder in der nächsten Periode wieder paarweise gegeneinander spielen u.s.w. Insgesamt entsteht eine Abfolge von Populationen, in denen sich die Anteile der Strategien über die Zeit entwickeln oder, im Falle von Stabilität, eben nicht entwickeln. In ihrer Form für diskrete Zeit lässt sie sich die einfache Replikatordynamik für das Hawk–Dove–Spiel wie folgt darstellen: Der Populationsanteil der Hawk–Spieler in Periode t +1, pH(t +1) hängt ab vom Populationsanteil der Hawk–Spieler in der Vorperiode pH(t) sowie der erwarteten Auszahlung der Strategie in der Vorperiode, der Einfachheit halber nun statt E (πH(t)) nur als πH(t) notiert, im Verhältnis zur populationsdurchschnittlichen Auszahlung der Vorperiode π(t): pH(t +1) = pH(t) πH(t) π(t) mit π(t) = pH(t)πH(t)+(1− pH(t)) πD(t) . (12.5) Hieraus lässt sich durch einfache Umformungen die relative Veränderung, also die Wachstumsrate der Populationsanteile der Strategien ermitteln: pH(t +1)− pH(t) pH(t) = πH(t)−π(t) π(t) . (12.6) 12.2 Evolutionäre Dynamik 201 Es lässt sich erkennen, dass eine Strategie ihren Anteil in der Population dann ausdehnt, wenn sie zu einer höheren Auszahlung gelangt als der Durchschnitt. Hat dagegen eine Strategie nur unterdurchschnittlichen Erfolg, so vermindert sich ihr Populationsanteil. Wenn man bedenkt, dass die erwarteten Auszahlungen πH(t) und πD(t) wie auch die populationsdurchschnittliche Auszahlung π(t) ihrerseits Funktionen der Populationsanteile pH(t) und pD(t) sind, erkennt man, dass es sich bei der Replikatorgleichung (12.5) um eine nichtlineare Differenzengleichung handelt. Solche Differenzengleichungen lassen sich nur in Spezialfällen allgemein lösen. Dies ist der Grund, dass Replikatordynamiken in der Literatur zumeist „simuliert“ werden, oder — weniger prosaisch — dass man sie mit Hilfe eines Computers schrittweise iteriert. 12.2.2 Replikatordynamik in kontinuierlicher Zeit Für diejenigen, die Diffenrentialgleichungen gegenüber Differenzengleichungen vorziehen (sehen ja auch irgendwie wissenschaftlicher aus), gibt es natürlich auch Varianten der Replikatordynamik, die in kontinuierlicher Zeit notiert sind. Um aus einer diskreten Replikatordynamik eine stetige zu gewinnen, ist zunächst folgender Gedanke hilfreich: Die Auszahlung eines Spielers gibt die (durchschnittliche) Anzahl von Nachkommen an, die er in einer Periode produziert. Damit lässt sich die Entwicklung der absoluten Anzahl von Spielern jeden Typs darstellen. Sei NH(t) die Anzahl der Hawk–Spieler zum Zeitpunkt t, so beträgt die Anzahl der Hawk–Spieler im Zeitpunkt t + τ NH(t + τ) = NH(t)+NH(t)τ πH(t) . Eine analoge Beziehung gilt natürlich auch für ND(t + τ), die Dove–Spieler. Die Gesamtanzahl von Spielern, also die Populationsgröße, in t + τ beträgt N(t + τ) = NH(t + τ)+ND(t + τ) . Um zu Populationsanteilen zurückzukehren, muss nun der Anteil der Hawk–Spieler in t + τ , pH(t + τ), bestimmt werden.3 Er beträgt pH(t + τ) = pH(t)(1+ τ πH(t)) 1+ τ π(t) . Hieraus lässt sich die Veränderung der Populationsanteile herleiten: pH(t + τ)− pH(t) = pH(t)τ πH(t)−π(t) 1+ τ π(t) 3 Die ausführliche Herleitung ist in Anhang 12.5 dargestellt. 202 12. Evolutionäre Spiele Die Veränderung pro Zeitinkrement τ beträgt damit pH(t + τ)− pH(t) τ = pH(t) πH(t)−π(t) 1+ τ π(t) . Hieraus folgt die gesuchte Differentialgleichung als d pH d t = ṗH = pH (πH −π) . (12.7) Prinzipiell besagt Gleichung (12.7) natürlich dasselbe wie die Gleichungen (12.5) und (12.6). Die Veränderung des Populationsanteils der Hawk– Spieler ergibt sich aus dem aktuellen Anteil der Hawk–Player, pH , multipliziert mit der Abweichung der Hawk–Auszahlung πH von der durchschnittlichen Auszahlung in der Population, π . In der Version in kontinuierlicher Zeit wird also noch deutlicher, dass die Richtung, in der sich der Populationsanteil einer Strategie über die Zeit verändert, nur von ihrer Auszahlung im Verhältnis zur populationsdurchschnittlichen Auszahlung abhängt. 12.2.3 Ruhepunkte der Dynamik Für den Fall des Hawk–Dove–Spiels (Tabelle 12.1, S. 195) lassen sich nun beispielhaft die Form der Dynamik und die Lage der Ruhepunkte herleiten. Es soll die Form in kontinuierlicher Zeit hergeleitet werden. Deshalb ist es nützlich, auf die explizite Darstellung der Zeitindices zu verzichten. So soll nun also beispielsweise πH statt πH(t) geschrieben werden. Aus (12.1) und (12.2) (S. 196) und den Auszahlungen aus Tab. 12.1 folgt πH = 2−3 pH , πD = 1− pH . Damit folgt πH −π = πH − pH πH − (1− pH)πD = (1− pH)(1−2pH) . Hieraus lässt sich schließlich die explizite Form der stetigen Replikatordynamik im Hawk–Dove–Spiel herleiten: ṗH = pH (πH −π) = pH(1− pH)(1−2 pH) . (12.8) Die Dynamik (12.8) hat drei stationäre Punkte, d.h. Punkte, bei denen ṗH = 0 ist, sich also die Populationsanteile über die Zeit nicht mehr verändern. Diese drei stationären Punkte lassen sich aus Gleichung (12.8) leicht ablesen. Es sind pH = ps1 = 0, pH = p s 2 = 1 und pH = p s 3 = 1 2 . 12.3 Evolutionäre Gleichgewichtsselektion: Stochastische Stabilität 203 Im Sinne eines evolutionär stabilen Zustandes lässt sich aber leicht zeigen, dass nur einer dieser stationären Punkte auch stabil ist. Direkt jenseits des stationären Zustands ps1 = 0 wird laut (12.8) pH über die Zeit größer: ṗH = pH ︸︷︷︸ ⊕ (1− pH) ︸ ︷︷ ︸ ⊕ (1−2 pH) ︸ ︷︷ ︸ ⊕ > 0 für 0 < pH < 1 2 . Eine leichte Abweichung von pH = 0 würde genügen, um niemals wieder zu einer reinen Hawk–Population zurückzugelangen. Analog gilt ṗH < 0 für 1 > pH > 12 direkt neben dem stationären Punkt p s 2. Keine der beiden homogenen Populationen, also weder die reine Dove–Population mit pH = 0 noch die reine Hawk–Population mit pH = 1 sind (asymptotisch) stabil.4 Lediglich für eine Population aus genau 50% Hawk– und 50% Dove– Spielern, also pH = ps3 = 1 2 ändern sich die Populationsanteile nicht mehr, d.h. ist ṗH = 0. Damit ist nur der stationäre Punkt bei pH = 12 ein asymptotisch stabiler Punkt der Replikatordynamik. Egal, mit welchem Populationsanteil an Hawk–Spielern die Dynamik beginnt: Solange die Population nicht aus lediglich einem Typ von Spielern besteht, konvergiert die Replikationsdynamik zum stationären Punkt pH = 12 . Damit ist dieser Punkt ein lokaler Attraktor der Replikationsdynamik für das Hawk–Dove–Spiel. Schon vorher wurde gezeigt, dass der lokale Attraktor der Replikationsdynamik ein ESS ist. Diese Beziehung gilt allgemein: Ein lokal stabiler Ruhepunkt der Replikatordynamik ist ein evolutionär stabiler Zustand und vice versa.5 12.3 Evolutionäre Gleichgewichtsselektion: Stochastische Stabilität 12.3.1 Das Spiel Das Spiel in simultanen Zügen aus Tab. 12.3 hat zwei Nash–Gleichgewichte in reinen Strategien, das Pareto–dominante Gleichgewicht (s1, s1) und das risikodominante (s2, s2). Beide Nash–Gleichgewichte bestehen aus evolutionär stabilen Strategien. Dadurch ist nicht klar, welches der Gleichgewichte unter dem Regime einer evolutionären Dynamik erreicht würde: Das Kriterium der evolutionären Stabilität ist in diesem Fall mehrdeutig. Um eins 4 „Nicht stabil“ bedeutet hier, dass schon die Invasion durch einen Spieler anderen Typs die Population aus ihrem stationären Zustand herausbewegen würde. Die Replikatordynamik selbst enthält aber keine Definition einer solchen „Invasion“. Dies bedeutet, dass unter dem Regime der Replikatordynamik auch die beiden instabil genannten Zustände über die Zeit beibehalten würden. 5 Dies gilt natürlich erst recht für global stabile Punkte, denn global stabile Punkte sind dann jeweils der einzige lokal stabile Punkt. 204 12. Evolutionäre Spiele s1 s2 s1 √ 3, √ 3 0, 1 s2 1, 0 1, 1 Tabelle 12.3: Mehrdeutige ESS der Gleichgewichte als langfristig stabil charakterisieren zu können, ist ein Kriterium zur weiteren Gleichgewichtsselektion notwendig. Dies kann beispielsweise das Kriterium der stochastischen Stabilität sein. Bei dem gezeigten Spiel soll es sich um ein so genanntes Populationsspiel handeln. In jeder Zeitperiode existiere eine Menge von n Spielern, die Population. Jedes Mitglied der Population spielt gegen jedes andere Mitglied, d.h. in jeder Zeitperiode spielt jeder Spieler das Spiel n−1 mal. Es sei nun zt die Anzahl von Spielern, die in Periode t die Strategie s1 spielen. Entsprechend spielen n− zt Spieler in t die Strategie s2. Ausgestattet mit diesen Kenntnissen lassen sich die Auszahlungen für jede der Strategien errechnen. Die Auszahlungen an einen Spieler, der in t Strategie s1 spielt, beträgt πs1 (zt) = (zt −1) √ 3 . (12.9) Die Auszahlung an einen s2–Spieler beträgt πs2 (zt) = zt +(n− zt −1) = n−1 . (12.10) Entsprechend betragen die durchschnittlichen Auszahlungen pro Spiel einer Periode πs1 (zt) = (zt −1) √ 3 n−1 (12.11) πs2 (zt) = 1 . (12.12) 12.3.2 Selektionsdynamik Nun sei folgende Dynamik angenommen: Ist in Periode t die durchschnittliche Auszahlung an s1 größer als an s2, so spielen in der nächsten Periode, t + 1, alle Spieler diese bessere Strategie. Ist dagegen in t die durchschnittliche Auszahlung an s2 höher als die an s1, spielen in t + 1 alle Spieler s2.6 Im Rahmen der evolutionären Dynamik spricht man in diesem Fall von einer extrem elitistischen Selektionsdynamik. Diese Dynamik lässt sich wie folgt formal darstellen: 6 Wegen der speziellen Auswahl der Auszahlungen in Tab. 12.3 kann es niemals zu gleich hohen durchschnittlichen Auszahlungen der beiden Strategien kommen. 12.3 Evolutionäre Gleichgewichtsselektion: Stochastische Stabilität 205 zt+1 = { n falls πs1 (zt) > πs2 (zt) , 0 falls πs1 (zt) < πs2 (zt) . (12.13) Diese Dynamik ist aber etwas eintönig: Sie verharrt sofort in einem der beiden möglichen Zustände der Population. Ist zt = 0, so folgt πs1 (zt) = − √ 3 n−1 < 1 = πs2 (zt) (12.14) und somit zt+1 = 0. Ist dagegen zt = n, folgt πs1 (zt) = √ 3 > 1 = πs2 (zt) (12.15) und damit zt+1 = n. Beide Zustände sind absorbierend. Sind sie einmal erreicht, werden sie unter dem Regime der Dynamik (12.13) nicht wieder verlassen. Wichtig ist zu bemerken, dass diese Dynamik, die so genannte reine Selektionsdynamik, immer zu homogenen Populationen führt, d.h. zu Populationen, in denen nur eine einzige Strategie gespielt wird. 12.3.3 Selektions– und Mutationsdynamik Die Dynamik ändert sich durch die Einführung von Mutation. Zusätzlich zur Selektion sei angenommen, dass jeder Spieler in jeder Periode mit der (annahmegemäß sehr kleinen) Wahrscheinlichkeit ε seine Strategie ins Gegenteil ändert. Hat also ein Spieler im Rahmen der Selektion für Periode t zunächst die Strategie s1 angenommen, so wechselt er mit der Wahrscheinlichkeit ε die Strategie und spielt in t + 1 die Strategie s2. Analoges gilt für einen Wechsel von s2 zu s1. Nun lässt sich fragen, wie viele Mutationen nötig sind, um von einer Population mit zt = 0 zu einer mit zt+1 = n bzw. um von einer Population mit zt = n zu einer mit zt+1 = 0 zu wechseln. Ist die Population in t vor der Mutationsphase vom Typ zt = n, so müssen, um zu einer Population vom Typ zt+1 = 0 überzugehen, so viele Spieler „mutieren“, dass πs2 (z̃t)> πs1 (z̃t) wird. z̃t soll dabei die Anzahl von s1–Spielern nach der Mutation bezeichnen. Es muss also gelten, dass πs2 (z̃t) > πs1 (z̃t) (12.16) ⇔ 1 > √ 3(z̃t −1) n−1 (12.17) ⇔ z̃t < 1− n−1√ 3 . (12.18) Um also von einem Stand von zt = n auf weniger als 1− n−1√3 s1–Spieler zu gelangen, sind mehr als n− ( 1− n−1√ 3 ) Mutationen nötig. Bezeichnet mn0 206 12. Evolutionäre Spiele die Anzahl der Mutationen, die für den genannten Übergang von zt = n zu zt+1 = 0 überschritten werden muss, gilt folglich mn0 = n− ( 1− n−1√ 3 ) (12.19) ⇔ mn0 = (n−1) √ 3−n+1√ 3 . (12.20) Nochmals, mit anderen Worten: Um durch Selektion und anschließende Mutation von einer Population mit zt = n zu einer Population mit zt+1 = 0 zu gelangen, sind mehr als mn0 viele Mutationen nötig. Außerdem lässt sich auch nach dem entgegengesetzten Übergang fragen, also bestimmen, wie viele Mutationen nötig sind, um von zt = 0 zu zt+1 = n überzugehen. Hier muss also gelten, dass πs1 (z̃t) > πs2 (z̃t) ⇔ z̃t = n−1√ 3 +1 . Analog zur vorangehenden Überlegung lässt sich feststellen, dass für einen solchen Übergang mehr als m0n Mutationen notwendig sind: m0n = n−1√ 3 +1 . (12.21) Nun lässt sich schließlich ermitteln, welcher der beiden möglichen Populationszustände leichter, d.h. mit weniger Mutationen, erreichbar ist, und welcher der beiden Zustände mit weniger Mutationen verlassen werden kann. zt = n zt = 0 > mn0 > m0n Abbildung 12.1: Mutationen zum Übergang zwischen den möglichen Populationszuständen Um zt = n zu erreichen, sind mehr als m0n Mutationen nötig. Um diesen Zustand zu verlassen, bedarf es mehr als mn0 Mutationen (s. Abb. 12.1). Für 12.3 Evolutionäre Gleichgewichtsselektion: Stochastische Stabilität 207 den Zustand zt = 0 ist dies genau anders herum. Es gilt also, die Werte m0n und mn0 miteinander zu vergleichen. Es ergibt sich m0n > mn0 (12.22) ⇔ (n−1) √ 3−n+1√ 3 > n−1√ 3 +1 (12.23) ⇔ n > 2 (√ 3−1 ) √ 3−2 . (12.24) Der Zustand zt = n ist also schwerer (d.h. mit mehr Mutationen) zu erreichen als zu verlassen, falls der Zusammenhang (12.24) gilt. Da der Ausdruck auf der rechten Seite des Größerzeichens in (12.24) negativ ist, ist diese Bedingung für jedes n > 0, d.h. für jede positive Populationsgröße erfüllt. Es lässt sich also ohne Einschränkung an Allgemeinheit festhalten, dass zt = n schwerer zu erreichen als zu verlassen und daher umgekehrt zt = 0 schwerer zu verlassen als zu erreichen ist. Dieser Gedanke lässt sich formalisieren, indem man für jeden Populationszustand das zugehörige stochastische Potenzial errechnet. Das stochastische Potenzial eines Populationszustandes ergibt sich als Differenz zwischen der Anzahl von Mutationen, die nötig sind, um den Zustand zu verlassen, und der nötigen Anzahl von Mutationen, um den Zustand zu erreichen.7 Die entsprechenden Werte SP(zt = n) und SP(zt = 0) lauten folglich SP(zt = n) = mn0 −m0n (12.25) = − 1√ 3 [( 2− √ 3 ) n+2 (√ 3−1 )] (12.26) < 0 (12.27) SP(zt = 0) = m0n −mn0 = −SP(zt = n) > 0 . (12.28) Das stochastische Potenzial von zt = n ist negativ, dieser Zustand lässt sich leichter verlassen als erreichen. Bei zt = 0 ist dies genau anders herum. Folglich ist also zt = 0 wesentlich weniger „anfällig“ für Mutationen und wird deshalb langfristig häufiger vorkommen als zt = n. Für eine Selektions–Mutations–Dynamik mit sehr kleiner Mutationswahrscheinlichkeit ε und folglich sehr seltenen Mutationen wird deshalb langfristig sehr viel häufiger eine Population vom Typ zt = 0 als vom Typ zt = n vorliegen, d.h. langfristig spielen die Mitglieder der Population 7 Vega-Redondo (1996, S. 132) definiert das stochastische Potenzial genau anders herum, also als Anzahl nötiger Mutationen zum Erreichen des Zustandes minus Anzahl nötiger Mutationen zum Verlassen des Zustandes. Die hier im Buch angegebene Definition resultiert aber in anschaulicheren Werten: Je höher hier das Potenzial, desto „stabiler“ ist der Zustand. 208 12. Evolutionäre Spiele meistens die Strategie s2 und damit das zugehörige risikodominante Nash– Gleichgewicht. Dieses Gleichgewicht, das unter dem Regime seltener Mutationen langfristig am häufigsten gespielt wird, heißt stochastisch stabiles Gleichgewicht. 12.4 Zwei–Populations–Spiele In Spielen, die in ihrer einfachsten Form nicht symmetrisch sind, lässt sich das oben vorgestellte Konzept der Evolutionsdynamik nicht verwenden. Als Beispiel soll das „Ultimatum–Minispiel“ (Normalform in Tab. 12.4) genutzt werden. Das Ultimatum–Minispiel, so behaupten wenigstens Binmore und R 1− pN pN Y N P pH H 2, 2 2, 2 1− pH L 3, 1 0, 0 Tabelle 12.4: Ultimatum–Minispiel. Normalform Samuelson (1994) und Binmore et al. (1995), gibt entscheidende Wesenszüge des „großen“ Ultimatum–Spiels wieder. Insbesondere besäße das Spiel, würde es sequentiell und mit P als erstem Spieler gespielt, ein teilspielperfektes Gleichgewicht bei (L, Y ). Diese Eigenschaften sind aber im Zusammenhang relativ unbedeutend. Wichtiger sind die dynamischen Eigenschaften des Spiels im evolutionären Kontext. Die Strategiemengen der beiden Spieler sind nun verschieden: Proposer, P, besitzen die Strategiemenge SP = {H, L}, Responder, R, die Menge SR = {Y, N}. Würden sowohl Proposer als auch Responder zur selben Population gehören, wären Teile des Spiels undefiniert: Was ist, wenn ein Proposer das Spiel gegen einen anderen Proposer spielen muss? Was passiert bei einem Spiel Responder gegen Responder? Um diesem Problem aus dem Wege zu gehen, konstruiert man im Fall von Spielern mit unterschiedlichen Strategiemengen Zwei–Populations–Spiele. Im Beispiel existieren in jeder Zeitperiode parallel zwei Populationen, eine Population aus Proposern und eine aus Respondern. In jeder Periode wird eine Reihe von Zwei–Personen–Ultimatum–Minispielen gespielt. Dazu wird jeweils aus jeder der Populationen zufällig ein Spieler ausgewählt, die beiden Spieler spielen gegeneinander und gewinnen so ihre Auszahlung. Die Dynamik des evolutionären Ultimatum–Minispiels lässt sich beispielsweise durch eine Replikator–Dynamik beschreiben, die der Dynamik 12.4 Zwei–Populations–Spiele 209 aus (12.5) sehr ähnlich ist. Es ist allerdings zu beachten, dass nun die erwarteten Auszahlungen jeder Strategie einer Population von den Populationsanteilen in der jeweils andern Population abhängt. So lauten die erwarteten Auszahlungen für die Proposer πH(t) = 2 ((1− pN(t))+2 pN(t) , πL(t) = 3−3 pN(t) . Eine Replikatordynamik, die der aus (12.5) entspricht, hat die Form pH(t +1) = pH(t) πH(t) πP(t) . (12.29) Dabei steht πP(t) für die populationsmittlere Auszahlung der Proposer in t. Durch Einsetzen von πP(t) = pH(t)πH(t)+(1− pH(t)) πL(t) ergibt sich (12.29) im Ultimatum–Minispiel konkret als pH(t +1) = pH(t) 2 3− pH(t)−3 pN(t) [1− pH(t)] . (12.30) Es ist zu erkennen, dass für die Bestimmung der Dynamik der Proposer– Population die Mischungsverhältnisse in beiden Populationen wichtig sind, denn in (12.30) erscheinen sowohl pH(t) als auch pN(t). Analog lässt sich auch die Dynamik der Responder–Population errechnen. Es ergibt sich pN(t +1) = pN(t) 2 pH(t) 1+ pH(t)− pN(t)+ pH(t) pN(t) . (12.31) Das System aus (12.30) und (12.31) kennzeichnet die evolutionäre Dynamik im Ultimatum–Minispiel. Diese Gleichungen lassen sich numerisch simulieren, d.h. iterieren: Man setzt (relativ willkürlich) Startwerte für pH(0) und pN(0) und errechnet hieraus die Werte für pH(1) und pN(1) u.s.w. Die Resultate lassen sich in einem System grafisch darstellen. Dies ist in der Abbildung 12.2 geschehen. Die Abbildungen zeigen den Verlauf der Populationsanteile pN(t) (Abszisse) und pH(t) (Ordinate) über die Zeit. Teilabbildung 12.2(a) zeigt die Dynamik für einen Startpunkt von pN(0) = 0.2, pH(0) = 0.8, Teilabbildung 12.2(b) zeigt Trajektorien für verschiedene Startpunkte. An den Abbildungen ist zu erkennen, dass die Dynamik, abhängig von den Startwerten, zu zwei Bereichen hin konvergiert. Eine große Anzahl der Trajektorien bewegt sich auf den Bereich pH = 1 hin, von wo aus die 210 12. Evolutionäre Spiele 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 p H pN (a) pN(0) = 0.2, pH(0) = 0.8 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 p H pN (b) verschiedene Startwerte Abbildung 12.2: Trajektorien der Evolutionsdynamik reine Replikator–Dynamik keine weitere Bewegung mehr zulässt: Der Bereich pH = 1 ist ein absorbierender Bereich der Replikatordynamik im Fall der Ultimatum–Minispiels. Der zweite Attraktor der Dynamik ist der Punkt pH = pN = 0. Dies ist der Punkt, in dem alle Proposer L und alle Responder Y spielen, also das teilspielperfekte Gleichgewicht des zugrundeliegenden Spiels in der sequentiellen Form mit den Proposern als ersten Spielern jedes Stufenspiels. 12.5 Anhang: Übergang von diskreter zu stetiger Replikatordynamik Ausgehend von den absoluten Anzahlen von Hawk– und Dove–Spielern lassen sich die Populationsanteile bestimmen. Hier soll exemplarisch nur der Anteil der Hawk–Spieler in t + τ , pH(t + τ) bestimmt werden: pH(t + τ) = NH(t + τ) N(t + τ) (12.32) = NH(t)(1+ τ πH(t)) NH(t)(1+ τ πH(t))+ND(t)(1+ τ πD(t)) ∣ ∣ ∣ ∣ ·N(t) N(t) = pH(t)(1+ τ πH(t)) pH(t)(1+ τ πH(t))+ pD(t)(1+ τ πD(t)) . (12.33) Der Nenner aus (12.33) lässt sich vereinfachen: 12.5 Anhang: Übergang von diskreter zu stetiger Replikatordynamik 211 pH(t)(1+ τ πH(t))+ pD(t)(1+ τ πD(t)) (12.34) = pH(t)+ τ pH(t)πH(t)+ pD(t)+ τ pD(t)πD(t) (12.35) = 1+ τ [pH(t)πH(t)+ pD(t)πD(t)] (12.36) = 1+ τ π(t) . (12.37) Einsetzen von (12.37) in (12.33) ergibt pH(t + τ) = pH(t)(1+ τ πH(t)) 1+ τ π(t) (12.38) Die Veränderung des Anteils der Hawk–Spieler von Zeitpunkt t zu Zeitpunkt t + τ beträgt damit pH(t + τ)− pH(t) = pH(t) [ 1+ τ πH(t)−1− τ π(t) ] 1+ τ π(t) (12.39) = pH(t)τ πH(t)−π(t) 1+ τ π(t) . (12.40) Die Veränderung pro Zeitinkrement τ beträgt pH(t + τ)− pH(t) τ = pH(t) πH(t)−π(t) 1+ τ π(t) . (12.41) Um zur zugehörigen Differentialgleichung zu gelangen, muss nun noch der Grenzwert der relativen Veränderung für das Zeitinkrement τ gegen Null gebildet werden. Dies ist identisch mit der ersten Ableitung des Populationsanteils pH nach der Zeit. d pH d t = ṗH = lim τ→0 pH(t + τ)− pH(t) τ (12.42) = lim τ→0 pH(t) πH(t)−π(t) 1+ τ π(t) . (12.43) Es resultiert schließlich ṗH = pH (πH −π) . (12.44)

Chapter Preview

References

Zusammenfassung

Vorteile

- Alle wichtigen Konzepte der modernen Spieltheorie

- Ein Klassiker in Neuauflage

Stimmen zum Werk

"(…) Wer eine kompakte und verständliche Einführung in die moderne Spieltheorie sucht, ist mit dem "Riechmann" hervorragend bedient. Das Buch enthält nicht nur alles Wissenswerte zu diesem Thema, es überzeugt auch durch eine sehr eingängige Stoffvermittlung, durch die selbst komplizierte Zusammenhänge verständlich werden. (…)"

in: Studium, 20.04.2008, 2. Auflage 2008

Zum Werk

Spieltheorie intuitiv - das muss nicht bedeuten: Spieltheorie ohne Mathematik. Dieses Lehrbuch gibt eine Einführung in alle wichtigen Konzepte der modernen Spieltheorie, indem es die "Idee" in den Mittelpunkt stellt, ohne dabei die notwendigen Formalia zu vernachlässigen.

Der Inhalt des Buches erstreckt sich von den Grundlagen der Spieltheorie über fortgeschrittene Themen wie Lernen in Spielen oder dynamische Gleichgewichtskonzepte in der evolutionären Spieltheorie.

Die Einbeziehung von Resultaten ökonomischer Laborexperimente erweitert die Perspektive des Buches über den Horizont herkömmlicher Werke zur Spieltheorie hinaus.

Insofern ist das Buch sowohl für Anfänger als auch für fortgeschrittene Spieltheoretiker gleichermaßen geeignet und nützlich.

Autor

Prof. Dr. Thomas Riechmann, Kaiserslautern.

Zielgruppe

Studierende der Wirtschaftswissenschaften.