Game Theory / Probability Interview question

Question

Got this for an interview and didn't get it. How to solve?

You and your opponent have a uniform random sampler from 0 to 1. We both sample from our own machines. Whoever has the higher number wins. The catch is when you see your number, you can resample. The opponent can re sample once but you can resample twice. What’s the probability I win?

My not-confident-at-all approach: For each player you come up with a strategy that revolves around the idea of “if this number is too low, resample.” you know that for myself, I have three samples, and the EV of the third sample is 1/2. So for the second sample, if it’s below 1/2, you should resample; if above 1/2, do not resample. And you do this for the first sample with a slightly higher threshold. And then assuming our player is opponent they will follow the same approach, but they only have two rolls.

No matter what, we know the game can end with six outcomes: it can end with me ending on the first, second, or third sample, and them ending on the first or second outcome. We just condition on each of those six cases and find the probability that my roll is bigger than their roll on that conditional uniform distribution.

Answer 1

Let's look at the single player game which is that I have a budget of $n$ total rolls and I want to come up with a strategy for getting the biggest roll in expectation.

For $k\leq n$, let us look at what happens from $k$ rolls. Now if we think of each of the rolls $R_1,R_2,\dots,R_k$ as being independent draws from the uniform distribution and we define a new random variable $X:=\max\{R_1,R_2,\dots,R_k\}$, we see that for an arbitrary $x\in[0,1]$, the probability that $X$ is smaller or equal to $x$ is $\mathbb{P}(X\leq x)=\mathbb{P}(R_1\leq x, R_2\leq x,\dots R_k\leq x)=\prod_{j=1}^k \mathbb{P}(R_j\leq x)=\prod_{j=1}^k x=x^k$.

This is clearly the cumulative distribution function of $X$, so we can differentiate that to get the density of $X$, which will obviously be $f_X(x)=kx^{k-1}$. This discussion can also be found with a bit more detail here: https://stats.stackexchange.com/questions/18433/how-do-you-calculate-the-probability-density-function-of-the-maximum-of-a-sample

But if we have the density function, we can immediately compute the expected value of $X$, which will be $\mathbb{E}[X]:=\int_0^1 xf_X(x)dx = \int_0^1 kx^k=\tfrac{k}{k+1}$.

So what does this mean? If I still have $k$ rolls left in my budget, I should expect that the maximum value I will encounter during those remaining $k$ rolls will be $\tfrac{k}{k+1}$.

With this in mind, an optimal strategy for the single player game with a total budget of $n$ rolls is quite straightforward.

Do the first roll and get the value $x_1$. Is $x_1>\tfrac{n-1}{n}$, which is the expected highest value I will see in the remaining $n-1$ rolls? If yes, stop. Otherwise roll again. Get $x_2$ on the second roll. Is $x_2>\tfrac{n-2}{n-1}$? Then stop. Else roll the third time. Inductively, if on roll $\ell$ you have that $x_\ell>\tfrac{n-\ell}{n-\ell+1}$, stop. Otherwise roll for the $\ell+1$-th time. If you are unlucky enough to get to the $n$-th roll, the value you will stop at will be arbitrary.

But now, what is the expected outcome of the optimal strategy? Note that you would stop at roll $1$ with probability $S_1=\tfrac{1}{n}$ and you will only do that when $x_1\in(\tfrac{n-1}{n},1]$. The average value of stopping at step $1$ will clearly be $A_1=\tfrac{1}{2}\big(\tfrac{n-1}{n}+1\big)=\tfrac{2n-1}{2n}$.

You stop at roll $2$ if you did not stop at roll $1$ and if $x_2\in(\tfrac{n-2}{n-1},1]$. The probability that you did not stop at roll $1$ is $1-\tfrac{1}{n}=\tfrac{n-1}{n}$ and the probability that you roll $x_2>\tfrac{n-2}{n-1}$ is $\tfrac{1}{n-1}$. So the probability that you stop at roll $2$ is $S_2=\tfrac{n-1}{n}\tfrac{1}{n-1}=\tfrac{1}{n}$. The average stopping value on roll $2$ is $A_2=\tfrac{2n-3}{2n-2}$.

