Traveler's dilemma

Reading time: 21 minutes | Coding time: 11 minutes

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

Game theorists analyze games without all the trappings of the colorful narratives by studying each one’s so-called payoff matrix—a square grid containing all the relevant information about the potential choices and payoffs for each
player.

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 dollars.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.

Algorithm

Note : Now imagine if both prisoners are lcoked up N times. Then what to do in such case?

Take your input in x and you opponent's input in y
pass via a payoff function:

F(x, y) = min(x, y) + 2*sgn(y-x)

While your opponent's payoff would be
F(y, x) = min(x, y) + 2*sgn(x-y)

This is the zero determinant strategy!

Complexity

• Worst case Performance : O(1)
• Worst case space complexity : O(1)

Implementations

Using Python 3.5 as our main language

• An interactive traveller dilemma

import random

def sgn(a):
    if a > 0:
        return 1
    elif a == 0:
        return 0
    else:
        return -1


x = input("What's your input: ")
y = random.randint(2, 100)

fxy = min(x, y) + 2*sgn(y - x)
fyx = min(x, y) + 2*sgn(x - y)

print ("You entered a compensation of {} while the computer said {} .\nSo, your payoff is {} and computer's payoff is {}").format(x, y ,fxy, fyx)

Applications

As you may hav alrady noticed, the traveller's dilemma formulation shows no signs of mutual cooperation and is driven by individual profits giving no regards to competitions well being.

Said that, it's actual application stays within the game. One may argue that it's variations like the one mentioned below are still accountable to real world scenarios.

"Usually the choice is time or money, especially when you are young. If you have the time, it's usually because you are unemployed, so you don't have the money, and visa versa. Then, even when you are older, you are working and often only
have a limited amount of vacation time to allot to any adventure.

This dynamic also works when you are on vacation.Say you are visiting London - a very popular and expensive place to visit. lf you stay right at Hyde Park say, you will be right there, and not waste any time on transport. Or you can stay out of
London, on a trainride to where you want to go, but you will waste possibly 2 hrs a day on commute. So on a 4 day stay, almost 1 day will be spend on getting to where you want to go. "

Although truth be told, this is a major detour from game theory and not necessarily serves the purpose of being a zero sum game!

Further Reading

• Anomalies in Traveler's Dilemma : Research Gate article