# Dilemme du voyageur

En théorie des jeux, le dilemme du voyageur (parfois abrégé en TD ) est un jeu à somme non nulle dans lequel chaque joueur propose un gain. La plus basse des deux propositions gagne; le joueur lowball reçoit le paiement lowball plus un petit bonus, et le joueur highball reçoit le même paiement lowball, moins une petite pénalité. Étonnamment, l' équilibre de Nash est pour les deux joueurs un lowball agressif. Le dilemme du voyageur est remarquable en ce que le jeu naïf semble dépasser l’équilibre de Nash; Cet apparent paradoxe apparaît également dans le jeu des centipèdes et le dilemme du prisonnier finement itéré.

## Formulation

Le scénario de jeu original a été formulé en 1994 par Kaushik Basu et se présente comme suit$^,$ :
"Une compagnie aérienne perd deux valises appartenant à deux voyageurs différents. Les deux valises se trouvent être identiques et contiennent des antiquités identiques. Un responsable de compagnie aérienne chargé de régler les réclamations des deux voyageurs explique que la compagnie aérienne est responsable d'un maximum de 100 USD par valise - il est incapable de connaître directement le prix des antiquités. "
"Pour déterminer une valeur estimée honnête des antiquités, le responsable sépare les deux voyageurs afin qu'ils ne puissent pas se concerter et leur demande d'écrire le montant de leur valeur entre pas moins de 2 $ et plus de 100 $. Il leur dit également que si les deux écrivent le même numéro, il traitera ce numéro comme la valeur réelle en dollars des deux valises et remboursera ce montant aux deux voyageurs. Toutefois, si l’un écrit moins que l’autre, ce dernier sera considéré comme la valeur réelle et les deux voyageurs recevront ce montant avec un bonus / malus : 2 $ supplémentaires seront versés au voyageur qui a écrit la valeur inférieure et une déduction de 2 $ seront prélevées sur la personne qui a consigné le montant le plus élevé. Le défi est le suivant : quelle stratégie les deux voyageurs devraient-ils suivre pour décider de la valeur à écrire ? "
Les deux joueurs tentent d'optimiser leurs gains, sans se soucier des gains de l'autre joueur.

## Analyse

On pourrait s'attendre à ce que le choix optimal du voyageur soit de 100 $; c'est-à-dire que le voyageur valorise les antiquités au prix maximum autorisé par le responsable de la compagnie. Remarquablement, et pour beaucoup, contre-intuitivement, la solution d’équilibre de Nash n’est en réalité que de 2 dollars; c'est-à-dire que le voyageur valorise les antiquités au prix minimum autorisé par le responsable de la compagnie aérienne.
Pour comprendre pourquoi 2 $ est l’ équilibre de Nash, considérons la preuve suivante:
* Alice, ayant perdu ses antiquités, se voit demander leur valeur. La première pensée d'Alice est de citer 100 $, la valeur maximale autorisée.
* Après réflexion, elle se rend compte que son compagnon de voyage, Bob, pourrait également citer 100 $. Alice se ravise et décide de proposer 99 dollars. Si Bob cite 100 dollars, il paiera 101 dollars.
* Mais Bob, étant dans une position identique à Alice, pourrait aussi penser à citer 99 $. Alice se ravise et décide de proposer 98 dollars. Si Bob cite 99 dollars, il paiera 100 dollars. C'est plus que les 99 $ qu'Alice recevrait si elle et Bob citaient tous les deux 99 $.
* Ce cycle de pensée se poursuit jusqu'à ce qu'Alice décide finalement de ne proposer que 2 $ - le prix minimum autorisé.
Une autre preuve va comme suit:
* Si Alice ne souhaite que maximiser ses profits, choisir 99 $ l'emporte sur 100 $. Si Bob choisit une valeur en dollars comprise entre 2 et 98, 99 $ et 100 $ donnent le même résultat. si Bob choisit 99 $ ou 100 $, choisir 99 $ rapportera un dollar supplémentaire à Alice.
* Un raisonnement similaire montre que choisir 98 $ est toujours préférable pour Alice que de choisir 99 $. Le seul cas où choisir 99 $ rapporterait plus que choisir 98 $ est le cas si Bob choisit 100 $ - mais si Bob cherche seulement à maximiser ses propres profits, il choisira toujours 99 $ au lieu de 100 $.
* Ce raisonnement peut être appliqué à toutes les options en dollars d’Alice jusqu’à ce qu’elle atteigne enfin 2 $, le prix le plus bas.

