Esoteric Dissertations from a One-Track Mind

January 25, 2008

Traveler’s Dilemma

Filed under: programming, science — Tags: — codesmithy @ 9:46 am

Scientific American has an article on the surprising result from a game known as the “Traveler’s Dilemma.”

A brief summary of game goes like this. There are two travelers Alice and Bob, and they each bought identical souvenirs. Unfortunately, both of them has been lost. The Airline is more than happy to compensate them for the loss, but the Airline manager doesn’t know how much the souvenirs cost. He doesn’t want to ask the travelers directly for fear they will inflate the price.

He comes up with a complicated scheme. He will ask Alice and Bob to write down the price of the souvenir without allowing them to communicate. If the amount they write down matches, then he will compensate Alice and Bob the amount they wrote down. If one of them writes a smaller amount than the other, the Airline figures the lower price is the honest price. The airline also imposes a $2 penalty on the person who had the higher, dishonest price, and rewards the person who gave the lower bid $2 for their honesty. The Airline cannot reimburse for goods over $100, or for goods under $2. Here are a couple scenarios:

Alice Bet Bob Bet Alice Outcome Bob Outcome
100 100 100 100
40 30 28 32
99 100 101 97

Now, what is interesting about this game is what happens when two rational, self-interested entities play it. Much like Prisoner’s dilemma, the particulars about how much the souvenir is worth (or one’s guilt or innocence) doesn’t really enter into the thinking about what to do in this scenario. Just like in the Prisoner’s dilemma, one knows nothing about the character of the other person, except that they are presumably rational, self-interested and capable of going through the same thought process you are. So what would such a rational thought process look like in code.

Well, first we define some of the rules of the game.

const int PENALTY = -2;
const int REWARD  = 2;
const int MIN_BET = 2;
const int MAX_BET = 100;

Next we write a function that given the two players bets, what their rewards would be.

void RewardPlayers(int aBet,int bBet,int* pAReward,int* pBReward)
    if(aBet == bBet)
        (*pAReward) = aBet;
        (*pBReward) = bBet;
    else if(aBet < bBet)
        (*pAReward) = aBet + REWARD;
        (*pBReward) = bBet + PENALTY;
        (*pAReward) = bBet + PENALTY;
        (*pBReward) = bBet + REWARD;

Next we write a function that given the opponent's bet, finds what the optimal bet I should make is.  For example, if the opponent bets $100, then I should bet $99 because then I'll receive $101.

&#91;sourcecode language='cpp'&#93;
int RationalBet(int oppBet)
    int oppOutcome = -1;
    int outcome = -1;
    int bestBet = -1;
    int bestOutcome = -1;
    for(int i = MIN_BET; i <= MAX_BET;++i)
        if(outcome > bestOutcome)
           bestBet = i;
           bestOutcome = outcome;
    return bestBet;

Finally, we determine the rational outcome. We assume that both Alice and Bob start their bets at the MAX_BET, or $100. We start with Alice, assuming Bob bets $100, does she rationally want to keep her bet at $100, or does she want to do something different. If she keeps the same bet, then we are done. If she changes her bet, then we record what her new rational bet is and switch to Bob’s perspective. Bob assumes Alice will do the rational thing, so looking at how the bets currently stand, does Bob want to change his bet given what he knows Alice will rationally do. Again, if Bob doesn’t change his bet, we are done. However, if he does, we record the new bet, switch to Alice’s perspective and repeat, until the bet doesn’t change.

void RationalOutcome(void)
    int bets[2];

    bets[0] = MAX_BET;
    bets[1] = MAX_BET;

    int side = 0;
    int newBet;
    int oldBet;
        oldBet = bets[side];
        newBet = RationalBet(bets[side == 0 ? 1 : 0]);
        if(oldBet != newBet)
           bets[side] = newBet;
           side = side == 0 ? 1 : 0;
    } while(newBet != oldBet);

    printf("A bets: %d\n",bets[0]);
    printf("B bets: %d\n",bets[1]);

As it turns out, the rational result is for both people to bet $2. There are reasons why this result occurs, but I first want to explore a reason why this result does not occur. This result does not occur because it assumes malevolence on the part of either of the players. The players are whole-heartedly disinterested, they are only looking out for themselves (self-interested) or the making the equivalent assumption about the other player (the other player is rational, self-interested and unconcerned about your welfare). To prove this is the case, you can set the penalty to 0 and rerun the simulation. You’ll arrive at the same result.So, why are we arriving at such a non-intuitive result? What is pushing the result down is the fact that the lesser bet wins, and, in fact, beats agreeing with the other person. It causes a race to the bottom. If Alice bets 98, then Bob’s best strategy is to bet 97. If Bob’s best strategy is to bet 97, then Alice’s best strategy is to bet 96, all the way down until they hit rock bottom. The article finds that people don’t act this way, even people well-versed in game theory, knowing they are going to compete with other people well-versed in game theory.

I imagine the reasons are similar to those found in the prisoner’s dilemma exercise. Successful players will cooperate, because cooperation helps their survival and the survival of those they cooperate with. When an optimal player comes across an uncooperative player, it will remember and punish the uncooperative player until it does cooperate. In short, the best strategy might be a tic-for-tat strategy or a specially optimized version of it.

The other reasons people don’t are similarly simple and attack some of the base assumptions we made. We don’t assume the other player will be perfectly rational. Even if we do assume they are somewhat rational, we don’t assume they’ll take the rational thinking to its logical conclusion. This might be because of so-called meta-thinking, the 97-96, 96-95, … sequence might be considered to similar too a Rock-Papers-Scissors loop which has no stable outcome R-P,S-P,S-R,P-R,P-S,R-S,R-P. People might go 3 or 4 iterations and just stop, seeing it as pointless to go further. Similarly, people rationally see the detriment to their own outcomes. When a player bets 98, they are no better off holistically if both players would have stayed at 100. One player assumes the other player recognizes this fact also, and takes it upon itself to be altruistic as opposed to self-interested.

Personally, I think the author gets too hung-up calling non-Nash equilibrium states emotional. I honestly don’t think it is an either/or. People come in with a wholly different set of assumptions than the mathematical analysis. The mathematical analysis is extraordinarily useful, and part of the reason why computers are good at beating people at games like chess and checkers, however calling people irrational because they deviate from the model is confusing what should be conforming to what. Should the model be conforming to reality? Or reality be conforming to the model?

It is no surprise that the model and its assumptions should conform to reality. My organic chemistry professor warned us not to confuse the two. I think the Scientific American article presents as good a warning as any as to why it is dangerous. Although, I will say that economics seems to be most guilty of committing error in judgment.

As the article explores, there are repercussions to this. It highlights the failures of pure rational self-interest, which is embodied in a few movements and policies notably Free Market Fundamentalism and Mutually Assured Destruction. It gives an example of people cooperating, even though reductionists says they should not, and opens an avenue of inquiry and possibly some evidence in favor of evolutionary psychology, to better explain why people think the way they do.


Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Blog at

%d bloggers like this: