Traveler's Dilemma

[EnderSword]

You still haven't shown anything wrong with the logic, Ender. I didn't assume anything, I showed everything. It is provable that rational actors will never, ever play 100. If you disagree with that proof, I can go over it again for you, or you can just be wrong.

100 being Eliminated requires 99 to be played. 47 doesn't invalidate 100, nor does 2.
Similarly 100, nor 47 nor 2 invalidate 99, only 98 does.

I have shown logical chains that contain the same thought process that don't hold.

If 99 can't be played, its existence doesn't help anything. You can't simultaneously eliminate multiple numbers when the elimination or one is solely dependant upon the playability of another.

I follow the Nash Equilibrium logic to get you to 2, requiring all moves be unilateral...but this Deductive elimination model is wrong no matter what. Once you've knocked out your premises, you break it.

[quintopia]

Ender: you're attacking a different proof. The one we are using now requires no chain deduction. Look at the proof in my last post again and tell me which step you disagree with.

If it is the first step: in what cases would a rational player who knows his opponent is going to play x where x>2 not play x-1?
If it is the second: In what cases would two rational players not make the same deductions leading to the same conclusions given that both players operate according to the same rules?
If it is the third: How does this not follow from the second step?

[thc]

Ender: you're attacking a different proof. The one we are using now requires no chain deduction. Look at the proof in my last post again and tell me which step you disagree with.

If it is the first step: in what cases would a rational player who knows his opponent is going to play x where x>2 not play x-1?
If it is the second: In what cases would two rational players not make the same deductions leading to the same conclusions given that both players operate according to the same rules?
If it is the third: How does this not follow from the second step?

Any rational player, who knows with certainty that his opponent (any opponent) will play x>2, will play x-1 in response.
Any rational player, playing against a known rational opponent, must necessarily play the same strategy as his opponent.
Any rational player knows with certainty what his rational opponent will play.
Therefore, contradiction. No rational player can play x>2 against a rational opponent.

I take issue with the 3rd step. A rational player doesn't necessarily know what his rational opponent will play. Take for example, rock paper scissors. You may say that it's not the same thing and TD doesn't have the same properties as RPS. But how do you know this? I.e., how do you know that you will know what your rational opponent will play? You go through IEDS. So your proof isn't any different, and you still have to justify IEDS.

[quintopia]

Alright, let's just get rid of that little problem:
Let A be a rational player who knows (by deduction from the rules and some knowledge of his opponent) that his opponent B will play some x>2 .
1) Any rational player, who knows with certainty that his opponent (any opponent) will play x>2, will play x-1 in response, and any player who knows with certainty that his opponent will play 2 will play 2 in response.
2) If a player can be known that he is certainly going to play x>2, then that player knows himself that he is going to play some x>2. Thus, B knows he is going to play some x>2.
3) In this situation, A now knows with certainty that he is going to play x-1. This follows from directly from (1).

Now assume that B is rational and that all of the above is common knowledge.
4) Because, of (2) and (1), B can deduce (because he is rational and knows (1)) that A is going to play x-1 with certainty.
5) Now, because of (1), B must play x-2 (if x>3) or 2 (if x=3), and B can deduce this (because he is rational and knows (1)). Thus, if B is rational and knows with certainty that he is going to play some x>2, he can deduce that he must certainly play max(2,x-2). Contradiction.

Thus, A has already deduced, in knowing that B will be playing some x>2, that B is irrational, because of the irrefutable fact that assuming B is rational and about to play some particular x>2 leads directly to contradiction.
The same sort of argument can be applied to mixed strategies as well.

Let's use the same method to analyze Rochambeau.

Let A be a player who knows (by logical deduction from the rules and some knowledge of his opponent) that his opponent B is going to play x paper with probability 1/3+e and rock with probability 1/3-e for some e>0.
1) Any rational player in this situation will decide to play scissors with probability 1/3+e and paper with probability 1/3-e, as doing so will result in a win 1/3+e^2 of the time and a loss a mere 1/3-e^2 of the time, while his opponent will win 1/3-e^2 of the time and lose 1/3+e^2 of the time.
2) Because A knows with certainty that B will play this strategy, so also does B.
3) Because A is rational and knows (1) and what B will play, he will play (r,p,s)=(1/3,1/3+e,1/3-e).

Now assume that B is rational and all of the above is common knowledge.
4) B, being rational and knowing (1) and by (2) that he is going to play (1/3-e,1/3,1/3+e) can deduce that A will play (1/3,1/3+e,1/3-e).
5) From (1), B, being rational, can deduce that he must play (1/3+e,1/3-e,1/3). Yet this knowledge is derived from the fact that he knows he is going to play (1/3-e,1/3,1/3+e). Contradiction. B cannot be rational.


I could do this with just about any game. It's very formulaic. A knows B will play a non-equilibrium strategy and therefore B must know also. A therefore knows the best non-equilibrium strategy to get the highest expected gain. Assume B is rational. Then B knows from the fact that he is going to play strategy x that he must play a different non-equilibrium strategy y. Contradiction. B is not rational.

