Traveler's dilemma
Encyclopedia
In game theory
, the traveler's dilemma (sometimes abbreviated TD) is a type of non-zero-sum
game in which two players attempt to maximize their own payoff, without any concern for the other player's payoff.
The game was formulated in 1994 by Kaushik Basu
and goes as follows:
An airline loses two suitcases belonging to two different travelers. Both suitcases happen to be identical and contain identical items. 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 items), and in order 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?
Naively, 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 traveler's optimum choice (in terms of Nash equilibrium
) is in fact $2; that is, the traveler values the antiques at the airline manager's minimum allowed price.
For an understanding of this paradoxical result, consider the following rather whimsical proof.
Another proof goes as follows:
The ($2, $2) outcome in this instance is the Nash equilibrium of the game. However, when the game is played experimentally, most participants select the value $100 or a value close to $100, including both those who have not thought through the logic of the decision and those who understand themselves to be making a non-rational choice
. 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 has led some to question the value of game theory in general, while others have suggested that a new kind of reasoning is required to understand how it can be quite rational ultimately to make non-rational choices. Note that the $100 choice here is the optimal pure strategy under a different model of decision making called superrationality
, which assumes that all logical thinkers must use the same strategy, so pure superrational strategies are restricted to the diagonal of the payoff matrix.
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 Prisoner's dilemma
and thus the traveler's dilemma can be viewed as an extension of prisoner's dilemma. The traveler's dilemma is also related to the game Guess 2/3 of the average
in that both involve deep iterative deletion of dominated strategies in order to demonstrate the Nash equilibrium, and that both lead to experimental results that deviate markedly from the game-theoretical
predictions.
Denoting by
the set of strategies available to both players and by 
the payoff function of one of them we can write
(Note that the other player receives
since the game is quantitatively symmetric
).
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
, the traveler's dilemma (sometimes abbreviated TD) is a type of non-zero-sum
Zero-sum
In game theory and economic theory, a zero-sum game is a mathematical representation of a situation in which a participant's gain of utility is exactly balanced by the losses of the utility of other participant. If the total gains of the participants are added up, and the total losses are...
game in which two players attempt to maximize their own payoff, without any concern for the other player's payoff.
The game was formulated in 1994 by Kaushik Basu
Kaushik Basu
Kaushik Basu is an Indian economist who is currently the Chief Economic Adviser to the Government of India and is also the C...
and goes as follows:
An airline loses two suitcases belonging to two different travelers. Both suitcases happen to be identical and contain identical items. 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 items), and in order 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?
Naively, 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 traveler's optimum choice (in terms of Nash equilibrium
Nash equilibrium
In game theory, Nash equilibrium is a solution concept of a game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his own strategy unilaterally...
) is in fact $2; that is, the traveler values the antiques at the airline manager's minimum allowed price.
For an understanding of this paradoxical result, consider the following rather whimsical proof.
- Alice, having lost her antiques, is asked their value. Alice's first thought is to quote $100, the maximum permissible value.
- On reflection, though, she realizes that her fellow traveler, Babar, might also quote $100. And so Alice changes her mind, and decides to quote $99, which, if Babar quotes $100, will pay $101!
- But Babar, being in an identical position to Alice, might also think of quoting $99. And so Alice changes her mind, and decides to quote $98, which, if Babar quotes $99, will pay $100! This is greater than the $99 Alice would receive if both she and Babar quoted $99.
- This cycle of thought continues, until Alice finally decides to quote just $2 - the minimum permissible price!
Another proof goes as follows:
- If Alice only wants to maximize her own payoff, choosing $99 trumps choosing $100. If Babar chooses any dollar value 2-98 inclusive, $99 and $100 give equal payoffs; if Babar chooses $99 or $100, choosing $99 nets Alice an extra dollar.
- A similar line of reasoning shows that choosing $98 is always better for Alice than choosing $99. The only situation where choosing $99 would give a higher payoff than choosing $98 is if Babar chooses $100 -- but if Babar is only seeking to maximize his own profit, he will always choose $99 instead of $100.
- This line of reasoning can be applied to all of Alice's whole-dollar options until she finally reaches $2, the lowest price.
The ($2, $2) outcome in this instance is the Nash equilibrium of the game. However, when the game is played experimentally, most participants select the value $100 or a value close to $100, including both those who have not thought through the logic of the decision and those who understand themselves to be making a non-rational choice
Rational choice theory
Rational choice theory, also known as choice theory or rational action theory, is a framework for understanding and often formally modeling social and economic behavior. It is the main theoretical paradigm in the currently-dominant school of microeconomics...
. 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 has led some to question the value of game theory in general, while others have suggested that a new kind of reasoning is required to understand how it can be quite rational ultimately to make non-rational choices. Note that the $100 choice here is the optimal pure strategy under a different model of decision making called superrationality
Superrationality
The concept of superrationality was coined by Douglas Hofstadter, in his article series and book "Metamagical Themas"...
, which assumes that all logical thinkers must use the same strategy, so pure superrational strategies are restricted to the diagonal of the payoff matrix.
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 Prisoner's dilemma
Prisoner's dilemma
The prisoner’s dilemma is a canonical example of a game, analyzed in game theory that shows why two individuals might not cooperate, even if it appears that it is in their best interest to do so. It was originally framed by Merrill Flood and Melvin Dresher working at RAND in 1950. Albert W...
and thus the traveler's dilemma can be viewed as an extension of prisoner's dilemma. The traveler's dilemma is also related to the game Guess 2/3 of the average
Guess 2/3 of the average
In game theory, Guess 2/3 of the average is a game where several people guess what 2/3 of the average of their guesses will be, and where the numbers are restricted to the real numbers between 0 and 100, inclusive. The winner is the one closest to the 2/3 average.- Equilibrium analysis :In this...
in that both involve deep iterative deletion of dominated strategies in order to demonstrate the Nash equilibrium, and that both lead to experimental results that deviate markedly from the game-theoretical
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
predictions.
Payoff matrix
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
the set of strategies available to both players and by the payoff function of one of them we can write
(Note that the other player receives
since the game is quantitatively symmetricSymmetric game
In game theory, a symmetric game is a game where the payoffs for playing a particular strategy depend only on the other strategies employed, not on who is playing them. If one can change the identities of the players without changing the payoff to the strategies, then a game is symmetric. ...
).