tag:blogger.com,1999:blog-3722233.post875604371584900743..comments2023-10-04T12:06:12.244-05:00Comments on Computational Complexity: Two hat problems you may or may not have seen but I have a point to make about one of themLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-69839181506277829782017-07-11T15:46:43.093-05:002017-07-11T15:46:43.093-05:00I didn't specify that I wanted a deterministic...I didn't specify that I wanted a deterministic protocol in the question (is deterministic or randomized the default? I had thought det). So I'll do it now- try to do as best you can with a deterministic protocol.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10048086188747395942017-07-11T13:08:59.368-05:002017-07-11T13:08:59.368-05:00ahh yeah, you're right. When I read the proble...ahh yeah, you're right. When I read the problem, I mentally pigeonholed myself into a solution where first I picked some random bits - any string \in \{0,1\}^n will work then right? And the one failure string is when it just so happens that flips coincide with it<br /><br />These are fun, here's a stab at 3 (spoilers below, again)<br /><br /><br /><br /><br /><br /><br /><br />3) Like in problem 1, it seems hopeless since you don't get any information from the world except what everyone else is wearing. The wording of the question is a tip off that maybe you can't do that great which begs the question, can you do anything? <br /><br />Here's a protocol that gives you something: After the hats go on, each player shouts out the most common color they see (breaking ties arbitrarily). Claim: The number of correct guesses is 1/c (in expectation).<br /><br />Pf idea: Let N_i be the number of agents with hat color i and c be the number of colors. By our assumption (and pigeonhole), \exist N_i > N/c, and every agent will guess color i. N_i of them will be right giving the claim.<br /><br />Remark: Actually this is not quite right. If, for example, exactly half the group gets red and the other half gets blue, then everyone will guess the opposite color that they see and no one will get it right. The dirty fix is to have each agent guess proportional to what they see, which a little fiddling I think that rule gives 1/c correct in expectation (where the randomness is each agents decision rule)<br /><br />Lowerbound: If the adversary picks the hat colors at random, ensuring that N-i = N_j \for i,j it seems intuitive that this is the best you can do. No idea how to prove itMike Hnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35499562440887095122017-07-10T12:42:31.869-05:002017-07-10T12:42:31.869-05:00I want a deterministic strategy (so no coin flips,...I want a deterministic strategy (so no coin flips, no random string)<br />to minimize the prob of failure. There is no adversary--- so effectively<br />I want to minize the number of sequences of R's and B's where<br />either everyone passes OR someone who gives a guess gets it wrong.<br /><br />what you have is very close to that.<br /><br />The key diff between the problem you solved and the one I intended to ask:<br /><br />I intended to have the hats put on randomly, but players det<br />So my prob of failure is based on the random sequence of hats.<br /><br />You solved the problem where their is an adversary but the players get to use randomization. So your prob of failure is based on the players coin flips and is not depending on the randomness of the hats, which is why you can have an adversary.<br /><br />I will modify the post, though oddly enough, my NOT specifiying that it was deterministic led to your solution and a great new problem and solution.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60403874750409733072017-07-10T12:24:58.925-05:002017-07-10T12:24:58.925-05:00"We want to maximize the probability that (1)..."We want to maximize the probability that (1) someone does not say PASS, and (2) ALL who do not say PASS are correct."<br /><br />Correct in terms of what? What is the goal? Are they trying to guess their own hat color or someone else's? <br /><br />"Hats are going to be put on the heads RANDOMLY- prob of RED or BLUE is 1/2."<br /><br />Does this mean that there are exactly as many red as blue hats in the hat reservoir, or does it mean that as we place a hat on someone's head, we flip a coin to decide whether to color it red or blue? <br /><br />I love a good puzzle. But this one is way underspecified.TShttps://www.blogger.com/profile/07035682350972766354noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34150503503813094452017-07-10T11:35:21.996-05:002017-07-10T11:35:21.996-05:00I think you have an answer to a slighly different ...I think you have an answer to a slighly different problem.<br /><br />My problem was: NO adversary, hats put on at random. For that problem<br />you can get it except in ONE case, so prob of sucess is like yours,<br />but you can to it deterministically with an algorithm for close to yours.<br /><br /> Yours does that well when there IS an adversary but the players are allowed randomization. Great!GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72460888501341208072017-07-10T11:13:10.363-05:002017-07-10T11:13:10.363-05:00So here's one (partially). Spoiler below I gue...So here's one (partially). Spoiler below I guess<br /><br /><br /><br /><br /><br /><br />Let h_i be the color of the i^{th} persons hat. Before the game starts the N people come up with a random string r_1, r_2, \ldots, r_N and all memorize it. Then they agree to the following protocol: For person i, if \exists j > i s.t. r_j == h_j, pass. O.w. shout out r_i and terminate the protocol.<br /><br />The protocol always succeeds if the first person passes. If the the first person doesn't pass, then all the keys in front at different which is suppa unlucky (1/2^{n-1}), in which guess player one has to guess (1/2 err prob). Thus the protocol succeeds w.p 1-1/2^n. No idea how to show a matching lower bound though, except that, you know, nothings ever double exponential. Mike Hnoreply@blogger.com