Ich habe versucht, ein missverstandenes Gefangenendilemma in Python zu implementieren. Mit diesem Programm habe ich wiederholt eine Strategie des Gefangenendilemma-Spiels simuliert und experimentiert.

Gefangenendilemma-Spiele werden häufig verwendet, um kollaboratives Verhalten zu analysieren, beispielsweise Absprachen zwischen Unternehmen, vor allem im wirtschaftlichen Bereich. Es gibt verschiedene andere Anwendungsbeispiele.

Im konventionellen Gefangenendilemma-Spielmodell wird angenommen, dass ** das Verhalten des Gegners direkt nachträglich beobachtet werden kann (vollständige Beobachtung) **, und die Spieler können die nächste Aktion basierend darauf entscheiden. Es ist fertig. In der realen Welt ist es jedoch oft unmöglich, das Verhalten der anderen Partei vollständig zu beobachten. In diesem Fall kann das herkömmliche Modell diese Situationen nicht gut erfassen.

Daher wurde in den letzten Jahren das Gefangenendilemma der ** unvollständigen Beobachtung ** aktiv untersucht. Bei der unvollständigen Beobachtung ist es möglich, ** Signale ** zu beobachten, die vom Verhalten der anderen Partei abhängen, anstatt das Verhalten der anderen Partei direkt zu beobachten.

Dieses Mal werden wir das Dilemma der wiederholten Gefangenen mit dieser unvollständigen Beobachtung simulieren.

Was ist das Dilemma des Gefangenen?

Das Gefangenendilemma ist eines der repräsentativsten Spiele in der Spieltheorie. Dieses Spiel wird oft in der folgenden Punktetabelle angegeben.

図1.png

Die Regel dieses Spiels ist, dass zwei Spieler $ X $ und $ Y $ sich für eine Zusammenarbeit ($ C : Zusammenarbeit) bzw. einen Verrat ( D $: Fehler) entscheiden. Die Punktzahl wird durch die von jedem Spieler gewählte Aktion bestimmt.

Wenn die Spieler $ X $ und $ Y $ die $ C $ des anderen wählen, können sie eine einigermaßen gute Punktzahl von $ 1 $ erzielen. Wenn entweder $ X $ oder $ Y $ $ C $ und der andere $ D $ wählt, erhält der Spieler, der $ C $ wählt, die niedrigste Punktzahl, $ -0,5 $. Der Spieler, der ， $ D $ wählt, kann die höchste Punktzahl von $ 1,5 $ erhalten. Wenn $ X $ und $ Y $ $ D $ für einander wählen, erhalten sie eine kleine Punktzahl von $ 0 $. Wenn Sie $ C $ für einander wählen, beträgt die Gesamtpunktzahl von beiden $ 2 \ (= 1 + 1) $, was die beste Punktzahl für das Ganze ist, und wenn der Gegner einseitig verrät, verliert der verratene Spieler viel Es hat eine Struktur wie

Auf diese Weise gibt es ein Dilemma, dass jeder Spieler wirklich kooperieren möchte, aber durch Verrat versucht wird.

Bei der Ausführung eines Spiels wird keine Zusammenarbeit zwischen egoistischen Spielern realisiert (Nash-Balance). Andererseits wird in dem ** wiederholten Gefangenendilemma-Spiel **, das dieses Spiel auf unbestimmte Zeit wiederholt, theoretisch bewiesen, dass eine Zusammenarbeit auch unter selbstsüchtigen Spielern (Gabeln) realisiert werden kann. Satz).

Daher wurde untersucht, welche Strategie in diesem sich wiederholenden Gefangenendilemma-Spiel stark ist (Beschleunigungsstab-Experiment).

Wiederholtes Spiel mit unvollständiger privater Beobachtung

Es unterscheidet sich vom traditionellen Gefangenendilemma-Spiel, bei dem eine perfekte Überwachung vorausgesetzt wird, bei der der Spieler alle in der Vergangenheit ergriffenen Maßnahmen genau beobachten kann. ** Imperfect Private Monitoring ** ermöglicht es Ihnen nicht, das Verhalten früherer Spieler direkt zu beobachten. Angenommen, Sie beobachten stattdessen ein Signal, das von den Aktionen des vorherigen Spielers abhängt. In diesem Spiel nehmen wir ** Private Monitoring ** an, das einzelne Signale empfängt. Das von jedem Spieler empfangene Signal kann vom Gegner nicht beobachtet werden.

