\documentclass[10pt]{amsart}
\usepackage{amssymb,amsfonts,latexsym,amsthm,amsmath}

\begin{document}
\title{Traveler's Dilemma}
\author{Satoru Kudose}
\date{7/5/2007}

\begin{abstract}
In the game called Traveler's Dilemma, the standard game theoretic analysis cannot explain why people choose to play the strictly dominated strategy of the game except by saying that they are not maximizing their expected payoff, i.e. acting irrationally. In this paper, we look at how people might choose to play irrationally.
\end{abstract}

\maketitle

\section{Introduction}
In 1994, Kaushik Basu formulated a simple game Traveler's Dilemma. Like many other games in economics, it comes with a story. Here it is:

Just as you return from your wonderful summer vacation, you find that the airline has smashed your recently purchased antique. Fortunately, an airline manager says that he is happy to compensate for the antique. He also informs you that, coincidentally, the airline also misplaced the identical antique from another traveler Bob.

The manager, unwilling to pay more than he has to and having no idea what the actual price of the antique is, figures out a scheme to determine the true price. He asks you and Bob to write down any integer between 2 and 100 without conferring together. If you and Bob write the same number, then the manager will take that to be the true price and pay you and Bob that amount. If the number is different, then the manager will take the lower number to be the true price, and assume that the person with higher number is lying. So, in this case, the manager will pay you and Bob the lower number with the reward of 2 dollar for the person with the lower number and the penalty of -2 dollar for the person with higher number. For example, if you choose 84 and Bob chooses 48, then you get 46 and Bob gets 50 dollars. What number should you write down?

\section{Game Theoretic Analysis}
It may seem obvious at first that the best choice 100. However, a rational person would choose 2.

To see this, first assume that both players are rational, in the sense that they always choose their strategy to maximize their payoff. We define few things.

\newtheorem*{Def1}{Definition 1}
\begin{Def1}
Let $S_{i}$ where $i=1,2$ be a set of strategies for player $i$, and let $\pi_{i}(s_{1},s_{2})$ be a payoff for player $i$ given some strategies $s_{1}\in S_{1}$ and $s_{2}\in S_{2}$. A strategy for player 1, $s_{1}$, is \textit{strictly dominated} by $s'_{1}$ if
\begin{align*}
	\pi_{1}(s'_{1},s_{2})>\pi_{1}(s_{1},s_{2})&&\text{for all $s_{2}\in S_{2}$.}
\end{align*}
Similarly, a strategy for player 2, $s_{2}$, is strictly dominated by $s'_{2}$ if
\begin{align*}
	\pi_{2}(s_{1},s'_{2})>\pi_{2}(s_{1},s_{2})&&\text{for all $s_{1}\in S_{1}$.}
\end{align*}
\end{Def1}

So no rational person would choose strictly dominated strategy, because he can always do better by choosing other strategy.

\newtheorem*{Def2}{Definition 2}
\begin{Def2}
A \textit{Nash equilibrium} is a pair of strategies $(s^{*}_{1},s^{*}_{2})$ such that
\begin{align*}
	\pi_{1}(s^{*}_{1},s^{*}_{2})\geq \pi_{1}(s_{1},s^{*}_{2})&&\text{for all $s_{1}\in S_{1}$,}
\end{align*}
and
\begin{align*}
	\pi_{2}(s^{*}_{1},s^{*}_{2})\geq \pi_{1}(s^{*}_{1},s_{2})&&\text{for all $s_{2}\in S_{2}$.}
\end{align*}
\end{Def2}

Now, we prove that $(2,2)$ is the unique Nash equilibrium, and that $(100,100)$ is strictly dominated in Traveler's Dilemma. Note the payoff matrix for Traveler's Dilemma is
\begin{align*}
	\pi(x,y)=\begin{cases}
		(x+2,x-2)&\text{if $x<y$}\\
		(x,x)&\text{if $x=y$}\\
		(y-2,y+2)&\text{if $x>y$ where $x,y\in\{2,\ldots, 100\}$}
	\end{cases}
\end{align*}

\begin{table}
\begin{tabular}{|l|l|l|l|l|}
\hline
 & 2    &$\cdots$ & 99               & 100 \\ \hline
2     & (2,2)  &$\cdots$ & (4,0)     & (4,0) \\ \hline
$\vdots$&$\vdots$&$\ddots$ &$\vdots$ &$\vdots$\\ \hline
99    & (0,4)  &$\cdots$ & (99,99)   & (101,97) \\ \hline
100   & (0,4)  &$\cdots$ & (97, 101) & (100, 100)\\
\hline
\end{tabular}
\caption{The payoff matrix for Traveller's Dilemma}
\end{table}
So given other player choose to play $n$, your best choice is to choose $n-1$.

\newtheorem*{Le1}{Lemma 1}
\begin{Le1}
In Traveler's Dilemma, the strategy $100$ is strictly dominated by $99$.
\end{Le1}
\begin{proof}
By symmetry of the game, it suffices to check the condition for player 1. Suppose $s_{2}\in S_{2}$. If $s_{2}=100$, then we have
\begin{align*}
	\pi_{1}(100,100)=100<101=\pi_{1}(99,100).
\end{align*}
If $s_{2}<100$, then we have
\begin{align*}
	\pi_{1}(100,s_{2})=s_{2}-2<99\leq \pi_{1}(99,s_{2}).
\end{align*}
Hence, the strategy for $100$ is strictly dominated by$99$.
\end{proof}

\newtheorem*{Le2}{Lemma 2}
\begin{Le2}
In Traveler's Dilemma, $(2,2)$ is the unique Nash equilibrium.
\end{Le2}
\begin{proof}
	By symmetry of the game, it suffices to check the condition for player 1. Consider some $n>2$, then we have
\begin{align*}
	\pi_{1}(2,2)=2\geq 0=\pi_{1}(n, 2) &&\text{for all $n>2$.}
\end{align*}
So $(2,2)$ is a Nash equilibrium.

Now, we show uniqueness. Consider $(m,n)$ where $m,n>2$. If $m\neq n$, suppose without loss of generality that $m>n$, then we have
\begin{align*}
	\pi_{1}(n-1,n)=n+1>n-2=\pi_{1}(m,n).
\end{align*}
If $m=n$, then we have
\begin{align*}
	\pi_{1}(n-1,n)=n+1>n=\pi_{1}(m,n).
\end{align*}
Hence, no $(m,n)$ where $m,n>2$ can be a Nash equilibrium. Hence, $(2,2)$ is the unique Nash equilibrium.
\end{proof}

These results hold for more general game with payoff matrix
\begin{align*}
	\pi(x,y)=\begin{cases}
		(x+R,x-R)&\text{if $x<y$}\\
		(x,x)&\text{if $x=y$}\\
		(y-R,y+R)&\text{if $x>y$}
	\end{cases}
\end{align*}
where $x,y\in\{2,\ldots, 100\}$ and $R\geq 2$. So, no matter what the R (reward/penalty) is, we expect both players to choose $2$ and never choose $100$. However, this is not what people actually do. Several experiments show that many people actually play high numbers $90\sim 100$. In effect, yielding higher payoff for those who play irrationally. Also, we see that people tend to behave more rationally when R is big. Because such choice is very prominent, there may be a good reason for choosing 100 even this is not what a rational person would choose. 

\section{A Model}
The choice of $90\sim 99$ can be accounted for rather nicely by assuming that the other player might play 100. This analysis is published by Becker, Carter and Naeve (2005). But why would anybody play 100 knowing that 99 is always better? To explain such a behavior, it seems reasonable to look at what people actually do, and cast aside the tension between the theory and experiment for a moment.

Often, it is clear that some game is better played cooperatively, while some game is better played without cooperation. For example, in one shot Prisoner's dilemma, both players choosing to cooperate leads to a better outcome, but, in the game of chess, cooperation clearly does not work. In particular, in the game like Prisoner's dilemma, both players being rational leads to an undesirable end. So, instead, people may want to cooperate. How then do we decide whether to actually choose cooperative strategy or not?

We attempt to make a model that describe such decision. Here is the hypothesis: people choose to play cooperatively or not to play cooperatively depending on the game and their beliefs. We restrict attention to the game with a payoff matrix of Traveler's Dilemma, and measure the player's inclination to cooperate and not to cooperate. Recall that the payoff matrix for Traveler's Dilemma is:
\begin{align*}
	\pi(x,y)=\begin{cases}
		(x+R,x-R)&\text{if $x<y$}\\
		(x,x)&\text{if $x=y$}\\
		(y-R,y+R)&\text{if $x>y$}
	\end{cases}
\end{align*}
where $x,y\in\{2,\ldots, 100\}$ and $R\geq 2$. We make a definition to refer to the cooperative solution of the game namely $(100,100)$.

\newtheorem*{Def3}{Definition 3}
\begin{Def3}
Let cooperative strategies (CS) be set of all strategies $(s_{1},s_{2})$ such that
\begin{align*}
	\pi_{1}(s_{1},s_{2})=\pi_{2}(s_{1},s_{2}).
\end{align*}
Let cooperative equilibrium strategies (CE) be strategies $(s^{*}_{1},s^{*}_{2})$ such that
\begin{align*}
	\pi_{i}(s^{*}_{1},s^{*}_{2})\geq \pi_{i}(s_{1},s_{2})&&\text{for all $s_{1},s_{2}\in CS$.}
\end{align*}
\end{Def3}
This is basically what the players would choose if they are cooperating. So, in Traveler's Dilemma, $(100,100)$ is the unique cooperative equilibrium and $(2,2)$ is the unique Nash equilibrium.

Let $CE$ be the strategy for cooperative equilibrium and $NE$ be the strategy for Nash equilibrium. We define inclination to cooperate (IC) to be:
\begin{align*}
	IC=k\frac{p\pi(CE)}{(1-p)\pi(NE)}.
\end{align*}
where $k$ is some experimentally determined constant and $p$ is a player's estimate of the probability that other player would play cooperatively (How much you expect other will cooperate.). We see that $\frac{p\pi(CE)}{(1-p)\pi(NE)}$ measures how much better it is for the player to cooperate than to play rationally. The constant $k$ accounts for the factors outside of the game that makes a person cooperate more; it should account for the individual differences. 

We define inclination not to cooperate (IN) to be
\begin{align*}
	IN=\frac{\pi(CE)-1+R}{\pi(CE)}.
\end{align*}
Note that $\pi(CE)-1+R$ corresponds to the maximum possible gain in playing without cooperation for this particular game. So, if the player believes the other player would cooperate with probability $p$, then $p(\pi(CE)-1+R)$ is the expected payoff. So $\frac{p(\pi(CE)-1+R)}{p\pi(CE)}$ measures how much better it is to not to cooperate than to play cooperatively.

We turn the hypothesis, that people decide to play cooperatively or not depending on their belief and on the game at hand, into an inequality.
\newtheorem*{Mod1}{Model}
\begin{Mod1}
Suppose we have a game with positive unique Nash equilibrium and cooperative equilibrium as in Traveller's Dilemma. If $IC>IN$, then the player decides to cooperate and choose CE strategy. Otherwise the player do not cooperate. 
\end{Mod1}

Rearranging the inequality, if
\begin{align*}
	k>\frac{1-p}{p}\cdot\frac{\pi(NE)(\pi(CE)-1+R)}{\pi(CE)^2},
\end{align*}
then the player chooses CE strategy. We note several points in regard to generalization. First, this model may be able to account for the game with multiple NE by letting $\pi(NE)$ be the average of $\pi(NE)$. If no cooperative equilibrium exists, then we can arbitrary let $\pi{CE}$ be some number very close to zero, so that people are less likely to cooperate. We now note several points in regard to the behavior of $p$. For a game with $n>2$ players, we expect that $p$ is smaller than that of two player game (perhaps $p^n$?), so that people cooperate less in the crowd. For repeated game, the value of $p$ changes according to the previous choices. In particular, if players know each other, we expect $p$ to be higher leading to more cooperation. All of this assertion must be experimentally verified. 

Because the value of k and p are not known, we cannot make a precise prediction of the proportion of people who choose to cooperate. However, we can make some qualitative observations. We see that if Nash equilibrium is very small in comparison to the cooperative solution, then people are more likely to choose to cooperate, i.e. choose 100. Players see the effect of playing rationally and choose not to do so. We see that people choose to not to cooperate if the reward for not doing so is high. We see that people who rule out the possibility of other player choosing to cooperate (the case where $p\approx 0$) do not cooperate; so the case where we assume that $p\approx 0$ corresponds to the assumption that both players act rationally.

If we let $k'=\frac{p}{1-p}$ and assume that $k'$ is distributed normally with mean 0.18 and standard deviation $.025$, then we can calculate the proportion of people who cooperate, which is 0.189. Since the Nash equilibrium is 2 and the cooperative equilibrium is 100, people who cooperate must satisfy $k>.0202$ from above inequality. We evaluate the area under the normal curve with lower limit 0.0202, and we get $\sim$0.189. So this model gives a correct number for proportion of people who cooperate for this particular payoff matrix. But, of course, these numbers are precisely chosen to do so for the specific sample in the paper by Becker et al.. So this must be tested further experimentally with different sample and different value of R. The determination of the mean and distribution for the value of $k'$ also requires experiments with different payoffs. (The mean is probably dependent on the game while the distribution is more or less independent. It's hard to say without any data.)

Furthermore, if both player believes that the other player would choose to play cooperatively or not depending on the game and his belief, then we see that a rational (payoff maximizing) person would naturally consider the Bayesian model of the game as in Becker et al. where it is assumed that the probability of the other player playing 100 is nonzero. (Unless they hold a firm belief that all humans always maximize their payoffs.) Players who choose 2 are ruling out the possibility of others choosing to play cooperativlely. In Traveler's Dilemma, we see that this assumption is not actually profitable. And we see that there is something "rational" about choosing 100 though the choice does not maximize player's payoffs; this choice is in fact a product of thoughtful consideration based on the game at hand.

\begin{thebibliography}{1}
	\bibitem{1} Basu, Kaushik	{\em The Traveler's Dilemma: Paradox of Rationality in Game Theory.} 1994.
	\bibitem{2} Becker et al.	{\em Experts Playing the Traveler's Dilemma.} 2005.
	\bibitem{3} Capra et al.	{\em Anomalous Behavior in a Traveler's Dilemma?.} 1999.
	\bibitem{4} Goeree et al.	{\em Stochastic Game Theory: For Playing Games, Not Just for Doing Theory.} 1999.
\end{thebibliography}





\end{document}
