In game theory, the traveler's dilemma (sometimes abbreviated TD) is a non-zero-sum game in which each player proposes a payoff. The lower of the two proposals wins; the lowball player receives the lowball payoff plus a small bonus, and the highball player receives the same lowball payoff, minus a small penalty. Surprisingly, the Nash equilibrium is for both players to aggressively lowball. The traveler's dilemma is notable in that naive play appears to outperform the Nash equilibrium; this apparent paradox also appears in the centipede game and the finitely-iterated prisoner's dilemma.
The original game scenario was formulated in 1994 by Kaushik Basu and goes as follows:[1] [2]
"An airline loses two suitcases belonging to two different travelers. Both suitcases happen to be identical and contain identical antiques. An airline manager tasked to settle the claims of both travelers explains that the airline is liable for a maximum of $100 per suitcase—he is unable to find out directly the price of the antiques."
"To determine an honest appraised value of the antiques, the manager separates both travelers so they can't confer, and asks them to write down the amount of their value at no less than $2 and no larger than $100. He also tells them that if both write down the same number, he will treat that number as the true dollar value of both suitcases and reimburse both travelers that amount. However, if one writes down a smaller number than the other, this smaller number will be taken as the true dollar value, and both travelers will receive that amount along with a bonus/malus: $2 extra will be paid to the traveler who wrote down the lower value and a $2 deduction will be taken from the person who wrote down the higher amount. The challenge is: what strategy should both travelers follow to decide the value they should write down?"
The two players attempt to maximize their own payoff, without any concern for the other player's payoff.
Backward induction only applies where there is perfect information. If it is used where there is information asymmetry- the Airline manager does not know the value of the antique- the result will be irrational behavior. This is what happens in the following analysis-
One might expect a traveler's optimum choice to be $100; that is, the traveler values the antiques at the airline manager's maximum allowed price. Remarkably, and, to many, counter-intuitively, the Nash equilibrium solution is in fact just $2; that is, the traveler values the antiques at the airline manager's minimum allowed price.
For an understanding of why $2 is the Nash equilibrium consider the following proof:
The above analysis depends crucially on (1) imperfect information- the airline manager does not know the true value and (2) irrationality- in particular failure to use the Muth Rational strategy.
Another proof goes as follows:
The ($2, $2) outcome in this instance is the Nash equilibrium of the game. By definition this means that if your opponent chooses this Nash equilibrium value then your best choice is that Nash equilibrium value of $2. This will not be the optimum choice if there is a chance of your opponent choosing a higher value than $2.[3] When the game is played experimentally, most participants select a value higher than the Nash equilibrium and closer to $100 (corresponding to the Pareto optimal solution). More precisely, the Nash equilibrium strategy solution proved to be a bad predictor of people's behavior in a traveler's dilemma with small bonus/malus and a rather good predictor if the bonus/malus parameter was big.[4]
Furthermore, the travelers are rewarded by deviating strongly from the Nash equilibrium in the game and obtain much higher rewards than would be realized with the purely rational strategy. These experiments (and others, such as focal points) show that the majority of people do not use purely rational strategies, but the strategies they do use are demonstrably optimal. This paradox could reduce the value of pure game theory analysis, but could also point to the benefit of an expanded reasoning that understands how it can be quite rational to make non-rational choices, at least in the context of games that have players that can be counted on to not play "rationally." For instance, Capraro has proposed a model where humans do not act a priori as single agents but they forecast how the game would be played if they formed coalitions and then they act so as to maximize the forecast. His model fits the experimental data on the Traveler's dilemma and similar games quite well.[5] Recently, the traveler's dilemma was tested with decision undertaken in groups rather than individually, in order to test the assumption that groups decisions are more rational, delivering the message that, usually, two heads are better than one.[6] Experimental findings show that groups are always more rational – i.e. their claims are closer to the Nash equilibrium - and more sensitive to the size of the bonus/malus.[7]
Some players appear to pursue a Bayesian Nash equilibrium.[8] [9]
The traveler's dilemma can be framed as a finitely repeated prisoner's dilemma.[8] [9] Similar paradoxes are attributed to the centipede game and to the p-beauty contest game[7] (or more specifically, "Guess 2/3 of the average"). One variation of the original traveler's dilemma in which both travelers are offered only two integer choices, $2 or $3, is identical mathematically to the standard non-iterated Prisoner's dilemma and thus the traveler's dilemma can be viewed as an extension of prisoner's dilemma. (The minimum guaranteed payout is $1, and each dollar beyond that may be considered equivalent to a year removed from a three-year prison sentence.) These games tend to involve deep iterative deletion of dominated strategies in order to demonstrate the Nash equilibrium, and tend to lead to experimental results that deviate markedly from classical game-theoretical predictions.
The canonical payoff matrix is shown below (if only integer inputs are taken into account):
| 100 | 99 | 98 | 97 | ⋯ | 3 | 2 | ||
|---|---|---|---|---|---|---|---|---|
| 100 | 100, 100 | 97, 101 | 96, 100 | 95, 99 | ⋯ | 1, 5 | 0, 4 | |
| 99 | 101, 97 | 99, 99 | 96, 100 | 95, 99 | ⋯ | 1, 5 | 0, 4 | |
| 98 | 100, 96 | 100, 96 | 98, 98 | 95, 99 | ⋯ | 1, 5 | 0, 4 | |
| 97 | 99, 95 | 99, 95 | 99, 95 | 97, 97 | ⋯ | 1, 5 | 0, 4 | |
| ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋱ | ⋮ | ⋮ | |
| 3 | 5, 1 | 5, 1 | 5, 1 | 5, 1 | ⋯ | 3, 3 | 0, 4 | |
| 2 | 4, 0 | 4, 0 | 4, 0 | 4, 0 | ⋯ | 4, 0 | 2, 2 |
Denoting by
S=\{2,...,100\}
F:S x S → R
F(x,y)=min(x,y)+2 ⋅ sgn(y-x)
F(y,x)