Konkretes Beispiel

Das Gefangenendilemma der unvollständigen privaten Beobachtung setzt einen ** Preiswettbewerb ** der folgenden Einzelhändler voraus.

Wenn Sie im Einzelhandelspreiswettbewerb davon ausgehen, dass Sie dasselbe Produkt verkaufen, versuchen Sie, den Umsatz zu sichern, indem Sie den Preis für dieses Produkt beibehalten oder den Preis senken.

Der tatsächliche Gewinn eines Einzelhandelsgeschäfts wird durch die Anzahl der Besucher (Signal) und den Preis des Produkts (Ihr eigenes Verhalten) bestimmt. Wenn zum Beispiel die Preise beibehalten (kooperiert) werden, können die Kunden die Produkte zu einem hohen Preis verkaufen, ohne auf ein Geschäft beschränkt zu sein, und beide Geschäfte können einen angemessen hohen Gewinn erzielen. Ich werde.

Kunden haben die gleiche Struktur wie das Gefangenendilemma, da sie je nach Preis der Produkte in jedem Geschäft zunehmen oder abnehmen.

In einer solchen Situation werden die folgenden Fälle angenommen. Wenn jedes Geschäft seinen Preis beibehält, können beide Geschäfte normalerweise hohe Gewinne erzielen, aber die Anzahl der Besucher schwankt aufgrund verschiedener Faktoren. Beispielsweise können unvorhersehbare Nachfrageschocks und die unwissende Eröffnung ähnlicher Geschäfte in der Nachbarschaft die Anzahl der Geschäftskunden verringern (siehe Abbildung unten). Der Punkt des Ladengewinns ist, dass der Preis (das Verhalten) des von jedem Geschäft festgelegten Produkts nicht direkt mit dem Gewinn verbunden ist.

Andererseits kann das Geschäft auch den Preis des Produkts senken und Kunden gewinnen, so dass die andere Partei es nicht weiß (z. B. einen Preis, der niedriger als der Katalogpreis ist, nur vor dem Kunden zu präsentieren). Eine solche Situation kann im traditionellen Gefangenendilemma nicht erfasst werden.

Eine solche Situation wird von einem sich wiederholenden Spiel mit unvollständiger privater Beobachtung angenommen.

Spielinhalt

Definiere das Spiel.

Wiederholen Sie das in der folgenden Punktetabelle angegebene Spiel.

図2.png

Die Regel dieses Spiels ist, dass $ 2 $ Spieler $ X $ und $ Y $ wählen, ob sie kooperieren ($ C : kooperieren) oder verraten ( D $: defekt). Die Punktzahl wird durch die von jedem Spieler gewählte Aktion bestimmt.

Wenn der gegnerische Spieler $ C $ wählt, beobachtet er im Grunde ein ** Signal ** namens $ g $, was * gut * bedeutet. Wenn Sie zu diesem Zeitpunkt die Aktion $ C $ wählen, erhalten Sie $ 1 $ Punkte. Wenn Sie die Aktion $ D $ auswählen, erhalten Sie $ 1,5 $ Punkte. Wenn der gegnerische Spieler $ D $ wählt, beobachtet er das Signal $ b $, was * schlecht * bedeutet. Wenn Sie zu diesem Zeitpunkt die Aktion $ C $ wählen, erhalten Sie $ -0,5 $ Punkte. Wenn Sie die Aktion $ D $ auswählen, erhalten Sie $ 0 $ Punkte.

Die bisherigen Annahmen entsprechen fast denen des traditionellen Gefangenendilemma-Spiels.

Definieren Sie den Beobachtungsfehler.

In diesem Modell werden die Verhaltenssignale $ g $ und $ b $ aufgrund eines Fehlers aufgrund von Faktoren wie der Umgebung umgekehrt.

Selbst wenn Ihr Gegner $ C $ wählt, erhalten Sie möglicherweise ein Signal von $ b $, was bedeutet, dass Ihr Gegner $ D $ gewählt hat. Selbst wenn die andere Partei $ D $ wählt, erhalten Sie möglicherweise ein Signal von $ g $, was bedeutet, dass die andere Partei $ C $ gewählt hat. Das Beobachten eines Signals, das dem Signal entgegengesetzt ist, das das tatsächliche Verhalten auf diese Weise bedeutet, wird als ** Beobachtungsfehler ** bezeichnet.

