2
$\begingroup$

Two players are playing a game where they each draw a secret random number uniformly between 0 and 1. If they are not satisfied with their draw they may redraw. The players do not know whether or not the other has chosen to re-draw. The players then compare their numbers and he/she who holds largest number wins $1. What is the best strategy assuming both players are perfectly rational?

Idea:

I believe we want to try and find the Nash Equilibrium of this game. A strategy that seems intuitive is to find some threshold $x$ where I redraw if my number $\leq x$. Let's imagine that our opponent has a similar strategy and his/her threshold is $y$.

I'm not too sure how to go from here. Also, how do I show that picking a threshold to reroll is the best strategy?

The answer is not to redraw if one draws below 0.5 by the way. Further we are not necessarily trying to maximize our expectation, rather our probability of winning.

$\endgroup$
7
  • $\begingroup$ The most general strategy specifies with what probability you will elect (randomly) to redraw based on the first number $x$ you see. Argue that when $x \lt 1/2$ it is best to redraw (with probability $1$) because it is more likely than not your value will improve; similarly, when $x \gt 1/2$ it is best to stand pat (that is, redraw with probability $0$). That proves there is a threshold and it equals $1/2.$ It exposes the essence of the problem, which concerns computing the chances that one random variable exceeds another (but not, as one might initially suspect, computing expected values). $\endgroup$
    – whuber
    Oct 27, 2019 at 14:31
  • $\begingroup$ @whuber No expected value? Isn’t this regression to the mean? $\endgroup$
    – Dave
    Jan 5, 2022 at 2:10
  • $\begingroup$ I believe that I have seen this question about the same game another time. $\endgroup$ Sep 24, 2022 at 16:31
  • $\begingroup$ One link is here math.stackexchange.com/questions/1200517/… but I thought I had seen a question with an answer that included a graphic. $\endgroup$ Sep 24, 2022 at 16:45
  • $\begingroup$ Related: stats.stackexchange.com/questions/262179/… $\endgroup$ Sep 24, 2022 at 16:58

2 Answers 2

3
$\begingroup$

Firstly, I will explain why maximizing the expected value does not work (BruceET's answer is wrong). Suppose the players play the following game with dice, whoever gets the larger number wins. Player one has a die with values $1,1,1,1,1,103$ and player 2 has a die with values $3,3,3,3,3,3$. The expected value of the first die is $18$ and of the second is $3$. Despite this, player 2 has a probability of $5/6$ to win.

Now to my approach. Assume that player 1 will redraw if his first number is less than $z$ and that player 2 will redraw if his number is less than $w$. Let us find the expected value for player 1, which in this case is 1 dollar multiplied by the probability of him winning, so we just need to find his chances of winning.

  1. Both players redraw.
  2. Player 1 redraws, player 2 stays.
  3. Player 1 stays, player 2 redraws.
  4. Both players stay with their first number.

We will compute the probability of player 1 to win in each scenario. Let $X$ denote the uniform random variable for player 1, and $Y$ for player 2. Assume $z \geq w$. This assumption is valid since both players will end up using the same 'threshold' to decide whether to redraw ($z=w$).

  1. $P(X < z) P(Y<w) P(X>Y) = \frac{z w}{2}.$
  2. $P(X < z) P(Y > w) P(X > Y \,| \, Y > w) = z P(w < Y < X) = z\int_{w}^{1}\int_{w}^{x} \, d y \, d x = \frac{z(w-1)^2}{2}$.
  3. $P(X > z) P(Y < w) P(X > Y \,| \, X > z) = w P(X > Y \cap X > z) = w\int_{z}^{1}\int_{0}^{x} \, d y \, d x= \frac{w(1-z^2)}{2}$.
  4. $P(X > z) P(Y > w) P(X > Y \,| \, X > z \cap Y > w) = \int_{z}^{1}\int_{w}^{x} \, d y \, d x= \frac{1-z^2}{2} - w(1 - z)$.

Adding everything up we get

$$\frac{1}{2} (z w + z w^2 + z - w - z^2 w + 1 -z^2).$$

Now we want to maximize player 1's expected value given that we know $w$. This is done by computing the partial derivative with respect to $z$ and equating to $0$, then solving for $z$.

$$w + w^2 + 1 - 2 z w - 2z = 0$$

Since both players will use the optimal strategy, $z$ must equal $w$. Subbing in $z$ for $w$ and solving:

\begin{align*} &z^2 + z - 1 = 0,\\ &z = \frac{\sqrt{5} - 1}{2}\\ &\boxed{z \approx 0.618034.} \end{align*}

An interesting observation is that the optimal value for $z$ is related to the golden ratio! $\boxed{z = \phi - 1.}$

$\endgroup$
1
$\begingroup$

It seems best to sample again from $\mathsf{Unif}(0,1)$ if the first sample is $d < .5.$ That gives an expected ending score of $0.625.$

Simulation in R:

set.seed(1026); d = .5
x = runif(10^6)
y = runif(10^6)
z.5 = x;  z.5[x < d] = y[x < d]
head(cbind(x,y,z.5))  # show results for 6 iterations
              x          y          z
[1,] 0.30443921 0.04987319 0.04987319
[2,] 0.93180797 0.41391005 0.93180797
[3,] 0.07850094 0.98809300 0.98809300
[4,] 0.80895610 0.30825302 0.80895610
[5,] 0.38833695 0.89505584 0.89505584
[6,] 0.12720588 0.41955704 0.41955704
mean(x); mean(y); mean(z.5)
[1] 0.5004253
[1] 0.4998209
[1] 0.6251785  # aprx 5/8 = 0.625

It should be easy to prove that d = .5 is indeed best.

d = .4
x = runif(10^6);  y = runif(10^6)
z.4 = x;  z.4[x < d] = y[x < d]
mean(z.4)
[1] 0.6200352

d = .6
x = runif(10^6);  y = runif(10^6)
z.6 = x;  z.6[x < d] = y[x < d]
mean(z.6)
[1] 0.6200457

par(mfrow=c(1,3))
 hist(z.4, prob=T, ylim=c(0,1.8), col="skyblue2", main="d = .4")
  abline(v=mean(z.4), col="red")
 hist(z.5, prob=T, ylim=c(0,1.8), col="skyblue2", main="d = .5")
  abline(v=mean(z.5), col="red")
 hist(z.6, prob=T, ylim=c(0,1.8), col="skyblue2", main="d = .6")
  abline(v=mean(z.6), col="red")
par(mfrow=c(1,1))

enter image description here

$\endgroup$
1
  • 1
    $\begingroup$ But knowing that the other player takes a redraw at 0.5, making their expected score higher than 0.5, then it becomes a better strategy to redraw at a higher number than 0.5. $\endgroup$ Sep 24, 2022 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.