## Résultats expérimentaux

Le résultat (2 $, 2 $) dans ce cas est l’ équilibre de Nash du jeu. Par définition, cela signifie que si votre adversaire choisit cette valeur d’équilibre de Nash, votre meilleur choix est cette valeur d’équilibre de Nash de 2 $. Ce ne sera pas le choix optimal s'il y a une chance pour que votre adversaire choisisse une valeur supérieure à 2 $. Lorsque le jeu est joué à titre expérimental, la plupart des participants choisissent une valeur supérieure à l'équilibre de Nash et plus proche de 100 $ (correspondant à la solution optimale de Pareto). Plus précisément, la solution de stratégie d’équilibre de Nash s’est révélée être un mauvais prédicteur du comportement des personnes face au dilemme d’un voyageur, avec un bonus / malus faible, et un prédicteur plutôt bon si le paramètre bonus / malus était important.
De plus, les voyageurs sont récompensés en s'écartant fortement de l'équilibre de Nash dans le jeu et obtiennent des récompenses bien supérieures à celles qui seraient obtenues avec la stratégie purement rationnelle. Ces expériences (et d'autres, telles que les points focaux ) montrent que la majorité des gens n'utilise pas de stratégies purement rationnelles, mais que les stratégies qu'elles utilisent sont manifestement optimales. Ce paradoxe pourrait réduire la valeur de l’analyse de la théorie des jeux pure, mais pourrait également indiquer l’avantage d’un raisonnement élargi qui comprend comment il peut être assez rationnel de faire des choix non rationnels, du moins dans le contexte de jeux où les joueurs peuvent compter sur ne pas jouer "rationnellement". Par exemple, Capraro a proposé un modèle dans lequel les êtres humains n'agissent pas a priori comme des agents uniques, mais ils prévoient comment le jeu serait joué s'ils formaient des coalitions, puis agissaient de manière à maximiser les prévisions. Son modèle correspond assez bien aux données expérimentales sur le dilemme du voyageur et à des jeux similaires. Récemment, le dilemme du voyageur a été mis à l’épreuve avec une décision prise en groupe plutôt qu’individuellement, afin de vérifier l’hypothèse voulant que les décisions de groupe soient plus rationnelles, en donnant le message que, en général, deux têtes valent mieux qu’une. Les résultats expérimentaux montrent que les groupes sont toujours plus rationnels - c'est-à-dire que leurs revendications sont plus proches de l'équilibre de Nash - et plus sensibles à la taille du bonus / malus.
Certains joueurs semblent poursuivre un équilibre de Nash bayésien$^,$.

## Jeux similaires

Le dilemme du voyageur peut être assimilé à celui d'un prisonnier finement répété$^,$. Des paradoxes similaires sont attribués au jeu des centipèdes et au jeu du concours p-beauté (ou plus précisément, " Devinez 2/3 de la moyenne "). Une variante du dilemme du voyageur original dans laquelle deux choix entiers, à 2 $ ou 3 $, est proposée aux deux voyageurs est mathématiquement identique au dilemme standard du prisonnier non itéré. Le dilemme du voyageur peut donc être considéré comme un prolongement du dilemme du prisonnier. Ces jeux impliquent généralement une suppression itérative profonde des stratégies dominées afin de démontrer l'équilibre de Nash et conduisent à des résultats expérimentaux s'écartant nettement des prédictions classiques de la théorie des jeux .