Equilibrium in a tug-of-war game: What's the error in my solution?

78 Views Asked by At

I spent the last couple of hours solving this problem. I got a very good approximation of the solution, but not the actual solution, and I'm trying to understand why. I will show as succintly as I can how I conceived the problem and what I did. I will skip all calculations because I'm confident they are correct, and believe this is a matter of conception rather than of computation. Here's what I did.


Firstly, observe that the whole of the events in which Robot 1 wins are

\begin{align*} (R_1 wins)_1 &\cup \Big( (\neg R_1 wins)_1 \cap (\neg R_2 wins_1) \cap (R_1 wins)_2 \Big) \\ &\cup \Big( (\neg R_1 wins)_1 \cap (\neg R_2 wins_1) \cap (\neg R_1 wins)_2 \cap (\neg R_2 wins)_2 \cap (R_1 wins)_3\Big) \\ &\cup \ldots .\end{align*}

where the subindex $i$ in $(R_k wins)_i$ and $(\neg R_k wins)_i$ means the event of winning or losing occurred on the $i$th rope pull by the robot $k$. So in natural terms we have that either $R_1$ wins on the first pull, or $R_2$ does not win on his own first pull and $R_2$ wins on his second pull, or $R_2$ does not win on his first and second pull and $R_1$ wins on his third pull, and so on.

Let $p_0$ be the initial position of whatever marker the robots have to pull beyond $0.5$ or $-0.5$ to win. We are asked to find the $p_0$ that gives equal chances to both robots.

$i$. The probability $(R_1 wins)_1$ is simply $\frac{1}{2} + p_0$.

$ii.$ The probability of not winning the first pull is $(\frac{1}{2} - p_0)$. The expected value of the marker in that case is $p_0 + \frac{1}{2}$, so

$iii$. the probability that $(\neg R_2 wins)_1$ is $1 + p_0$, and the expected value at this point is for the marker to be back at $p_0$, so

$iv$. the probability $(R_1 wins)_2$ once more $\frac{1}{2} + p_0$.

Computing the probabilities in this way, we always have the same expected value for the marker's position after the robots do not pull a win. To be very clear (since I believe my error is here), I conceive that after $R_1$ fails to pull a win, the expected position is $p_0 + 0.5$. If then $R_2$ fails to pull a win, the expected position is once more $p_0$, and so on.

Thus, I arrived at the objective function

\begin{align*} f(p_0) = \left(\frac{1}{2} + p_0 \right) &+ \left(\frac{1}{2}-p_0\right)\left(1+p_0 \right) \left(\frac{1}{2}+p_0 \right) \\ &+ \left(\frac{1}{2}-p_0 \right) \left(1+p_0 \right)\left(\frac{1}{2}-p_0 \right) \left(1+p_0 \right) \left(\frac{1}{2}+p_0 \right) \\ &\ldots .\end{align*}

This comes down to

\begin{align*} f(p_0) = \left(\frac{1}{2}+p_0 \right) \sum_{i=1}^{\infty} \left(\frac{1}{2} - p_0 \right)^i(1+p_0)^i .\end{align*}

The series is a geometric series and converges within the interval of interest [-1, 1], so we reduce it to its closed form expression:

\begin{align*} f(p_0) &= \frac{\frac{1}{2} + p_0}{1- \left(\frac{1}{2}-p_0 \right)(1+p_0)} \\ &= \frac{2 + 2p_0}{2p_0^2 + p_0 + 1} .\end{align*}

Now, there are two ways to conceive the equilibrium point. One is to solve $f(p_0) = \frac{1}{2}$, finding the value of $p_0$ that makes the chances equal. The second is to solve for $f(p_0) = 1 - f(p_0)$, finding the $p_0$ that makes the winning chances equal for both robots. The results for both approaches is the same. Namely,

\begin{align*} p_0 = \frac{3 - \sqrt{17}}{4} = -0.28077\ldots .\end{align*}

I was sad to observe that this is not the correct solution. However, it approximates it extremely well. The correct answer is $p_0 = -0.28500\ldots$.


My solution is "correct" up to two decimal points, which I'm happy with. But I am determined to understand my mistake. My guess is that the problem lies in the fact that my objective function $f(p_0)$ does not conceive the position of the marker after each failed pull using probabilities (that would require convolutions and it gets messy). Instead, it just uses the expected position of the marker, which is always $p_0$ after $R_2$ does not win, and is always $p_0 + \frac{1}{2}$ after $R_1$ does not win. Perhaps this makes $f$ to only approximate the actual solution? I'm a bit lost, and would appreciate any kind of help.

1

There are 1 best solutions below

1
On BEST ANSWER

Your first mistake is when you calculate $P(\text{$R_2$ does not win in round $2$)}$. You need to account for the fact that the probability that $R_2$ does not win depends on how much $R_1$ moved the rope.

If $R_1$ does not win in the first round, it means $R_1$ brought the marker to some number $x$ between $p_0$ and $\tfrac12$. To find the probability that $R_2$ does not win in the second round, we "add up" the probability that $R_1$ moves to $x$, times the probability that $R_2$ does not win conditional on moving to $x$, for each $x$ in this interval. There are infinitely many $x$, so instead of summation, we need to integrate. The probability that $R_2$ does not win starting from $x$ is $(\frac12+x)$, so the total probability is $$ \begin{align} P(\text{$R_2$ does not win in round $2$}) &=\int_{p_0}^{1/2}(\tfrac12+x)\,dx \\&=\tfrac12(\tfrac12+(\tfrac12)^2)-\tfrac12(p_0+p_0^2) \\&=\tfrac38-\tfrac12p_0-\tfrac12p_0^2. \end{align} $$

The formula is more involved than you thought. If you try to extend the same reasoning to the probability of $R_1$ winning in the third round, and so on, you will get messier and messier integrals, so I think that this is not a viable method of attack.


Define a function $f(x)$ on the domain $[-\tfrac12,\tfrac12]$ as follows: $f(x)$ is the probability that the first robot will eventually win the game when the marker starts over $x$. For example, $f(\tfrac12)=1$. The goal is to find $x$ such that $f(x)=\frac12$.

We then use the law of total probability to get an equation for $f(x)$ in terms of itself. The probability the first robot wins on the first turn is $\frac12+x$. Otherwise, the first robot will push the number to some number $y$ in the range $[x,\frac12]$. Here is the trick that makes this problem tractable. At this point, it is $R_2$'s turn, starting from $y$. The probability that $R_2$ wins starting from $1$ is exactly the probability that $R_1$ wins starting from $-y$, which is $f(-y)$. You then subtract from one probability that $R_2$ wins to get the probability $R_1$ wins. Therefore, the function to be integrated is $$ 1-f(-y). $$ Therefore, we get this equation for $f$: $$ f(x)=(\tfrac12+x)+\int_{x}^{1/2}(1-f(-y))\,dy=1-\int_{x}^{1/2}f(-y)\,dy\tag1 $$ Taking the derivative of both sides with respect to $x$, $$ f'(x)=f(-x) $$ To solve this differential equation, note that $$ f''(x)=[f'(x)]'=[f(-x)]'=-f'(-x)=-f\big(-(-x)\big)=-f(x) $$ The differential equation $f''(x)=-f(x)$ implies that $f(x)=A\sin x+B\cos x$ for real constants $A$ and $B$. To find those constants, substitute the formula $A\sin x+B\cos x$ for $f(x)$ in $(1)$. I have not completed this problem, but I am pretty sure this method will work, since I have seen it used to solve a similar problem.