EDIT: It seems I have just begged the question. I have no idea how to prove that player A knows what player B will play. This only proves that if he does, then the move that he knows he will play is 2. I'll think about it some and come back to you.

[Scooch]

If the manager knows you have antiques which will require reimbursement, how does he not know their value? If he doesn't have proof of the antique's existence, can Lucy and Pete scam him repeatedly with 20 dollar luggage and bribing the baggage handler 10 dollars to lose the luggage and agreeing on 100 dollars for the claim? And Lucy should write a letter to the airline's VP complaining about the really crappy manager. I'm sure she'll be reimbursed the full amount.

[Puck]

quintopia, I don't think you're begging the question, unless I'm misunderstanding your argument. If B can come up with a strategy, then A will come up with the same strategy - both know what strategy they arrived at, so they both also know what strategy the other arrived at, knowing that they are identical.

So if it is possible for a rational player to determine a strategy (pure or mixed), then it must be an equilibrium strategy, because a non-equilibrium strategy would mean that there is a different, better strategy to play against it.

I'm not sure how you prove that it is possible for a rational player to select a strategy, exactly, other than to define a rational player as a strategy selector.

[quintopia]

Exactly. "Can a player select a strategy at all?" is equivalent to "Can a player determine the opponent's strategy with certainty?" so we're both facing the same problem. Now I want to talk to a specialist. . .

[AvalonXQ]

Please point out the incomplete or incorrect logic step below, if there are any. If you dislike my definitions, that works too.

A rational player is one that is guaranteed to never make a suboptimal move.
A move is suboptimal if, over the range of moves that the opponent could make, making the suboptimal move is inferior to making some other move.
Because a rational player will never make a suboptimal move, any move that is suboptimal can be removed from the range of possible moves for that player.

Players are P and Q. P and Q are rational players playing the Traveller's Dilemma. This is common knowledge between them.
Over the range of [2,100], moving 100 is suboptimal.
P will not move 100. P's range is restricted to [2,99].
Q will not move 100. Q's range is restricted to [2,99].
P knows that Q is rational. P knows that Q knows that moving 100 is suboptimal. Thus, P knows that Q's range is restricted to [2,99].
Q knows that P is rational. Q knows that P knows that moving 100 is suboptimal. Thus, Q knows that P's range is restricted to [2,99].
Over the range of [2,99], moving 99 is suboptimal.
P knows that Q's range is restricted to [2,99]. Therefore, P will not move 99. P's range is restricted to [2,98].
Q knows that P's range is restricted to [2,99]. Therefore, Q will not move 99. Q's range is restricted to [2,98].
P knows that Q knows that P's range is restricted to [2,99]. Therefore, P knows that Q's range is restricted to [2,98].
Q knows that P knows that Q's range is restricted to [2,99]. Therefore, Q knows that P's range is restricted to [2,98].
Over the range of [2,98], moving 98 is suboptimal.
P knows that Q's range is restricted to [2,98]. Therefore, P will not move 98. P's range is restricted to [2,97].
Q knows that P's range is restricted to [2,98]. Therefore, Q will not move 98. Q's range is restricted to [2,97].
P knows that Q knows that P's range is restricted to [2,98]. Therefore, P knows that Q's range is restricted to [2,97].
Q knows that P knows that Q's range is restricted to [2,98]. Therefore, Q knows that P's range is restricted to [2,97].
Over the range of [2,97], moving 97 is suboptimal.
P knows that Q's range is restricted to [2,97]. Therefore, P will not move 98. P's range is restricted to [2,96].
Q knows that P's range is restricted to [2,97]. Therefore, Q will not move 98. Q's range is restricted to [2,96].
P knows that Q knows that P's range is restricted to [2,97]. Therefore, P knows that Q's range is restricted to [2,96].
Q knows that P knows that Q's range is restricted to [2,97]. Therefore, Q knows that P's range is restricted to [2,96].
...
Over the range of [2,n], moving n is suboptimal.
P knows that Q's range is restricted to [2,n]. Therefore, P will not move 98. P's range is restricted to [2,n-1].
Q knows that P's range is restricted to [2,n]. Therefore, Q will not move 98. Q's range is restricted to [2,n-1].
P knows that Q knows that P's range is restricted to [2,n]. Therefore, P knows that Q's range is restricted to [2,n-1].
Q knows that P knows that Q's range is restricted to [2,n]. Therefore, Q knows that P's range is restricted to [2,n-1].
...
Over the range of [2,3], moving 3 is suboptimal.
P knows that Q's range is restricted to [2,3]. Therefore, P will not move 3. P will move 2.
Q knows that P's range is restricted to [2,3]. Therefore, Q will not move 3. Q will move 2.

[Puck]

Ender will argue that moving 100 being suboptimal is because 99 exists, and once you have determined that 99 is suboptimal, 100 now ceases to be suboptimal. I'm not sure how to convince him of the foolishness of this argument, exactly.

[quintopia]

I can already tell you what part Ender will take issue with:

P knows that Q's range is restricted to [2,99]. Therefore, P will not move 99. P's range is restricted to [2,98].
Q knows that P's range is restricted to [2,99]. Therefore, Q will not move 99. Q's range is restricted to [2,98].

