Could there still be new hat puzzles?

[Yat]

Here's a hat puzzle inspired by this one.

Seven perfectly rational players stand in a circle.
Everyone gets assigned, randomly and independently, a black hat or a white hat. Nobody can see the color of his own hat but the colors of all other players.
All the players must try to guess the color of their hat simultaneously, without any communication. Let's say they somehow aren't even able to recognize eachother, or they haven't met in person before. They only see hat colors and the relative position of their wearers in the circle.

To win the game, they need a majority (at least 4) of correct guesses.

They can devise a strategy, but it can't be nominative. The player's can't take into account their own identity, the whole strategy has to be exactly the same for all players.

What is the probability that they win the game?

[HonoreDB]

Spoiler:

Simple strategy: Each player should guess the hat color that she sees the most of. In a tie, she picks black. This succeeds in all cases except when there are 4 white hats and 3 black hats, in which case everybody guesses wrong. In a 4/3 split the other way, everybody guesses black, for 4 correct guesses.
In any more lopsided split, everybody with the majority hat color sees a majority of their color and guesses correctly. A 4/3 split in favor of white happens 27% of the time, so this is a 73% success rate.

This fails for one of the two most common splits, and doesn't use relative positions, so it's probably not optimal.

[Yat]

This fails for one of the two most common splits, and doesn't use relative positions, so it's probably not optimal.

It is a good start, but you are right, it is possible to get less than half this error rate.

[cellocgw]

I'm just starting out the cheap way: generating different strategies and running stochastic simulations.

Spoiler:

The "pick majority seen" method is confirmed to be around 73%.
An absurd strategy where the prime-numbered players (2,3,5,7) pick the minority color and the other players pick the majority color does worse;
no surprise there

More news later.

Well, a surprising (to me) improvement gets me up to about 76.4% . I have each player, when 3&3 are seen, count the number of value changes, e.g., WWBWBB has 3 changes in polarity, and WBBBWW has two .

Spoiler:

Code: Select all

function hatout = hat7(runs)
eachrandwin=[];
for jj = 1:runs
    seq = randi(2,7,1) - 1; % output of randi is 1s and 2s
    for kk = 1:7 %people       
   % count() is how many "white" are seen by each person
        count(kk) = sum(seq( (1:numel(seq)~=kk)));
         pick4(kk) = count(kk) > 3;
        pick3(kk) = count(kk) ==3;
        % majority strategy:match your hat to viewed majority, which
        % "ignores" 3+3 seen
        eachmajwin(kk) = pick4(kk) == seq(kk);
        % add the 'pick black if tie' option also a randomize
        if pick3(kk) ,
            each3win(kk) = 1 == seq(kk);
            eachrandwin(kk) = randi(2,1,1)-1 == seq(kk);
            eachadj(kk) = ~ seq(mod(kk+1,7)+1);
            fliptmp = seqle(seq);% seqle is an RLE implementation
            eachflips(kk) = ~mod(length(fliptmp.run),2);
        else
            each3win(kk) = eachmajwin(kk);
            eachrandwin(kk) = eachmajwin(kk);
            eachadj(kk) = eachmajwin(kk);
            eachflips(kk) = eachmajwin(kk);
        end
   
    end %of kk
     majoritywin(jj) = sum(eachmajwin) >= 4 ;
    win3(jj) = sum(each3win) >= 4;
    randwin(jj) = sum(eachrandwin) >= 4;
    winadj(jj) = sum(eachadj) >= 4;
    flips(jj) = sum(eachflips) >=4;
end %of jj
hatout.majority = sum(majoritywin);
hatout.win3 = sum(win3);
hatout.rand = sum(randwin);
hatout.adj = sum(winadj);
hatout.flip = sum(flips);
hatout.runs = runs;
end

with the results (out of 10 000 runs repeatedly)
>> mean([fooh.flip])
ans =
7.6395e+03
>> mean([fooh.win3])
ans =
7.2671e+03
>> mean([fooh.majority])
ans =
7.2634e+03

[HonoreDB]

I'm just starting out the cheap way: generating different strategies and running stochastic simulations.