Dieses Mal ist ** die Wahrscheinlichkeit, dass nur einer der Spieler ausfällt ** als $ \ epsilon $ definiert, und ** die Wahrscheinlichkeit, dass beide Spieler ausfallen **, als $ \ xi $ definiert. Es wird angenommen, dass die Fehlerraten $ \ epsilon $ und $ \ xi $ nicht sehr groß sind.

Definieren Sie die Strategie des Spielers.

Wir definieren die Strategie von Spieler $ X $ als $ {\ bf p} = (p_ {Cg}, p_ {Cb}, p_ {Dg}, p_ {Db}; p_0) . Diese Strategie wird als Memory-One-Strategie bezeichnet. Spieler, die diese Strategie anwenden, bestimmen diese Aktion wahrscheinlich ( C $ oder $ D $), indem sie nur die Ergebnisse des vorherigen Spiels berücksichtigen.

Zum Beispiel ist $ p_ {Cg} $ die Wahrscheinlichkeit einer Zusammenarbeit in diesem Spiel, wenn Spieler $ X $ $ C $ auswählt und $ g $ im vorherigen Spiel beobachtet. $ p_ {Cb} $ ist die Wahrscheinlichkeit einer Zusammenarbeit in diesem Spiel, wenn Spieler $ X $ $ C $ auswählt und $ b $ im vorherigen Spiel beobachtet. Andere werden auf die gleiche Weise betrachtet. $ p_0 $ ist die Wahrscheinlichkeit einer Zusammenarbeit im ersten Spiel.

In ähnlicher Weise lautet die Strategie für Spieler $ Y $ $ {\ bf q} = (q_ {Cg}, q_ {Cb}, q_ {Dg}, q_ {Db}; q_0) $.

Die folgende Abbildung ist ein Beispiel für den Übergang von $ CC $ (gegenseitige Zusammenarbeit) zu $ CD $ ($ X $ Zusammenarbeit, $ Y $ Verrat). In dieser Abbildung können Sie nachvollziehen, wie jeder Spieler das Signal beobachtet und in den nächsten Zustand übergeht, basierend auf der oben definierten Strategie gemäß der von jedem Spieler festgelegten Aktion. Obwohl dies in dieser Simulation nicht relevant ist, kann dies als Markov-Prozess angesehen werden, und die Übergangsmatrix dieses Spiels kann aus dem folgenden Übergangsdiagramm definiert werden.

Python-Programm

Das folgende Python-Programm implementiert das oben Gesagte. Sie können durch Simulation herausfinden, welche Strategie stark ist. Unten lautet die Strategie jedes Spielers $ {\ bf p} = (1/2, 1/2, 1/2, 1/2; 1/2) $ und $ {\ bf q} = (1/2, 1/2, 1/2, 1/2; 1/2) $. Die Häufigkeit, mit der das Spiel wiederholt wird, beträgt 100.000 US-Dollar. Die Fehlerraten sind auf $ \ epsilon = 0,05 $ und $ \ xi = 0,05 $ festgelegt.

import random

max_t = 100000 #Anzahl der Spielwiederholungen

point  = {'x' : 0, 'y' : 0} #Gesamtpunktzahl des Spielers
action = {'x' : None, 'y' : None} #Spielerverhalten C oder D.
signal = {'x' : None, 'y' : None} #Vom Spieler beobachtete Signale
state  = {'x' : '0', 'y' : '0'} #Spielstatus einstellen
payoff = {'Dg':1.5, 'Cg':1.0, 'Db':0, 'Cb':-0.5} #Spielergebnis
epsilon = 0.05; xi = 0.05 #Nur ein Fehler, Wahrscheinlichkeit beider Fehler

p = {'Cg':1/2, 'Cb':1/2, 'Dg':1/2, 'Db':1/2, '0' :1/2} #Spieler X Strategie
q = {'Cg':1/2, 'Cb':1/2, 'Dg':1/2, 'Db':1/2, '0' :1/2} #Strategie von Spieler Y.

