Tausendfüßler-Spiel - Centipede game

In der Spieltheorie ist das Tausendfüßler-Spiel , das erstmals 1981 von Robert Rosenthal eingeführt wurde , ein Spiel mit umfangreicher Form, bei dem sich zwei Spieler abwechseln, entweder einen etwas größeren Anteil an einem zunehmenden Pot zu nehmen oder den Pot an den anderen Spieler weiterzugeben. Die Auszahlungen sind so angeordnet, dass, wenn man den Pot an seinen Gegner weitergibt und der Gegner den Pot in der nächsten Runde nimmt, man etwas weniger erhält, als wenn man den Pot in dieser Runde gewonnen hätte, aber nach einem zusätzlichen Wechsel ist die mögliche Auszahlung höher. Obwohl ein Spieler in jeder Runde einen Anreiz hat, den Pot zu gewinnen, wäre es daher besser, zu warten. Obwohl das traditionelle Tausendfüßlerspiel ein Limit von 100 Runden hatte (daher der Name), wird jedes Spiel mit dieser Struktur, aber einer anderen Anzahl von Runden, als Tausendfüßlerspiel bezeichnet.

Das einzigartige Subgame-perfekte Gleichgewicht (und jedes Nash-Gleichgewicht ) dieser Spiele führt dazu, dass der erste Spieler den Pot in der ersten Runde des Spiels gewinnt ; in empirischen Tests tun dies jedoch relativ wenige Spieler und erzielen dadurch eine höhere Auszahlung als im Teilspiel Perfekt und Nash-Gleichgewicht. Diese Ergebnisse werden verwendet, um zu zeigen, dass unter bestimmten Umständen perfekte Gleichgewichte des Teilspiels und Nash-Gleichgewichte nicht in der Lage sind, menschliches Spiel vorherzusagen. Das Centipede-Spiel wird häufig in einführenden Spieltheoriekursen und -texten verwendet, um das Konzept der Rückwärtsinduktion und der iterativen Eliminierung dominierter Strategien hervorzuheben , die einen Standardweg zur Bereitstellung einer Lösung für das Spiel darstellen.

Spiel

Eine mögliche Version eines Tausendfüßler-Spiels könnte wie folgt gespielt werden:

Betrachten Sie zwei Spieler: Alice und Bob . Alice bewegt sich zuerst. Alice hat zu Beginn des Spiels zwei Münzstapel vor sich: Ein Stapel enthält 4 Münzen und der andere Stapel enthält 1 Münze. Jeder Spieler hat zwei Züge zur Verfügung: entweder den größeren Münzstapel "nehmen" und den kleineren Stapel dem anderen Spieler geben oder beide Stapel über den Tisch zum anderen Spieler "schieben". Jedes Mal, wenn die Münzstapel über den Tisch laufen, verdoppelt sich die Menge der Münzen in jedem Stapel. Nehmen wir zum Beispiel an, Alice beschließt, die Stapel bei ihrem ersten Zug zu "schieben", indem sie die Stapel mit 1 und 4 Münzen an Bob übergibt und sie auf 2 und 8 verdoppeln. Bob könnte nun seinen ersten Zug verwenden, um entweder die Stapel mit 8 Münzen und geben Sie Alice 2 Münzen, oder er kann die beiden Stapel wieder über den Tisch zu Alice "schieben", wodurch die Stapel wieder auf 4 und 16 Münzen erhöht werden. Das Spiel wird für eine festgelegte Anzahl von Runden fortgesetzt oder bis ein Spieler beschließt, das Spiel zu beenden, indem er einen Haufen Münzen einsteckt.

Das Hinzufügen von Münzen wird als Externalität angesehen , da es von keinem Spieler beigesteuert wird.

Formale Definition

Das Tausendfüßlerspiel kann als where und geschrieben werden . Spieler und Stellvertreter, beginnend mit Spieler , und dürfen in jedem Zug einen Zug mit maximal Runden spielen. Das Spiel endet, wenn zum ersten Mal gespielt wird, ansonsten nach Zügen, wenn nie gespielt wird. ${\displaystyle {\mathcal {G}}(N,~m_{0},~m_{1})}$${\displaystyle N,m_{0},m_{1}\in\mathbb{N}}$${\displaystyle m_{0}>m_{1}}$${\displaystyle I}$${\displaystyle II}$${\displaystyle I}$${\displaystyle \{\mathrm {nehmen} ,\mathrm {schieben} \}}$${\displaystyle N}$${\displaystyle \mathrm {nehmen}}$${\displaystyle N}$${\displaystyle \mathrm {nehmen}}$