No need to be stochastic (with deterministic strategies, anyway). There are only 128 different ways to place the hats, faster and more accurate to just test each of them once.

[cellocgw]

I'm just starting out the cheap way: generating different strategies and running stochastic simulations.

No need to be stochastic (with deterministic strategies, anyway). There are only 128 different ways to place the hats, faster and more accurate to just test each of them once.

Yeah, but where's the fun in that? .
FWIW, the execution time for 10 sets of 10000 runs was under a second.

[Yat]

An absurd strategy where the prime-numbered players (2,3,5,7) pick the minority color and the other players pick the majority color

As I said in the OP, "They can devise a strategy, but it can't be nominative. The player's can't take into account their own identity, the whole strategy has to be exactly the same for all players." In other words, there are no prime numbered players. Everybody must follow the same strategy.

Sorry if my explanations were not clear enough.

[Poker]

Proof of a theoretical maximum, assuming a deterministic strategy: EDIT: Actually, I don't even think we need to assume a deterministic strategy. I'll edit my argument in.

Spoiler:

There are 128 configurations of hats. Each player, in any given deterministic strategy, will be right in 64 cases and wrong in the other 64. Therefore, over all configurations, there are 64*7 = 448 correct guesses. Since each successful configuration requires 4 correct guesses, there can be at most 112/128 successful configurations, which is an 87.5% chance of success.

EDIT: Even assuming a randomized strategy, each player will be right with probability 0.5, so the total guesses will be 50% wrong and 50% right. The guesses in the successful outcomes are at minimum 4/7 right, so there can be at most (1/2)/(4/7) successful outcomes, which is 7/8, or 87.5%.

An actual maximum deterministic strategy:

Spoiler:

• If the hat color division of the other players is, guess the minority color.
• If the hat color division of the other players is 5/1, then if the player in the minority is one of the three on your left guess the minority color, but if the player in the minority is one of the three on your right guess the majority color.
• If the hat color division of the other players is 4/2, then divide up the players into two groups, one being the first, second, and fourth players from your left, the other being the first, second, and fourth players from your right. If the two in the minority are in the same group, guess the minority color. Otherwise, guess the majority color.
• If the hat color division of the other players is 3/3, and the hat arrangement is antisymmetric (that is, the player on your left and the player on your right have opposite colors, etc.), then guess the hat color of the player on your left. If the hat arrangement is not antisymmetric, but the players next to you still have opposite color hats, guess the hat color of the player on your right. Otherwise, guess assuming that exactly one of you, the player two to your left, and the player three to your right has the same hat color as the players next to you.

WLOG (including all rotations and color inversion) there are 10 different hat configurations. Here is an analysis of each, along with the total number of that kind of configuration:

• BBBBBBB (2) - Everyone will guess W, so all players will guess incorrectly. FAILURE
• BBBBBBW (14) - The player with W will guess W. The three players to W's right will also guess W and be wrong, but the three players to W's left will guess B. Four players guess correctly. SUCCESS
• BBBBBWW (14) - The players with W will split - one guessing W, the other guessing B. The two B players next to them will guess W, but the three B players NOT next to them will guess B. Four players guess correctly. SUCCESS
• BBBBWBW (14) - Again, the players with W will split - one guessing W, the other guessing B. The three B players next to them will guess B, while the two B players NOT next to them will guess W. Four players guess correctly. SUCCESS
• BBBWBBW (14) - Once again, the players with W will split - one guessing W, the other guessing B. The two B players between them will guess B. The other two B players next to them will guess W, while the B that isn't next to any W will guess B. Four players guess correctly. SUCCESS
• BBBBWWW (14) - The two W players on the end will guess W, while the one in the middle will guess B. The B players will guess, in order from left to right, W, B, W, B. Four players guess correctly. SUCCESS
• BBBWBWW (14) - The lone W player will guess B, while the adjancent pair will guess W. The lone B will guess W, as will the B on the left of the trio, but the B players in the middle and on the right will guess B. Four players guess correctly. SUCCESS
• BBBWWBW (14) - All of the W players will guess B, while all of the B players will guess W. All players guess incorrectly. FAILURE
• BBWBBWW (14) - The lone W player will guess B, while the adjacent pair will guess W. The B players will each follow the player on their right, leading to two B guesses and two W guesses. Four players guess correctly. SUCCESS
• BBWBWBW (14) - The W in the "middle" will guess B, while the other two will guess W. The B players in between W players will split, as will the adjacent B player pair, leading to two B guesses and two W guesses. Four players guess correctly. SUCCESS

