10
$\begingroup$

This is from Mark Joshi's classic book. The full question is:

"I pick a number n from 1 to 100. If you guess correctly, I pay you $n and zero otherwise. How much would you pay to play this game?"

Joshi offers a solution, but I am struggling with it. From what I understand, the person picking the number has incentive to pick lower numbers as this will result in lower payoffs. However, low numbers will likely be selected by the player so the number should not be too low. Joshi suggests the following as the expectation of the game:

$$\Big(\sum_{i=1}^{100}\frac{1}{i}\Big)^{-1}$$

Not sure if anyone could with the intuition on how the solution was obtained. I guess it arises as the initial person picking the number should pick with decaying probability going from 1 to 100?

Thanks

$\endgroup$
14
$\begingroup$

The intuition is that in an optimal strategy, the picker should be indifferent to what the guesser chooses.

Suppose we just take $n=3$ for simplicity. Suppose the picker chooses $1$ with probability $p_1$, chooses $2$ with probability $p_2$, and $3$ with probability $p_3$. The selection of $p_1, p_2, p_3$ constitutes the picker's strategy.

The indifference criterion means that $1p_1=2p_2=3p_3$. However, also $p_1+p_2+p_3=1$. To solve, plug in and get $$p_1+\frac{1}{2}p_1+\frac{1}{3}p_1=1$$ Hence, $p_1=(1+\frac{1}{2}+\frac{1}{3})^{-1}$. This is also the average amount that the guesser wins, regardless of which number guessed. This is also the expected value of the game.

$\endgroup$
7
  • 1
    $\begingroup$ You are saying optimal $p_n$ for the picker is $\dfrac{1}{n \sum_i \frac1i}$. It is worth adding that a similar argument gives the same optimal probabilities for the guesser $\endgroup$
    – Henry
    May 29 '19 at 17:31
  • 1
    $\begingroup$ The expectation is $1p_1=2p_2=3p_3$, which happens to equal $p_1$. $\endgroup$
    – vadim123
    May 30 '19 at 3:37
  • 1
    $\begingroup$ @vadim123 Why would the expectation is $1p_1 = 2p_2 = 3p_3?$ $\endgroup$
    – Idonknow
    Feb 12 '20 at 2:02
  • 1
    $\begingroup$ @Idonknow: from the statement that the picker is indifferent to what the guesser chooses. If the guesser always chooses $1$ the expectation is $p_1$ because the picker receives $1$ a fraction $p_1$ of the time and nothing the rest of the time. If the guesser always chooses $2$ the expectation is $2p_2$. $\endgroup$ Feb 12 '20 at 4:19
  • 1
    $\begingroup$ Your argument basically finds the value of $p_1$, the probability that the Picker will assign to the number 1. Why this value should be taken as the "expectation of the game", as the question asks and why as you say this is also the average value that the Guesser wins, it is not clear at all. $\endgroup$
    – RandomGuy
    Jun 18 '20 at 7:30
5
$\begingroup$

Here is a rigorous justification for the answer. First, note that this is a zero-sum game - my gain is the negative of your loss. It's clear that I should never play a deterministic strategy - you can simply play adversarially by always avoiding my deterministic guess. Should you play deterministically? It's not clear yet, but if you are ever going to play a deterministic strategy, that strategy has to always play 1, since that minimizes my gain/your loss. Then let's think about randomized strategies - is there a randomized strategy that is better for you than always playing 1? A randomized strategy for a player is just a probability distribution according to which the player either picks or guesses the number. Let my strategy $P$ be $<p_1,...,p_{100}>$, where $p_i$ denotes the probability that I guess $i$. Now there is a result in game theory that says that in a 2-player zero-sum game, to calculate player A's optimal strategy, we can examine each of player B's deterministic strategies, calculate the payoff of A, and maximize the minimum of those payoffs. (another result is that in a 2-player zero-sum game, if both players play optimally, then they can publish their strategies and it would not affect the expected payoff, which is why I assume that both players know the other play's strategy). You have 100 deterministic strategies. If you always play 1, then my exp. payoff is $p_1$; if you always play 2, then my exp. payoff is $2p_2$; ...; if you always play $i$, then my exp. payoff is $ip_i$. Thus, I want to maximize the minimum among $p_1,2p_2,...,100p_{100}$, subject to $p_1+p_2+...+p_{100}=1$, and all $p_i\geq 0$. Clearly we should set them equal, and that gives $$p_k=\frac{1}{k}\frac{1}{\sum_{i=1}^{100}\frac{1}{i}}$$ The payoff is then $$\frac{1}{\sum_{i=1}^{100}\frac{1}{i}}$$ By the way, this is lower than 1, so you should not play deterministically.

$\endgroup$
6
  • $\begingroup$ How do we obtain $q_k$? Where does the 1/k factor come from? $\endgroup$ Aug 4 '20 at 14:55
  • $\begingroup$ Sorry I meant $p_k$. $p_k$ is obtained by setting $p_1=2p_2=3p_3=...=100p_{100}$. Does this help? $\endgroup$ Aug 4 '20 at 17:41
  • $\begingroup$ Yes its more clear! $\endgroup$ Aug 8 '20 at 3:04
  • $\begingroup$ I like this answer, but I am a little confused by what is meant by "You have 100 deterministic strategies." "You" here indicates the person picking the number, and not the guesser, I assume. Why is it deterministic if there's a probability distribution? $\endgroup$
    – roulette01
    Mar 29 at 15:36
  • $\begingroup$ Indeed, "you" is the person that picks the number, and "I" is the guesser. The picker has 100 deterministic strategies - each one of them of the form: "always pick $i$" for some integer $i$ between 1 and 100. The guesser's strategy is $<p_1,..., p_{100}>$, not the picker's strategy. Does this help? $\endgroup$ Mar 29 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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