You stop at roll $3$ if you did not stop at roll $1$, did not stop at roll $2$ and if $x_3\in(\tfrac{n-3}{n-2},1]$. This will happen with probability $S_3=(1-2\tfrac{1}{n})\tfrac{1}{n-2}=\tfrac{1}{n}$ and your average stopping value will be $A_3=\tfrac{2n-5}{2n-4}$.

You can show by induction that $S_k=\tfrac{1}{n}$ since you stop at roll $k$ if you have not stopped at any of the previous rolls (which happens with probability $1-\sum_{j=1}^{k-1} S_j=\tfrac{n-k}{n}$ by the induction hypothesis) and if $x_k>\tfrac{n-k-1}{n-k}$ which has probability $\tfrac{1}{n-k}$. The average outcome will be $A_k=\tfrac{2n-2k+1}{2n-2k+2}$. This will hold for all $2\leq k\leq n-1$. Stopping at roll $n$ will occur with probability $S_n=1-\sum_{j=1}^{n-1} S_j=\tfrac{1}{n}$ with average outcome $A_n=\tfrac{1}{2}=\tfrac{2n-2n+1}{2n-2n+2}$.

The expected value of the single player strategy is then $E_n=\sum_{k=1}^n S_kA_k= \tfrac{1}{n} \sum_{k=1}^n \tfrac{2n-2k+1}{2n-2k+2} =\tfrac{1}{n} \sum_{k=1}^n\big(1-\tfrac{1}{2k}\big)=1-\tfrac{1}{2n}\sum_{k=1}^n \tfrac{1}{k}$.

$E_2=1-\tfrac{1}{4}\big(1+\tfrac{1}{2}\big)=\tfrac{5}{8}$.

$E_3=1-\tfrac{1}{6}\big(1+\tfrac{1}{2}+\tfrac{1}{3}\big)=\tfrac{25}{36}$.

As expected $E_3>E_2$. I am unsure what the game theory perspective on this is though. If both players follow the single-player strategy, the player with $3$ rolls is definitely expected to win. How the other player would want to adapt his strategy depends on some factors. For instance, do both players know what roll the other player is on or whether they stopped early?

Major edit thanks to @hgmath

What I described above is not the optimal single player strategy. Indeed, consider the case when $n=3$. If on roll one we get $x_1\in(E_2,\tfrac{2}{3})=(\tfrac{5}{8},\tfrac{2}{3})$, rolling again and pursuing the above strategy would be a mistake, since our expected outcome would just be $E_2$ (the upper bound $\tfrac{2}{3}$ is put there since even with the current strategy we would not reroll if we got above $\tfrac{2}{3}$).

This suggests an inductive strategy. Namely, if we already know the optimal expected outcome of $E_{n-1}$ rolls, we should only reroll after the first roll if $x_1<E_{n-1}$ instead of rerolling if $x_1<\tfrac{n-1}{n}$. So let us try to write down these optimal expectations $E_k$.

If $n=1$, i.e., if our roll budget is $1$, clearly we will stop after $x_1$ with probability $S_1=1$ and the average outcome will be $A_1=\tfrac{1}{2}$, meaning that the optimal $E_1=S_1A_1=\tfrac{1}{2}$.

If our roll budget is $n=2$, then after the first roll $x_1$, we need to check if $x_1>E_1=\tfrac{1}{2}$. This will happen with probability $S_1=1-E_1=\tfrac{1}{2}$ and the average outcome will be $A_1=\tfrac{1+E_1}{2}=\tfrac{3}{4}$. If $x_1\leq E_1$, which will happen with probability $E_1=\tfrac{1}{2}$, we stop at $S_2=1-S_1=\tfrac{1}{2}$ with average outcome $A_2=\tfrac{1}{2}$. Thus the expected optimal outcome is $E_2=S_1A_1+S_2A_2=\tfrac{1}{2}\big((1-E_1)(1+E_1)+E_1\big)=\tfrac{1}{2}(1+E_1-E_1^2)=\tfrac{5}{8}$. So far no difference to our previous computation.

