#### Posers and Puzzles

wolfgang59
Posers and Puzzles 01 Mar '11 00:04
1. wolfgang59
01 Mar '11 00:04
A simple game.
You toss a coin.
If its HEADS you get \$1 and may toss again or "stick" on your total money.
If its TAILS you lose all your money and its GAME OVER.

You are competing against another player in another room (ie neither of you knows when the other "sticks"ðŸ˜‰

What is your best strategy? Is it stick after 1 head? 2? or more?

What about a 3 player game?

What about an N player game?

NOTE:
In ALL cases you are playing to beat your opponents not necessarily optimise your winnings.
2. 01 Mar '11 10:13
With one player, I don't think you can do better than sticking at 1.

Let's say opponent sticks at N. (1/2)^N chance they end up with N, 1 - (1/2)^N chance they end up with nothing. Let's say I stick at M.

If N >= M:
P(I win) = P(I get M and he gets nothing) = (1/2)^M[1 - (1/2)^N]

If N < M:
P(I win) = P(I get M) = (1/2)^M

Whatever the value of N, this is maximised by M = 1.

Multi-player gets much more complex, though, by the look of it.
3. 01 Mar '11 17:06
Originally posted by wolfgang59
A simple game.
You toss a coin.
If its HEADS you get \$1 and may toss again or "stick" on your total money.
If its TAILS you lose all your money and its GAME OVER.

You are competing against another player in another room (ie neither of you knows when the other "sticks"ðŸ˜‰

What is your best strategy? Is it stick after 1 head? 2? or more?

What abou ...[text shortened]...
In ALL cases you are playing to beat your opponents not necessarily optimise your winnings.
Presumably the game is over when everyone has stuck or flipped TAILS, except one person, who is told to stop and is declared the winner (he won't know he is the winner). Right?

Also presumably, if at some point there is more than one player left and they stick on the same turn, there is nobody left and no winner. Right? (But see footnote.**)

Then whatever the probability/expected value calculations are, all players who base their decision on the same calculations will stick on the same turn and there will be no winner. So the rational player will take a chance and wait till the NEXT turn. But all of them, if rational, will do the same thing. So the rational player will wait until the NEXT NEXT turn. And so on.**

The rational outcome is, the game doesn't end with a winner.

**If the last players to stick on a turn when there are more than one left are declared the winners, does that change the rational player's decision?
4. 01 Mar '11 17:32
Originally posted by JS357
Presumably the game is over when everyone has stuck or flipped TAILS, except one person, who is told to stop and is declared the winner (he won't know he is the winner). Right?
That's not how I interpreted it. I'd have thought each player keeps going until they either flip tails or stick. Then when everybody has finished they are told the result.
5. 01 Mar '11 20:21
Originally posted by mtthw
That's not how I interpreted it. I'd have thought each player keeps going until they either flip tails or stick. Then when everybody has finished they are told the result.
Yes, it is open to that interpretation, too. The question then is, if person A was the last one left and then he flipped tails, would he still be the winner? Or would he have to leave the game by sticking, to win? I think our interpretations of what it takes to win differ, but both are reasonable and both make for a puzzle to be solved.
6. Palynka
Upward Spiral
02 Mar '11 21:201 edit
Originally posted by JS357
Presumably the game is over when everyone has stuck or flipped TAILS, except one person, who is told to stop and is declared the winner (he won't know he is the winner). Right?

Also presumably, if at some point there is more than one player left and they stick on the same turn, there is nobody left and no winner. Right? (But see footnote.**)

Then whateve more than one left are declared the winners, does that change the rational player's decision?
No, that's not a "rational outcome" in the sense that it is not a Nash equilibrium. If people keep on going and you know this, then you have the incentive to stop at the first turn (being "rational" ).

The Nash equilibrium will feature mixed strategies where you stop at the first turn with a certain probability (p1), at second one with probability p2 and so on.
7. 03 Mar '11 01:47
Originally posted by Palynka
No, that's not a "rational outcome" in the sense that it is not a Nash equilibrium. If people keep on going and you know this, then you have the incentive to stop at the first turn (being "rational" ).

The Nash equilibrium will feature mixed strategies where you stop at the first turn with a certain probability (p1), at second one with probability p2 and so on.
This depends on whether stopping leaves you as a potential winner. It wasn't specified.
8. Palynka
Upward Spiral
03 Mar '11 13:21
Originally posted by JS357
This depends on whether stopping leaves you as a potential winner. It wasn't specified.
It wasn't specified? What do you mean?
9. forkedknight
Defend the Universe
03 Mar '11 15:171 edit
Originally posted by JS357
This depends on whether stopping leaves you as a potential winner. It wasn't specified.
Of course you can win if you stop. I would assume you *have* to stop in order to win. You could flip ten heads in a row, but if you chose to flip again and flip a tails, you would lose.

Compare this to a single opponent, who flipped head once and stuck, who would win.

Otherwise the game makes no sense, it would just be, "flip until you flip a tails, and whoever happens to get the most heads in a row (by chance) wins". That's not a "game" as far as game theory is concerned.
10. 03 Mar '11 17:48
Originally posted by forkedknight
Of course you can win if you stop. I would assume you *have* to stop in order to win. You could flip ten heads in a row, but if you chose to flip again and flip a tails, you would lose.

Compare this to a single opponent, who flipped head once and stuck, who would win.

Otherwise the game makes no sense, it would just be, "flip until you flip a ta ...[text shortened]... heads in a row (by chance) wins". That's not a "game" as far as game theory is concerned.
Yes, the winner is whoever is the last to flip heads, there is no rationally optimal turn on which to stop. But if the winner is whoever is the last to stop, there is still no rationally optimal turn on which to stop.

Why?

Assume all players are rational optimizers: Suppose your first-pass rational analysis shows the best turn on which to stop is turn N. (It could be "ASAP."ðŸ˜‰ For all rational optimizers, the first-pass answer is the same: turn N. You know this. So you realize that if everyone uses use their first-pass answer, everyone will stop at once and there will be no winner.

So in this situation, you realize that you should take a chance and stop at turn N+1 if you survive the flip at turn N. This is your second-pass answer.

But then you realize that everyone else will realize this too, so will come up with the same answer, to stop at turn N+1 if they survive turn N.

So you, and everybody, will decide to stop on turn N+2, no, N+3, no,... etc. So everyone stays in the game until each of you flips a tail. No winner.

Aha! Now you know. Go back to the plan to stop at turn N. But everybody, being rational optimizers, will do that.:'(

If there are irrational optimizers in the game, one of them will probably win. ðŸ™‚
11. 03 Mar '11 21:161 edit
Originally posted by JS357
Yes, the winner is whoever is the last to flip heads, there is no rationally optimal turn on which to stop. But if the winner is whoever is the last to stop, there is still no rationally optimal turn on which to stop.

Why?

Assume all players are rational optimizers: Suppose your first-pass rational analysis shows the best turn on which to stop is turn N. that.:'(

If there are irrational optimizers in the game, one of them will probably win. ðŸ™‚
For all rational optimizers, the first-pass answer is the same: turn N. You know this. So you realize that if everyone uses use their first-pass answer, everyone will stop at once and there will be no winner.

No, I don't see how that follows. Even if one were to suppose that both players have full intention of following the same "first-pass" rule, which is further supposed to be uniform for all rational players (such as stop after N heads or ASAP or whatever), it certainly does not follow that one should thereby think both players will fufill the condition of the rule and then there will be no winner.** As a trivial counterexample, your opponent (or you) can flip a tail right out of the starting gate, completely regardless of what optimization rule there is intent to follow.

I do not think your argument justifies your thesis (which was: if the winner is whoever is the last to stop, there is still no rationally optimal turn on which to stop).

I think there would still be a rational plan to follow, like the mixed strategies plan that Palynka mentioned.

**It also doesn't follow that one should think he will not win if he stops in accordance with his optimization rule -- although, I would think that, on average, one rational player could expect to do no better than any other rational player in this sort of game.
12. Palynka
Upward Spiral
03 Mar '11 21:41
Originally posted by JS357
Yes, the winner is whoever is the last to flip heads, there is no rationally optimal turn on which to stop. But if the winner is whoever is the last to stop, there is still no rationally optimal turn on which to stop.

Why?

Assume all players are rational optimizers: Suppose your first-pass rational analysis shows the best turn on which to stop is turn N. ...[text shortened]... that.:'(

If there are irrational optimizers in the game, one of them will probably win. ðŸ™‚
You definitely need to read up on mixed strategies buddy.
13. 04 Mar '11 03:57
Originally posted by Palynka
You definitely need to read up on mixed strategies buddy.
Could you be less specific?
14. 04 Mar '11 05:35
Originally posted by LemonJello
[b]For all rational optimizers, the first-pass answer is the same: turn N. You know this. So you realize that if everyone uses use their first-pass answer, everyone will stop at once and there will be no winner.

No, I don't see how that follows. Even if one were to suppose that both players have full intention of following the same "first-pass" ru ...[text shortened]... nal player could expect to do no better than any other rational player in this sort of game.[/b]
That's why I said,
"If there are irrational optimizers in the game, one of them will probably win."
Flipping a coin would satisfy this "if".
Is there another better mixed strategy?
15. wolfgang59
04 Mar '11 07:05
mtthw's interpretation of the game is correct. You cannot win if you toss a tail .. its all about how far you go.

My thinking was stick after a single head (but I'm not 100% sure)

I dont think this is a"mixed strategy" solution since I allow draws.

I do not have a clue what the solution is for 3 players. Thats the real challenge.