Optimal Strategy of guessing numbers

game theoryprobability

The question is related to this question. Consider the following game:

Player A chooses a random integer between 1 and 100, with probability pj of choosing j (for j=1,2,…,100). Player B guesses the number that player A picked, and receives from player A that amount in dollars if the guess is correct (and 0 otherwise).

One can derived that the optimal strategy is choosing $j$ with probability proportional to $\frac{1}{j}$. My question is, how can I derive the weight $\frac{1}{j}$?

What I tried is, let assume the probability distribution of Player A and B choosing j to be $p^a_j,p^b_j$ respectively. Then the expected payoff $P_B$ of player B is:$$E[P_B] = \sum_{j = 1}^{100}p^a_jp^b_jj.$$
Now I want to make this quantity independent from $j$, how does that lead to $\frac{1}{j}$?

Best Answer

I won't take the bait of your using superscripts which look like exponents (I once caused a debate in the British House of Lords over this point). Let's instead use $p_j$ for A's distribution and $q_j$ for B's distribution. Then the expectation of B's gain would be written $\sum\limits_{j=1}^n p_jq_j j $

Suppose there are two values $x$ and $y$ where A has probabilities $p_x$ and $p_y$ adding up to $r$. If B's probabilities for these are $q_x$ and $q_y$ with a fixed sum $q_x+q_y=k$ then, from $x$ and $y$, B's expected gain is $p_x q_xx+p_yq_yy$ and

  • if $p_x x < p_y y$ then B maximises the expectation by having $q_x=0, q_y=k$
  • if $p_x x > p_y y$ then B maximises the expectation by having $q_x=k, q_y=0$
  • if $p_x x = p_y y$ then then any strategy by B gives the same expectation for all possible $q_x,q_y$ and this is lower than the maximised expectations in the previous two points

and

  • if $q_x x < q_y y$ then A minimises the expectation by having $p_x=r, q_y=0$
  • if $q_x x > q_y y$ then A minimises the expectation by having $p_x=0, q_y=r$
  • if $q_x x = q_y y$ then then any strategy by A gives the same expectation for all possible $p_x,p_y$ and this is higher than the minimised expectations in the previous two points

The first three of these point to A optimally choosing $p_x x = p_y y$ to prevent B increasing the expectation and the second three point to B optimally choosing $q_x x = q_y y$ to prevent A reducing the expectation. But this is true for all possible distinct $x$ and $y$, so $p_j j$ and $q_j j$ must each be constant across $j$, leading to the "proportional to $\frac1j$" conclusion. This implies $p_j =q_j = \frac1{jH_n}$ where $H_n$ is the harmonic number $H_n=\sum\limits_{j=1}^n \frac1j$, about $5.187$ when $n=100$.

If you merely wanted to show that a "proportionate to $\frac1j$" strategy leads to indifference by the other player, suppose B sets $q_j$ proportional to $\frac1j$, i.e. $q_j = \frac1{jH_n}$. Then $q_j j = \frac1{H_n}$ and $\sum\limits_{j=1}^n p_jq_j j = \sum\limits_{j=1}^n p_j\frac1{H_n} = \frac1{H_n}$ so the expected outcome is unaffected by A's strategy.

Similarly, if A sets $p_j$ proportional to $\frac1j$, i.e. $p_j = \frac1{jH_n}$, then $p_j j = \frac1{H_n}$ and $\sum\limits_{j=1}^n p_jq_j j = \sum\limits_{j=1}^n q_j\frac1{H_n} = \frac1{H_n}$ so the expected outcome is unaffected by B's strategy. So the principle of indifference confirms this is an optimal strategy for each player.

Related Question