36
$\begingroup$

Eight people are going to play a game where they work together to try to win a prize. They will all stand in a circle, and while their eyes are closed, a referee will place a hat on their head bearing the word "rock," "paper", or "scissors". Everyone's hat is chosen randomly and independently, with all three options equally likely.

After the hats are chosen, the players will open their eyes, so they can read everybody's hat except for their own. Each player will then play a game of rock-paper-scissors against their own hat. That is, after all hats are revealed, each player will simultaneously announce "rock", "paper", or "scissors". Each player's choice is played against the word on that player's hat, and the wins, losses, and draws are tallied up. The team wins a huge prize exactly when the number of wins exceeds the number of losses.

Before the game begins, the team may agree on a strategy. During the proceedings of the game, no communication between players is possible.

What strategy maximizes the probability of taking home the prize?
A good answer will exhibit a strategy, and prove that no other strategy does better.

When everyone plays randomly, the team wins about 42% of the time. How much better can they do?

Hint: A good warm-up problem is to solve the variant with only two people.

Improve this question
$\endgroup$
11
  • 9
    $\begingroup$ Good ol' rock, nothing beats that! $\endgroup$ Commented Sep 14 at 18:07
  • 2
    $\begingroup$ Does it have to be a deterministic algorithm, or can it be randomised? For example, can they use coin tosses as part of their strategy? $\endgroup$ Commented Sep 14 at 23:21
  • 2
    $\begingroup$ @Pranay The best random strategy cannot do better than the best deterministic strategy. This is not always true if quantum strategies are allowed. $\endgroup$ Commented Sep 15 at 23:07
  • 1
    $\begingroup$ @Lucenaposition. In general, BPP vs P isn’t settled, right? Are you talking about this particular problem? If so, is it easy to see why randomisation doesn’t give better strategies in this problem? $\endgroup$ Commented Sep 15 at 23:20
  • 2
    $\begingroup$ @Pranay Randomisation is like a "local hidden variable" while quantum is like "non-local hidden variable". (I assume the hats are chosen by chance, not by an opponent who knows their strategy) If the opponent knows the strategy and can choose, randomisation can be useful. $\endgroup$ Commented Sep 15 at 23:30

5 Answers 5

Reset to default
19
$\begingroup$

Building on other answers, this is a strategy that gets

8/9

The starting point is

Albert.Lang's method which achieves 2/3 with 2 players, via each playing what loses to the other player's hat. Moreover, as Albert.Lang notes, this extends to 8 players by having the other 6 act as "nulls" by pairing off and playing what's on their partner's hat, guaranteeing a net tie in the pair.

To improve on this, note that

the other 6 players can see when the duo is about to lose by looking at their hats, and switch to a riskier strategy. The duo get 2 losses the 1/3 of the time that they fail, so the other 6 players need 3 wins net. Let's make a strategy that does this 2/3 of the time, bringing the overall win chance to 8/9.

Here's a warm-up strategy that salvages things 1/3 of the time. Consider the sum S of their six hats mod 3, fixing some assignment of rock/paper/scissor to 0/1/2 that the players agree to. Say every player assumes that S is 0, and deduces what their hat must be to make this true. They all play to beat their hat, so that every single one of them wins when S=0. In the other two equally likely cases where S is 1 or 2, they all tie or all lose.

To improve this chance to 2/3, they need to succeed for two of the three S's, and do so by +3 or more. In particular, the strategy is to aim for +3/+3/-6 net scores, as opposed to +6/0/-6 in the warm-up.

To do this, the players instead have S be the sum of the hats of the first 3 players, minus that of the other 3. Now, everyone plays so that if S is 0, they lose to what their hat must be. But now, when S=1 or S=2, three of the players will win and three will tie, depending on whether they're in the plus-group or minus-group, because their respective "errors" go in opposite directions in the rock-paper-scissors cycle.

Can they do better?