In all, this is 112 successes and 16 failures, just as required.

I'm sure there's a more aesthetically pleasing arrangement, but it works, anyway.

[Yat]

Proof of a theoretical maximum, assuming a deterministic strategy: EDIT: Actually, I don't even think we need to assume a deterministic strategy. I'll edit my argument in.

Spoiler:

There are 128 configurations of hats. Each player, in any given deterministic strategy, will be right in 64 cases and wrong in the other 64. Therefore, over all configurations, there are 64*7 = 448 correct guesses. Since each successful configuration requires 4 correct guesses, there can be at most 112/128 successful configurations, which is an 87.5% chance of success.

EDIT: Even assuming a randomized strategy, each player will be right with probability 0.5, so the total guesses will be 50% wrong and 50% right. The guesses in the successful outcomes are at minimum 4/7 right, so there can be at most (1/2)/(4/7) successful outcomes, which is 7/8, or 87.5%.

An actual maximum deterministic strategy:

Spoiler:

• If the hat color division of the other players is, guess the minority color.
• If the hat color division of the other players is 5/1, then if the player in the minority is one of the three on your left guess the minority color, but if the player in the minority is one of the three on your right guess the majority color.
• If the hat color division of the other players is 4/2, then divide up the players into two groups, one being the first, second, and fourth players from your left, the other being the first, second, and fourth players from your right. If the two in the minority are in the same group, guess the minority color. Otherwise, guess the majority color.
• If the hat color division of the other players is 3/3, and the hat arrangement is antisymmetric (that is, the player on your left and the player on your right have opposite colors, etc.), then guess the hat color of the player on your left. If the hat arrangement is not antisymmetric, but the players next to you still have opposite color hats, guess the hat color of the player on your right. Otherwise, guess assuming that exactly one of you, the player two to your left, and the player three to your right has the same hat color as the players next to you.

WLOG (including all rotations and color inversion) there are 10 different hat configurations. Here is an analysis of each, along with the total number of that kind of configuration:

• BBBBBBB (2) - Everyone will guess W, so all players will guess incorrectly. FAILURE
• BBBBBBW (14) - The player with W will guess W. The three players to W's right will also guess W and be wrong, but the three players to W's left will guess B. Four players guess correctly. SUCCESS
• BBBBBWW (14) - The players with W will split - one guessing W, the other guessing B. The two B players next to them will guess W, but the three B players NOT next to them will guess B. Four players guess correctly. SUCCESS
• BBBBWBW (14) - Again, the players with W will split - one guessing W, the other guessing B. The three B players next to them will guess B, while the two B players NOT next to them will guess W. Four players guess correctly. SUCCESS
• BBBWBBW (14) - Once again, the players with W will split - one guessing W, the other guessing B. The two B players between them will guess B. The other two B players next to them will guess W, while the B that isn't next to any W will guess B. Four players guess correctly. SUCCESS
• BBBBWWW (14) - The two W players on the end will guess W, while the one in the middle will guess B. The B players will guess, in order from left to right, W, B, W, B. Four players guess correctly. SUCCESS
• BBBWBWW (14) - The lone W player will guess B, while the adjancent pair will guess W. The lone B will guess W, as will the B on the left of the trio, but the B players in the middle and on the right will guess B. Four players guess correctly. SUCCESS
• BBBWWBW (14) - All of the W players will guess B, while all of the B players will guess W. All players guess incorrectly. FAILURE
• BBWBBWW (14) - The lone W player will guess B, while the adjacent pair will guess W. The B players will each follow the player on their right, leading to two B guesses and two W guesses. Four players guess correctly. SUCCESS
• BBWBWBW (14) - The W in the "middle" will guess B, while the other two will guess W. The B players in between W players will split, as will the adjacent B player pair, leading to two B guesses and two W guesses. Four players guess correctly. SUCCESS

