## Traveler's Dilemma

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Oort
Posts: 522
Joined: Fri Sep 29, 2006 10:18 pm UTC

### Traveler's Dilemma

Stolen from Scientific American.

Lucy and Pete have identical antiques which are lost by the airline they took to get home. The manager will pay them back, but he assumes they'll try to inflate the price, so he decides to have them each (separately) write down the value of their item (an integer from 2 to 100 dollars). If they write the same number, he'll assume they're telling the truth and pay them each that. If they're different, he'll use the lower number, but pay the person who wrote it a bonus of \$2, and subtract \$2 from the person who (he thinks) tried to inflate the price. What should Lucy write?

crazyjimbo
Posts: 887
Joined: Fri Apr 20, 2007 11:45 pm UTC
Location: Durham, England
Contact:
What are the rules governing how much Pete writes? Will he be honest and write the actual price? Will he try to maximize his own profit? We he pick a random number between 2 and 100?

Does he also know the rules of the game? (In which case it is clear they should both write \$100).

Karrion
Posts: 92
Joined: Fri Jun 22, 2007 12:14 am UTC
Location: Melbourne, AU
crazyjimbo wrote:Does he also know the rules of the game? (In which case it is clear they should both write \$100).

Except that if Lucy knows that Pete will write \$100, then she should write \$99, so that Pete gets \$98 and she gets \$101. Unfortunately Pete would know this, too...

crazyjimbo
Posts: 887
Joined: Fri Apr 20, 2007 11:45 pm UTC
Location: Durham, England
Contact:
Karrion wrote:
crazyjimbo wrote:Does he also know the rules of the game? (In which case it is clear they should both write \$100).

Except that if Lucy knows that Pete will write \$100, then she should write \$99, so that Pete gets \$98 and she gets \$101. Unfortunately Pete would know this, too...

Very true, I didn't really think that through before posting.

Maybe we have enough information - I'll think it through as I go to sleep.

So until tomorrow, good night!

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC
Lucy should write \$100 and convey this information to Pete. That way, Pete will write \$99, and Lucy will get \$97 out of the transaction. Otherwise, they'll play a stupid "be under the other guy by \$1" game and end up at \$2 each.

Blatm
Posts: 638
Joined: Mon Jun 04, 2007 1:43 am UTC
Cauchy wrote:Otherwise, they'll play a stupid "be under the other guy by \$1" game and end up at \$2 each.

But if Pete is going to write \$96, it's to Lucy's advantage to write \$100, not \$95. Without having analyzed the problem much, I get the feeling that \$96 and \$100 are the best they could do if they're stubborn.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC
Blatm wrote:But if Pete is going to write \$96, it's to Lucy's advantage to write \$100, not \$95. Without having analyzed the problem much, I get the feeling that \$96 and \$100 are the best they could do if they're stubborn.

No, if Pete's going to write \$96, Lucy makes more money writing \$95 (\$97) than writing \$100 (\$94).

Blatm
Posts: 638
Joined: Mon Jun 04, 2007 1:43 am UTC
Serves me right for writing so late (he says as he tries again.)

