J'ai essayé de mettre en œuvre un jeu de dilemme de prisonnier mal compris en Python

J'ai essayé de mettre en œuvre un jeu de dilemme de prisonnier incompris en Python. En utilisant ce programme, j'ai simulé et expérimenté à plusieurs reprises une stratégie de jeu de dilemme d'un prisonnier.

Le jeu du dilemme du prisonnier est principalement utilisé dans le domaine économique pour analyser les comportements collaboratifs tels que la collusion entre entreprises. Il existe divers autres exemples d'application.

Dans le modèle de jeu de dilemme conventionnel du prisonnier, on suppose que ** le comportement de l'adversaire peut être directement observé (observation complète) ** après coup, et les joueurs peuvent décider de l'action suivante en fonction de cela. C'est fait. Cependant, dans le monde réel, il est souvent impossible d'observer complètement le comportement de l'autre partie. Dans ce cas, le modèle conventionnel ne peut pas bien saisir ces situations.

Par conséquent, ces dernières années, le jeu de dilemme du prisonnier de ** l'observation incomplète ** a été activement étudié. Dans l'observation incomplète, au lieu d'observer directement le comportement de l'autre partie, il est possible d'observer des ** signaux ** qui dépendent du comportement de l'autre partie.

Cette fois, nous simulerons le jeu de dilemme des détenus répétés avec cette observation incomplète.

Quel est le jeu du dilemme du prisonnier?

Le jeu du dilemme du prisonnier est l'un des jeux les plus représentatifs de la théorie des jeux. Ce jeu est souvent donné dans le tableau des scores ci-dessous.

図1.png

La règle de ce jeu est que deux joueurs $ X $ et $ Y $ choisissent respectivement de coopérer ($ C : Coopérer) ou de trahir ( D $: Défaut). Le score est déterminé par l'action choisie par chaque joueur.

Si les joueurs $ X $ et $ Y $ choisissent les $ C $ de l'autre, ils peuvent obtenir un score raisonnablement bon de 1 $. Si $ X $ ou $ Y $ choisit $ C $ et que l'autre choisit $ D $, le joueur qui choisit $ C $ obtiendra le score le plus bas, -0,5 $. Le joueur qui choisit , $ D $ peut obtenir le score le plus élevé de 1,5 $. Si $ X $ et $ Y $ choisissent $ D $ l'un pour l'autre, ils obtiendront un petit score de 0 $. Si vous choisissez $ C $ l'un pour l'autre, le score total des deux sera de 2 $ \ (= 1 + 1) $, qui est le meilleur score pour l'ensemble, et si vous êtes unilatéralement trahi par l'adversaire, le joueur trahi perdra beaucoup. Il a une structure telle que

De cette façon, il y a un dilemme que chaque joueur veut vraiment coopérer, mais est tenté par la trahison.

Dans l'exécution d'un jeu, la coopération entre joueurs égoïstes n'est pas réalisée (équilibre de Nash). D'autre part, dans le ** jeu de dilemme du prisonnier répété ** qui répète indéfiniment ce jeu, il a été théoriquement prouvé que la coopération peut être réalisée même entre des joueurs égoïstes (folk). théorème).