Angenommen, das Spiel endet in der Runde mit dem Spieler , der den letzten Zug macht. Dann wird das Ergebnis des Spiels wie folgt definiert: ${\displaystyle t\in\{0,\ldots ,N-1\}}$${\displaystyle p\in\{I,II\}}$

• Wenn gespielt , dann erhält man Münzen und Gewinne .${\displaystyle p}$${\displaystyle \mathrm {nehmen}}$${\displaystyle p}$${\displaystyle 2^{t}m_{0}}$${\displaystyle p^{\ast}}$${\displaystyle 2^{t}m_{1}}$
• Wenn gespielt , dann erhält man Münzen und Gewinne .${\displaystyle p}$${\displaystyle \mathrm{drücken}}$${\displaystyle p}$${\displaystyle 2^{t+1}m_{1}}$${\displaystyle p^{\ast}}$${\displaystyle 2^{t+1}m_{0}}$

Hier bezeichnet die anderen Spieler. ${\displaystyle p^{\ast}\in \{I,II\}}$

Gleichgewichtsanalyse und Rückwärtsinduktion

Eine Extensive Form- Darstellung eines vierstufigen Tausendfüßler-Spiels, das nach vier Runden mit der Aufteilung des Geldes endet. Das Weiterreichen der Münzen über den Tisch wird durch einen Zug von R dargestellt (über die Reihe des Gitters gehen, manchmal auch durch A für quer) und das Einstecken der Münzen ist ein Zug D (das Gitter nach unten). Die Zahlen 1 und 2 am oberen Rand des Diagramms zeigen den abwechselnden Entscheidungsträger zwischen zwei Spielern, hier als 1 und 2 bezeichnet, und die Zahlen am unteren Rand jedes Zweigs zeigen die Auszahlung für Spieler 1 bzw. 2.

Standardmäßige spieltheoretische Tools sagen voraus, dass der erste Spieler in der ersten Runde überlaufen wird und den Münzstapel für sich selbst nimmt. Im Tausendfüßler-Spiel besteht eine reine Strategie aus einer Reihe von Aktionen (eine für jeden Wahlpunkt im Spiel, auch wenn einige dieser Wahlpunkte möglicherweise nie erreicht werden) und eine gemischte Strategie ist eine Wahrscheinlichkeitsverteilung über die möglichen reinen Strategien. Es gibt mehrere reine Strategie- Nash-Gleichgewichte des Tausendfüßler-Spiels und unendlich viele gemischte Strategie-Nash-Gleichgewichte. Es gibt jedoch nur ein Teilspiel-perfektes Gleichgewicht (eine beliebte Verfeinerung des Nash-Gleichgewichtskonzepts).

In dem einzigartigen Teilspiel perfektes Gleichgewicht entscheidet sich jeder Spieler, bei jeder Gelegenheit zu scheitern. Dies bedeutet natürlich Überläufer auf der ersten Stufe. In den Nash-Gleichgewichten können jedoch die Aktionen, die nach den anfänglichen Wahlmöglichkeiten durchgeführt werden (auch wenn sie nie erreicht werden, da der erste Spieler sofort defekt ist), kooperativ sein.

Der Fehler des ersten Spielers ist das einzigartige perfekte Gleichgewicht des Teilspiels und wird von jedem Nash-Gleichgewicht benötigt , es kann durch Rückwärtsinduktion hergestellt werden . Angenommen, zwei Spieler erreichen die letzte Runde des Spiels; der zweite Spieler wird besser abschneiden, indem er einen etwas größeren Anteil des Pots nimmt. Da wir annehmen, dass der zweite Spieler überlaufen wird, schneidet die erste Spielerin besser ab, wenn sie in der vorletzten Runde überläuft und eine etwas höhere Auszahlung erhält, als sie erhalten hätte, wenn sie dem zweiten Spieler in der letzten Runde erlaubt hätte, überzulaufen. Aber wenn man dies weiß, sollte der zweite Spieler in der drittletzten Runde überlaufen und eine etwas höhere Auszahlung erhalten, als er erhalten hätte, wenn er dem ersten Spieler in der vorletzten Runde erlaubt hätte, überzulaufen. Diese Argumentation geht rückwärts durch den Spielbaum, bis man zu dem Schluss kommt, dass die beste Aktion darin besteht, dass der erste Spieler in der ersten Runde überfällt. Die gleiche Argumentation kann für jeden Knoten im Spielbaum gelten.