Ether way. after some more thought, I figure probably best to pick \$100. Assuming Lucy and Pete are perfect logicians (after all, who isn't these days?), they will both have the same reasoning, and will both come to the same conclusion, and that conclusion should be as high as possible.

Of course, they could always just be honest and give the correct price. Or one could be really greedy and guess a dollar under that.

arbivark
Posts: 531
Joined: Wed May 23, 2007 5:29 am UTC
What should Lucy write?

A letter to her attorney, cc'd to airport guy.

GhostWolfe
Broken wings and scattered feathers
Posts: 3892
Joined: Fri May 11, 2007 11:56 am UTC
Location: Brisbane, Aust
Contact:
Lucy should just write \$100. The worst that will happen is that she'll get the value of the item less \$2. Pete can't screw Lucy without also screwing himself.
Linguistic Anarchist
Hawknc: ANGELL IS SERIOUS BUSINESS :-[
lesliesage: Animals dunked in crude oil: sad. Animals dunked in boiling oil: tasty.
Belial: I was in your mom's room all night committing to a series of extended military actions.

V
Posts: 49
Joined: Thu Nov 09, 2006 1:15 pm UTC
SilverWolfe wrote:Lucy should just write \$100. The worst that will happen is that she'll get the value of the item less \$2. Pete can't screw Lucy without also screwing himself.

This is not quite true. In case Pete guesses Lucys answer, he will get \$101 by writing \$99, wherea Lucy only gets \$98.

Interessting puzzle, by the way.

V.

__Kit
Posts: 1576
Joined: Tue May 08, 2007 5:12 am UTC
Location: 16/M/NZ
Contact:
100
=]

Poker
Posts: 60
Joined: Fri Jun 15, 2007 2:33 am UTC
Location: Multiple Places (only one now that you read this...)
Actually, a little thing needs clearing up.

Does he pay each person what they said it was worth (possibly + or - 2), or does he pay each person the lower of the two values (possibly + or - 2)? Because we seem to have different members believing different situations.

evilbeanfiend
Posts: 2650
Joined: Tue Mar 13, 2007 7:05 am UTC
Location: the old world
it says the lower number in the first post.

i'd go with them both picking 100 as it is near optimal even if the other decides to betray them
in ur beanz makin u eveel

apeman5291
Posts: 634
Joined: Sun Jun 17, 2007 12:19 am UTC
Location: Columbia, SC, USA
Contact:
Poker wrote:Does he pay each person what they said it was worth (possibly + or - 2), or does he pay each person the lower of the two values (possibly + or - 2)?

The lower value +/- 2.

Anyway, I decided to completely ignore the logical aspect of this problem, and assumed that Pete would pick a random number between 2 and 100. When lucy picks 96 or 97, the expected value of the money she gets is the highest at around 49.081. Maybe that's the answer by some stroke of luck.

Legrow
Posts: 15
Joined: Fri Jun 29, 2007 7:23 am UTC
Poker wrote:Actually, a little thing needs clearing up.

Does he pay each person what they said it was worth (possibly + or - 2), or does he pay each person the lower of the two values (possibly + or - 2)? Because we seem to have different members believing different situations.

If Lucy writes \$72 and Pete writes \$77, Lucy will receive \$74 and Pete will receive \$70.

My guess wrote:My guess is that it depends on how you want to define what she should pick -- is Lucy to guarantee that she earns more money than Pete? Or is Lucy to attempt to maximize her earnings? The absolute maximum she can earn is in the case where she writes \$99 and Pete writes \$100. However, the minimum she could earn in this case is \$0, if Pete writes \$2. If she writes \$2, the minimum she could earn is \$2, and the maximum is \$4.

I don't believe there's one simple answer here, as continually undercutting Pete means that you'll end up earning more than he will. Additionally, Pete's behavior isn't defined - he may act rationally, but he may also act randomly or irrationally, which further clouds Lucy's ability to decide on an amount to write. In this type of problem, Lucy can't reason based solely on mathematical logic, Lucy's choice has to be made as a function of mathematical logic, deductive reasoning, and a guess.

A long story short, if I were Lucy, I write \$99, as that number gives you the maximal potential earnings (\$101).

"And over there, we have the forum guards. One always writes \$1 less than you, one always writes the same number as you, and one stabs people who ask Game Theory questions."

Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL
The issue here is what the players want. Pete's going to be thinking the same things that Lucy is, so the solution for the "best" thing to do ought to be symmetric. Further, I believe they would try to maximize their actual payoffs, given that their opponent is trying to do the same.

Game Theory wrote:Let's say the actual value of the antique is 100, even though it doesn't matter if it's more or less. One possible starting strategy is both players say it's worth 100. This would be great, neither player has any motivation (or ability) to inflate the price, and they both get full value for it. Then again, what if Pete says 99? He'd get 101, and Lucy would get only 97. Strictly better for Pete in this instance to say 99 rather than 100, and in fact no matter what Lucy writes, 99 is a better choice than 100. This is of course also true for Lucy, so it is illogical for either to write down 100, even if the other person also wrote 100.

His payoff is maximized by picking P = L - 1, where L is what Lucy wrote down, and P for what Pete wrote. Of course, Lucy's payoff is maximized by picking L = P - 1. Extending the logic in the above example, 98 is strictly better than 99, the highest "logical" choice so far, and by extension of the same argument, we get to the worst case of all. Both players will write 2. This is a stable equilibrium of the game, as both players do strictly worse by writing any other number, given that their opponent picks 2.

This of course ignores collusion between players, sharing of profits, or the possibility that this happens repeatedly, and they want to establish trust and reputations between each other.

To address Legrow's guess, I'd say your guess assumes that your opponent isn't trying to maximize his own payout, or else you'd never get anywhere near the one you're hoping for.

Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL
OK, now for another question: let's say this happens to our poor antique collectors on a weekly basis. In other words, every Sunday they get on a plane, and every Monday they get a phone call to say something's been lost, how much is it worth? They can't call each other or converse, nor do they know what the other person wrote, but the check arrives on Thursday, so they can deduce what the other person must have written and plan for next Monday accordingly.

My last post demonstrated how two rational people can get to an answer that nobody likes. Assuming she gets to send a telegram/letter/e-mail to Pete the day before this mess begins, can Lucy set up a system by which she can do even better? (Still assuming they don't share the money, and assume they both want to make the most possible money.)

If your brain isn't hurting too much, consider this: does your answer change if they know they'll be playing this game exactly k times, and not some indeterminate/infinite number?

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney
I think the best solution is probably a mixed one ie a collection of probabilities on the numbers from 2 to 100. What those probabilities are though isn't something I'm going to calculate right now.

Oort
Posts: 522
Joined: Fri Sep 29, 2006 10:18 pm UTC
To clarify:

Pete and Lucy can't talk to each other. If they did they would probably cheat.

We can assume that each wants to maximize his/her own earnings.

We can also assume there is no collusion or sharing of profits.

LE4dGOLEM
is unique......wait, no!!!!
Posts: 5972
Joined: Thu Oct 12, 2006 7:10 pm UTC
Location: :uoıʇɐɔol
Oort wrote:To clarify:

Pete and Lucy can't talk to each other. If they did they would probably cheat.

We can assume that each wants to maximize his/her own earnings.

We can also assume there is no collusion or sharing of profits.

still, both should pick 100, and then both get 100.
Une See Fights - crayon super-ish hero webcomic!
doogly wrote:It would just be much better if it were not shitty.

Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL
As has been mentioned before, this is NOT optimal. If you pick 100, I'll gladly pick 99 and take home 101, leaving you with 97.

Also, even if they spoke to each other, what's to keep one from betraying the other? Even if you promised me you'd pick 100, it's irrational for me to choose 100 over 99, since I get strictly more money.

LE4dGOLEM
is unique......wait, no!!!!
Posts: 5972
Joined: Thu Oct 12, 2006 7:10 pm UTC
Location: :uoıʇɐɔol
Gwydion wrote:As has been mentioned before, this is NOT optimal. If you pick 100, I'll gladly pick 99 and take home 101, leaving you with 97.

Also, even if they spoke to each other, what's to keep one from betraying the other? Even if you promised me you'd pick 100, it's irrational for me to choose 100 over 99, since I get strictly more money.

Alternatively, you both could get \$100.

100+100 > 101+97 ?
Une See Fights - crayon super-ish hero webcomic!
doogly wrote:It would just be much better if it were not shitty.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC
This is just a fancy Prisoner's Dilemma, and everyone knows that the ideal solution there is for both people to not rat out the other. They should know this too and both pick \$100.

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London
Cauchy wrote:This is just a fancy Prisoner's Dilemma, and everyone knows that the ideal solution there is for both people to not rat out the other. They should know this too and both pick \$100.

Except for the fact that the equilibrium strategy in the Prisoner's Dilemma is the complete opposite.

Actually, a very similar problem to this is the first example given in the Wikipedia page on Nash equilibria.

Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL
You're right, Cauchy. But in the prisoner's dilemma, the "ideal" solution is not the one two rational people would come to without collusion or some fear of repercussions. Since this decision is unstable, we can expect it to fall apart, and pretty fast in reality. If I offered you a choice between \$101 or \$100, which would you take?

Ansain
Posts: 207
Joined: Sun Apr 15, 2007 1:15 am UTC
Location: Here
hypothetically picking 100 you could assume that they might undercut you and pick 99 giving you only 97. being that a 99-100 is the optimum undercut their is no reason for either player to go below 96 because they are just messing up both players. (if I say 95 to undercut a possible 96 then I get 97, the same I get if I say \$100, just pete is worse off). If both players realize this and want to maximize their profits then they wouldnt argue it all the way down to \$2 undercuting each other by one. Thus I would say \$98 or \$99 are equally good choices. 100 does the same or worse then them regaurdless of your opponents pick.

Alternately if you think pete is a good guy who would not lie you should say one dollar below the actual price, and if he is a complete idiot or if you just dont like him you should say \$2.

__Kit
Posts: 1576
Joined: Tue May 08, 2007 5:12 am UTC
Location: 16/M/NZ
Contact:
What if she picked 1\$ and then Pete had to pay the guy a dollar, I'd do that just for kicks.
=]

Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL
Ansain wrote:(if I say 95 to undercut a possible 96 then I get 97, the same I get if I say \$100, just pete is worse off).

I don't think I follow. If you say 95 to undercut Pete's 96, you get 97. However, if you say 100 to Pete's 96, you get 94. One of these choices gets you three dollars more.

The idea here is that two rational players won't just sit at 100. One will definitely undercut to 99, so what's to stop you from doing one better, cutting to 98? Of course, you're a smart person, but so is he. He'll cut to 97, etcâ€¦ Like with many problems of this nature, you don't often like where the argument leads you, but every step is logical.

Please don't make me draw up a 99x99 table. It will depress me on my day off.

Strilanc
Posts: 646
Joined: Fri Dec 08, 2006 7:18 am UTC
The Nash equilibrium is at 2\$. If they want to maximize their shared profit they will pick 100, if they want to maximize personal profit (with no regard for the other person) they will pick 2\$.
Don't pay attention to this signature, it's contradictory.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC
A "rational" player wouldn't be so greedy as to try to squeeze out an extra \$1 from the game, instead picking \$100 and hoping the other person came to the same conclusion, I would think.

I understand very well how Nash equilibria work, but I don't think they're necessarily the "rational" decision.

Strilanc
Posts: 646
Joined: Fri Dec 08, 2006 7:18 am UTC
Cauchy wrote:A "rational" player wouldn't be so greedy as to try to squeeze out an extra \$1 from the game, instead picking \$100 and hoping the other person came to the same conclusion, I would think.

I understand very well how Nash equilibria work, but I don't think they're necessarily the "rational" decision.

The problem is that if the other player picks 2\$, you get nothing. You need to maximize the minimum amount you can get.
Don't pay attention to this signature, it's contradictory.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC
\$0 versus \$2, boohoo. If he wants to only get \$4 off the deal, let him. He's just cutting off his nose to spite his face.

Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL
All right, Cauchy, let's change the game then. Instead of an integer between 2 and 100, let's make it a multiple of \$1,000 between \$2,000 and \$100,000. An extra thousand bucks, while small in the face of a hundred grand, is still a lot of cash. That would set me up pretty well, in fact, enough that I'd definitely pick 99K over 100K to get the 101K.

Further, what if it were an integer between 2 and 10? Does the expected behavior change because the difference between max and min changes? How about between 2 and 4?

anfurny
Posts: 55
Joined: Thu Jun 14, 2007 2:48 am UTC
Location: Loudoun County, Virginia
Contact:
I do not believe the optimal solution is two dollars, but I do know what a Nash equilibrium is.

IF only the lower bidder got paid, then it would be \$0, I believe (off-hand) striving for the \$2 profit, if both players were rational agents and believed the other to be a rational agent.

If Pete believes Lucy will say anything above \$5, then he will go with \$100 (and actually he doesn't even need to be 100% certain, a 25% chance may be sufficient in most cases).

Reasoning:
Let's say Pete is fairly certain that Lucy will say at least \$5, but he can't say for sure what she'll say. So the odds of him exactly undercutting her to get the extra two dollars is minimal due to the uncertainty. To avoid the risk of himself being the lower one, he should make sure to bet ABOVE (or equal, or one less, or two less) than her. So he'd probably pick something around \$98 or \$99 (if she bids over he gains or hits \$100, if she bids below he gets her bet which is all he could reasonably hope for).

Sort of reminds me of the IPD tournament.
Privilege Revocation: You are not allowed to refer the xkcdians in first person. The exception to the rule is that-- wait, no, you're the exception to the rule of "don't be a dick". --LE4dGOLEM

Gelsamel
Lame and emo
Posts: 8237
Joined: Thu Oct 05, 2006 10:49 am UTC
Location: Melbourne, Victoria, Australia
99 imho

Edit: Wait do they know that each other wants the most money possible and that they know that they're both perfect logicians? If so - then 99 or 100. If only the former then it's a stupid puzzle, if only the latter then 2.
"Give up here?"
- > No
"Do you accept defeat?"
- > No
"Do you think games are silly little things?"
- > No
"Is it all pointless?"
- > No
"Do you admit there is no meaning to this world?"
- > No

MFHodge
Posts: 4246
Joined: Thu Apr 19, 2007 6:27 pm UTC
Location: :noitacoL Raleigh, NC
Contact:
I think we can agree that strict adherence to game theory would have both players at \$2. That's why game theory isn't perfect.

Here's how I look at it:

For a guess of \$100 possible returns are (\$100, \$97 or less)
For a guess of \$99 possible returns are (\$101, \$99, \$96 or less)
For a guess of \$98 possible returns are (\$100, \$98, \$95 or less)
For a guess of \$97 possible returns are (\$99, \$97, \$94 or less)
For a guess of \$96 possible returns are (\$98, \$96, \$93 or less)
(etc)

A guess of \$99 is clearly the best strategy as it has both the highest average return and the highest potential return.

Being perfect logicians, both players will realize that following game thoery will result in a lower average return for all parties and both players will conclude that a guess of \$99 will be optimal.

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney
Initially I tried to look for a probabilistic solution here, but in the end I reasoned as follows.

The players are symmetric. Whatever strategy one adopts, the other will adopt too, because that is the strategy that their reason tells them to adopt. Therefore, if we rule out strategies that are based on probabilities (ie half the time choose 100 and half the time choose 99), the best answer is to go for 100. The case of different numbers just won't come up. otoh, if we allow probabilistic strategies, the solution still comes down to always choosing 100, or at least it did in the few cases I checked.

But this all hinges on the inference that the two players will play the same strategy, which I think is sound, but which a great many of you will no doubt reject.

Strilanc
Posts: 646
Joined: Fri Dec 08, 2006 7:18 am UTC
jestingrabbit wrote:But this all hinges on the inference that the two players will play the same strategy, which I think is sound, but which a great many of you will no doubt reject.

They don't know this. For all they know, the other player enjoys being poor or will adopt a probabilistic strategy. Also, if we could assume this, the prisoner's dilemma would go away.
Don't pay attention to this signature, it's contradictory.

LSK
Posts: 573
Joined: Fri Oct 06, 2006 12:25 am UTC
Location: 60645
Via the law of diminishing returns, I suspect that both players writing \$100 is optimal. Because, after all, what's \$2 worth when you're getting \$100? There's such a minor incentive to defect!