Q 3.4

This forum is for discussing our interview question book. If you want the answer to a follow-up question or to dispute the solutions, this is the place to ask.

Q 3.4

I dont think I understand this question. If the amount that I pay is predecided, then my opponent can always think of a number less than that. Say I say I will pay x to play the game, my opponent can think of the number x-1 (or lower).

And if my opponent cant decide after i say what i will pay, then shouldnt i be paying just 50.5?
f0X_in_s0X

Posts: 86
Joined: Tue Dec 04, 2007 5:47 pm

the amount that would be paid out is decided before, but not revealed.

The possible payout is the number that opponent has in mind, so it's not like when you are throwing a dice or something (where it's assumed uniformly distributed, that's your answer 50.5)

The opponent tries to think of the smallest number possible (because this is the amount he has to pay if you guess correctly) but on the other hand if he chooses number too small then he's increasing probability of paying out.
quant

Posts: 31
Joined: Wed May 28, 2008 5:53 pm

thanks a lot !!
f0X_in_s0X

Posts: 86
Joined: Tue Dec 04, 2007 5:47 pm

But if the probability of choosing 'k' is
P(k) = 1/k * [sum(j,1,100) (1/j)]^-1

then isnt the expected payout equal to

100 * [sum(j,1,100) (1/j)]^-1 instead of just [sum(j,1,100) (1/j)]^-1

(by taking the expectation, i.e, sum(k,1,100) [k*P(k)]
f0X_in_s0X

Posts: 86
Joined: Tue Dec 04, 2007 5:47 pm

no, again, it's not like you are throwing a dice where you get paid whatever the result.

In this game you get paid only if you guess correctly, and the correct one is only one out of all 100.

If the expected payout were n * [sum(j,1,n) (1/j)]^-1, which is increasing and going to infinity, the expected payout would be increasing with n, which clearly cannot be the case.
quant

Posts: 31
Joined: Wed May 28, 2008 5:53 pm

I get it now. The comparision with the dice was very useful. Thanks :)
f0X_in_s0X

Posts: 86
Joined: Tue Dec 04, 2007 5:47 pm

I thought that this was a very nasty problem. I got the solution from a colleague who teaches game theory...
mj

Posts: 1380
Joined: Fri Jul 27, 2007 7:21 am

could anyone please explain how the [sum(j,1,100)(1/j)]^(-1) comes up? thx!

mj wrote:I thought that this was a very nasty problem. I got the solution from a colleague who teaches game theory...
woodeasy

Posts: 5
Joined: Wed Jul 30, 2008 9:26 pm
Location: UK

You take the probability of choosing k to be proportional to 1/k.

P (num chosen = k) = alpha * 1/k

To find alpha, u use sum(k,1,100) P (num chosen = k) = 1;

Thats how you get alpha in that form. so

P(k) = 1/k * [sum(j,1,100) (1/j)]^-1
f0X_in_s0X

Posts: 86
Joined: Tue Dec 04, 2007 5:47 pm

got it, thanks a lot!

f0X_in_s0X wrote:You take the probability of choosing k to be proportional to 1/k.

P (num chosen = k) = alpha * 1/k

To find alpha, u use sum(k,1,100) P (num chosen = k) = 1;

Thats how you get alpha in that form. so

P(k) = 1/k * [sum(j,1,100) (1/j)]^-1
woodeasy

Posts: 5
Joined: Wed Jul 30, 2008 9:26 pm
Location: UK

Re: Q 3.4

You take the probability of choosing k to be proportional to 1/k.

P (num chosen = k) = alpha * 1/k

To find alpha, u use sum(k,1,100) P (num chosen = k) = 1;

Thats how you get alpha in that form. so

P(k) = 1/k * [sum(j,1,100) (1/j)]^-1

It is not immediately clear to me why you would take the probability of choosing k to be proportional to 1/k, instead of 1/sqrt(k), k^(-2), exp(-k) or any other monotonically decreasing convex function. Am I missing something?
will0t5

Posts: 3
Joined: Sun May 09, 2010 7:17 pm

Re: Q 3.4

The intuition is that the expected pay-out from each state is the same.
mj

Posts: 1380
Joined: Fri Jul 27, 2007 7:21 am

Re: Q 3.4

will0t5 wrote:
You take the probability of choosing k to be proportional to 1/k.

P (num chosen = k) = alpha * 1/k

To find alpha, u use sum(k,1,100) P (num chosen = k) = 1;

Thats how you get alpha in that form. so

P(k) = 1/k * [sum(j,1,100) (1/j)]^-1

It is not immediately clear to me why you would take the probability of choosing k to be proportional to 1/k, instead of 1/sqrt(k), k^(-2), exp(-k) or any other monotonically decreasing convex function. Am I missing something?

