Traveler's dilemma

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.

Formulation

The game 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?

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:

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, Bob, might also quote $100. And so Alice changes her mind, and decides to quote $99, which, if Bob quotes $100, will pay $101.
But Bob, 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 Bob quotes $99, will pay $100. This is greater than the $99 Alice would receive if both she and Bob 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 Bob chooses any dollar value 2–98 inclusive, $99 and $100 give equal payoffs; if Bob 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 Bob chooses $100—but if Bob 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.

Experimental results

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 close to $100.

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.^[4]

Variation

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.

Payoff matrix

The canonical payoff matrix is shown below (if only integer inputs are taken into account):

Canonical TD payoff matrix
	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\}$ the set of strategies available to both players and by $F:S\times S\rightarrow {\mathbb {R}}$ the payoff function of one of them we can write

F(x,y)=\min(x,y)+2\cdot \operatorname{sgn}(y-x)

(Note that the other player receives $F(y,x)$ since the game is quantitatively symmetric).

References

↑ Kaushik Basu, "The Traveler's Dilemma: Paradoxes of Rationality in Game Theory"; American Economic Review, Vol. 84, No. 2, pp. 391–395; May 1994.
↑ Kaushik Basu,"The Traveler's Dilemma"; Scientific American Magazine, June 2007
↑ Wolpert, D (2009). "Schelling Formalized: Strategic Choices of Non-Rational Personas". SSRN 1172602.
↑ Capraro, V (2013). "A Model of Human Cooperation in Social Dilemmas". PLoS ONE. 8 (8): e72427. doi:10.1371/journal.pone.0072427.

Topics in game theory

Definitions	Normal-form game Extensive-form game Escalation of commitment Graphical game Cooperative game Succinct game Information set Hierarchy of beliefs Preference

Equilibrium concepts	Nash equilibrium Subgame perfection Mertens-stable equilibrium Bayesian Nash equilibrium Perfect Bayesian equilibrium Trembling hand Proper equilibrium Epsilon-equilibrium Correlated equilibrium Sequential equilibrium Quasi-perfect equilibrium Evolutionarily stable strategy Risk dominance Core Shapley value Pareto efficiency Gibbs equilibrium Quantal response equilibrium Self-confirming equilibrium Strong Nash equilibrium Markov perfect equilibrium

Strategies	Dominant strategies Pure strategy Mixed strategy Tit for tat Grim trigger Collusion Backward induction Forward induction Markov strategy

Classes of games	Symmetric game Perfect information Simultaneous game Sequential game Repeated game Signaling game Screening game Cheap talk Zero-sum game Mechanism design Bargaining problem Stochastic game n-player game Large Poisson game Nontransitive game Global games Strictly determined game Potential game

Games	Prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Rock-paper-scissors Pirate game Dictator game Public goods game Blotto games War of attrition El Farol Bar problem Fair division Fair cake-cutting Cournot game Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Prisoners and hats puzzle Trust game Princess and monster game Monty Hall problem Rendezvous problem

Theorems	Minimax theorem Nash's theorem Purification theorem Folk theorem Revelation principle Arrow's impossibility theorem

Key figures	Albert W. Tucker Amos Tversky Ariel Rubinstein Daniel Kahneman David K. Levine David M. Kreps Donald B. Gillies Drew Fudenberg Eric Maskin Harold W. Kuhn Herbert Simon Hervé Moulin Jean Tirole Jean-François Mertens John Harsanyi John Maynard Smith John Nash John von Neumann Kenneth Arrow Kenneth Binmore Leonid Hurwicz Lloyd Shapley Melvin Dresher Merrill M. Flood Oskar Morgenstern Paul Milgrom Peyton Young Reinhard Selten Robert Aumann Robert B. Wilson Roger Myerson Samuel Bowles Thomas Schelling William Vickrey

See also	All-pay auction Alpha–beta pruning Bertrand paradox Bounded rationality Combinatorial game theory Confrontation analysis Coopetition List of game theorists List of games in game theory No-win situation Topological game Tragedy of the commons Tyranny of small decisions

This article is issued from Wikipedia - version of the 10/6/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.