Traveler's Dilemma
Moderators: jestingrabbit, Moderators General, Prelates
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?
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:
 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 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.
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).
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.
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.
 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.
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.
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.
 evilbeanfiend
 Posts: 2650
 Joined: Tue Mar 13, 2007 7:05 am UTC
 Location: the old world

 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.
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."
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.
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.
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.
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/email 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?
My last post demonstrated how two rational people can get to an answer that nobody likes. Assuming she gets to send a telegram/letter/email 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
 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 superish hero webcomic!
doogly wrote:It would just be much better if it were not shitty.
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.
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 superish hero webcomic!
doogly wrote:It would just be much better if it were not shitty.
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.
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?
hypothetically picking 100 you could assume that they might undercut you and pick 99 giving you only 97. being that a 99100 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.
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.
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.
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.
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?
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?
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 (offhand) 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.
IF only the lower bidder got paid, then it would be $0, I believe (offhand) 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.
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
 > 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
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.
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.
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.
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.
Who is online
Users browsing this forum: Google [Bot] and 9 guests