3 heroes with hats vs a villain

[rigwarl]

There are 3 heroes standing in a circle, and each has either a red or a blue hat. The heroes can't see their own hats, but can see each others'. All 3 are given a strip of paper and a pen, and simultaneously write "red", "blue", or "abstain". Nobody can see what the other people are writing, or convey information in any other way. The heroes win if and only if at least one person guesses his own hat color, and nobody guesses wrong.

The heroes can come up with a strategy beforehand, but the villain must also be informed of the strategy and he places the hats to minimize the heroes' chances of winning. What is the best strategy for the heroes?

My thoughts:

Spoiler:

You can get at least 50% by having a designated guesser randomly choose. I don't see how you can get better than that, but I'm told the solution is greater than 50%.

Sorry if it's been done before, I searched and only found this similar one but it doesn't have the villain: viewtopic.php?f=3&t=1722. JR you can move it if you see fit (thanks for being an awesome moderator).

[Tirian]

I suspect that the person who told you that you can do better than 50% is not realizing that the villain is allowed to foil your plans. If the hats are chosen randomly, you can do significantly better, though.

[rigwarl]

The specific difference in this problem is that there is a villain trying to mess you up. I honestly don't see how you can get more than 50% but the person who gave me the problem is pretty smart and said you can do better, I spent all day thinking about it and am convinced otherwise so I posted it here =)

[xkcdfan]

Does the villain have to be informed honestly of the strategy?

[GreedyAlgorithm]

Does the villain have to be informed honestly of the strategy?

Um, yes? "our strategy is Alice will guess red", then Alice guesses blue.

[ConMan]

Generally the "villain" is put in to confirm that you're looking not at an average result but at a worst-case one. So if your strategy was "When I see two different colours of hat I'll abstain, otherwise I'll guess the colour I don't see", then the worst-case is that all the hats are the same colour - so your villain is guaranteed to pick that situation.

That said, I'm still not sure of the best strategy, but I'm working on it.

[Qaanol]

I don’t have a solution yet, but here is a restatement of the problem in mathematical terms:

Spoiler:

Assuming a strategy for each player must be of the form “If I see the other two people (in dictionary order) have hat colors (x, y), then I will guess red with probability pr(x, y), I will guess blue with probability pb(x, y), and I will abstain the rest of the time” (and assuming I didn’t make any typos) the problem is equivalent to the following:

Do there exist 24 non-negative real numbers, called {ABC}{1-8}, satisfying the following 20 inequalities?

1 >= A1 + A2
1 >= A3 + A4
1 >= A5 + A6
1 >= A7 + A8
1 >= B1 + B2
1 >= B3 + B4
1 >= B5 + B6
1 >= B7 + B8
1 >= C1 + C2
1 >= C3 + C4
1 >= C5 + C6
1 >= C7 + C8

0.5 < (A1)(1-B2)(1-C2) + (1-A1-A2)(B1)(1-C2) + (1-A1-A2)(1-B1-B2)(C1)
0.5 < (A3)(1-B4)(1-C1) + (1-A3-A4)(B3)(1-C1) + (1-A3-A4)(1-B3-B4)(C2)
0.5 < (A5)(1-B1)(1-C4) + (1-A5-A6)(B2)(1-C4) + (1-A5-A6)(1-B1-B2)(C3)
0.5 < (A7)(1-B3)(1-C3) + (1-A7-A8)(B4)(1-C3) + (1-A7-A8)(1-B3-B4)(C4)
0.5 < (A2)(1-B6)(1-C6) + (1-A1-A2)(B5)(1-C6) + (1-A1-A2)(1-B5-B6)(C5)
0.5 < (A4)(1-B8)(1-C5) + (1-A3-A4)(B7)(1-C5) + (1-A3-A4)(1-B7-B8)(C6)
0.5 < (A6)(1-B5)(1-C8) + (1-A5-A6)(B6)(1-C8) + (1-A5-A6)(1-B5-B6)(C7)
0.5 < (A8)(1-B7)(1-C7) + (1-A7-A8)(B8)(1-C7) + (1-A7-A8)(1-B7-B8)(C8)