And the idea of "restricting to ranges" in general.

I, OTOH, can find no flaw.

Ninja'd by Puck

[AvalonXQ]

Ender will argue that moving 100 being suboptimal is because 99 exists, and once you have determined that 99 is suboptimal, 100 now ceases to be suboptimal.

I'm not sure I follow. The argument is that 100 is not suboptimal over the range of [2,98]?
It might help if to note that there's two separate ranges under consideration. There's what P could play, and what Q could play.
Aha! I think I have a way to edit this that might help.

A rational player is one that is guaranteed to never make a suboptimal move.
A move is suboptimal if, over the range of moves that the opponent could make, making the suboptimal move is inferior to making some other move.
Because a rational player will never make a suboptimal move, any move that is suboptimal can be removed from the range of possible moves for that player.

Players are P and Q. P and Q are rational players playing the Traveller's Dilemma. This is common knowledge between them.
Over the range of [2,100] for your opponent's move, moving 100 is suboptimal.
P knows that Q's range is [2,100]. P will not move 100. P's range is restricted to [2,99].
Q knows that P's range is [2,100]. Q will not move 100. Q's range is restricted to [2,99].
P knows that Q is rational. P knows that Q knows that moving 100 is suboptimal. Thus, P knows that Q's range is restricted to [2,99].
Q knows that P is rational. Q knows that P knows that moving 100 is suboptimal. Thus, Q knows that P's range is restricted to [2,99].
Over the range of [2,99] for your opponent's move, moving 100 or 99 is suboptimal.
P knows that Q's range is restricted to [2,99]. Therefore, P will not move 100 or 99. P's range is restricted to [2,98].
Q knows that P's range is restricted to [2,99]. Therefore, Q will not move 100 or 99. Q's range is restricted to [2,98].
P knows that Q knows that P's range is restricted to [2,99]. Therefore, P knows that Q's range is restricted to [2,98].
Q knows that P knows that Q's range is restricted to [2,99]. Therefore, Q knows that P's range is restricted to [2,98].
Over the range of [2,98] for your opponent's move, moving 100, 99, or 98 is suboptimal.
P knows that Q's range is restricted to [2,98]. Therefore, P will not move 100, 99, or 98. P's range is restricted to [2,97].
Q knows that P's range is restricted to [2,98]. Therefore, Q will not move 100, 99, or 98. Q's range is restricted to [2,97].
P knows that Q knows that P's range is restricted to [2,98]. Therefore, P knows that Q's range is restricted to [2,97].
Q knows that P knows that Q's range is restricted to [2,98]. Therefore, Q knows that P's range is restricted to [2,97].
Over the range of [2,97] for your opponent's move, moving 100, 99, 98, or 97 is suboptimal.
P knows that Q's range is restricted to [2,97]. Therefore, P will not move 100, 99, 98, or 97 . P's range is restricted to [2,96].
Q knows that P's range is restricted to [2,97]. Therefore, Q will not move 100, 99, 98, or 97 . Q's range is restricted to [2,96].
P knows that Q knows that P's range is restricted to [2,97]. Therefore, P knows that Q's range is restricted to [2,96].
Q knows that P knows that Q's range is restricted to [2,97]. Therefore, Q knows that P's range is restricted to [2,96].
...
Over the range of [2,n] for your opponent's move, moving 100, 99, 98, 97 ... or n is suboptimal.
P knows that Q's range is restricted to [2,n]. Therefore, P will not move 100, 99, 98, 97 ... or n. P's range is restricted to [2,n-1].
Q knows that P's range is restricted to [2,n]. Therefore, Q will not move 100, 99, 98, 97 ... or n. Q's range is restricted to [2,n-1].
P knows that Q knows that P's range is restricted to [2,n]. Therefore, P knows that Q's range is restricted to [2,n-1].
Q knows that P knows that Q's range is restricted to [2,n]. Therefore, Q knows that P's range is restricted to [2,n-1].
...
Over the range of [2,3] for your opponent's move, moving 100, 99, 98,... or 3 is suboptimal.
P knows that Q's range is restricted to [2,3]. Therefore, P will not move 100, 99, 98,... or 3. P will move 2.
Q knows that P's range is restricted to [2,3]. Therefore, Q will not move 100, 99, 98,... or 3. Q will move 2.

... see? When determining P's optimum moves noting Q's more limited range, we still consider all possible moves for P, and find them suboptimal even over the reduced range. Excluding both 99 and 100 from your opponent's range doesn't suddenly make it better for you to choose 100 again.

[quintopia]

I think that does make it clearer. We'll find out if he ever comes back here.

A move is suboptimal if, over the range of moves that the opponent could make, making the suboptimal move is inferior to making some other move.

I suspect that if there's anything there he might disagree with, it would be that. He might say that the opponent might consider adding 100 back into his range also (because that brings back the possibility of getting a greater gain) and therefore, the opponent's range of moves does not shrink past a certain point.

But again, I'm only guessing. It would be much more useful if we didn't have to argue on behalf of the person we were trying to convince. Therefore, I really wish he would come back and say something here or we'll just have to give up and let him be wrong (and confident that he is right).