Für ein Spiel, das nach vier Runden endet, geht diese Argumentation wie folgt vor. Wenn wir die letzte Runde des Spiels erreichen waren, Spieler 2 würde es besser machen , indem Sie d statt r , Empfangen 4 Münzen statt 3. Angesichts der Tatsache, dass 2 wählen , wird d , 1 sollte wählen D in der vorletzten Runde , erhält 3 statt 2. Da 1 in der vorletzten Runde D wählen würde , sollte 2 in der drittletzten Runde d wählen und 2 statt 1 erhalten. Aber in Anbetracht dessen sollte Spieler 1 D in der ersten Runde wählen , erhält 1 statt 0.

Es gibt eine große Anzahl von Nash-Gleichgewichten in einem Tausendfüßler-Spiel, aber in jedem defekten Spieler des ersten Spielers in der ersten Runde und des zweiten Spielers in der nächsten Runde häufig genug, um den ersten Spieler vom Passen abzuhalten. In einem Nash-Gleichgewicht zu sein, erfordert nicht, dass Strategien zu jedem Zeitpunkt des Spiels rational sind , wie im perfekten Gleichgewicht des Teilspiels. Dies bedeutet, dass Strategien, die in den nie erreichten späteren Runden des Spiels kooperativ sind, sich immer noch in einem Nash-Gleichgewicht befinden können. Im obigen Beispiel besteht ein Nash-Gleichgewicht darin, dass beide Spieler in jeder Runde (auch in den späteren Runden, die nie erreicht werden) überlaufen. Ein weiteres Nash-Gleichgewicht besteht darin, dass Spieler 1 in der ersten Runde überspringt, aber in der dritten Runde passt und Spieler 2 bei jeder Gelegenheit überfällt.

Empirische Ergebnisse

Mehrere Studien haben gezeigt, dass das Spiel des Nash-Gleichgewichts (und gleichermaßen des perfekten Gleichgewichts des Teilspiels) selten beobachtet wird. Stattdessen zeigen die Probanden regelmäßig teilweise Kooperation, indem sie mehrere Züge lang „R“ (oder „r“) spielen, bevor sie schließlich „D“ (oder „d“) wählen. Es ist auch selten, dass die Probanden während des gesamten Spiels kooperieren. Für Beispiele siehe McKelvey und Palfrey (1992) sowie Nagel und Tang (1998). Wie in vielen anderen spieltheoretischen Experimenten haben Wissenschaftler den Effekt einer Erhöhung der Einsätze untersucht. Wie bei anderen Spielen, zum Beispiel dem Ultimatum-Spiel , nähert sich das Spiel mit steigenden Einsätzen dem Nash-Gleichgewichtsspiel (aber erreicht es nicht).

Erklärungen

Da die empirischen Studien zu Ergebnissen geführt haben, die mit der traditionellen Gleichgewichtsanalyse nicht vereinbar sind, wurden mehrere Erklärungen für dieses Verhalten angeboten. Rosenthal (1981) schlug vor, dass es vorteilhaft sein kann, nicht in der ersten Runde zu überlaufen, wenn man Grund zu der Annahme hat, dass sein Gegner von Nashs Verhalten abweicht.

Ein Grund für die Annahme, dass Menschen vom Gleichgewichtsverhalten abweichen können, ist, wenn einige altruistisch sind . Die Grundidee ist, dass, wenn Sie gegen einen Altruisten spielen, diese Person immer kooperiert, und daher sollten Sie, um Ihre Auszahlung zu maximieren, in der letzten Runde und nicht in der ersten überlaufen. Wenn genug Menschen Altruisten sind, ist es den Preis wert, die Auszahlung der Überläufer in der ersten Runde zu opfern, um festzustellen, ob Ihr Gegner ein Altruist ist oder nicht. Nagel und Tang (1998) schlagen diese Erklärung vor.

