5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Are there any guarantees about the number of red hats or green hats? Are they allowed to make a strategy ahead of time, or does the strategy have to rely solely on them all being perfect logicians (and knowing the other three are also perfect logicians)? $\endgroup$ – DqwertyC Aug 30 '17 at 16:09
  • 1
    $\begingroup$ Without a guarantee, I don't think there is a strategy. For example, if I see 3 green, I cannot infer my hat is red if there isn't a guarantee of at least one red hat. Other people passing will never help me know my own hat colour. $\endgroup$ – Trenin Aug 30 '17 at 16:16
  • $\begingroup$ I know that this is sort-of standard, but you really should say whether each contestant can see the colors of the hats of the other three contestants. $\endgroup$ – Peregrine Rook Aug 31 '17 at 5:14
  • $\begingroup$ Has a correct answer been given? If so, please don't forget to $\color{green}{\checkmark \small\text{Accept}}$ it. If not, some responses to the answerers to help steer them in the right direction would be helpful. $\endgroup$ – Rubio Sep 5 '17 at 5:07
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You should be able to get only one combination fail. $\endgroup$ – Acccumulation Aug 30 '17 at 19:08
  • $\begingroup$ My first answer is vague and needs rewriting, but I think my second beats this: given that a single loss arrangement loses you over $60,000, a solution with one loss will basically always beat one with two. I'll edit some maths into my second post (the first needs a more thorough edit). $\endgroup$ – BlueHairedMeerkat Aug 30 '17 at 19:10
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "Next round, B passes (-4), then A sees B in red, and signals this by passing (-6)." You're phrasing it as A acting after B. So does A pass first in the second round, then B passes, then A passes again in the third round? $\endgroup$ – Acccumulation Aug 30 '17 at 19:09
  • $\begingroup$ Massive rewrite, with a slightly improved algorithm. $\endgroup$ – BlueHairedMeerkat Aug 31 '17 at 10:36
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This answer would be improved if you say how much the expected earnings are. $\endgroup$ – ffao Aug 30 '17 at 22:11
  • $\begingroup$ Your algorithm is not accurate. Take for example RRRG. A, B, C will pass. D will announce Green. A will announce Green and lose. $\endgroup$ – LeppyR64 Aug 31 '17 at 14:53
  • $\begingroup$ @LeppyR64 that was just an order mistake, if the player before A has already guessed, A should guess red regardless of the number of red hats A sees. I'll fix that. $\endgroup$ – MMAdams Aug 31 '17 at 16:52
  • $\begingroup$ Now it's broken by GGRR. A,B,C,D pass. A picks Green, B picks Red and loses. Sorry :) $\endgroup$ – LeppyR64 Aug 31 '17 at 17:25
  • $\begingroup$ @LeppyR64 Leppy, you're killing me. jk, i'll word it better so this doesn't happen. $\endgroup$ – MMAdams Aug 31 '17 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.