[Jedaz]

Alot of the arguments for the $2 solution seem to be assuming that you know the oponents stratergy, infact it seems that the assumption is that the oponent has the same rational as you.

If we use this assumption, that the oponent is just as rational as you, then the most optimal move is $100. Any rational player would know that $100 > $4 (the max that you could achive with going $2). If you are assuming the oponent is using the same rational then you know that they would also realize that if you both go $100 you would get more then if you both went $2. Since you are both using the same rational it is imposible to "out game" the other person, and thus going $100 is a much better solution then $2. Again, this is only if you know that your oponent is equally rational as you.

The best move, if your opponent can deduce your stratergy (ie, know what you are going to do), is to play $100. You can not beat such an opponent and $97 is better then $2 (by going a "sub-optimal" $100 we achive a much more optimal result).


I think to determine what is better out of the $2 and $100 strategies we need to have a little experiment. The biggest assumption around is what your opponent will do, in the problem presented we aren't told. So what I purpose is someone to create a poll on what people would chose (between 2 to 100). We can then deduce what would be more profitable against a random (potentially not rational) player.

[Silknor]

The only way your opponent can deduce your strategy is if that strategy is arrived at rationally. Picking 100, as shown many times earlier, is never rational.

As for the experiment, that's been done (see the Sciam article linked on the first page). Such an experiment tells you nothing about what is rational to do because many of the players there aren't rational and there's no reason to assume they are rational. Also once you move from hypothetical perfectly rational players to real human ones, you get all sorts of emotional values assigned to various outcomes, which, by choice, are not reflected in the original. So there's no reason to think those experiments tell you what the rational strategy is.

What's the most profitable strategy against a random opponent? It's certainly neither $2 nor $100. It's not $2 because experimentally most people will play >$95. It's not $100 because no matter what your opponent does, $99 produces a better payoff. The answer probably lies in the $97-$99 range, though that may vary based on what population you're drawing from.

[Jedaz]

The only way your opponent can deduce your strategy is if that strategy is arrived at rationally. Picking 100, as shown many times earlier, is never rational.

It's the most rational when the oponent has perfect information about you. Of course it's not going to happen in reality.

As for the experiment, that's been done (see the Sciam article linked on the first page). Such an experiment tells you nothing about what is rational to do because many of the players there aren't rational and there's no reason to assume they are rational. Also once you move from hypothetical perfectly rational players to real human ones, you get all sorts of emotional values assigned to various outcomes, which, by choice, are not reflected in the original. So there's no reason to think those experiments tell you what the rational strategy is.

Acually, by knowing how the general population reacts you can devise a stratergy which gives the most optimal payoffs. Wouldn't that be the most rational course of action? For example, if you know that 25% of the population plays $90+ while 75% plays $2 then by analysing this you know the most rational choice would be to play 89 as you would make $22.75 on average rather then $2.5.

What's the most profitable strategy against a random opponent? It's certainly neither $2 nor $100. It's not $2 because experimentally most people will play >$95. It's not $100 because no matter what your opponent does, $99 produces a better payoff. The answer probably lies in the $97-$99 range, though that may vary based on what population you're drawing from.

Agreed. I didn't intend to imply that $100 was the most optimal against a random opponent, but to more point out that $2 may not be the most optimal either, especially when you are against an opponent of equal rationality (who would then rationalise that both of you going $100 is optimal since they reach a sub-optimal conclusion when trying to beat the other player). I belive that earlier in the thread it was decided that $96 and $97 have equally good payoffs against a random opponent.

[quintopia]

Jedaz: Changing the question doesn't change the answer to the original problem. A person that says "I'll play the strategy that does best against an average human being" will fail miserably when they are playing a rational person who knows that they will play this strategy.

[Macbi]

Jedaz: Changing the question doesn't change the answer to the original problem. A person that says "I'll play the strategy that does best against an average human being" will fail miserably when they are playing a rational person who knows that they will play this strategy.

Jedaz's strategy against a normal human was "always play 89", if they play against a rational player who knows their stratgegy, then their expected gain is 86, which is better than the expected value against the average human. Hardly failing miserably, which is interesting.

[Silknor]

Well if you're playing against someone who knows your strategy, you might as well pick 100, since 97 is the highest payoff you can get when you play against an opponent who knows what you will pick. If that's truly common knowledge, then it's just a sequential game were player one has to reveal his pick before player 2 makes his choice.

Yes Jedez, you're right that it's rational to take in to account what strategies your opponents are using so you can maximize gain. What I meant was such experiments tell you nothing about how perfectly rational players who know the other is perfectly rational, and know the other knows this, and knows the other knows that etc (eg common knowledge) will play. So it's an interesting empirical question, but doesn't tell you how to play if you're playing in the common knowledge rational player setup.

[Jedaz]

Jedaz: Changing the question doesn't change the answer to the original problem. A person that says "I'll play the strategy that does best against an average human being" will fail miserably when they are playing a rational person who knows that they will play this strategy.

Jedaz's strategy against a normal human was "always play 89", if they play against a rational player who knows their stratgegy, then their expected gain is 86, which is better than the expected value against the average human. Hardly failing miserably, which is interesting.