No. 8/9 is optimal as argued by tehtmi -- in summary, the expected net win-loss score is zero, so at best they can counterbalance net +1 score 8/9 of the time with -8 score (all losses) 1/9 of them time.

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ @FirstNameLastName the "warm-up strategy" just demonstrates the concept that picking some S in that way enables everyone to coordinate an answer (in that case the correct one). In the case where it is not 0, they lose by some amount. The real strategy instead gets them all to lose on 0, while eking out a win on 1 and 2 $\endgroup$ Commented Sep 15 at 16:03
  • 1
    $\begingroup$ This strategy extends nicely to the next tiers at 26, 80 and so forth (n x 3 + 2), each time reducing the loss probability by a factor of 3. I wonder, is there any way to do better in between? Are odd numbered Ns salvageable? $\endgroup$ Commented Sep 15 at 17:08
  • 1
    $\begingroup$ One useful component for more general solutions might be that a generalization of the n=2 and n=6 strategies in the solution allows getting 1/3 chance of each of the total scores a/b/c for any numbers with a+b+c=0, using a number of players equal to the max(abs(a),abs(b),abs(c)). $\endgroup$ Commented Sep 15 at 20:04
  • 1
    $\begingroup$ @nitrodon In the 3 person case, If Bart always picks rock, then his wins and ties do nothing to improve the team's performance, while his losses kill the wins. This gives us a 4/9 chance of winning, which isn't great $\endgroup$ Commented Sep 15 at 21:43
  • 2
    $\begingroup$ @kagami: In the 3 person case, the two non-Bart players will choose their strategy based on Bart's hat. Ie, if Bart wins, they neutralize (p=1), if Bart ties, they play the normal two-player strategy (p=2/3), and if Bart loses, they shoot for two wins (p=1/3). End result is 2/3. $\endgroup$ Commented Sep 16 at 5:36
15
$\begingroup$

To get things rolling here is a strategy to win

2 out of 3 times.

in the two player case. This serves as a lower bound for the 8 player scenario because we can "neutralise" any even number of excess players by pairing them up and have each player choose what they can read on their partner's hat.

The two player strategy is to choose

what loses to what's on the other player's hat.

If the players happen to have the same thing on their hats they will lose 0:2. If what's on their hats is different then one will draw, the other will win, so the team will win. As the second scenario is twice as likely as the first the claimed collective win rate is achieved.

Improve this answer
$\endgroup$
11
  • 1
    $\begingroup$ Wouldn’t your strategy extended to, say, 4 players give the probability of winning as 4/9 instead of 2/3? When you pair them up as you said, there are three possibilities. Both pairs lose with probability 1/9, that’s a team loss. One pair loses while the other wins with probability 4/9, but that’s still a team loss because in such a scenario, the number of wins is 1 and the number of losses is 2. Finally, both pairs win with probability 4/9, which is a team win. $\endgroup$ Commented Sep 14 at 21:51
  • 1
    $\begingroup$ @FirstNameLastName Here is my own simulation: ato.pxeger.com/… $\endgroup$ Commented Sep 15 at 0:32
  • 1
    $\begingroup$ I see. I just saw your code and there you say “…any even number of excess players can be…”. I added that word to your answer. That was really the source of my confusion. I see what you mean by “neutralize” now. $\endgroup$ Commented Sep 15 at 0:36
  • 2
    $\begingroup$ @FirstNameLastName Their strategy is to always pick what loses to what they see on their partner's hat. $\endgroup$ Commented Sep 15 at 0:44
  • 1
    $\begingroup$ OH! that is an interesting boolean difference ! I misread or misinterpreted, what wins :) $\endgroup$ Commented Sep 15 at 0:45
9
$\begingroup$

Quick upper bound of

8/9

Because:

