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
and
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.