Timeline for A hat puzzle question—how to prove the standard solution is optimal?
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 24 at 16:11 | comment | added | Joel David Hamkins | I find all the mixed strategy stuff an irrelevant distraction. The main point I take is: every instance of someone guessing correctly must be balanced by an instance of that person making the same judgement but being incorrect. So if we win six rows, there must be at least six instances of incorrect guess, and this uses up the remaining slots in the other two rows. So winning seven is impossible. | |
| Jul 24 at 13:30 | vote | accept | Joel David Hamkins | ||
| Jul 24 at 13:26 | comment | added | Joel David Hamkins | Thanks for the edit---an elegant answer. | |
| Jul 24 at 7:55 | comment | added | Vincent | Excellent answer, it gives insight into this class of problem where you want no failure in order to win : you have to fail as hard as you can on a few bad cases. (Here all 3 players fail at the same time, allowing them to win on 3 different games) | |
| Jul 24 at 4:52 | comment | added | Steven Landsburg | 1. The choice of a triple of strategies is essentially a one-player game, so there is no advantage to mixing. 2. Your argument generalizes quite nicely to give the result in the "edited to add" section of my own answer. | |
| Jul 24 at 4:45 | comment | added | bof | Very nice, thanks! By the way, I don't see the point of considering mixed strategies when the enemy's strategy is known. | |
| Jul 24 at 4:18 | comment | added | RavenclawPrefect | @bof The three-person strategy can be generalized to an approach which saturates this bound whenever the number of participants is one less than a power of $2$. Given a Hamming code on strings of length $2^n-1$, each person ventures a guess only if what they see is compatible with the arrangement forming a codeword, and guesses whichever color on their hat would not lead to a codeword. Since all strings are either a codeword or exactly one bit-flip away from a codeword, this leads to success on all non-codeword inputs. | |
| Jul 24 at 3:55 | comment | added | bof | If you play the same game with 4 people, the same argument shows that a winning probability of 75% is the best possible. Can you do better with greater numbers of people? Or is 75% always the best possible for $\ge3$ people? | |
| Jul 23 at 23:55 | comment | added | RavenclawPrefect | @JoelDavidHamkins I've reworded the original answer in the hopes of making things clearer as to how this plays out for mixed strategies. | |
| Jul 23 at 23:55 | history | edited | RavenclawPrefect | CC BY-SA 4.0 |
added 338 characters in body
|
| Jul 23 at 23:23 | comment | added | RavenclawPrefect | Here's a simple table of this allocation in the standard solution; we have 6 correct answers and 6 incorrect answers, distributed across 6 and 2 world states respectively. | |
| Jul 23 at 23:18 | comment | added | RavenclawPrefect | Since I win for every row with at least one "correct" and no "incorrect"s, the best I can hope for is to get 6 rows with a single "correct" and 2 rows each with three "incorrect"s - because if I had 7 or more rows used up on being correct, I wouldn't have room to fit my ≥7 incorrect guesses. | |
| Jul 23 at 23:18 | comment | added | Joel David Hamkins | Yes, my question is about the deterministic case, not probabilistic mixed strategies. But I guess it would be a stronger result to handle mixed strategies. | |
| Jul 23 at 23:17 | comment | added | RavenclawPrefect | Sorry if this was poorly explained! I was trying to cover the case of mixed strategies, but it's easier to talk about in the deterministic case. For any deterministic strategy, I'll be able to say for each of eight possible hat assignments and each of three people whether that person was right conditional on that hat assignment. Because every instruction I give to a hat-wearer forces their choice in worlds where they're right as well as worlds where they're wrong, I'll always have as many "correct" cells in this 8x3 grid as "incorrect" cells. | |
| Jul 23 at 23:14 | comment | added | Joel David Hamkins | I'm sorry, I don't quite get it. Can you explain a little more fully? What do you mean by putting a probability mass on worlds? I guess you just mean the probability that the putative superior strategy wins in that event. But this is not an individualized thing, so I don't quite get the focus on individual perspectives that you mention. | |
| Jul 23 at 23:09 | history | answered | RavenclawPrefect | CC BY-SA 4.0 |