Par conséquent, quel type de stratégie est fort dans ce jeu de dilemme répétitif du prisonnier a été étudié (expérience de la tige d'accélérateur).

Jeu répété avec observation privée incomplète

Il est différent du jeu de dilemme traditionnel du prisonnier, qui suppose une ** surveillance parfaite ** qui permet au joueur d'observer avec précision toutes les actions entreprises dans le passé. ** La surveillance privée imparfaite ** ne vous permet pas d'observer directement le comportement passé des joueurs. Supposons plutôt que vous observiez un signal qui dépend des actions du joueur précédent. Dans ce jeu, nous supposons que ** Private Monitoring ** reçoit des signaux individuels. Le signal reçu par chaque joueur ne peut pas être observé par l'adversaire.

Exemple concret

Le jeu de dilemme du prisonnier de l'observation privée incomplète suppose la ** concurrence des prix ** des détaillants suivants.

Dans la concurrence des prix de détail, en supposant que vous vendez le même produit, vous essayez de sécuriser les ventes en maintenant le prix du produit ou en abaissant le prix.

Le bénéfice réel d'un magasin de détail est déterminé par le nombre de visiteurs (signal) et le prix du produit (votre propre comportement). Par exemple, si les prix sont maintenus (coopèrent) les uns avec les autres, les clients peuvent vendre des produits à un prix élevé sans être biaisés en faveur d'un seul magasin, et les deux magasins peuvent obtenir des bénéfices raisonnablement élevés. Je vais.

Dans une telle situation, les cas suivants sont supposés. Normalement, si chaque magasin maintient son prix, les deux magasins peuvent obtenir des bénéfices élevés, mais le nombre de visiteurs fluctue en raison de divers facteurs. Par exemple, des chocs de demande imprévisibles et l'ouverture inconsciente de magasins similaires dans le quartier peuvent réduire le nombre de clients des magasins (voir la figure ci-dessous). Le point de profit du magasin est que le prix (comportement) du produit décidé par chaque magasin n'est pas directement lié au profit.

D'autre part, le magasin peut également réduire le prix du produit et acquérir des clients afin que l'autre partie ne le sache pas (par exemple en présentant un prix inférieur au prix catalogue uniquement devant le client). Une telle situation ne peut pas être saisie dans le jeu de dilemme traditionnel du prisonnier.

Une telle situation est assumée par ** jeu répétitif avec observation privée incomplète **.

Contenu du jeu

--Définissez le jeu.

Répétez le jeu indiqué dans le tableau des scores ci-dessous.

図2.png

La règle de ce jeu est que les joueurs $ 2 $ $ X $ et $ Y $ choisissent respectivement de coopérer ($ C : Coopérer) ou de trahir ( D $: Défaut). Le score est déterminé par l'action choisie par chaque joueur.

En gros, lorsque l'adversaire choisit $ C $, il observe un ** signal ** appelé $ g $ qui signifie * bon *. À ce moment-là, si vous choisissez l'action de $ C $, vous obtiendrez des points de 1 $. De plus, si vous sélectionnez l'action $ D $, vous obtiendrez 1,5 $ points. De même, lorsque l'adversaire choisit $ D $, il observe le signal $ b $, ce qui signifie * mauvais *. À ce moment-là, si vous choisissez l'action de $ C $, vous obtiendrez -0,5 $ points. De plus, si vous sélectionnez l'action $ D $, vous obtiendrez 0 $ points.

Les hypothèses jusqu'à présent sont presque les mêmes que celles du jeu de dilemme traditionnel du prisonnier.

--Définissez l'erreur d'observation.

Dans ce modèle, les signaux de comportement $ g $ et $ b $ sont inversés en raison d'une erreur due à des facteurs tels que l'environnement.

Même si votre adversaire choisit $ C $, vous pouvez obtenir un signal de $ b $, ce qui signifie que votre adversaire a choisi $ D $. Inversement, même si l'autre partie choisit $ D $, vous pouvez obtenir un signal de $ g $, ce qui signifie que l'autre partie a choisi $ C $. L'observation d'un signal qui est l'opposé du signal qui signifie que le comportement réel de cette manière est appelé ** erreur d'observation **.

Cette fois, ** la probabilité qu'un seul des joueurs échoue ** est définie comme $ \ epsilon $, et ** la probabilité que les deux joueurs échouent ** est définie comme $ \ xi $. On suppose que les taux d'erreur $ \ epsilon $ et $ \ xi $ ne sont pas très grands.

Nous définissons la stratégie du joueur $ X $ comme $ {\ bf p} = (p_ {Cg}, p_ {Cb}, p_ {Dg}, p_ {Db}; p_0) . Cette stratégie s'appelle la stratégie Memory-One. Les joueurs qui utilisent cette stratégie détermineront de manière probabiliste cette action ( C $ ou $ D $) en ne considérant que les résultats du jeu précédent.

Par exemple, $ p_ {Cg} $ est la probabilité de coopération dans ce jeu lorsque le joueur $ X $ sélectionne $ C $ et observe $ g $ dans le jeu précédent. $ p_ {Cb} $ est la probabilité de coopération dans ce jeu lorsque le joueur $ X $ sélectionne $ C $ et observe $ b $ dans le jeu précédent. D'autres sont considérés de la même manière. $ p_0 $ est la probabilité de coopérer au premier jeu.

De même, la stratégie pour le joueur $ Y $ est $ {\ bf q} = (q_ {Cg}, q_ {Cb}, q_ {Dg}, q_ {Db}; q_0) $.

La figure ci-dessous est un exemple de transition de $ CC $ (coopération mutuelle) à $ CD $ (coopération $ X $, trahison $ Y $). Dans cette figure, vous pouvez comprendre comment chaque joueur observe le signal et passe à l'état suivant en fonction de la stratégie définie ci-dessus en fonction de l'action décidée par chaque joueur. Bien que cela ne soit pas pertinent dans cette simulation, cela peut être considéré comme un processus de Markov, et la matrice de transition de ce jeu peut être définie à partir du diagramme de transition ci-dessous.

Programme Python

Le programme Python suivant implémente ce qui précède. Vous pouvez découvrir quel type de stratégie est fort par simulation. Ci-dessous, la stratégie de chaque joueur est $ {\ bf p} = (1/2, 1/2, 1/2, 1/2; 1/2) $ et $ {\ bf q} = (1/2, 1/2, 1/2, 1/2; 1/2) $. Le nombre de répétitions du jeu est de 100 000 $. Les taux d'erreur sont définis sur $ \ epsilon = 0,05 $ et $ \ xi = 0,05 $.

import random

max_t = 100000 #Nombre de répétitions du jeu

point  = {'x' : 0, 'y' : 0} #Score total du joueur
action = {'x' : None, 'y' : None} #Comportement du joueur C ou D
signal = {'x' : None, 'y' : None} #Signaux observés par le joueur
state  = {'x' : '0', 'y' : '0'} #Définir l'état du jeu
payoff = {'Dg':1.5, 'Cg':1.0, 'Db':0, 'Cb':-0.5} #Score du jeu
epsilon = 0.05; xi = 0.05 #Une seule erreur, probabilité des deux erreurs

p = {'Cg':1/2, 'Cb':1/2, 'Dg':1/2, 'Db':1/2, '0' :1/2} #Stratégie du joueur X
q = {'Cg':1/2, 'Cb':1/2, 'Dg':1/2, 'Db':1/2, '0' :1/2} #Stratégie du joueur Y

#Répéter le jeu
for t in range(max_t):
    #Sélectionnez C ou D en fonction du résultat du jeu précédent
    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'
    #Erreur d'observation
    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'
    #Distribuez les gains en fonction des actions et des signaux
    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']        
        #Résultats du jeu de remplacement
        state[player] = action[player] + signal[player]

#Sortie du score moyen de chaque joueur
print('Player X: {} Points'.format(point['x'] / max_t))
print('Player Y: {} Points'.format(point['y'] / max_t))

Lorsque ce programme est exécuté, les résultats d'exécution suivants seront obtenus. ..

Player X: 0.49855 Points
Player Y: 0.49827 Points

Autrement dit, $ {\ bf p} = (1/2, 1/2, 1/2, 1/2; 1/2) $ et $ {\ bf q} = (1/2, 1/2, 1 / 2, 1/2; 1/2) Lorsque vous jouez une stratégie $ Vous pouvez voir que les résultats sont presque les mêmes. C'est un résultat naturel.

Ensuite, j'aimerais essayer différentes stratégies.

Expérimentez la stratégie à zéro déterminant

La stratégie à zéro déterminant (stratégie ZD) est l'un des jeux de dilemme du prisonnier. Auparavant, je l'ai introduit dans Stratégie pour exploiter les adversaires dans le jeu du dilemme du prisonnier (Qiita). Cette stratégie ZD est une stratégie simple et peut être définie par la stratégie mémoire 1 $ \ bf p $ ou $ \ bf q $ (la dérivation de la stratégie ZD elle-même est un peu difficile). Cette fois, nous expérimenterons cette stratégie dans ce jeu de dilemme incompris du prisonnier.

La stratégie ZD comprend la stratégie Equalizer et la stratégie Extorsion en tant que stratégies partielles bien connues. La stratégie Equalizer peut fixer le score moyen de l'adversaire, et la stratégie d'extorsion Extorsion signifie chantage, et cette stratégie peut exploiter le score de l'adversaire.

C'est la fin de l'explication détaillée, et nous expérimenterons cette stratégie.

Stratégie d'égalisation

Quelle que soit la stratégie de votre adversaire, vous pouvez fixer le score de votre adversaire. Stratégie d'égalisation pour obtenir le score moyen de votre adversaire 0,5 $ points $ {\ bf p} = (0,8, 0,365217,0,634783, 0,2; 1/2) $ et $ {\ bf q} = (1/2, 1/2, Si vous définissez 1/2, 1/2; 1/2) $ et exécutez la simulation, vous obtiendrez les résultats suivants.

Player X: 0.496385 Points
Player Y: 0.50177 Points

Certes, il s'agit de `` Joueur Y: 0,50177 points '', et vous pouvez voir que le score de l'adversaire est proche de 0,5 $ points. Cela peut arriver, donc si vous essayez la stratégie de l'adversaire avec la stratégie de trahison toujours la plus forte (stratégie $ ALLD $) $ {\ bf q} = (0,0,0,0; 0) $ dans le jeu de dilemme du prisonnier , Les résultats suivants sont obtenus.

Player X: -0.004545 Points
Player Y: 0.50022 Points

Après tout, c'est `` Joueur Y: 0,50022 points '', et vous pouvez voir que le score de l'adversaire est proche de 0,5 $ points.

Dans la figure ci-dessous, en plus de la stratégie ci-dessus, la stratégie de l'adversaire $ \ bf q $ reçoit différents nombres aléatoires et une simulation est effectuée. $ \ Bf q $ a été généré pour 100 stratégies, et le programme a été exécuté pour chacune. À partir de cette figure, vous pouvez voir que l'adversaire est fixé au point $ 0,5 $ quelle que soit la stratégie de l'adversaire $ \ bf q $.

error_fig_eq.png

Par conséquent, la stratégie Equalizer peut fixer le score de l'adversaire même s'il y a une erreur, quelle que soit la stratégie de l'adversaire.

Stratégie d'extorsion

La stratégie d'extorsion est connue pour être une stratégie d'exploitation du score d'un adversaire dans un jeu de dilemme du prisonnier ordinaire sans erreur. Vous pouvez revenir avec un match nul contre la stratégie de trahison toujours la plus forte (stratégie $ ALLD $) et la stratégie d'extorsion.

Est-ce possible s'il y a une erreur?

Semblable à la figure créée pour la stratégie Equalizer, si vous changez la stratégie de l'adversaire $ \ bf q $ avec des nombres aléatoires et jouez la stratégie Extorsion et le jeu, vous obtiendrez la figure suivante.

ext.png

À partir de cette figure, nous pouvons voir que la stratégie Extorsion ne peut plus battre la stratégie $ ALLD $ (point rouge). D'un autre côté, nous sommes toujours en mesure de gagner contre la plupart des stratégies autres que la stratégie $ ALLD $.

En l'absence d'erreurs, la stratégie d'extorsion pourrait entraîner un match nul contre la stratégie $ ALLD $, empêchant l'exploitation de $ ALLD $. Cependant, l'erreur a conduit à autoriser l'exploitation à partir de la stratégie $ ALLD $. En revanche, il s'est avéré qu'il est possible d'exploiter des stratégies autres que la stratégie $ ALLD $.

Résumé

J'ai implémenté une simulation de jeu de dilemme d'un prisonnier avec une erreur en Python. La stratégie du joueur cette fois est une stratégie simple de mémoire 1, mais peut-être qu'une stratégie plus forte peut être trouvée si une stratégie avec une mémoire accrue ou une stratégie avec apprentissage est utilisée.

Cette fois, j'ai expérimenté la stratégie du déterminant zéro. Même avec des erreurs, la stratégie Equalizer peut fixer le score de l'adversaire, la stratégie Extorsion permet l'exploitation pour la stratégie $ ALLD $, mais exploite pour la plupart des autres stratégies. J'ai trouvé que je pouvais le faire. Par conséquent, même s'il y a une erreur, on peut dire que c'est une stratégie efficace dans une certaine mesure.

Si vous trouvez une stratégie forte ou intéressante, merci de nous le faire savoir (> _ <)

Littérature liée

Recommended Posts

J'ai essayé de mettre en œuvre un jeu de dilemme de prisonnier mal compris en Python
J'ai essayé de mettre en œuvre un jeu de dilemme de prisonnier mal compris en Python
J'ai essayé d'implémenter le jeu de cartes de Trump en Python
J'ai essayé d'implémenter PLSA en Python
J'ai essayé d'implémenter la permutation en Python
J'ai essayé d'implémenter un automate cellulaire unidimensionnel en Python
J'ai essayé d'implémenter PLSA dans Python 2
J'ai essayé d'implémenter ADALINE en Python
J'ai essayé d'implémenter PPO en Python
J'ai essayé d'implémenter le blackjack du jeu Trump en Python
J'ai essayé de jouer à un jeu de frappe avec Python
J'ai essayé d'implémenter TOPIC MODEL en Python
J'ai essayé d'implémenter le tri sélectif en python
Je veux facilement implémenter le délai d'expiration en python
J'ai essayé d'implémenter le poker de Drakue en Python
J'ai essayé d'implémenter GA (algorithme génétique) en Python
J'ai essayé d'implémenter ce qui semble être un outil de snipper Windows avec Python
J'ai essayé "Comment obtenir une méthode décorée en Python"
J'ai essayé d'implémenter la fonction d'envoi de courrier en Python
J'ai fait un chronomètre en utilisant tkinter avec python
[Python] J'ai essayé d'implémenter un tri stable, alors notez
J'ai écrit un doctest dans "J'ai essayé de simuler la probabilité d'un jeu de bingo avec Python"
Je veux créer une fenêtre avec Python
Je veux faire un jeu avec Python
J'ai essayé d'ajouter un module Python 3 en C
J'ai créé un jeu ○ ✕ avec TensorFlow
J'ai essayé d'implémenter la régression linéaire bayésienne par échantillonnage de Gibbs en python
J'ai essayé de développer un formateur qui génère des journaux Python en JSON
J'ai essayé d'implémenter le tri par fusion en Python avec le moins de lignes possible
J'ai essayé de représenter graphiquement les packages installés en Python
Je souhaite intégrer une variable dans une chaîne Python
J'ai essayé de créer une classe qui peut facilement sérialiser Json en Python
J'ai essayé d'implémenter Mine Sweeper sur un terminal avec python
Je veux écrire en Python! (2) Écrivons un test
[Python] Deep Learning: J'ai essayé d'implémenter Deep Learning (DBN, SDA) sans utiliser de bibliothèque.
J'ai essayé d'implémenter PCANet
Je veux échantillonner au hasard un fichier avec Python
J'ai essayé d'implémenter le perceptron artificiel avec python
Je veux travailler avec un robot en python.
J'ai essayé de résumer comment utiliser les pandas de python
J'ai essayé d'implémenter StarGAN (1)
J'ai essayé d'implémenter une ligne moyenne mobile de volume avec Quantx
J'ai essayé de mettre en œuvre le modèle de base du réseau neuronal récurrent
J'ai fait un jeu de frappe simple avec tkinter de Python
[Chaîne de Markov] J'ai essayé de lire les citations en Python.
J'ai essayé "un programme qui supprime les déclarations en double en Python"
J'ai créé une classe en Python et essayé de taper du canard
J'ai fait un jeu de puzzle (comme) avec Tkinter of Python
J'ai essayé de simuler la probabilité d'un jeu de bingo avec Python
Une histoire sur la tentative d'implémentation de variables privées en Python.
Je veux ajouter un joli complément à input () en python
J'ai essayé d'implémenter Deep VQE
J'ai essayé de toucher Python (installation)
J'ai essayé d'implémenter Realness GAN
J'ai essayé la notification de ligne en Python
Django super introduction par les débutants Python! Partie 6 J'ai essayé d'implémenter la fonction de connexion