if you start with thinking of the simplest case where there are only 2 numbers to choose (instead of 100), then it is clear to choose k to be proportional to 1/k, so that your opponent can not exploit by choosing any of 1 or 2 (i.e. the expectations of choosing 1 or 2 for your opponent are the same). When the 3rd number 3 is added, you should mix all the three choices so that the expectations of your opponents of choosing 3, which is 3, and not choosing 3 (reduced to the 2 number case) are the same. This choice should be proprotional to 1/k. and then you can add more numbers.
feifeipig

Posts: 5
Joined: Fri May 28, 2010 6:07 am

Re: Q 3.4

It took me a hour or so to figure out why it is optimal to choose k with probability 1/k.

• The equilibrium mixed strategies are computed as following. We assume player 2 plays the strategy i with probability p_i and require that the player's 1 reward from playing strategy k is the same. Then we reverse the players. If the payoff matrix has size nXn we have 2n +2 unknowns and 2n + 2 equations.
• The payoff matrix P1 for the first player has the cost (X) everywhere except for the diagonal. On the diagonal we have X-1, X-2, ..., X-n. We have a zero sum game and the payoff matrix for the second player P2 equals -P1.
• It is not difficult to see that adding a number to the payoff matrix does not change the relative ordering of the payoffs. In particular, the optimal strategy remains the same. Hence we can consider the game with X=0 to figure out the optimal strategy.
• The condition that the first player is indifferent between the strategies when the second player chooses strategy k with probability p_i reads -i*p_i = const because the off diagonal elements are zero when X=0.
• Since the payoff matrix is symmetric the argument for the second player is the same. Hence it is optimal for both players to choose k with the probability proportional to 1/k.
aickley

Posts: 1
Joined: Thu Oct 27, 2016 11:00 am

Re: Q 3.4

Thanks to the awesome work of aickley, I draw the game's payoff matrix and finally got the closed form solution I was looking for (equations attached).

Below is a very detailed step-by-step of my solution because I actually ended up having a different result than that presented as the solution in the book.

• a mixed strategy consists in assigning probabilities to all possible actions such that the other player is indifferent among all her actions;
• player 1 (P1)'s optimal strategy is to randomise, since always picking the smallest value would not generate any gain;
• since the game is symmetric (zero sum), the vector of probabilities we derive for P1 when piking a number will also be (part of) the equilibrium guessing strategy for player 2 (P2);
• let k represents the number P1 chooses and pi_k its respective probability;
• let x represents the cost/value of the game;
• P1 will choose each number k with a certain probability that would make P2's expected value of guessing any number exactly the same;
• the expected value of P2 guessing a number k will then be given by equation (1) attached;
• equating this to the expected value of choosing (any other number, say) k+1 leads to a relationship between the probabilities given by equation (2);
• it's straightforward to re-write this equation in terms of k=1 (and pi_1) as in equation (3) which shows how each probability pi_k is proportional to 1/k:
f0X_in_s0X wrote:P (num chosen = k) = alpha * 1/k

• now we use the fact that the sum of the probabilities assigned to each number equals 1 to get equation (4) and calculate pi_1=0.1928 -> here I diverge from the book's solution...;
• finally, we calculate the expected value of the game as in equation (6) which is simply the product of each P2's guess expected value (each column) times the probability of guessing that number;
• making use of the fact that in a mixed strategy equilibrium the expected value of every action is the same (that's the intuition of randomising), we replace the expected value of any action to be that of guessing k=1, which is easy to derive from equation (1);
• we also replace pi_k for equation (3) and then the summation of 1/k for 1/pi just like derived in equation (4);
• at last, we get x=pi/2 or \$0.096

equations.png (40.42 KiB) Viewed 273 times

aickley wrote:It took me a hour or so to figure out why it is optimal to choose k with probability 1/k.

• The equilibrium mixed strategies are computed as following. We assume player 2 plays the strategy i with probability p_i and require that the player's 1 reward from playing strategy k is the same. Then we reverse the players. If the payoff matrix has size nXn we have 2n +2 unknowns and 2n + 2 equations.
• The payoff matrix P1 for the first player has the cost (X) everywhere except for the diagonal. On the diagonal we have X-1, X-2, ..., X-n. We have a zero sum game and the payoff matrix for the second player P2 equals -P1.
• It is not difficult to see that adding a number to the payoff matrix does not change the relative ordering of the payoffs. In particular, the optimal strategy remains the same. Hence we can consider the game with X=0 to figure out the optimal strategy.
• The condition that the first player is indifferent between the strategies when the second player chooses strategy k with probability p_i reads -i*p_i = const because the off diagonal elements are zero when X=0.
• Since the payoff matrix is symmetric the argument for the second player is the same. Hence it is optimal for both players to choose k with the probability proportional to 1/k.
vdan

Posts: 1
Joined: Wed Sep 12, 2018 2:09 pm