10
$\begingroup$

Consider this simple 2-person game I just made up:

Player A goes gets to draw a uniform U[0,1] number up to X times. At any time, he may either keep his number, or draw a brand new uniform number. However, if he draws all X times, he must keep his last draw as his score.

Player B goes second, and gets to draw up to Y times. Same rules apply to him.

The winner is the player with the highest score. Assuming both A and B play optimally, the probability that player A wins the game is given by F(X,Y). F(X,Y) can be given by the following recurrence relationship (I'll leave it as a separate exercise to derive this):

$F(0,Y) = 0$ $\forall$ Y>0

$F(X,Y) = \left(\frac{Y}{Y+1}\right)*\left(F(X-1,Y)\right)^{\frac{Y+1}{Y}} + \frac{1}{Y+1}$

Here's the question: Find the limit $\lim_{n\rightarrow \infty}$ $F(n,n)$. Obviously, this can be approximated numerically directly from the recurrence definition, but I'm wondering if this limit has an elegant closed-form solution (or perhaps can be derived as a unique root of an implicit equation).

The solution has a nice interpretation to it. Basically, as you let each player have more and more turns, how much does this neutralize B's advantage of getting to go second?

$\endgroup$
4
  • 1
    $\begingroup$ Does player B see what player A got? $\endgroup$ Sep 30, 2014 at 21:12
  • 2
    $\begingroup$ Yes of course, otherwise there would be no advantage to going second. $\endgroup$ Sep 30, 2014 at 23:33
  • 2
    $\begingroup$ There is an error in your formula. $F(1,2) = 1/3$ is correct, but then your formula gives $F(2,2) = 2 \cdot 3^{-5/3} + 1/3$ when it should be $2 \cdot 3^{-5/2} + 1/3$. $\endgroup$ Sep 30, 2014 at 23:55
  • $\begingroup$ Oops, good catch. Exponent should be $\frac{Y+1}{Y}$. That is now fixed... $\endgroup$
    – bigO6377
    Oct 1, 2014 at 3:53

3 Answers 3

9
$\begingroup$

Not a complete solution, but a strategy showing that $\liminf F(n,n)>0.4$.

Edit: I added a more general strategy below, giving a bound that seems likely to be optimal.

Player A will pick some positive constant $c$ and accept the first draw greater than $1-\frac{c}{n}$. The probability A sees such a draw is asymptotic to $1-e^{-c}$, and the value of the first such draw is uniform in $[1-c/n,1]$.

The probability that A wins using this strategy is asymptotic to $$ \left(1-e^{-c}\right)\cdot\frac{n}{c}\int_{1-c/n}^1 t^n\,dt\to \frac{\left(1-e^{-c}\right)^2}{c}. $$ This is maximized by taking $c\approx 1.25643$, giving a probability $\approx 0.407264$.

Variation: As bigO6377 points out in the comments, it's not optimal to choose $c$ to be a constant. We should be more likely to accept a draw that occurs near the end. Here's a strategy that does this.

Player A will choose a continuous function $c:[0,1]\to [0,\infty)$ (not depending on $n$), and will accept the $i$-th draw if its value is at least $1-c(i/n)/n$. This is like the strategy above except the value of $c$ depends on the proportion of draws that have already occurred. For the strategy above $c$ is a constant function.

It can be checked that as $n\to\infty$ the probability A wins approaches $$ \int_0^1 \left(1-e^{-c(x)}\right)\exp\left(-\int_0^x c(t)\,dt\right)\,dx. $$ To maximize this, we do some variational calculus and find that $c$ should satisfy the separable ODE $$ c’(x)=e^{c(x)}-c(x)-1, $$ along with the boundary condition $c(1)=\infty$ (I’m going to ignore convergence issues). If we define $$ F(s):=1-\int_{s}^\infty \frac{1}{e^t-t-1}\,dt, $$ then $c=F^{-1}(x)$ (I believe $F$ cannot be expressed in terms of elementary functions). The function $c(x)$ is increasing, and blows up like $-\log(1-x)$ as $x\to 1$.

Plugging everything back into our expression for the probability A wins, and making substitutions to eliminate the inverse functions, we get that the probability A wins is $$ \int_{w}^\infty \frac{\left(1-e^{-x}\right)\exp\left(-\int_w^x\frac{t}{e^t-t-1}\,dt\right)}{e^x-x-1}\,dx, $$ where $w\approx 0.8662746635723$ is the unique positive real root of $F(s)$.

I computed this numerically and got $0.4205151954612$, so based on Robert Israel’s computations it might be reasonable to hope this strategy is asymptotically optimal.

$\endgroup$
1
  • 3
    $\begingroup$ Nifty approach. One thing though: here you are assuming that A's cutoff (smallest value for which he will keep his number) is constant throughout the process. However, this is not optimal. After each unsuccessful draw, you will need to lower his cutoff value slightly. If you have 1000 draws left, you can be selective and only take ones that are super close to 1.0. However, if you are down to your last 2 draws, you're standards will drop, as you have only one more chance to improve your score. In fact, on your very last draw, your cutoff value is by definition 0 (since you must accept it) $\endgroup$
    – bigO6377
    Oct 1, 2014 at 17:34
2
$\begingroup$

Not an answer, but here are some numerical results to show that Julian Rosen's asymptotic lower bound is not too far from optimal.

$$\matrix{F(10^1,10^1) &= 0.4284225780\cr F(10^2,10^2) &= 0.4212694133\cr F(10^3,10^3) &= 0.4205898646\cr F(10^4,10^4) &= 0.4205226511\cr F(10^5,10^5) &= 0.4205159409\cr F(10^6,10^6) &= 0.4205152700\cr}$$

$\endgroup$
0
$\begingroup$

Here is a partial sketch.

The best strategy for Player B is to wait until he gets a value higher than A's score. So if A gets a score of $x$, then the probability of A winning is $\mathbb P(\max_{i \leq n} U_i \leq x) = x^n$ where $U_1,\dots$ are i.i.d uniforms on $[0,1]$.

It seems to me that A is trying to solve a secretary problem. The optimal solution is: wait until $n^{1/2}$ draws have been made, let $Y$ denote the maximum attained in these draws so that $Y= \max_{i \leq n^{1/2}} U_i$, stop at the first draw which has a value greater than $Y$.

Let $X$ be the score that player A obtains when adopting this strategy. Then there are two cases: either A stops at a draw before the last draw or A is stuck with the last draw. The probability of the last event goes to zero as $n \rightarrow \infty$ so we can ignore that and suppose that A stops before the last draw. Then conditionally on $Y=y$, A's score is uniform on $[y,1]$. So conventionally on $Y=y$, the probability that A wins is $$ \mathbb E[X^n|Y=y]= \frac{1}{1-y}\int_y^1 x^n \, dx = \frac{1-y^n}{(1-y)(n+1)}. $$

Integrating this the probability that A wins is given by $$ \int_0^1\frac{1-y^n}{(1-y)(n+1)} n^{1/2}y^{n^{1/2}-1} \, dy. $$

I am pretty much stuck here and have no idea how to evaluate this integral asymptotically.

$\endgroup$
3
  • 2
    $\begingroup$ That is not the correct optimal strategy for player $A$. Consider his situation if his first draw is $x$. If he stops here, his probability of winning is $x^n$. If he does not, his probability of winning is $F(n-1,n)$. So he should accept the first draw if $x > (F(n-1,n))^{1/n}$. $\endgroup$ Oct 1, 2014 at 15:45
  • $\begingroup$ We can write $(1-y^n)/(1-y)=1+y+\ldots+y^{n-1}$, multiply out and integrate termwise to get that the value of the integral is $1/(n+1) \sum_{j=0}^{n-1} (1+j / \sqrt{n})^{-1}$, which is asymptotic to $\log(n)/(2\sqrt{n})$ as $n\to\infty$. $\endgroup$ Oct 1, 2014 at 15:46
  • $\begingroup$ @RobertIsrael You are right. The secretary problem maximises $\mathbb E[X]$. I thought the same strategy might maximise $\mathbb E[X^n]$ which it doesn't. $\endgroup$
    – Bati
    Oct 2, 2014 at 9:19

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.