#Spiel wiederholen
for t in range(max_t):
    #Wählen Sie C oder D basierend auf dem Ergebnis des vorherigen Spiels
    action['x'] = 'C' if random.random() < p[state['x']] else 'D'
    action['y'] = 'C' if random.random() < q[state['y']] else 'D'
    #Signal
    signal['x'] = 'g' if action['y'] == 'C' else 'b'
    signal['y'] = 'g' if action['x'] == 'C' else 'b'
    #Beobachtungsfehler
    if random.random() < 2 * epsilon:
        player = 'x' if random.random() < 0.5 else 'y'
        if signal[player] == 'g':
            signal[player] = 'b'
        else:
            signal[player] = 'g'
    elif 2 * epsilon < random.random() < 2 * epsilon + xi:
        for player in ['x', 'y']:
            if signal[player] == 'g':
                signal[player] = 'b'
            else:
                signal[player] = 'g'
    #Verteilen Sie die Gewinne basierend auf Aktionen und Signalen
    for player in ['x', 'y']:
        if action[player] == 'C' and signal[player] == 'g':
            point[player] += payoff['Cg']
        elif action[player] == 'C' and signal[player] == 'b':
            point[player] += payoff['Cb']
        elif action[player] == 'D' and signal[player] == 'g':
            point[player] += payoff['Dg']
        elif action[player] == 'D' and signal[player] == 'b':
            point[player] += payoff['Db']        
        #Ersetzen Sie die Spielergebnisse
        state[player] = action[player] + signal[player]

#Geben Sie die durchschnittliche Punktzahl jedes Spielers aus
print('Player X: {} Points'.format(point['x'] / max_t))
print('Player Y: {} Points'.format(point['y'] / max_t))

Wenn dieses Programm ausgeführt wird, werden die folgenden Ausführungsergebnisse erhalten. ..

Player X: 0.49855 Points
Player Y: 0.49827 Points

Das heißt, $ {\ bf p} = (1/2, 1/2, 1/2, 1/2; 1/2) $ und $ {\ bf q} = (1/2, 1/2, 1 / 2, 1/2; 1/2) Wenn Sie eine $ -Strategie spielen Sie können sehen, dass die Ergebnisse fast gleich sind. Dies ist ein natürliches Ergebnis.

Als nächstes möchte ich verschiedene Strategien ausprobieren.

Experimentieren Sie mit der Null-Determinanten-Strategie

Die Zero-Determinant-Strategie (ZD-Strategie) ist eines der Dilemma-Spiele des Gefangenen. Zuvor habe ich es in Strategie zur Ausbeutung von Gegnern im Gefangenendilemma (Qiita) eingeführt. Diese ZD-Strategie ist eine einfache Strategie und kann durch die Speicher-1-Strategie $ \ bf p $ oder $ \ bf q $ definiert werden (die Ableitung der ZD-Strategie selbst ist etwas schwierig). Dieses Mal werden wir mit dieser Strategie in diesem missverstandenen Gefangenendilemma experimentieren.

Die ZD-Strategie umfasst die Equalizer-Strategie und die Extortion-Strategie als bekannte Teilstrategien. Die Equalizer-Strategie kann die durchschnittliche Punktzahl des Gegners festlegen, und die Erpressungsstrategie Erpressung bedeutet Erpressung, und diese Strategie kann die Punktzahl des Gegners ausnutzen.

Dies ist das Ende der detaillierten Erklärung, und wir werden mit dieser Strategie experimentieren.

Equalizer-Strategie

Egal welche Strategie Ihr Gegner hat, Sie können die Punktzahl Ihres Gegners festlegen. Equalizer-Strategie, um die durchschnittliche Punktzahl Ihres Gegners $ 0,5 $ Punkte $ {\ bf p} = (0,8, 0,365217,0,634783, 0,2; 1/2) $ und $ {\ bf q} = (1/2, 1/2, Wenn Sie 1/2, 1/2; 1/2) $ einstellen und die Simulation ausführen, erhalten Sie die folgenden Ergebnisse.

Player X: 0.496385 Points
Player Y: 0.50177 Points

Sicherlich ist es "Spieler Y: 0,50177 Punkte", und Sie können sehen, dass die Punktzahl des Gegners nahe bei 0,5 $ Punkten liegt. Es kann also vorkommen, dass Sie im Dilemma des Gefangenen die Strategie des Gegners mit der stärksten Strategie für immer Verrat ($ ALLD $ -Strategie) $ {\ bf q} = (0,0,0,0; 0) $ ausprobieren ， Die folgenden Ergebnisse werden erhalten.

