2
$\begingroup$

About half a year ago I asked a question on MSE about a random two player game. At the time, the question received some attention and some progress was made, but was not resolved completely. I have regained interest in this question recently and so I decided to post on here (too late for migration. If I should do anything else to move the question here please let me know).

The original problem is as follows:

Alice and Bob play a game. The game terminates when Alice reaches $a$ points and Bob reaches $1$ point. Alice wins if she ever reaches $a$ points ($a$ is a parameter of the game, and therefore fixed throughout the game). In each round of the game, Alice picks a real number $x$. Then a coin is flipped, Alice is awarded $x$ points if the coin comes up heads, and Bob is awarded $x$ points if the coin comes up tails. Your task is to find the probability that Alice wins for each $a$ given she is using the best strategy.

The formalization of the problem is not quite trivial, so I will offer the following to ensure that there are no ambiguities. First, note that at the beginning of any round, we can normalize the game so that Bob needs exactly $1$ more point. We will define a strategy $s:\mathbb{R^+}\to\mathbb{R^+}$ as a function that takes as an input the number of points Alice needs, and outputs her choice $x$. Define $p_s(a)$ to be the probability that Alice wins the game needing $a$ points and playing strategy $s$. Let $S$ be the set of all strategies. Find $$p, p(a)=\sup_{s \in S}p_s(a).$$


The following is an exhaustive list of the progress on this question that I am aware of:

$$\begin{align} p(a) &\leq \frac 12 + 2^{-a} \tag{1} \\ p(a) &\leq \frac 12 + \frac 1{2a} \tag{2} \\ p(a) &= 1, a \leq 1 \tag{3} \\ \end{align}$$

Furthermore, $(1)$ is tight over the naturals, and $(2)$ is tight over $a=\frac{1}{1-2^{-n}}$. Proofs and the strategies that give the tight bounds can all be found in the linked MSE question.


If I should do anything else to make the migration of content easier please let me know (resubmit answers, etc.)

$\endgroup$
  • $\begingroup$ @PatDevlin what do you mean negative? Alice and Bob each have a strictly positive score thought the game $\endgroup$ – DreamConspiracy May 11 at 0:25
  • $\begingroup$ (Sorry! Posted accidentally before finishing typing [or proofreading].) $\endgroup$ – Pat Devlin May 11 at 0:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.