However, if $n=3$, we should stop at $x_1$ if $x_1>E_2$, with probability $S_1=1-E_2=\tfrac{3}{8}$ and average outcome $A_1=\tfrac{1+E_2}{2}=\tfrac{13}{16}$. If $x_1\leq E_2$, then we roll the second time to get $x_2$. We stop if $x_2>E_1$, an event with probability $S_2=(1-S_1)(1-E_1)=E_2(1-E_1)=\tfrac{5}{8}\tfrac{1}{2}=\tfrac{5}{16}$, and an average outcome $A_2=\tfrac{1+E_1}{2}=\tfrac{3}{4}$. If $x_2<E_1$, we roll again and we are forced to stop with $x_3$, an event with probability $S_3=1-S_1-S_2=E_2-E_2(1-E_1)=E_1E_2=\tfrac{5}{16}$ and average outcome $A_3=\tfrac{1}{2}$.

Thus, the expected outcome of the optimal $3$ roll strategy is $E_3=S_1 A_1+S_2A_2+S_3A_3=\tfrac{1}{2}\big((1-E_2)(1+E_2)+E_2(1-E_1)(1+E_1)+E_1E_2\big) = \tfrac{1}{2}(1+E_2+E_2E_1-E_2^2-E_2E_1^2)=\tfrac{1}{2}\big(1+\tfrac{5}{8}+\tfrac{5}{16}-\tfrac{25}{64}-\tfrac{5}{32}\big)=\tfrac{89}{128}$.

This is bigger than what we got with the old strategy by an eight of a percent.

If $n=4$, we would get $S_1=1-E_3$ with $2\cdot A_1=1+E_3$, $S_2=(1-S_1)(1-E_2)=E_3(1-E_2)$ with $2\cdot A_2=1+E_2$, $S_3=(1-S_1-S_2)(1-E_1)=E_3E_2(1-E_1)$ with $2\cdot A_3=1+E_1$ and $S_4=(1-S_1-S_2-S_3)=E_3E_2E_1$ with $2\cdot A_4=1$, meaning that $E_4=\tfrac{1}{2}(1+E_3+E_3E_2+E_3E_2E_1-E_3^2-E_3E_2^2-E_3E_2E_1^2)$. After some computation, this means $E_4=\tfrac{25195}{32768}$. This is an almost $4\%$ increase over the expected outcome of our previous strategy, which would have been $1-\tfrac{1}{8}(1+\tfrac{1}{2}+\tfrac{1}{3}+\tfrac{1}{4})=\tfrac{71}{96}$.

It is not difficult to find a recursive relation for $E_n$ based on induction and the obvious pattern from the computed cases, but I don't know if there is any reasonable way to get a closed form expression for $E_n$.

Answer 2

First, we propose a method for computing the best response for a certain policy of the opponent.

For example, assuming that the opponent plays a thresholding policy with threshold = 1/2. With a single sample, I have a winning probability of 3/8. Therefore in the second round, I will only resample if my winning probability is less than 3/8. We can compute that the threshold is 7/12. Then I can compute the conditional winning probability if I resample in the first round, assuming which to be $1/2+a$. Then I can similarly use this value to determine my threshold for the first round.

With this idea, if both players can resample once, then one can compute the unique pure strategy Nash equilibrium is $(x_1,x_2)=(\frac{\sqrt{5}-1}{2},\frac{\sqrt{5}-1}{2})$, where $x_1$ and $x_2$ are the thresholds of the two players. Similarly, we can compute a pure strategy Nash for the original problem, but which will be quite complicated.

Answer 3

My calculations are not the same as others, so let's compare.

If Player 1's rerolls are when $x_1$ and $x_2$, and Player 2's reroll is when $y_1$ or below, I think (assuming $x_2 \le y_1\le x_1$) that the probability of Player 2 winning is

$$\int_0^{x_2} y_1(x_1x_2y)\, dy \\+\int_{x_2}^{y_1} y_1(x_1x_2y+x_1y- x_1x_2)\, dy \\+ \int_{y_1}^{x_1} (y_1+1)(x_1x_2y+x_1y- x_1x_2)\, dy \\+ \int_{x_1}^1 (y_1+1)(x_1x_2y+x_1y- x_1x_2+y-x_1)\, dy$$ giving