Eine andere Möglichkeit beinhaltet Fehler. Wenn eine erhebliche Möglichkeit eines Handlungsfehlers besteht, vielleicht weil Ihr Gegner die Rückwärtsinduktion nicht vollständig durchdacht hat, kann es vorteilhaft (und rational) sein, in den ersten Runden zu kooperieren.

Parco, Rapoport und Stein (2002) zeigten jedoch, dass die Höhe der finanziellen Anreize einen tiefgreifenden Einfluss auf das Ergebnis eines Spiels mit drei Spielern haben kann: Je größer die Anreize zur Abweichung sind, desto größer ist die Neigung zum Lernverhalten in einem wiederholten Einzelspiel - Experimentelles Design spielen, um sich dem Nash-Gleichgewicht zu nähern.

Palacios-Huerta und Volij (2009) stellen fest, dass erfahrene Schachspieler anders spielen als College-Studenten. Mit steigendem Elo sinkt die Wahrscheinlichkeit, das Spiel fortzusetzen; alle Großmeister im Experiment stoppten bei ihrer ersten Gelegenheit. Sie kommen zu dem Schluss, dass Schachspieler mit der Verwendung von Rückwärtsinduktionsschlussfolgern vertraut sind und daher weniger lernen müssen, um das Gleichgewicht zu erreichen. In einem Versuch, diese Ergebnisse zu replizieren, finden Levitt, List und Sadoff (2010) jedoch stark widersprüchliche Ergebnisse, wobei null von sechzehn Großmeistern das Spiel am ersten Knoten stoppen.

Bedeutung

Wie das Gefangenendilemma stellt dieses Spiel einen Konflikt zwischen Eigeninteresse und gegenseitigem Nutzen dar. Wenn es durchgesetzt werden könnte, würden beide Spieler es vorziehen, dass sie beide während des gesamten Spiels kooperieren. Das Eigeninteresse eines Spielers oder das Misstrauen der Spieler kann sich jedoch stören und eine Situation schaffen, in der beide schlechter abschneiden, als wenn sie blind kooperiert hätten. Obwohl das Dilemma des Gefangenen aufgrund dieser Tatsache viel Aufmerksamkeit erregt hat, hat das Centipede Game relativ weniger Aufmerksamkeit erhalten.

Darüber hinaus hat Binmore (2005) argumentiert, dass einige Situationen der realen Welt durch das Centipede-Spiel beschrieben werden können. Ein Beispiel, das er präsentiert, ist der Warenaustausch zwischen Parteien, die sich gegenseitig misstrauen. Ein weiteres Beispiel, das Binmore (2005) mit dem Centipede-Spiel vergleicht, ist das Paarungsverhalten eines hermaphroditischen Wolfsbarsches, der abwechselnd Eier zur Befruchtung austauscht. In diesen Fällen finden wir Kooperationen im Überfluss.

Da die Auszahlungen für ein gewisses Maß an Kooperation im Centipede-Spiel so viel größer sind als das sofortige Übertreten, können die "rationalen" Lösungen, die durch Rückwärtsinduktion gegeben werden, paradox erscheinen. Dies, zusammen mit der Tatsache, dass Versuchspersonen regelmäßig im Centipede-Spiel zusammenarbeiten, hat eine Debatte über die Nützlichkeit der Idealisierungen ausgelöst, die in den Rückwärtsinduktionslösungen enthalten sind, siehe Aumann (1995, 1996) und Binmore (1996).

Siehe auch

• Rückwirkende Induktion
• Experimentelle Ökonomie
• Das Dilemma des Reisenden
• Unerwartetes Hängeparadoxon

Verweise

Externe Links

• EconPort-Artikel zum Centipede Game
• Rationalität und Spieltheorie - AMS Kolumne über das Tausendfüßlerspiel
• Online-Experiment im VeconLab
• Spiele das Centipede-Spiel in deinem Browser auf gametheorygame.nl