Player X: -0.004545 Points
Player Y: 0.50022 Points

Immerhin ist es "Spieler Y: 0,50022 Punkte", und Sie können sehen, dass die Punktzahl des Gegners nahe bei 0,5 $ Punkten liegt.

In der folgenden Abbildung erhält die gegnerische Strategie $ \ bf q $ zusätzlich zu der obigen Strategie verschiedene Zufallszahlen, und es wird eine Simulation durchgeführt. $ \ Bf q $ wurde für 100 Strategien generiert und das Programm für jede ausgeführt. Aus dieser Abbildung können Sie ersehen, dass der Gegner unabhängig von der Strategie des Gegners $ \ bf q $ auf den Punkt $ 0,5 $ festgelegt ist.

Der von der grauen Linie umgebene Bereich ist der Bereich, der sich auf die realisierbare Verstärkung bezieht. Die Gewinnbeziehung zwischen den beiden Spielern ist immer irgendwo in diesem Bereich. Die vertikale Achse ist die Punktzahl des Spielers, der die Equalizer-Strategie anwendet, und die horizontale Achse ist die Punktzahl des Gegners.

Daher kann die Equalizer-Strategie die Punktzahl des Gegners auch dann korrigieren, wenn ein Fehler vorliegt, unabhängig von der Strategie des Gegners.

Erpressungsstrategie

Es ist bekannt, dass die Erpressungsstrategie eine Strategie ist, um die Punktzahl des Gegners in einem normalen Gefangenendilemma fehlerfrei auszunutzen. Sie können mit einem Unentschieden gegen die stärkste Strategie des Verrats ($ ALLD $ Strategie) und die Erpressungsstrategie zurückkehren.

Ist es möglich, wenn ein Fehler vorliegt?

Ähnlich wie bei der für die Equalizer-Strategie erstellten Figur erhalten Sie die folgende Figur, wenn Sie die Strategie $ \ bf q $ des Gegners mit Zufallszahlen ändern und die Erpressungsstrategie und das Spiel spielen.

Rote Punkte stehen für die $ ALLD $ -Strategie des Gegners und blaue Punkte für die $ ALLC $ -Strategie des Gegners (immer Kooperationsstrategie). Die vertikale Achse ist die Punktzahl des Spielers, der die Erpressungsstrategie anwendet, und die horizontale Achse ist die Punktzahl des Gegners.

Aus dieser Abbildung können wir ersehen, dass die Erpressungsstrategie die $ ALLD $ -Strategie (roter Punkt) nicht mehr übertreffen kann. Auf der anderen Seite können wir immer noch gegen die meisten anderen Strategien als die $ ALLD $ -Strategie gewinnen.

Wenn keine Fehler vorliegen, kann die Erpressungsstrategie zu einem Unentschieden gegen die $ ALLD $ -Strategie führen und die Ausbeutung durch $ ALLD $ verhindern. Der Fehler führte jedoch dazu, dass die Ausnutzung der $ ALLD $ -Strategie zugelassen wurde. Andererseits stellte sich heraus, dass es möglich ist, andere Strategien als die $ ALLD $ -Strategie auszunutzen.

Zusammenfassung

Ich habe eine Simulation eines Gefangenendilemma-Spiels mit einem Fehler in Python implementiert. Die Strategie des Spielers ist diesmal eine einfache Strategie für Gedächtnis 1, aber möglicherweise kann eine stärkere Strategie gefunden werden, wenn eine Strategie mit erhöhtem Gedächtnis oder eine Strategie mit Lernen verwendet wird.

Dieses Mal habe ich mit der Null-Determinanten-Strategie experimentiert. Selbst bei Fehlern kann die Equalizer-Strategie die Punktzahl des Gegners korrigieren, und die Erpressungsstrategie ermöglicht die Ausnutzung der $ ALLD $ -Strategie, jedoch die Ausnutzung für die meisten anderen Strategien. Ich fand, dass ich es schaffen konnte. Selbst wenn ein Fehler vorliegt, kann daher gesagt werden, dass es sich in gewissem Maße um eine wirksame Strategie handelt.

Wenn Sie eine starke Strategie oder eine interessante Strategie finden, lassen Sie es uns bitte wissen (> _ <)

Ich habe versucht, ein missverstandenes Gefangenendilemma in Python zu implementieren