$$p_2=\tfrac12(1-x_1x_2y_1^2-x_1y_1^2+x_1x_2^2y_1+x_1x_2y_1+x_1^2y_1-x_1y_1+y_1-x_1x_2+x_1^2-x_1)$$ and $p_1=1-p_2$. Then I think the derivatives are zero when

• $\frac{dp_1}{dx_2}=0 \implies x_2= \frac{y_1^2-y_1+1}{2y_1}$ and
• $\frac{dp_1}{dx_1}=0 \implies x_1=\frac{\left( x_2+1\right) {{y_1}^{2}}+\left( -{{x_2}^{2}}-x_2+1\right) y_1+x_2+1}{2 (y_1+1)}$ and
• $\frac{dp_2}{dy_1}=0 \implies y_1=\frac{x_1 {{x_2}^{2}}+x_1 x_2+{{x_1}^{2}}-x_1+1}{2 x_1 (x_2+1)}$

so three non-linear simultaneous equations with three unknowns and the solution of $(x_1,x_2,y_1) \approx (0.697910,0.593225,0.651477)$ giving $p_1 \approx 0.576461$ and $p_2 \approx 0.423539$.

Let's compare this with a simulation (using the same seed for reproducibility):

firstplayerwins <- function(x1,x2,y1){
  x <- runif(1)
  if (x < x1){x <- runif(1)}
  if (x < x2){x <- runif(1)}
  y <- runif(1)
  if (y < y1){y <- runif(1)}
  return(x > y)
  }

set.seed(2023)
sims <- replicate(10^5, firstplayerwins(0.697910, 0.593225, 0.651477))
c(mean(sims), mean(!sims))
# 0.57728 0.42272

so close, allowing for simulation noise.

AnCars answer seems to suggest using $(\frac23,\frac12,\frac12)$ (as does Paul Smith) which gives

set.seed(2023)
sims <- replicate(10^5, firstplayerwins(2/3, 1/2, 1/2))
c(mean(sims), mean(!sims))
# 0.58361 0.41639

which is worse for the second player, but Player 2 changing $y_1$ would improve the probability $p_2$ (in this case optimally at $c=\frac{23}{36}\approx 0.6389$)

set.seed(2023)
sims <- replicate(10^5, firstplayerwins(2/3, 1/2, 23/36))
c(mean(sims), mean(!sims))
# 0.574 0.426

though then Player 1 could then change $x_1$ and $x_2$, and so on until you settle on the zero-derivative solution.

Harish Vemuri suggests $(0.69,0.55,0.74)$ which again gives an advantage to Player 1

set.seed(2023)
sims <- replicate(10^5, firstplayerwins(0.69, 0.55, 0.74))
c(mean(sims), mean(!sims))
# 0.58287 0.41713

and again changing $y_1$ would improve the probability for Player 2

set.seed(2023)
sims <- replicate(10^5, firstplayerwins(0.69, 0.55, 0.62976))
c(mean(sims), mean(!sims))
# 0.57578 0.42422 

We can in fact use the consequences of the zero derivatives to iterate towards the equilibrium solution:

iterated <- function(x1, x2, y1, rounds=20){
  for (n in 1:rounds){
    x1[n+1] <- ((x2[n]+1)*y1[n]^2 + (-x2[n]^2-x2[n]+1)*y1[n] + x2[n] + 1) / 
               (2*(y1[n]+1))
    x2[n+1] <- (y1[n]^2 - y1[n] + 1) / (2*y1[n])
    y1[n+1] <- (x1[n]*x2[n]^2 + x1[n]*x2[n] + x1[n]^2 - x1[n] + 1) / 
               (2*x1[n]*(x2[n]+1))
    }
  print(cbind(x1,x2,y1))
  }

iterated(2/3, 1/2, 1/2)

giving (despite a blip in $x_2$ early and then in $y_1$)

             x1        x2        y1
 [1,] 0.6666667 0.5000000 0.5000000
 [2,] 0.6666667 0.7500000 0.6388889
 [3,] 0.6909134 0.6020531 0.7083333
 [4,] 0.7115098 0.5600490 0.6562810
 [5,] 0.6988111 0.5900093 0.6380170
 [6,] 0.6949647 0.6026866 0.6502897
 [7,] 0.6976317 0.5940330 0.6550889
 [8,] 0.6987173 0.5907996 0.6517936
 [9,] 0.6979795 0.5930108 0.6505392