Exactly. There is no reason to "win" the game by beating the other person, you win by maximising your final outcome. If that means taking a "sub-optimal" $86 rather then an "optimal" $2 then I don't see a problem.

Yes Jedez, you're right that it's rational to take in to account what strategies your opponents are using so you can maximize gain. What I meant was such experiments tell you nothing about how perfectly rational players who know the other is perfectly rational, and know the other knows this, and knows the other knows that etc (eg common knowledge) will play. So it's an interesting empirical question, but doesn't tell you how to play if you're playing in the common knowledge rational player setup.

Ah I see, I misunderstood what you ment. Well I don't see any reason why two perfectly rational players (and they know their opponent is perfectly rational) wouldn't realize that their maximum payoff is when they both go $100. Want to go $99? Sure, but you know that your opponent is thinking the same thing so there's no point in trying as you will just reach a sub-optimal conclusion.

[Silas]

Exactly. There is no reason to "win" the game by beating the other person, you win by maximising your final outcome. If that means taking a "sub-optimal" $86 rather then an "optimal" $2 then I don't see a problem.

It's the definition of rational, though. A rational player is (definition:) one who, knowing in advance his counterpart's choice, will never choose a move with a lower payout than another move would have.

Those are the axioms, like Yakk was talking about, that imply that the game will come down to a Nash equilibrium solution:
Both players are rational, like above: they'll never have regret, considering their information.
Since the game and the behavior of both players are well-known*, each player will know in advance what move the other will take.

*I'm greying this out, because it puts a claim on inference that I'm not prepared to defend.

[Jedaz]

Exactly. There is no reason to "win" the game by beating the other person, you win by maximising your final outcome. If that means taking a "sub-optimal" $86 rather then an "optimal" $2 then I don't see a problem.

It's the definition of rational, though. A rational player is (definition:) one who, knowing in advance his counterpart's choice, will never choose a move with a lower payout than another move would have.

And do you belive that $2 is the correct move? By going $2 and not allowing the opponent to undercut you with $88 you have just played a move which results in a lower payout then another move would have (which is going $89). Infact any move under $84 is garunteed to do just that. If I know what Quintopia is going to do, and Quintopia knows what I'm going to do then there isn't any chance for me to undercut and get a more optimal value (infact if I know for a fact that Quintopia is always going to try and play 1 less then me I will play $100 as I will receive $97 which is a better move then $2. If I tried $98 then I know that Quintopia would play $97, so $100 is the best move).

I find this the most interesting part of the discussion. When there are to two perfectly rational players it implys that they will reach the same conclusion. You can not have one perfectly rational player make a different choice then another perfectly rational player, otherwise one of them must not be perfectly rational. By both perfectly rational players knowing that the other is perfectly rational you can then determine that regardless of any attempts to undercut the other person they will not be able to. $100 is the best solution because of the identical decision making, if you decide to go $99 then you are garunteed that the other person will go $99 which is an inferior move to $100, in short the move pair of going $99, $100 does not exist, thus it's imposible to go x-1. This is what happens when you have two perfectly rational players who know their opponent is rational, they will always play the same thing.

To demonstrate what I mean consider this example, both players know what the other is going and is able to change their move at any time (basically the situation of two perfectly rational players as they will be able to deduce the opponents move).

Player A choses $100
Player B undercuts A with $99
Player A undercuts B with $98
ect..
Players A and B are at $2

Player A knows that by going $100 he can get $97 by letting B undercut him. Player A knows that as soon as he changes to try and undercut Player B, Player B will undercut A (who will undercut B, ect) thus leading back to $2. A therefore decides that going $100 and getting $97 is the best outcome that can be achived. This is because no such move to undercut the other person exists for A. If both players are perfectly rational they will decide on going $100 and both receive $100.

[Puck]

Heh, did you bother reading the previous 15 pages of discussion?

You are talking about superrationality. If a rational player knows that his opponent will pick 100, then he will always pick 99, not 100.

[Jedaz]

Heh, did you bother reading the previous 15 pages of discussion?

You are talking about superrationality. If a rational player knows that his opponent will pick 100, then he will always pick 99, not 100.

