Four hats and penalty for passing

Question

There are four contestants, each with a red or green hat. They start with a prize pool of one million dollars. They take turns either guessing their hat color or passing. If anyone guesses incorrectly, the game is over and they win no money. If the first person to guess their hat color has a red hat, 100 dollars are subtracted from the prize money. If someone with a red hat passes, one dollar is subtracted from the prize money. If someone with a green hat passes, a number of dollars equal to the number of contestants with green hats is subtracted from the prize money. If all four correctly guess their hat color, the prize pool is distributed among the contestants. What strategy maximizes expected winnings if:

A. They go in the same order each round

B. Each round, each gets one turn, but they don't know what order ahead of time

?

[The contestants don't know their own hat color, or how much has been subtracted from the prize pool during the game, they are perfectly rational and know the others are perfectly rational, etc., etc.]

Answer 1

Sorry to add a second answer, but I've spotted another method that may have been your intent: assume at least one green hat, and then if you see n green hats, guess green in the n+1th round! (This is a variation on the blue eyed islander problem).

RRRR: 1st sees no green, guesses green, loses 1000000. RRRG: 1.5 reds pass, the green guesses green, then all the reds guess red. Loses 1.5 on average. RRGG: Everyone passes. Then 2/3 of a red passes, then everyone guesses correctly. Loses 6 2/3. RGGG: Everyone passes. Then, everyone passes. Then 1/4 of a red passes, then everyone guesses correctly. Loses 20 1/4. GGGG: Everyone passes, thrice. Then they all guess green. Loses 48.

Average loss is 62511, so average winnings of 937489.

Answer 2

Since Curtis' answer is either vague and I'm misunderstanding it or incorrect altogether (and I also don't have the rep here to comment at him), here's a precise strategy with a completely order-agnostic expected value of $874,971:

Round 1:
Guess green if you see all red,
Guess red if the first person to guess guessed green,
Guess red if you see all green,
Guess green if the first person to guess guessed red,
Pass otherwise.

GRRR, RGRR, RRGR, RRRG, RGGG, GRGG, GGRG, GGGR succeed
RRRR, GGGG fail

Rounds 2 and 3 if necessary:
Continue round 1 logic and collect winnings if someone has already guessed.
If everyone passed in round 1, we know there are two red and two green hats.
Guess the lesser-represented hat unless it's red and you'd be the first to guess.

GGRR, GRGR, GRRG, RGGR, RGRG, RRGG succeed

Answer 3

So we're going to have to do some guessing. After all, if we all pass until we know our hat colour, then we have no way to give information, and thus can never find out our hat colour. Hence, we've got a chance of walking away with nothing. Once we accept that, our goal is first to minimise the number of configurations that lead to that end, then minimise the amount of passing required for that.

So let's try this strategy:

• Label them A,B,C and D based on their first round order.
• First round: if A sees three reds, she guesses green and all others guess red. Else, she passes. Then B,C and D know that one of them is green; B and C guess if they're the last green (IE if no greens are after them this round), and C guesses red if B guessed green. In this way, D knows his hat colour; he guesses if A wears green; else he passes.
• We now have one or two signallers (A and D, who know their hat colour) and up to two guessers (B and C). When it is a signaller's turn, they will signal a guesser (preferably one who has not gone this round, and then preferably B) by guessing if the guesser wears green and passing otherwise. (Note that with one signaller and two guessers, the first guesser to become a signaller may have to signal the second.)

To calculate the expected winnings, we first look at the possible second rounds, as they're going to repeat a lot:

• A, AD: just guess, 0 loss.
• AB: B passes 1/2 the time, A passes if B wears red.
• ABC: A passes 5/6 if B red, 1/6 if C red, 1/6 if both; B 1/2, 5/6 if C red, -1/6 if both; C 5/6, 1/9 if B red.
• ABD: A and D pass 1/2 if B red, B passes 1/3.
• ABCD: A and D pass 5/12 if B red, 11/24 if C red; B 7/24, 1/6 if C red; C 1/2, 1/12 if B red.

So now:

• RRRR: Lose 1m.
• GRRR: Perfect, loses 0.
• RGRR: Goes to AD, loses 2.
• RRGR: Goes to ABD, loses 4 1/3.
• RRRG: Goes to ABCD, loses 5 11/12.
• GGRR: Goes to A, loses 2.
• GRGR: Goes to AB, loses 5 1/2.
• GRRG: Goes to ABC, loses 8 4/9.
• RGGR: Goes to ABD, loses 4 2/3.
• RGRG: Goes to ABCD, loses 9 1/8.
• RRGG: Goes to ABCD, loses 8 17/24
• GGGR: Goes to AB, loses 7 1/2.
• GGRG: Goes to ABC, loses 12 1/3.
• GRGG: Goes to ABC, loses 12 5/6.
• RGGG: Goes to ABCD, loses 12 3/8.
• GGGG: Goes to ABC, loses 17 1/3.

That gives a total loss of 1m + 113 5/72, an average loss of 62507 77/1152, and thus winnings of a little under $937493.

This algorithm only fails in one case (all red), which I believe is optimal, takes few rounds to resolve, and always has a green guess first, so if it isn't optimal it's damn near.

Answer 4

Okay, so maybe there were some flaws in my psuedocode, and I'll rework it, but here's the basic idea.

You want a green player to guess first, otherwise you lose 100 dollars. So the question is, how soon can a player definitely know they are wearing a green hat?

If she see three red hats, she knows immediately (or rather, she doesn't know, but there's a 50/50 shot, and we need to make a guess somewhere, so this is the case where we guess).

If she see two red hats, and the person with the green hat has already passed in the first round (he didn't know for sure he was green, so therefore, he didn't see three red hats) she knows for sure she's green.

If she sees only one red hat, and the two green hatted people both passed in previous rounds (didn't know for sure they were green) she can conclude she must be a green hat. (this is the 'last player in the round' clause I was trying to make work before).

I drew up a flow chart for this I need to test through, but I think it does work.