Limiting probabilities for two-player game drawing random uniform numbers

Question

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?

Answer 1

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.

Answer 2

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}$$

Answer 3

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.