I read the pages and I still stick to the fact that the best solution that two perfectly rational players who know that their opponent is perfectly rational (and know's that they know, ect) should go $100 as it is the most optimal solution. Here are my assumptions on these perfectly rational players
*Since they are both perfectly rational they can correctly determine their opponents stratergy with 100% accuracy.
*Since their rationality is perfect they must come up with the same answer, otherwise one player has chosen an irrational solution.
*Both players know that both of them going $100 is better then both of them going $2.

It's exactly like playing the game against yourself. What are you going to pick $2 or $100? You lose out if you try to rip the opponent off because the opponent is thinking the exact same thing as you.

If that still doesn't convince you, why is it not rational to play $100 and let the opponent pick $99 if they are *always* going to play 1 lower then you? How could you hope to defeat such an opponent? Wouldn't a rational player take $97 over $2?

[quintopia]

I agree with all of the assumptions you listed but must insist on a rewording of the third one to more accurately reflect the truth: "both players know that both playing 100 is better than both playing 2 and would love to have that outcome if only it weren't an impossible outcome that lead directly to contradiction with their rationality". I didn't take away anything from the assumption or contradict either of the other assumptions so it is quite possible the assumptions you listed don't lead inexorably to the incorrect answer you insist they do.

[Yat]

Jedaz: Changing the question doesn't change the answer to the original problem. A person that says "I'll play the strategy that does best against an average human being" will fail miserably when they are playing a rational person who knows that they will play this strategy.

Wait... what ? Changing the question ? Have you actually read the original question ?

Of course the problem is more interresting and disturbing when you consider perfectly rational actors, and that's what we are discussing about, but that is changing the question. The original problem has no statement about one of the actors being a perfectly rational player, it was implied by most people trying to answer this problem with pure logic. I totally agree with you on the fact that people coming here after 15 pages of discutions about rational actors, and simply saying that they should play the actual value of the antique or act as human being, are totally out of topic, but I don't think you can say that they changed the question.

[Jedaz]

I agree with all of the assumptions you listed but must insist on a rewording of the third one to more accurately reflect the truth: "both players know that both playing 100 is better than both playing 2 and would love to have that outcome if only it weren't an impossible outcome that lead directly to contradiction with their rationality". I didn't take away anything from the assumption or contradict either of the other assumptions so it is quite possible the assumptions you listed don't lead inexorably to the incorrect answer you insist they do.

Why do they have to play $2? I would think that those assumptions would be known by the two perfectly rational players. By knowing the first two they can rationaly conclude that in order to maximise their own individual profits they must play the move with the highest net gain for both players. In this case it is $100.

I understand that they would have to play $2 if they are following the nash equalibrium, but why should the players be bound by this if they can rationaly think of a move which benifits them better?

[Cithoge]

If that still doesn't convince you, why is it not rational to play $100 and let the opponent pick $99 if they are *always* going to play 1 lower then you? How could you hope to defeat such an opponent? Wouldn't a rational player take $97 over $2?

The opponent doesn't know what you'll pick, so he cannot play 1 lower than you - he can only play 1 lower than he believes you will play. And he knows that if he were to play 99, the best thing for you to do is to play 98, so he will undercut that, and eventually end up on 2. So if you play $100, you will walk away with $0. The only thing you can do about it is play $2.

I'm sure we can all agree that two rational players will always play the same number. I'm sure we can also agree that no rational player would play something that allows the other player to undercut him. Given these two facts it is easy to see that the only possible solution is $2.

One thing to keep in mind (and this has been touched upon earlier) is that a rational player won't pick whatever the other rational player happens to pick - the two players will independently reach the same conclusion. Just because you decide to stay at $100 doesn't mean the other player will.

[Goplat]

I'm sure we can all agree that two rational players will always play the same number. I'm sure we can also agree that no rational player would play something that allows the other player to undercut him.

Once you've established that both players must play the same number, it's impossible for either to ever undercut the other no matter what they pick.

One thing to keep in mind (and this has been touched upon earlier) is that a rational player won't pick whatever the other rational player happens to pick - the two players will independently reach the same conclusion. Just because you decide to stay at $100 doesn't mean the other player will.

The argument for $2 depends on each "rational" player making inferences about what the other "rational" player will do. "He won't pick $100, because that's irrational." "He won't pick $99: he knows that since I'm rational, I won't pick $100, so it would be irrational for him to pick $99" and so on. Why is this argument valid but the symmetry argument isn't?

[Cithoge]

Once you've established that both players must play the same number, it's impossible for either to ever undercut the other no matter what they pick.

Aye, but you can't just pick an arbitrary number and say that's what both rational players will play. There must be a chain of reasoning that leads them to play than number - one that both players will follow independently. Therefore one is free to try undercut the other, although you are right that neither will succeed. This is how they end up on 2.

Why is this argument valid but the symmetry argument isn't?

Picking 100 is not rational, as it leaves the player open to being undercut. Surely you agree playing (99,100) is better than playing (100,100)? Therefore neither rational player will play 100, as each knows the other player knows a counter-move. This is true for every other number too, except 2. That's why I struggle to see how two rational players playing each other could end up with anything other than (2,2).

[Goplat]

Therefore one is free to try undercut the other, although you are right that neither will succeed. This is how they end up on 2.

If you know you're going to fail at something, to your own detriment, it's rational to not try it.

Picking 100 is not rational, as it leaves the player open to being undercut. Surely you agree playing (99,100) is better than playing (100,100)? Therefore neither rational player will play 100, as each knows the other player knows a counter-move. This is true for every other number too, except 2. That's why I struggle to see how two rational players playing each other could end up with anything other than (2,2).

And you're right! The argument in favor of 2 is logically sound. But the problem is, the argument for 100 is as well. This is a contradiction - a proof that one of our premises (namely, that of "two rational players") is faulty. You can't have two rational players. Saying "both players are rational" in the Traveler's Dilemma is like saying "Let p/q = √2 where p and q are integers" or "Let S = the set of all sets not containing themselves". They may sound fine at first, but a bit of logic shows that such things cannot exist.

[Cithoge]

If you know you're going to fail at something, to your own detriment, it's rational to not try it.

But if you don't "try", the opponent will, and you will lose more. It is similar to the Prisoner's Dilemma - (cooperate, cooperate) is better for both than (defect, defect), but (defect, cooperate) is better for the individual who plays defect, so both will have to assume that the other will play it, and must therefore play it themselves. Even if you would prefer (100,100), this is not an option.

What, exactly, is the logically sound proof that (100, 100) is rational?

[Goplat]

But if you don't "try", the opponent will

Where would this asymmetry come from?

What, exactly, is the logically sound proof that (100, 100) is rational?

Both players are rational, so they have to end up playing the same thing. Of all possibilities that aren't eliminated by that fact - (2,2), (3,3), (4,4) on up to (100,100) - it's (100,100) that gives the highest payoff, so the rational player (which both of them are) must play 100.

[Cithoge]

But if you don't "try", the opponent will

Where would this asymmetry come from?

I'm not saying the players have to pick the same number, only that they will. There is a subtle but important distinction here. Think of it like this: Two people with similar tastes in food could walk into a restaurant and independently order the same thing. They don't have to, but they will. The fact that the players pick the same thing is not a rule - it is a result of the rules. The players are required to pick the best option, and (99, 100) is better than (100, 100). Therefore each player has to play 99 (re-evaluating once the get this far).

What, exactly, is the logically sound proof that (100, 100) is rational?

Both players are rational, so they have to end up playing the same thing. Of all possibilities that aren't eliminated by that fact - (2,2), (3,3), (4,4) on up to (100,100) - it's (100,100) that gives the highest payoff, so the rational player (which both of them are) must play 100.

But if you know your opponent is rational, you also know he won't play 100 (in fact, he will play 2), so in order to maximise your own payoff, you have to pick 2 too.

[Goplat]

I'm not saying the players have to pick the same number, only that they will. There is a subtle but important distinction here. Think of it like this: Two people with similar tastes in food could walk into a restaurant and independently order the same thing. They don't have to, but they will.

If it's a certainty that they will, then they do have to. That's what "have to" means.

But if you know your opponent is rational, you also know he won't play 100

You're using the same kind of reasoning about the opponent as I did. He's rational, so he has to act in a certain way.

[Cithoge]

If it's a certainty that they will, then they do have to. That's what "have to" means.

No, "have to" means that there is something forcing the players to act in a certain way (They have to pick a number between 2 and 100). "Will" means that it will occur, but could (theoretically) not have occurred (The players will never pick a sub-optimal number).

I realise this is a subtle distinction, and if drawn into a debate about the semantics of it, I may have to concede that someone will do something they have to. But the point I'm trying to make here is that rationality does not demand both players pick the same number (in non-symmetrical games, for instance, the two players can happily choose different strategies). Because this is a symmetrical game, however, the end result will be that both players will follow the same logical process and end up on the same number. Neither has chosen what the other player chose - they have both chosen the most rational strategy, which (since this is a symmetrical game) will be the same for both of them.

He's rational, so he has to act in a certain way.

Which includes not picking 100.

[Jedaz]

If that still doesn't convince you, why is it not rational to play $100 and let the opponent pick $99 if they are *always* going to play 1 lower then you? How could you hope to defeat such an opponent? Wouldn't a rational player take $97 over $2?

The opponent doesn't know what you'll pick, so he cannot play 1 lower than you - he can only play 1 lower than he believes you will play. And he knows that if he were to play 99, the best thing for you to do is to play 98, so he will undercut that, and eventually end up on 2. So if you play $100, you will walk away with $0. The only thing you can do about it is play $2.

Working on the above assumptions that I listed they are able to know what you will play, namely the following assumption provides this ability.
*Since they are both perfectly rational they can correctly determine their opponents stratergy with 100% accuracy.

I'm sure we can all agree that two rational players will always play the same number. I'm sure we can also agree that no rational player would play something that allows the other player to undercut him. Given these two facts it is easy to see that the only possible solution is $2.

I agree, however you are missing that additional logic step on why $100 is also a posible move (and makes much more sense). Let me recap on what I've said before.

1) Both players will come to the same conclusion.
2) Both players want to maximize their individual incomes.
3) Both players know that by going $100 they both receive more then going $2
4) Both players know the previous and know that their opponent knows, ect.
5) Because of #4 they know that going $100 is a safe move and that their opponent is unable to undercut them (#1), this also garuntees the maximum profit.

