Question 3.4 from Joshi's book

[fastrack]

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?


The books explains:
The solution is to pick k with probability proportional to 1/k. We therefore pick k with probability
(1) \(\frac{1}{k} (\sum\limits_{j=1}^{100} \frac{1}{j})^{-1}\)

Our expected payout is then

\((\sum\limits_{j=1}^{100} \frac{1}{j})^{-1}\)


Can someone explain how Joshi arrives at (1)?

 

[ferdia]

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?


The books explains:
The solution is to pick k with probability proportional to 1/k. We therefore pick k with probability
(1) \(\frac{1}{k} (\sum\limits_{j=1}^{100} \frac{1}{j})^{-1}\)

Our expected payout is then

\((\sum\limits_{j=1}^{100} \frac{1}{j})^{-1}\)


Can someone explain how Joshi arrives at (1)?

You want to pick \(k\) with probability proportional to \(\frac{1}{k}\), so \(\mathbf P(k)=\frac{C}{k}\) for some constant \(C\). You must however make sure that all probabilities add up to \(1\), so
\(1=\sum\limits_{j=1}^{100} \mathbf P(j)=C\sum\limits_{j=1}^{100}\frac{1}{j}\implies C=\large(\sum\limits_{j=1}^{100} \frac{1}{j}\right)^{-1}\), so you pick \(k\) with probability \( \frac{1}{k}\large(\sum\limits_{j=1}^{100} \frac{1}{j}\right)^{-1}\)

 

[Karth]

I'm a little confused by this question -- could you explain why the probability of choosing n should be proportional to 1/n? The question seems underconstrained, since there isn't any prior distribution on how you choose n from 1 to 100.

 

[ferdia]

The person who sets up the game wants to pick the numbers so that there is no strategy the player can employ to earn more than if he were to use any other strategy. If he didn't pick \(k\) with probability proportional to \(\frac{1}{k}\), there would be at least one \(k\) which is chosen with probability greater than \(\frac{1}{k}\). We can choose a \(k\) like this such that \(k\) times this probability is maximal. It should now be clear that in this case the player's optimal strategy is consistently choosing the number \(k\) and this strategy outperforms the other strategies. So if the person running the game wants to avoid this, he picks \(k\) with probability \(\frac{1}{k}\large(\sum\limits_{j=1}^{100}\frac{1}{j}\right)^{-1}\), giving an expected payout (if the player picks \(k\) with probability \(p_k\)) of \[\sum\limits_{k=1}^{100} p_kk\frac{1}{k}\large(\sum\limits_{j=1}^{100}\frac{1}{j}\right)^{-1}=\large(\sum\limits_{j=1}^{100} \frac{1}{j}\right)^{-1}\sum\limits_{k=1}^{100} p_k=\large(\sum\limits_{j=1}^{100} \frac{1}{j}\right)^{-1}\]
which is independent of the player's strategy. This being the expected payout, the player will not want to pay more than this to play the game.

 

[Karth]

This argument assumes that this game is completely observed though - namely, that we know the adversary's strategy. Is this ok to assume?

If we were not aware of the adversary's strategy, then isn't it totally reasonable for the adversary to choose some other distribution over the payoffs?

 

[ferdia]

If I recall correctly, Joshi says in his book that you should assume, given an interview question like this, that the strategies are optimal.

If the adversary's idea of optimality is as described in the post above (expected payout is independent of player's strategy), what reason do we have to think that he will choose a different distribution? I agree that the adversary may choose other distributions if he has other ideas of optimality.