In all, this is 112 successes and 16 failures, just as required.

I'm sure there's a more aesthetically pleasing arrangement, but it works, anyway.

Congrats!
It certainly is more aesthetically pleasing than my own solution, as it is symetric and formulated as a short set of rules.
I just have a table of 64 rules and the situation that triggers a failure with 3 white hats is not the same as with 3 black hats.

[Poker]

Well, I was right - there is a much more elegant maximal strategy. You don't even need to divide it up into cases to use the strategy (though checking it will divide into cases)!

Spoiler:

Check the players that are first, second, and fourth from your left. Guess whichever color hat is worn by an even number (whether it is 0 or 2) of those three.

A few facts about this strategy that will be useful in the proof: given any players, exactly one of them checks the other, and there is exactly one other player that checks both of them, and exactly one other player who checks neither of them.

• In the cases where the hats divide 7/0, everyone picks the wrong color hat, making the guesses 0/7.
• In the cases where the hats divide 6/1, the minority always gets it right, while half of the majority has the 1 in their set of checked players and thus get it right, while the other half doesn't and thus get it wrong, making the guesses 4/3.
• In the cases where the hats divide 5/2, regardless of how the two in the minority are positioned, exactly one has the other in their set of checked players, and so they will make opposite guesses. As for the other five, exactly one will have both of the minority in their set of checked players and exactly one will have neither (as both the checked and unchecked sets have members all three possible distances apart), so those two will guess wrong while the other three will guess right, making the guesses 4/3.
• In the cases where the hats divide 4/3, the minority will sometimes split 2 right 1 wrong (with one of them checking neither of the others, another checking only the first one, and the third checking each of the other two), and sometimes all get it wrong (with each of them checking only one of the others, in a cycle).
  
  • In the cases where the minority split 2 right 1 wrong, the majority must split 2 right 2 wrong (two checking the pairs that did not get checked, and the other two checking one each), making the guesses 4/3.
  • In the cases where the minority all get it wrong, the majority either all get it right (one player checking all three in the minority, and the other three each only checking one) or all wrong (three players each checking a different pair, and the fourth checking none of them), making the guesses either 4/3 or 0/7.

This proves that in every case, the number of players who get it right is either 0 or 4. This is sufficient to prove the strategy is maximal, as each player is right 50% of the time, meaning there should be an average of 3.5 right guesses, and the only division of a whole into 0 and 4 with an average of 3.5 is to have 87.5% be 4 and 12.5% be 0.

[Yat]

Well, I was right - there is a much more elegant maximal strategy. You don't even need to divide it up into cases to use the strategy (though checking it will divide into cases)!

Spoiler:

Check the players that are first, second, and fourth from your left. Guess whichever color hat is worn by an even number (whether it is 0 or 2) of those three.

A few facts about this strategy that will be useful in the proof: given any players, exactly one of them checks the other, and there is exactly one other player that checks both of them, and exactly one other player who checks neither of them.

• In the cases where the hats divide 7/0, everyone picks the wrong color hat, making the guesses 0/7.
• In the cases where the hats divide 6/1, the minority always gets it right, while half of the majority has the 1 in their set of checked players and thus get it right, while the other half doesn't and thus get it wrong, making the guesses 4/3.
• In the cases where the hats divide 5/2, regardless of how the two in the minority are positioned, exactly one has the other in their set of checked players, and so they will make opposite guesses. As for the other five, exactly one will have both of the minority in their set of checked players and exactly one will have neither (as both the checked and unchecked sets have members all three possible distances apart), so those two will guess wrong while the other three will guess right, making the guesses 4/3.
• In the cases where the hats divide 4/3, the minority will sometimes split 2 right 1 wrong (with one of them checking neither of the others, another checking only the first one, and the third checking each of the other two), and sometimes all get it wrong (with each of them checking only one of the others, in a cycle).
  
  • In the cases where the minority split 2 right 1 wrong, the majority must split 2 right 2 wrong (two checking the pairs that did not get checked, and the other two checking one each), making the guesses 4/3.
  • In the cases where the minority all get it wrong, the majority either all get it right (one player checking all three in the minority, and the other three each only checking one) or all wrong (three players each checking a different pair, and the fourth checking none of them), making the guesses either 4/3 or 0/7.