If you know there is symetry (ie: know that your opponent is going to play the same as you) then the most logical choice is to maximise the gain when playing on the line of symetry. #5 is the most important, they aren't playing a move which allows the opponent to undercut them because they know that their opponent can't under cut them because of the symetry.

One thing to keep in mind (and this has been touched upon earlier) is that a rational player won't pick whatever the other rational player happens to pick - the two players will independently reach the same conclusion. Just because you decide to stay at $100 doesn't mean the other player will.

I realize that, and I think I have logically shown why they both will pick $100.


Play a game of TD aginst yourself (ie: two players with identical reasoning). You want to maximize your own profit. You know the stratergy your opponent (yourself) will pick and be able to predict what they will go. What is the best move?

This is the same situation as two perfectly rational players as they know that the other has the exact same reasoning as the other.

[Cithoge]

If you know there is symetry (ie: know that your opponent is going to play the same as you) then the most logical choice is to maximise the gain when playing on the line of symetry. #5 is the most important, they aren't playing a move which allows the opponent to undercut them because they know that their opponent can't under cut them because of the symetry.

I think you are still confusing axiomatic rules with inevitable conclusions. Try inverting the bold above to see what I mean. You opponent doesn't have to play what you play any more than you have to play what s/he plays (which you have no way of knowing). Pretend we have both (independently) arrived at (2,2). Now you have to play what I'm going to play. What is it?