These can be interpreted as:
X1: probability for player X to guess Red when seeing (Red, Red)
X2: probability for player X to guess Blue when seeing (Red, Red)
X3: probability for player X to guess Red when seeing (Red, Blue)
X4: probability for player X to guess Blue when seeing (Red, Blue)
X5: probability for player X to guess Red when seeing (Blue, Red)
X6: probability for player X to guess Blue when seeing (Blue, Red)
X7: probability for player X to guess Red when seeing (Blue, Blue)
X8: probability for player X to guess Blue when seeing (Blue, Blue)

Also, I’m pretty sure that if a solution does exist, then a solution exists with all rational numbers. That comes from a continuity argument and the fact that at least one of the inequalities is strict.

[taggedjc]

Here's my work on it:

Spoiler:

If Person#1 votes a color, he has to be correct in order to survive (if he is incorrect, he loses). Since the villain can choose to put either Red or Blue on his head, he will choose to put the color most likely to cause the heroes to lose - so the hero must choose between red or blue with equal probability, since if he chose Red 60% of the time, for example, the villain would ensure a Blue hat was on his head. If he abstains, he doesn't change the outcome at all, but at least one person will have to vote a color, since three abstains will lose for certainty. Let's let Person#1 be the first person to actually choose a color, then see what the other two should do.
Now, if Person#2 votes a color, he also has to be correct in order to survive. However, since Person#1 will already be voting for a color, choosing to abstain will not affect the outcome at all - if Person#1 is correct, they survive regardless. Likewise, if Person#1 is incorrect, they all lose regardless. So the optimal strategy for Person#2 is to abstain. This is the same strategy as Person#3.

So they will survive 50% of the time.

And actually, if the hats are distributed randomly, I don't think you can get much better than 50% either, since each person's hat is chosen without regards to the other hats and there is no way to convey any information to the other heros except the color of your own hat. Thus, you are guessing entirely based on seeing two other hats that have no relationship to your own hat whatsoever. Thus, if more than one person guesses a color, it is much rarer for them to both be correct.
For example, if the first two people vote Blue (or one votes Red and one votes Blue) and one abstains, then only 2 of the 8 permutations will be correct. However, if that first person votes Blue and the next two abstain, 4 of the 8 permutations will be correct.
Let's look at a quick example. Let's say a possible guess is wrong because of Person#1's response. Perhaps they voted Blue and it was supposed to be Red. Well, anything you could do that would make this situation more likely to be correct would inversely cause the opposite situation to be more likely to be incorrect. If the arrangement is RRB, and #1 voted B, then they were wrong. However, if they instead vote R in that situation, then they will get BRB wrong instead (which they would have been correct on otherwise)... The only time where it would become more likely to be correct by changing an abstain vote to red/blue is if all three people are abstaining, in which case I believe your strategy is already suboptimal. Compare "Vote Red if you see exactly one red hat, otherwise abstain" which is successful in 2/8 cases with "Vote Red if you see exactly one red hat, otherwise abstain unless you're Person#1 in which case vote the color of the hats you do see" which is successful in 4/8 cases as it avoids the two losses that occur from all three people abstaining).

Interesting that a complicated strategy as that one succeeds just as often as "Person#1 chooses blue, the other two abstain".

Actually, reading the other topic on this was interesting, so it looks like the random distribution can be better than 50%. However, I don't see how the worst-case-scenario could be better than 50%... still, I'll read a bit more about it and see if I can puzzle out more of it My musings certainly don't "prove" anything.

[Gwydion]

If the hats are chosen randomly, there's a way to do significantly better than 50%:

Spoiler:

If one sees two hats of the same color, guess the other color; otherwise abstain. In this case, each individual abstains in 4/8 cases, guesses right in 2/8, and guesses wrong in 2/8, but they all guess wrong on the same 2/8 instances, leaving a winning percentage of 75% overall.

