- 01 Mar '11 00:04A 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. - 01 Mar '11 10:13With 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. - 01 Mar '11 17:06

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?*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.

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? - 01 Mar '11 17:32

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.*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?** - 01 Mar '11 20:21

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.*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.** - 02 Mar '11 21:20 / 1 edit

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" ).*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?

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. - 03 Mar '11 01:47

This depends on whether stopping leaves you as a potential winner. It wasn't specified.*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. - 03 Mar '11 15:17 / 1 edit

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.*Originally posted by JS357***This depends on whether stopping leaves you as a potential winner. It wasn't specified.**

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. - 03 Mar '11 17:48

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.*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.

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. - 03 Mar '11 21:16 / 1 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. - 03 Mar '11 21:41

You definitely need to read up on mixed strategies buddy.*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. - 04 Mar '11 05:35

That's why I said,*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]

"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? - 04 Mar '11 07:05mtthw'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.