I think that makes it more clear - it is not what the other player plays that determines your choice - it is your reasoning. You might as well pick an arbitrary number and expect your opponent to pick the same because you "will both play the same number".

[Puck]

We've covered all this ground, but I realize that this thread is ridiculously long, so I'm going to go over the important stuff.

The "proof" for 100 goes like this:
- Both players must play the same number
- Therefore we can consider only this space
- Of choices where both players pick the same number, (100, 100) is the best

However, this argument is invalid because it fails to examine the choices to see if there is another reason why they might be irrational.

Consider the following:

If a rational player knows with certainty that his opponent will play 100, then he will respond with 99.
A rational player, playing against a known rational opponent, will arrive at the same play as his opponent.
A rational player knows what his rational opponent will play.

Do you see the contradiction? A rational player cannot play 100, because if he did, he would know his opponent was also playing 100; but if a rational player knows his opponent is playing 100, then he must play 99.

[Jedaz]

If you know there is symetry (ie: know that your opponent is going to play the same as you) then the most logical choice is to maximise the gain when playing on the line of symetry. #5 is the most important, they aren't playing a move which allows the opponent to undercut them because they know that their opponent can't under cut them because of the symetry.

I think you are still confusing axiomatic rules with inevitable conclusions. Try inverting the bold above to see what I mean. You opponent doesn't have to play what you play any more than you have to play what s/he plays (which you have no way of knowing). Pretend we have both (independently) arrived at (2,2). Now you have to play what I'm going to play. What is it?

I think that makes it more clear - it is not what the other player plays that determines your choice - it is your reasoning. You might as well pick an arbitrary number and expect your opponent to pick the same because you "will both play the same number".

You are right, it's the reasoning that determines the choice, and two perfectly rational players implys that their reasoning is identical (I'll conceed if this is not true). If the reasoning is not the same then it means one player is not perfectly rational. Therefore the players realize that their moves are always going to be the same (because of the identical rationality) as long as they rationaly come to a conclusion. As of such rather then picking an arbitary number they chose the number which benifits the both of them the most ($100, which is rational when you know the opponent thinks exactly the same as you).

We've covered all this ground, but I realize that this thread is ridiculously long, so I'm going to go over the important stuff.

The "proof" for 100 goes like this:
- Both players must play the same number
- Therefore we can consider only this space
- Of choices where both players pick the same number, (100, 100) is the best

However, this argument is invalid because it fails to examine the choices to see if there is another reason why they might be irrational.

Consider the following:

If a rational player knows with certainty that his opponent will play 100, then he will respond with 99.
A rational player, playing against a known rational opponent, will arrive at the same play as his opponent.
A rational player knows what his rational opponent will play.

Do you see the contradiction? A rational player cannot play 100, because if he did, he would know his opponent was also playing 100; but if a rational player knows his opponent is playing 100, then he must play 99.

No, I see an error in your logic. I agree with the premis of the proof (abeit it is lacking nessecary detail). However let's look at your following logic.

If a rational player knows with certainty that his opponent will play 100, then he will respond with 99.
This is your error. Yes, it's true, they will respond with x-1 if posible. However that move is invalid, the logical player will know that the move {x-1,x} doesn't exist in this situation (see my response to Cithoge as to why). The only moves that exist are on the move set of {x,x}, and thus by playing 99 they have just tried to play a move that doesn't exist {99,100}. To make it clearer as to what I mean clear consider the following.

Player A and B are currently playing {100,100}, they are both perfectly rational and know that the other person is and so on.
A knows that if they are able to play {99,100} they can achive a better result then playing {100,100}
A also knows that since B has identical reasoning they will also consider the previous play.
A knows that B will reach the same conclusion due to their rational being identical, as of such if A decides to try and play {99,100} they effectively play {99,99}
A concludes that playing {100,100} is better then playing {99,99}

[Cithoge]

You are right, it's the reasoning that determines the choice, and two perfectly rational players implys that their reasoning is identical (I'll conceed if this is not true). If the reasoning is not the same then it means one player is not perfectly rational. Therefore the players realize that their moves are always going to be the same (because of the identical rationality) as long as they rationaly come to a conclusion. As of such rather then picking an arbitary number they chose the number which benifits the both of them the most ($100, which is rational when you know the opponent thinks exactly the same as you).

But (99, 100) is a possible outcome, because staying at 100 is irrational when the opponent can play 99. Therefore the player who picks 100 is no longer being rational, and the symmetry is broken.