If we imagine all the 3^8 hat configurations, and look at all the 8*3^8 rock-paper-scissors matches, then no matter what, 1/3 of the matches will be wins, 1/3 will be ties, and 1/3 will be losses. (Consider 1 player. For each configuration of the other 7 players' hats, they will contribute one of each result as their own hat varies. Thus it follows.) We can then relax the problem by imagining we could assign the r-p-s results to the matches arbitrarily. To maximize the number of net-winning configurations, we are basically gerrymandering. In each net losing configuration, we may as well make everyone lose. It turns out with 3^6 configurations using 8 losses each, the remaining configurations could all win by 1 e.g. with 3 wins, 3 ties, and 2 losses each. (This is not the only way, but you have to win by 1 in each winning configuration to achieve this 8/9.) If you had fewer losing configurations, it doesn't work out as there are no longer enough wins to cover all the losses in all the remaining configurations. So, this is an upper bound. I don't know yet if it is achievable.

Best I have achieved so far (lower bound, probably not optimal) is:

5286/6561 or just over 80%

This is done by:

A disorganized strategy (I wouldn't know how to characterize it except by the method of finding it or else the listing of what guesses should be made by each player in each scenario which is not particularly human-readable) found by a greedy search -- we can assign r-p-s choices to a particular player in a particular configuration sort of like what is discussed above, except whenever we assign a choice, we have to also assign the same choice to the two other configurations that look the same to the player we are assigning a choice for. Then to do the greedy search, we simply go through each configuration, and if the already-made choices have enough slack to allow a win, we try to win by exactly 1 or else as little as possible. If a win is not possible, we make all unassigned players in the configuration lose in order to lose by as much as possible. The unspecified details such as how exactly to make a winner as well as the order of iteration may matter, so here is my (hopefully bug-free, sorry it wasn't really written to share) code. Addendum: I was able to make some minor improvements by trying to get wins-by-one with at least 3 wins where possible, and to more aggressively make 8-lose configurations.

Improve this answer
$\endgroup$
4
$\begingroup$

It's not clear to me how much this overlaps with FirstName LastName, but I feel that a good strategy for a large number of players is

safety in numbers i.e. assume that one's hat is the same as the most popular hat in the ones that can be seen. (Tie-breaking rules to follow).

This means that

In any situation where there the most popular hat appears at least two times more than the second most popular hat, we win. e.g. if there are 100 contestants and the hats are 36 paper, 34 scissors and 30 stone then everyone assumes that their hat is paper; they shout "scissors" and the score is 36 wins, 30 losses and 34 draws.

Things do not go our way if

there is a tie for the most popular hat. In this case we always fail e.g. if there are 34 paper, 34 scissors and 32 stone the people with paper hats will assume that they have scissors hats; the people with scissors hats will assume that they have paper hats (the people with stone hats do something not yet specified, but we have already racked up 34 losses and 34 draws).

Well also need to consider

What happens when there is exactly one more of the most popular hat than the second most popular. Here we can use a tiebreaker to say that if anyone views a two-way tie for the most popular hat they assume that they have the "winner" hat (i.e. for a paper-scissors tie assume scissors; a scissors-stone tie assume stone; a stone-paper tie assumee stone) and for a three way tie choose paper.

This would mean that

When there are $n$ paper hats and $(n-1)$ scissors hats and fewer than $(n-1)$ stone hats we lose, but when there are $n$ scissors hats, $(n-1)$ paper hats and fewer than $(n-1)$ stone hats we win. (Similarly winning half of other $n,n-1,n>$ cases and one third of $n,n-1,n-1$ cases).

Mathematically, if we have $m$ players the count of losing cases is

$$3\sum_{m/3<n\le m/2}\frac {m!}{(n!)^2(m-2n)!}+3\sum_{m/3< n<m/2}\frac{m!}{(n-1)!n!(m-2n+1)!} $$ out of $3^m$ possible arrangements of hats. (With an extra $2(3k+1)!/(k!)^2(k+1)!$ term when $m=3n+1$). If you prefer binomial coefficients to factorials, the above expression is $$3\sum_{m/3<n\le m/2}\binom{2n}{n}\binom m{2n}+3\sum_{m/3\le n<m/2}\binom{2n-1}n\binom m{2n-1} $$

My intuition is

that the proportion of losing cases will tend to zero as $m\to\infty$.

A little sagemath gives

a loss rate of 41.6% when $m=8$, a loss rate of 14.7% when $m=100$, and a loss rate of 4.6% when $m=1000$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Is this the opposite of Albert.Lang’s strategy for two people? $\endgroup$ Commented Sep 15 at 1:26
  • 1
    $\begingroup$ Yes, I missed the bit where there are 8 players. The above may not work well for small $m$ $\endgroup$ Commented Sep 15 at 1:29
2
$\begingroup$

Partial answer:

Key insights:

  1. No matter what strategy the players choose, they have no information about their own hat. The chances for each player are $\frac{1}{3}:\frac{1}{3}:\frac{1}{3}$ (win : draw : lose).

  1. Therefore, the only way to increase the chances for an overall win is to correlate their results. This is explained for 2 players in Albert.Lang's answer. In particular, one maximizes the chance to lose simultaneously, while maintaining the overall $\frac{1}{3}:\frac{1}{3}:\frac{1}{3}$ distribution. The chosen strategy eliminates the $(2:0:0)$ and the two $(0:1:1)$ scenarios out of the set of $\{ (2:0:0), 2 \times (1:1:0), 2 \times (1:0:1), 2 \times (0:1:1), (0:0:2) \}$. The symmetry is that removing certain scenarios is only possible if the sum of wins, draws and losses is equal, otherwise this would contradict the fact that each player has chances of $\frac{1}{3}:\frac{1}{3}:\frac{1}{3}$.

  1. I don't know yet what the optimal strategy is, but one can set an upper bound to what is possible. If any strategy reaches this bound, there is no strategy which performs better.
    We can find the optimal chance of a team victory by starting with the full set of possible outcomes and then eliminating some of them by "trading in" some of the scenarios with an unnecessarily high number of individual wins for some where the team lost by a narrow margin.
    Optimizing this sounds like a lot of work and it's already later than I wanted to stay awake, so I'm going to pause here.

Improve this answer
$\endgroup$
0

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.