Get this book -> Problems on Array: For Interviews and Competitive Programming

Reading time: 21 minutes | Coding time: 11 minutes

### Introduction to 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.

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

### 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!

## Questions

#### What is the best strategy for this game

### Further Reading

- Anomalies in Traveler's Dilemma : Research Gate article