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.
La règle de ce jeu est que deux joueurs $ X $ et $ Y $ choisissent respectivement de coopérer ($ C
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.
- Les clients ont la même structure que le dilemme du prisonnier car ils augmentent ou diminuent en fonction du prix des produits dans chaque magasin.
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.
La règle de ce jeu est que les joueurs $ 2 $ $ X $ et $ Y $ choisissent respectivement de coopérer ($ C
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.
- Définissez la stratégie du joueur.
Nous définissons la stratégie du joueur $ X $ comme $ {\ bf p} = (p_ {Cg}, p_ {Cb}, p_ {Dg}, p_ {Db}; p_0)
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 $.
- La zone entourée par la ligne grise est la zone liée au gain qui peut être réalisé. La relation de gain entre les deux joueurs se situe toujours quelque part dans ce domaine. L'axe vertical est le score du joueur qui adopte la stratégie Equalizer, et l'axe horizontal est le score de l'adversaire.
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.
- Les points rouges sont pour la stratégie $ ALLD $ de l'adversaire, et les points bleus sont pour la stratégie $ ALLC $ de l'adversaire (toujours stratégie de coopération). L'axe vertical est le score du joueur qui adopte la stratégie d'extorsion, et l'axe horizontal est le score de l'adversaire.
À 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
-
Stratégie pour exploiter les adversaires dans le jeu du dilemme du prisonnier (Qiita)
-
A. Mamiya and G. Ichinose, Strategies that enforce linear payoff relationships under observation errors in Repeated Prisoner’s Dilemma game J. Theor. Biol. 477, 63-76, 2019.
Recommended Posts