[10,] 0.6977016 0.5938628 0.6513951
[11,] 0.6978917 0.5932808 0.6517233
[12,] 0.6979648 0.5930584 0.6514990
[13,] 0.6979149 0.5932104 0.6514132
[14,] 0.6978958 0.5932686 0.6514718
[15,] 0.6979088 0.5932288 0.6514943
[16,] 0.6979138 0.5932136 0.6514789
[17,] 0.6979104 0.5932240 0.6514730
[18,] 0.6979091 0.5932280 0.6514771
[19,] 0.6979100 0.5932253 0.6514786
[20,] 0.6979104 0.5932242 0.6514775
[21,] 0.6979101 0.5932249 0.6514771

Answer 4

Refer to AnCar's answer.

Each player is attempting to maximize their own score. Suppose you have $n$ rolls. The most you can expect from these $n$ rolls is to end up with a score of greater that $1 - 1/2^n$ with a probability of $1/2$ (assuming they can simply choose the max of their rolls). The difficulty is that, at each point, you are stuck with whatever your last roll was, and the knowledge of how many rolls you have left. So, suppose you are on your $k$th roll of the game and you got a roll of $\alpha \in [0,1]$. You can expect, with $1/2$ probability, that you will get a score greater than $1 - 1/2^{n - (k - 1)}$ with your remaining $n - k$ rolls. So, you should only roll again if $\alpha < 1 - 1/2^{n - (k - 1)}$. Assuming this strategy is optimal, we can calculate the expected value (average score) from playing this strategy. There is a $1/2^n$ chance you get a score greater than $1 - 1/2^n$ on your first roll. Theere is a $1/2^{n - 1}$ chance you get a score greater than $1 - 1/2^{n - 1}$ on your second roll. So on, and so forth. $$ E(\text{score}) = \frac{1 - 1/2^n}{2^n} + \frac{1 - 1/2^{n - 1}}{2^{n - 1}} + \cdots + \frac{1 - 1/2^2}{2^2} + \frac{1 - 1/2^1}{2^1} $$ Let's put these all under a common denominator: \begin{align*} E(\text{score}) &= \frac{2^0(1 - 1/2^n) + 2^1(1 - 1/2^{n - 1}) + \cdots + 2^{n - 2}(1 - 1/2^2) + 2^{n - 1}(1 - 1/2^1)}{2^n} \\ &= \frac{(2^0 + 2^1 + \cdots + 2^{n - 2} + 2^{n - 1}) - (\overbrace{1/2^n + 1/2^n + \cdots + 1/2^n}^{n \text{ times}})}{2^n} \\ &= \frac{(2^n - 1) - n/2^n}{2^n} \\ &= 1 - \frac{1 + n/2^n}{2^n} \\ &= 1 - \frac{1}{2^n} - \frac{n}{2^{2n}}. \end{align*} Keep in mind that this is all speculation. I am not sure if the strategy I have selected is optimal. Please point out a better strategy if you find one. In the context of this problem. That would make the expected score of the first player (the one with three rolls) equal to approximately $0.828$ and the expected score of the second player (the one with two rolls) equal to $0.625$. These values are somewhat expected: $0.828$ is slightly less than $1 - 2^3 = 0.875$ and $0.625$ is slightly less than $1 - 2^2 = 0.75$.

This still doesn't answer the question of the probability that the first player wins. We have only shown that the first player will win more often. I might think about the problem more, but this is what I have to say for now.

Answer 5

With one roll, the odds of getting 1/2 or better are 50/50. With two rolls, the odds of getting 2/3 or better are 50/50. To maximise my roll, If my first roll is less than 2/3, roll again. If my second roll is less than 1/2, roll again.

My opponent has only one roll to improve, they should roll again if they get less than 1/2. So the odds of my winning are 50/50 plus the odds of getting between 1/2 and 2/3 on my first roll which are 1/6. I expect to win four games out of six.

---- Edit for Henry's answer Henry has the most correct answer here so far, but I don't think you could come up with it in an interview situation? I brute forced an optimisation using Henry's algorithm, and the results surprised me. It was very hard to get a best case above 60% and even harder to find a worst case below 55%.