In the case of the villain, any deterministic strategy (person X chooses red, either all the time or based on person Y/Z's hats) is doomed to fail. Any asymmetric mixed strategy (more likely to choose red than blue when not abstaining) can be exploited as well - if person X is more likely to choose red, he will always wear a blue hat - when he votes, he is more likely to hurt the team than help, and when he abstains he does not help the team win. This leaves a symmetric mixed strategy - decide whether to vote or not, and if voting, flip a coin. Since the voting is simultaneous and without communication, the best case strategy is 50% because the villain can and will exploit any deviation from 50/50 to his advantage.

[Qaanol]

Any asymmetric mixed strategy (more likely to choose red than blue when not abstaining) can be exploited as well - if person X is more likely to choose red, he will always wear a blue hat - when he votes, he is more likely to hurt the team than help, and when he abstains he does not help the team win.

You’ve left out the most general case: “Dynamic strategies”.

That is where each individual chooses among all options, with probabilities that varies depending on what hats the other two are wearing. Now we cannot immediately rule out asymmetric strategies (where in some situations some person might be more likely to guess red than blue, for instance), because the probabilities of each guess for each person depend on the hats of all the other people.

If the villain changes one person’s hat to make them less likely to be right, the other two people now see different hats and could make different decisions with different probabilities. And if the villain changes those other people’s has, the first person sees something different and could make different decisions.

How about we look at some simpler cases?

1. If the three people all use identical strategies, and those strategies do not consider the other people’s hats (so everyone is guessing blind) what are the highest odds they can have of beating the villain in the worst case?

Spoiler:

(9+4√2)/49 ≈ 29.9%, achieved by abstaining (1+2√2)/7 ≈ 54.7% of the time, and the rest of the time guessing red or blue with equal likelihood, which is (3-√2)/7 ≈ 22.65% each.

2. If the three people are allowed to use different strategies, but still guess blind, what is the best they can do in the worst case?

Spoiler:

50%, by having a dedicated guesser.

3. If the people must use identical strategies, but can use the information (hats colors) they see as part of that strategy, what is the best they can do in the worst case?

[Goplat]

I'm pretty sure it's impossible for any strategy to do better than 50%. My reasoning:

Spoiler:

If hero X has probability p of making a correct guess in a certain hat setup, then in the setup where X's hat has changed and the other two stay the same, X has probability p of making a wrong guess. So the sum, over all hat setups, of the expected numbers of correct guesses is equal to the sum of the expected numbers of wrong guesses. For this to be true there must exist at least one setup where E[wrong guesses] >= E[correct guesses].

Since given a particular hat setup, the heroes' choices are independent of each other, there's no way to get the wrong guesses correlated together like there is in the non-adversarial case.

[skeptical scientist]

I'm pretty sure it's impossible for any strategy to do better than 50%. My reasoning:

Spoiler:

If hero X has probability p of making a correct guess in a certain hat setup, then in the setup where X's hat has changed and the other two stay the same, X has probability p of making a wrong guess. So the sum, over all hat setups, of the expected numbers of correct guesses is equal to the sum of the expected numbers of wrong guesses. For this to be true there must exist at least one setup where E[wrong guesses] >= E[correct guesses].

Since given a particular hat setup, the heroes' choices are independent of each other, there's no way to get the wrong guesses correlated together like there is in the non-adversarial case.

Spoiler:

Even given your last line, the probability of a correct guess could still be greater than the probability of an incorrect guess, e.g. in a situation where A guesses correct, and B/C each guess incorrectly 2/3 of the time, and otherwise don't guess. The expected number of incorrect guesses is 4/3>1, but the chance of an incorrect guess is 8/9<1.

Can you show that if E(wrong guesses) ≥ E(correct guesses), and guesses are independent, then p(correct guess and no wrong guess)≤1/2?

[Goplat]

Spoiler:

Even given your last line, the probability of a correct guess could still be greater than the probability of an incorrect guess, e.g. in a situation where A guesses correct, and B/C each guess incorrectly 2/3 of the time, and otherwise don't guess. The expected number of incorrect guesses is 4/3>1, but the chance of an incorrect guess is 8/9<1.

Can you show that if E(wrong guesses) ≥ E(correct guesses), and guesses are independent, then p(correct guess and no wrong guess)≤1/2?

Spoiler:

I haven't been able to prove it, but a search of the entire strategy space for a single hat setup (6 parameters to represent the probability of guessing right/wrong/abstain for A, B, and C) in 1/64 unit increments shows no counterexamples.

[Qaanol]

Matlab’s minimax constrained optimization finds, for the general problem, the local minimum with all people guessing symmetrically and blindly that I mentioned above. I did not do a comprehensive search of the parameter space to check for other minima, but I’m not convinced there are non-trivial solutions.

Edit:

4. Suppose there will definitely be at least 2 red hats, and everyone knows this. What is the best the heroes can do in the worst case?

Spoiler:

It’s 1 - x, where x is a root of x^3 - 3x^2 + 4x -1 = 0, near x ≈ 0.317672, giving a value approximately 68.2%. Here x is the probability of guessing Red when seeing 2 other Red hats, which optimizes the worst case at about x ≈ 31.8%.

5. Suppose there will definitely be at least 1 red hat, and everyone knows this. What is the best the heroes can do in the worst case?

[taggedjc]

Spoiler:

I've made a spreadsheet that calculates the chances of failure for each hat combination for each strategy for each player (eg: if playerX sees colorY on my left and colorZ on his right, he will vote Red/Blue/Abstain p/q/r% of the time). Running a few solver routines seem to come up with nothing that gets lower than 50% failure rate like the one we figured out earlier.

It also pretty easily comes up with the optimal solution for the strategies for merely average success rates (instead of the minimum success rate, as would be the case with a villain) as well, so my guess is that 50% is our bound.

[Giallo]

Kinda easy:

Number the heroes from 1 to 3. Now the hero 1 writes the color of the hat of the hero 2, the hero 2 of the hero 3 and the hero 3 of the hero 1.
100% probability of win since there will be surely two heroes with the same hat's color and they'll be adjacent since they're only 3.

What did I win?

[rigwarl]

Kinda easy:

Number the heroes from 1 to 3. Now the hero 1 writes the color of the hat of the hero 2, the hero 2 of the hero 3 and the hero 3 of the hero 1.
100% probability of win since there will be surely two heroes with the same hat's color and they'll be adjacent since they're only 3.

What did I win?

You won a free trip to reread the problem more clearly!

[Yakk]

So there are 3 players -- Alice Bob and Charlie.

Each has 8 percentages that determine their strategy. Given an input, you can define your strategy by your chance of going Red, your chance of going Blue, and the remaining chance of Abstaining.

"I see two red hats".
"I see one red hat to my left and one blue hat to my right".
"I see one blue hat to my left and one red hat to my right".
"I see two blue hats".

If we check at a resolution of 1 percentage, and note that R+B<=100, we get:
((100)(101)/2)^4 < 2^50.

At 1 check/second, that is 2^25 years, which is too long. Checking every 10% takes only a relatively small fraction of a year, and we can check far faster than 1 per second, so that seems viable.

So for each such strategy (all 9150625 of them), we find the performance against a number of different hat layouts. The ones with the least worst performances would then be worth searching closer to.

Might work.

[Giallo]

Kinda easy:

Number the heroes from 1 to 3. Now the hero 1 writes the color of the hat of the hero 2, the hero 2 of the hero 3 and the hero 3 of the hero 1.
100% probability of win since there will be surely two heroes with the same hat's color and they'll be adjacent since they're only 3.

What did I win?

You won a free trip to reread the problem more clearly!

Aww I beg your pardon, sir. Right answer to wrong question

[John612]

Hi, seems to be an interesting puzzle. But one thing I would like to know that what the villain has to do with the strategy since the heroes have to guess the color that's it.

[mfb]

If the heros choose a strategy which is good in many cases and bad in a few cases, the villain will choose one of the "unlucky" cases.

See the post of Gwydion: With random hats, the heros get free in 75% of the cases.
But if the villain knows that plan, he can place the hats in a way that the heros will always die.

[Moonbeam]

I can't see how you can get a winning strategy . I'm not really following the maths here, but surely becuase the villain knows their plan beforehand, he can place the hats to thwart them ???

....so say for example, they have the plan, "if you see 2 opposite colours, abstain and if you see 2 same colours, vote the opposite colour" the villain would just place the same colour on all 3 heads and they'd all vote wrong ...... and so on for other strategies.
I could poss understand if the hats are placed randomly, but the villlain places the hats knowing their strategy. What am I missing here ???

[ConMan]

I can't see how you can get a winning strategy . I'm not really following the maths here, but surely becuase the villain knows their plan beforehand, he can place the hats to thwart them ???

....so say for example, they have the plan, "if you see 2 opposite colours, abstain and if you see 2 same colours, vote the opposite colour" the villain would just place the same colour on all 3 heads and they'd all vote wrong ...... and so on for other strategies.
I could poss understand if the hats are placed randomly, but the villlain places the hats knowing their strategy. What am I missing here ???

Definitely any deterministic strategy is doomed to failure. But if they develop a strategy with a random element, it may be able to give a decent chance of success. As the OP says, getting one person to choose randomly is a strategy guaranteed to win 50% of the time. It's hard to work out how you might improve on that, but there's the suggestion that somewhere in the set of strategies there's something better.

[ConMan]

The one thing I can think of that might be the trick is a strategy that works something like this:

* Every arrangement of hats is likely to cause a different person to guess
* Any attempt by the villain to thwart the strategy by tricking someone into guessing wrong also flips the odds of who is more likely to guess

Actually setting those probabilities is proving a bit tricky, though.

[t1mm01994]

In that case, methinks the villain can think 1 line more ahead, and thwart that plan too.

[Yakk]

The trick is to think "infinitely far ahead", so that no matter what the villain does, the situation for the heroes is under control (or, the degree to which the villian can screw the heroes, following the rules, is bounded).

It is basic game theory, where you take the best of the worst in the decision tree (to hand-wave it).

[taggedjc]

Using a spreadsheet that gives the probability of failure for each possible hat arrangement, plus a table of strategies for each player for each possible arrangement they can see (ie: the chance of choosing red, blue, and abstain each for if I see two red hats, two blue hats, a red hat on my left and a blue on the right, and vice versa... for each player), plus running a solver algorithm multiple times to see just how much it can improve the odds...

It's coming up that 50% is the highest chance of success for the heroes, and that's if one person guesses randomly and the other two abstain 100% of the time.

The tricky part comes in the fact that the villain knows the strategy the heroes will apply, so he will choose the hat arrangement that gives the greatest possible chance of failure. On the other hand, if the villain isn't involved and the hats are distributed randomly, then the chance of failure is just the average chance of failure for the given strategies over all hat arrangements. In this case, 75% is the best average, achieved by guessing only if you see two hats of the same color and guessing the opposite color (thus, it succeeds in 6 of the 8 cases, only failing when all three have red hats or all three have blue hats, and succeeding otherwise). This strategy doesn't work for the villain mode, since then the villain will just ensure that the hats are all red.



Of course, this assumes that the villain gets to actually choose each individual hat. If the villain, for example, has a magical bag of hats which lets him pull out up to three hats, each of which could be either blue or red with 50% probability, then it changes the question a little bit. After all, if the villain gets unlucky and pulls only red hats, and the hero strategy is "guess red no matter what", then the heroes will still succeed despite the villains attempts otherwise. If the hat colors are randomized and the villain just gets to choose who gets which hat, then the 75% case is the best strategy as described above, as all players have the same strategy so the villain gains nothing by choosing who gets which of the hats.

[JPAL]

If all the heroes follow this strategy then there is no losing pattern.
At least one of their guesses will be right.

Spoiler:

Imagine the heroes arranged in a circle.
There is one hero on your left and one on your right.

2
1 3

Strategy: If you see 2 of the same color guess that color; otherwise there is one of each, guess the color of hat on the hero to your right.
Left Hero: Right Hero: Guess
R: R: R
B: B: B
R: B: B
B: R: R


Hats------------------Guesses
1 2 3------------------1 2 3
B B B------------------B B B-----------------all correct------------------case 0 red hats
R B B------------------B R B-----------------last guess correct---------case 1 red hat
R R B------------------B R R-----------------2nd guess correct--------case 2 red hats
R R R------------------R R R-----------------all correct-----------------case 3 red hats

[t1mm01994]

While you do have the "Someone needs to guess right" part, you missed the "no-one can guess wrong" part.

[WarDaft]

Hmmm....

Spoiler:

In a group G of heroes, we have a proper subset K such that all guesses made by heroes in N are made by members of K. Let this group have odds C of winning. Now let H be a hero outside of K, but in G. The guesses of heroes in K are independent of the guess of H. H should guess iff the probability of H guessing wrong multiplied by the probability of K being successful is less than or equal to the probability of H being right multiplied by no one in K guessing.

Proof:
Suppose there are guesses from K.
If any of these guesses is wrong, H can not improve the situation by guessing.
If at least one of the guesses is right, H can only increase the chance of their being a wrong guess by guessing.
If there are no guesses from K, H can decrease the chance of there not being at least 1 right guess by guessing.

Clearly, if |K| is one, and that hero guesses with probability one, H cannot improve the situation at all.

So if there is a strategy better than 50%, there has to be a strategy that's better even for only 2 of the heroes guessing, so we don't even need to worry about 3 guessing yet.


Suppose Hero 1 guesses with probability less than 1, and does not guess evenly between the two colors. Then the villain can just select the less likely of their guesses and so they would have been better off guessing equally between the two colours.

So now we suppose Hero 1 guesses with probability less than 1, but evenly between the colours. Let e be the chance that Hero 1 does not guess. So hero one will be correct with probability 0.5-e/2. Hero 2 now decides if they should guess. They cannot hope to have better than 50% accuracy either, for the villain could surely chose to make their hat random if that were to the villains advantage. So by guessing, Hero 2 has a 50% chance of dooming the heroes, and a 50% chance of saving the heroes only if Hero 1 did not guess. So Hero 2 guessing makes our odds of victory 0.5(0.5-e/2) + e/2, or 0.25+e/4. Obviously e cannot be greater than 1, so this value is still bounded by 0.5, and two heroes guessing cannot do better than 1 hero guessing.

So the best we can do is 50%

Or did I miss anything?

[mfb]

Proof by total confusion?

Spoiler:

What is N? What is "such that all guesses made by heroes in N are made by members of K"? So N is a subset of K? For all sets N of heroes? In that case, K is the empty set?
How can a subset of heroes "win" with probability C, if others may ruin it? Do you define "a subset wins" if there is at least one correct guess and no wrong guess?

>> The guesses of heroes in K are independent of the guess of H
Why? They see the hat color of some other hero and their strategy can depend on this color. They always see such a hat if K is not empty and there are (at least) 3 heroes.

>> H should guess iff the probability of H guessing wrong multiplied by the probability of K being successful is less than or equal to the probability of H being right multiplied by no one in K guessing.
That is the obvious part, why do you prove just that

>> So if there is a strategy better than 50%, there has to be a strategy that's better even for only 2 of the heroes guessing
As long as there is a unique way to define 3 heroes which all 3 heroes can use. The only way to do this is numbering the heroes.

>> Suppose Hero 1 guesses with probability less than 1, and does not guess evenly between the two colors. Then the villain can just select the less likely of their guesses and so they would have been better off guessing equally between the two colours.
This hat color which is less likely to be guessed by 1 may help hero 2 or 3 to make a correct guess. As the guessing probability of 1 can be small, I don't think this general statement follows from your argument.

[WarDaft]

Spoiler:

What is N? What is "such that all guesses made by heroes in N are made by members of K"? So N is a subset of K? For all sets N of heroes? In that case, K is the empty set?
How can a subset of heroes "win" with probability C, if others may ruin it? Do you define "a subset wins" if there is at least one correct guess and no wrong guess?

Woops, that should be heroes in G, not N. No idea where the N came from.

That is the obvious part, why do you prove just that

That was just another assumption. I suppose I didn't state what I actually meant to prove beforehand, it was that we can't do better than 50%.

Why? They see the hat color of some other hero and their strategy can depend on this color. They always see such a hat if K is not empty and there are (at least) 3 heroes.

I can't remember my reasoning for that, could be a conditional probability fail on my part.

[mward]

mfb wrote:

Why? They see the hat color of some other hero and their strategy can depend on this color. They always see such a hat if K is not empty and there are (at least) 3 heroes.

Note that the villain knows their strategy beforehand: if their strategy says that seeing a particular set of colours skews your choice away from a particular colour (so that you select that colour with probability less than 50%) the villain simply ensures that your hat is that colour.

For example, the strategy given in http://forums.xkcd.com/viewtopic.php?f=3&t=1722 (which is based on random hat allocations) is defeated by giving everyone the same colour hat.

The only way to avoid this is if your choice does not depend on the hat colours you see.

[mfb]

>> The only way to avoid this is if your choice does not depend on the hat colours you see.
In that case, "one guesses at random" is the unique (up to determination of the guessing hero) best choice.

>> if their strategy says that seeing a particular set of colours skews your choice away from a particular colour (so that you select that colour with probability less than 50%) the villain simply ensures that your hat is that colour.
I am not fully convinced that a reduction of the probability of a correct guess at one prisoner cannot be outweighted by a higher chance by another prisoner.
I think this is true, and the strategy "you guess, we do not" is the best. But I think I did not see a valid proof of that yet.

[Yakk]

mfb wrote:

Why? They see the hat color of some other hero and their strategy can depend on this color. They always see such a hat if K is not empty and there are (at least) 3 heroes.

Note that the villain knows their strategy beforehand: if their strategy says that seeing a particular set of colours skews your choice away from a particular colour (so that you select that colour with probability less than 50%) the villain simply ensures that your hat is that colour.

So, your argument is wrong (regardless of if your conclusions are). As an example, a strategy where you abstain would involve your colour having probability less than 50% for both colours, and the villain cannot set your hat to two colours at once.

There may be a way to repair your claim, but that isn't my job. Nor is your claim strong merely because people haven't knocked it down yet. If you are going to claim something strongly, please be careful and attach it to logical foundations.

[sfwc]

I'm pretty sure it's impossible for any strategy to do better than 50%. My reasoning:

Spoiler:

If hero X has probability p of making a correct guess in a certain hat setup, then in the setup where X's hat has changed and the other two stay the same, X has probability p of making a wrong guess. So the sum, over all hat setups, of the expected numbers of correct guesses is equal to the sum of the expected numbers of wrong guesses. For this to be true there must exist at least one setup where E[wrong guesses] >= E[correct guesses].

Since given a particular hat setup, the heroes' choices are independent of each other, there's no way to get the wrong guesses correlated together like there is in the non-adversarial case.

Spoiler:

Even given your last line, the probability of a correct guess could still be greater than the probability of an incorrect guess, e.g. in a situation where A guesses correct, and B/C each guess incorrectly 2/3 of the time, and otherwise don't guess. The expected number of incorrect guesses is 4/3>1, but the chance of an incorrect guess is 8/9<1.

Can you show that if E(wrong guesses) ≥ E(correct guesses), and guesses are independent, then p(correct guess and no wrong guess)≤1/2?

Spoiler:

We have three people to consider: A, B and C. Let's call the probability that A guesses correctly A1, and the probability that he guesses incorrectly A2. Similarly, we can define B1, B2, C1 and C2. Then the constraint E(wrong guesses) ≥ E(correct guesses) becomes A2 + B2 + C2 ≥ A1 + B1 + C1. We are interested in how large we can make p(correct guess an no wrong guess), which I'll call p. In the notation above, p = (1 - A2)(1-B2)(1 - C2) - (1 - A1 - A2)(1 - B1 - B2)(1 - C1 - C2).

Of course, each of the As, Bs and Cs should lie between 0 and 1, and we must have that each of A1 + A2, B1 + B2 and C1 + C2 is at most 1. I'll call these the bounding conditions.

We want to show that p ≤ 1/2, which we can now do by the circuitous method of supposing that we can choose A1, A2, B1, B2, C1 and C2 meeting the constraint above but with p > 1/2, and showing that that leads to an absurd conclusion. So suppose we have such values for the As, Bs and Cs.

Lets first of all think about what happens if we change A1 and A2 a bit. We don't want to break the constraint, so whatever we add on to A1, we should also add on to A2. So what happens if we replace A1 by A1 + d, and A2 by A2 + d? Well, the value of p changes by an amount proportional to d, namely d*[-(1-B2)(1-C2) + 2(1 - B1 - B2)(1 - C1 - C2)]. So by either taking d to be positive (if -(1-B2)(1-C2) + 2(1 - B1 - B2)(1 - C1 - C2) is positive) or negative (otherwise), we can modify the values of A1 and A2 without lowering the value of p. In fact, we can keep on changing the values of A1 and A2 in the appropriate direction until we can go no further because of the bounding conditions. This happens when either at least one of A1 and A2 is 0 or else A1 + A2 = 1. So, we may as well suppose that one of these things happen: if not, we can make it happen without breaking the constraint or reducing the value of p.

We can quickly rule out the case A1 + A2 = 1. From the constraint, we get 1 - A2 = A1 ≤ A2 + B2 + C2, and so 2(1-A2) + (1 - B2) + (1 - C2) ≤ 3. By the AM-GM inequality applied to 2(1-A2), 1 - B2 and 1 - C2 we now get 2*(1-A2)*(1-B2)*(1 - C2) ≤ 1, and so p = (1 - A2)(1 - B2)(1 - C2) ≤ 1/2. That's not possible, as we're assuming p > 1/2.

So either A1 = 0 or A2 = 0. Similarly we can assume that one of B1 and B2 is 0 and that at least one of C1 and C2 is zero (note for pedants: we can make all three of these assumptions at once, since the changes we made to force either A1 or A2 to be 0 didn't affect the values of the Bs or the Cs at all).

We can't have that all three of A1, B1 and C1 are 0, since in that case p would be 0. So let's suppose that A1 > 0, which forces A2 = 0. Then, using the constraint, B2 + C2 ≥ A1 > 0, so B2 and C2 can't both be zero. Let's suppose that B2 > 0, which forces B1 = 0. We now have 2 cases to consider: the case where C1 = 0, and the case where C2 = 0.

First, let's examine the case where C1 = 0. Then we get A1 ≤ B2 + C2, so that A1 + (1 - B2) + (1 - C2) ≤ 2. In this case, p = (1 - B2)(1-C2) - (1 - A1)(1 - B2)(1 - C2) = A1(1 - B2)(1 - C2) ≤ 8/27 < 1/2, by applying the AM-GM inequality to A1, (1 - B2) and (1 - C2). Once again, this case is eliminated since we are assuming p > 1/2.

Next, lets examine the case where C2 = 0. Then we get A1 + C1 ≤ B2, so that (1 - B2) + (A1 + C1) ≤ 1. In this case, p = (1 - B2) - (1 - A1)(1 - B2)(1 - C1) = (1 - B2)[1 - (1 - A1)(1 - C1)] = (1 - B2)(A1 + C1 - A1*C1) ≤ (1 - B2)(A1 + C1) ≤ 1/4 < 1/2, by applying the AM-GM inequality to 1-B2 and A1 + C1. This final case is therefore also eliminated since we are assuming p > 1/2.

We have now eliminated all possible cases, which is absurd. So our assumption must have been false. That is, we always have p ≤1/2. This, together with the arguments quoted above, shows that the heroes have no strategy which is guaranteed to succeed more than half the time.

[mfb]

A related puzzle I found today: No villain, but n prisoners. How can we modify the strategy?

[sfwc]

That is discussed in the thread linked to within the spoiler in the OP.

Another challenge: n prisoners, but with a villain. Can they do better than 1/2?

Spoiler:

Look out for a cameo appearance by e, one of the rock stars of the real line.

[jk47]

Simple solution?

Spoiler:

Say the heroes have a strategy such that their probability of success is > 50%. The villain can then give each hero a random hat with 50:50 probability, hence anyone who guesses can only have a 50% chance of success (as the hats are independent of one another.) This contradicts our assumption that there exists a solution with greater than 50% odds. Therefore (as a 50% strategy does exist), that is the best we can do.

[jestingrabbit]

Simple solution?

Spoiler:

Say the heroes have a strategy such that their probability of success is > 50%. The villain can then give each hero a random hat with 50:50 probability, hence anyone who guesses can only have a 50% chance of success (as the hats are independent of one another.) This contradicts our assumption that there exists a solution with greater than 50% odds. Therefore (as a 50% strategy does exist), that is the best we can do.

That argument must be wrong. Your villain uses no knowledge of the strategy, so if there is a strategy that delivers better than 50% when the villain is uninformed, that contradicts you.

Spoiler:

Now consider what happens if every hero uses the strategy "if the other two are wearing hats that are the same colour, I guess the other colour, otherwise I abstain", then in RRB, RBR, BRR, RBB, BRB and BBR the heroes win, and they only lose on RRR and BBB where every hero guesses wrong.

The question is whether there can be a similar strategy when the the villain knows what the heroes will do. Smart money says no.