7
$\begingroup$

Five people each announce a number in turn. The number must be an integer in the range from $1$ to $100$, and different from the ones already announced by others. The winner (or winners) of the game is the person who's number is closest to half of the average of the five numbers. We assume that all people have sufficient calculating and reasoning capabilities, and will randomize between equally optimal choices.

What number should the first person announce?

$\endgroup$
8
  • $\begingroup$ Does "randomize between equally optimal choices" mean that if I have N equally (sub)optimal cases, I have 1/N probability to pick each? $\endgroup$ Jun 7, 2022 at 13:48
  • $\begingroup$ @JLee Yes, rationality is common knowledge. Announcements are heard by all. $\endgroup$
    – Eric
    Jun 7, 2022 at 14:05
  • $\begingroup$ @GeorgeMenoutis Yes, if each of the N numbers leads you to the same optimal winning probability, then each is picked up with 1/N probability. $\endgroup$
    – Eric
    Jun 7, 2022 at 14:08
  • 4
    $\begingroup$ It seems like we need to know how players act when they have no chance of winning. I.e. a=1, b=2, c=3, and d=4. E cannot win, but has the power to pick the winner by his choice. $\endgroup$
    – JLee
    Jun 7, 2022 at 17:03
  • 2
    $\begingroup$ I'm assuming that a player with no chance of winning will just pick randomly, given that they "will randomize between equally optimal choices." $\endgroup$
    – SQLnoob
    Jun 7, 2022 at 17:46

2 Answers 2

6
$\begingroup$

I ran a computer program, brute-forcing through all possibilities. Assuming my program is correct, the best choice for the first player is

6, giving them a probability of 31/96 to be a winner.

After this, play continues with

11 for the second player, giving them a 30/96 probability of being a winner.
8, 9, or 10 for the third player, each giving probability 26/96.
3 for the fourth player, with a probability between 11/96 and 13/96 depending on the third player's choice.
Fifth player cannot win, so chooses any remaining number at random.

Note that the probabilities add to more than 1 since there can be more than one winner.

Obviously, if the last player has a winning move, they will choose it. For any of the first players to win, they need to choose numbers such that player five's winning move is already taken.

This usually forces player four's move. Player four must choose the number that player five would want to play. So it must be such that if five played the same then it is about half the average. A little algebra shows that it should be (a+b+c)/8, where a,b,c are the moves of the first three players. In the optimal playing sequence above that is indeed the case.

I have only a rough explanation for the first three plays. The fifth player's random choice can shift the half-average by about 10. So ideally the first three moves should cover most of such a range about equally, forcing the fourth player to accept a smaller cut at the low end of the range.

My program previously counted shared wins differently, by spreading the probability amongst them. This is equivalent to one of the winning players being chosen at random to be the sole winner of the round. If that variation of the game is used, then play is slightly different.

Player one plays 11 first, then player two chooses 6 or 7, player three has a few more choices in the 5-10 range, and then player four still chooses 3.

$\endgroup$
3
  • $\begingroup$ This seems plausible. I assumed the first player would want to choose a really really low number, but intuitively suspected 1 was not optimal, just wasn't sure how much higher would satisfy the need to be low but also capture a larger share of the higher results from cases where later players choose randomly in situations they couldn't win. $\endgroup$
    – SQLnoob
    Jun 7, 2022 at 18:17
  • $\begingroup$ I assume you meant to measure the fourth player's probability of winning in rot13(AVARGL-fvkguf vafgrnq bs gjragl-fvkguf?) $\endgroup$ Jun 7, 2022 at 21:51
  • $\begingroup$ Can you add your code to the answer, or add some explanation about how the program works to solve the puzzle? $\endgroup$
    – Eric
    Jun 8, 2022 at 7:40
1
$\begingroup$

A stab at the solution:

Call the people $A, B, C, D,$ and $E$, respectively. Working backwards, $E$'s best guess will be the integer closest to the sum of the previous four numbers divided by $9$. This is because he wants to minimize the distance between his own number and half the average of all five numbers, so essentially he wants to solve for:

$(A+B+C+D)/10 + E/10 - E = 0$

$(A+B+C+D)/10 - 9E/10 = 0$

$(A+B+C+D) = 9E$

$(A+B+C+D)/9 = E$

Of course, $D$ knows this and therefore, using similar logic, wants to choose the integer closest to the sum of the previous three numbers divided by $8$. Similarly, $C$ wants to choose the sum of $A$ and $B$ divided by $7$, and finally $B$ wants to choose as close as possible to $A/6$.

Knowing all this, $A$'s best shot at winning is by choosing as low a number as possible - I initially assumed this meant $1$, but I actually think he does slightly better by choosing $2$ instead. $B$'s best option in that case is to choose $1$. $C$ can't win at that point, so will choose randomly (?), in which case $D$ can probably pick a winning number, but if $C$ chooses low enough then $A$ can still win.

I'll try to simulate the results and see if it supports this conclusion, but that's my initial impression of the problem.

Thoughts given @Jaap Scherphuis simulation posted in another answer:

Perhaps it's unsurprising that he found $A = 6$ to be an optimal starting point, since my naive calculation above estimates that $B$'s best choice is $A/6$ and the lowest $B$ can possibly guess is $1$, so $A$ choosing as high as $6$ doesn't influence $B$'s choice at all and allows $A$ to capture more of the upside from the later players randomly choosing much higher numbers when they can't win? Of course, by that reasoning, $A$ could go as high as $8$ so I'm not sure that logic stands up to scrutiny, just thought it was an interesting possible relationship. I'm still thinking of how to get a non-brute-forced proof, not sure how feasible that is given the sheer number of possible permutations.

$\endgroup$
3
  • $\begingroup$ Brute force from the 1st person's perspective gives 21 as the sweet spot. I am running it for the other 4 and will compare to see what each person's strategy should be, knowing that there is common knowledge of rationality. $\endgroup$
    – JLee
    Jun 7, 2022 at 15:41
  • $\begingroup$ I don't see how the 1st person could ever win with a guess of 21. He'll immediately be undercut by a much lower number. $\endgroup$
    – SQLnoob
    Jun 7, 2022 at 16:11
  • $\begingroup$ that is brute force of all possible games, disregarding any strategy at all, just as a baseline. $\endgroup$
    – JLee
    Jun 7, 2022 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.