This proves that in every case, the number of players who get it right is either 0 or 4. This is sufficient to prove the strategy is maximal, as each player is right 50% of the time, meaning there should be an average of 3.5 right guesses, and the only division of a whole into 0 and 4 with an average of 3.5 is to have 87.5% be 4 and 12.5% be 0.

That is awesome. May I ask how you came up with this method? Did you extract the pattern from your first answer and tried to figure out how it worked, or did you first came up with the rules?

[Poker]

Well, I was right - there is a much more elegant maximal strategy. You don't even need to divide it up into cases to use the strategy (though checking it will divide into cases)!

Spoiler:

Check the players that are first, second, and fourth from your left. Guess whichever color hat is worn by an even number (whether it is 0 or 2) of those three.

A few facts about this strategy that will be useful in the proof: given any players, exactly one of them checks the other, and there is exactly one other player that checks both of them, and exactly one other player who checks neither of them.

• In the cases where the hats divide 7/0, everyone picks the wrong color hat, making the guesses 0/7.
• In the cases where the hats divide 6/1, the minority always gets it right, while half of the majority has the 1 in their set of checked players and thus get it right, while the other half doesn't and thus get it wrong, making the guesses 4/3.
• In the cases where the hats divide 5/2, regardless of how the two in the minority are positioned, exactly one has the other in their set of checked players, and so they will make opposite guesses. As for the other five, exactly one will have both of the minority in their set of checked players and exactly one will have neither (as both the checked and unchecked sets have members all three possible distances apart), so those two will guess wrong while the other three will guess right, making the guesses 4/3.
• In the cases where the hats divide 4/3, the minority will sometimes split 2 right 1 wrong (with one of them checking neither of the others, another checking only the first one, and the third checking each of the other two), and sometimes all get it wrong (with each of them checking only one of the others, in a cycle).
  
  • In the cases where the minority split 2 right 1 wrong, the majority must split 2 right 2 wrong (two checking the pairs that did not get checked, and the other two checking one each), making the guesses 4/3.
  • In the cases where the minority all get it wrong, the majority either all get it right (one player checking all three in the minority, and the other three each only checking one) or all wrong (three players each checking a different pair, and the fourth checking none of them), making the guesses either 4/3 or 0/7.

This proves that in every case, the number of players who get it right is either 0 or 4. This is sufficient to prove the strategy is maximal, as each player is right 50% of the time, meaning there should be an average of 3.5 right guesses, and the only division of a whole into 0 and 4 with an average of 3.5 is to have 87.5% be 4 and 12.5% be 0.

That is awesome. May I ask how you came up with this method? Did you extract the pattern from your first answer and tried to figure out how it worked, or did you first came up with the rules?

I started by producing every symmetric method (ones where black and white were interchangeable) that would produce the desired result, then I refined my search to look only at those that had nice left-right symmetry (where if the hats were 5-1 or 3-3 then reversing the order of the hats would always change the guess, and if the hats were 4-2 then reversing the order of the hats would never change the guess). At that point I noticed all of the solutions used the 4-2 case from my original solution, and I realized it might be possible to reduce all four cases to one if I could always use the division of hats from that case. So I checked, and I could.

[itaibn]

A deliberately obfuscated strategy:

Spoiler:

Each player assigns to all other players a 3-bit code, so that going around in clockwise order from the player just after them the codes are 111, 101, 001, 010, 100, and 011. The player then computes the bitwise XOR of the codes of all the players that are wearing a black hat. If the result is 000, 001, 011, or 100 then the player guesses they have a black hat, otherwise they guess they have a white hat.

Be advised that I have proven that this strategy is correct, but I have not tested it. In particular, If I made any mistakes while calculating the obfuscated form then the strategy will not work.