Tag: game theory

Before I begin, I’d like to thank commenters Guy Moore and Jason Weisman for sharing their own solutions and for pointing out a different way of interpreting the problem. The “Random-ball” variant is due to Guy Moore. Ok, here we go…

What is a solution, anyway?

The problem talks about “optimal strategies”, so it’s worth discussing what this means so we’re all on the same page. An optimal strategy is a Nash equilibrium. It’s a set of strategies for each player such that if any one player changed their strategy (while the others held their strategies fixed), it would result in a worse outcome for that player. Hence, no player has any incentive to change their strategy.

A strategy is a rule that tells you what to do based on what you observe. In this game, an example of a strategy would be “always aim to hit the remaining player with the best accuracy”. This is an example of a pure strategy because each player always behaves the same way no matter what they observe. Not every game is guaranteed to have a Nash equilibrium consisting of pure strategies. In some games, such as rock-paper-scissors, it’s optimal to use a mixed strategy. That is, a probabilistic strategy such as “pick rock paper or scissors randomly and with equal probability”. If you used a pure strategy in rock-paper-scissors, your opponents would counter you and you would lose every time!

It turns out that every finite game has at least one mixed Nash equilibrium. So we need not worry about the case where there is no optimal solution. That being said, it’s entirely possible for there to exist many Nash equilibria! So we shouldn’t be surprised if this turns out to be the case…

Murder-ball vs Coinflip-ball vs Random-ball

There are at least three ways of interpreting the problem. In the first interpretation, if two players target each other and hit, then both players are eliminated. I’ll call this variant “Murder-ball”. In Murder-ball, it’s possible for nobody to win! The second interpretation is that whenever two players hit each other, we should flip a coin and the loser of the coin flip gets eliminated. We also flip a 3-way coin to deal with the case where all three players would be simultaneously eliminated. I’ll call this “Coinflip-ball”. Finally, we could interpret the game as having a randomly chosen shooting order for the players. I’ll call this variant “Random-ball”. In Random-ball, if A hits B and B hits C, but the order is such that A shoots first, then B gets eliminated before shooting C and C survives. All these variants have different solutions!

Two players

Let’s start by considering the case with only two players $P$ and $Q$; a duel! In this case, there are no decisions to make. The players always target each other. Suppose the two players have probabilities of $p$ and $q$ to hit each other, respectively, and we want to figure out the probability that either player will win the duel. In Murder-ball, Player $P$ can only win if he hits $Q$ and $Q$ misses $P$. The probability of this occurring is $p(1-q)$. But if both players miss (probability $(1-p)(1-q)$) then the game repeats. So the chance that $P$ is the ultimate winner is:
\begin{align}
\mathbb{P}_P &= p(1-q)\biggl(1+(1-p)(1-q)+(1-p)^2(1-q)^2+\cdots\biggr) \\
&= \frac{p(1-q)}{1-(1-p)(1-q)}
\end{align}Repeating a similar argument for the other player, we find the probabilities of interest are:
\begin{gather}
\mathbb{P}_P = \frac{p(1-q)}{1-(1-p)(1-q)},
\qquad
\mathbb{P}_Q = \frac{(1-p)q}{1-(1-p)(1-q)}, \\
\qquad
\mathbb{P}_0 = \frac{pq}{1-(1-p)(1-q)}.
\end{gather}Here, $\mathbb{P}_0$ is the probability that the two players simultaneously hit each other, so nobody wins. Naturally, the three probabilities above sum to $1$.

In Coinflip-ball and Random-ball, Player $P$ can also win if both players hit each other but he wins the coin flip. It turns out that in this case, it’s impossible for nobody to win, and $\mathbb{P}_0$ from the solution above gets split evenly between both players.

Three players

I will solve the Murder-ball case in detail. With three players, each has a choice of who to target. We will make no assumptions about the nature of the strategies used, and we will allow for the possibility of using a mixed strategy. An example of a mixed strategy would be “Player $A$ should target $B$ with probability $0.4$ and $C$ with probability $0.6$”. In some games, such as rock-paper-scissors, it’s optimal to use a mixed strategy because if you always did the same thing, your opponents would realize this and you would lose every time! So, let’s define the numbers $x,y,z$ as follows:
\begin{align}
&A\text{ targets }B\text{ with prob }x\text{ and targets }C\text{ with prob }(1-x)\\
&B\text{ targets }C\text{ with prob }y\text{ and targets }A\text{ with prob }(1-y)\\
&C\text{ targets }A\text{ with prob }z\text{ and targets }B\text{ with prob }(1-z)
\end{align}We can compute the probabilities that any player will win by enumerating the possible ways it can happen. I’ll give one example to illustrate. To compute the probability that $A$ wins, it can happen in two main ways:

1. $B$ and $C$ are eliminated simultaneously and $A$ survives. This can happen in three ways. Either $B$ and $C$ hit each other, or $B$ hits $C$ and $A$ hits $B$, or $C$ hits $B$ and $A$ hits $C$. We can also have everybody survive for some number of rounds first! The total probability is:
   \[
   \frac{a b (1-c) x y + a (1-b) c (1-x) (1-z) + b c y (1-z)}{1-(1-a)(1-b)(1-c)}
   \]

2. $B$ is eliminated first, and then $A$ wins the duel with $C$ (a case we already solved with $p$ and $q$ above). In any case, $B$ must miss his shot. Either $A$ and $C$ both target $B$ and at least one of them hits, or only one of them targets $B$ and the other misses. The total probability in this case is:
   \[
   \frac{a(1-c)}{1-(1-a)(1-c)} \frac{(1-b)\left(a (1-c) x + (1-a) c (1-z) + a c x (1-z)\right)}{1-(1-a)(1-b)(1-c)}
   \]

3. $C$ is eliminated first, and then $A$ wins the duel with $B$. This case is similar to the previous one and the total probability is:
   \[
   \frac{a(1-b)}{1-(1-a)(1-b)} \frac{(1-c)\left(a (1-b) (1-x) + (1-a) b y + a b (1-x) y\right)}{1-(1-a)(1-b)(1-c)}
   \]

Summing the three probabilities above, we get $\mathbb{P}_A$, the probability that $A$ wins. We can do a similar computation to get the probability that $B$ wins, that $C$ wins, and that nobody wins (all four probabilities will sum to $1$). By symmetry, the formula for $\mathbb{P}_B$ can be obtained by just cyclically permuting all variables: $a\to b\to c \to a$ and $x \to y \to z \to x$. Finally, the probability that nobody wins is such that all four probabilities sum to one: $\mathbb{P}_0 =1-\mathbb{P}_A-\mathbb{P}_B-\mathbb{P}_C$.

Murder-ball optimal strategies

We now have the probabilities that each player wins, and these are the functions:
\[
\mathbb{P}_A(x,y,z),\quad \mathbb{P}_B(x,y,z),\quad \mathbb{P}_C(x,y,z).
\]Each function is parameterized by $a,b,c$, the accuracy of each player, and is a function of $(x,y,z)$, the (mixed) strategy being used. Our goal is to find a choice of $(x,y,z)$ such that no change in $x$ alone can improve $\mathbb{P}_A$, no change in $y$ alone can improve $\mathbb{P}_B$, and no change in $z$ alone can improve $\mathbb{P}_C$. A key observation that will help us solve the problem is that all three functions are linear in $x$, $y$, and $z$ separately. When optimizing a linear function, the maximum always occurs at a boundary. This implies that there must exist pure Nash equilibria!!! So we can restrict our search to cases where $x$, $y$, and $z$ are each $0$ or $1$. So there are 8 strategies in total.

I computed the Nash equilibria via an exhaustive search. For each value of $(a,b,c)$, I computed the values of $(\mathbb{P}_A,\mathbb{P}_B,\mathbb{P}_C)$ for all 8 strategies, tried changing $(x,y,z)$ for each one to see if it was a Nash equilibrium, and if I found multiple Nash equilibria, I chose one at random. Then, I made a plot illustrating who wins when. When $a=1$, we obtain the following picture:

What a mess! There are many Nash equilibria here, and pretty much anything can happen. The reason is that without a coinflip, the player targeted by Abbott will always lose. So, in fact, anything that player does is optimal! That losing player has a big effect on which remaining player wins, and hence the messy solutions. However, these Nash equilibria are mostly unstable. That is, if we change Abbott’s accuracy to $a=0.99$, the picture changes completely:

Coinflip-ball optimal strategies

I will omit the derivations for Coinflip-ball because the algebra is quite lengthy and tedious to write out, but the idea is similar in spirit to how I derived the probabilities for the Murder-ball variant. As in the Murder-ball case, all probabilities are linear in $(x,y,z)$, so once again, pure Nash equilibria must exist. As above, I used an exhaustive search to plot the probability of winning for each player. Here is what I obtained in the case where $a=1$.

For most of the cases, the strategies are obvious. For example, when $b=0.8$ and $c=0.5$, the optimal strategy is for Abbott and Bob to target each other and for Costello to target Abbott. In this case, it turns out Costello wins most of the time! In the top right corner, you’ll notice that there is a mixture of possible outcomes because there are multiple Nash equilibria there. In that region, all three players are highly accurate and the strategy of ganging up on Abbott is no longer optimal. In this regime, it’s Nash-optimal for the three players to target each other in a chain (A to B to C to A) or (A to C to B to A). This is a result of the rules of the game. In my interpretation of Coinflip-ball, if all three players hit each other simultaneously, the outcome of the game is decided by a coin flip where each player has an equal chance to win.

Random-ball optimal strategies

Again, I omit the derivation. This case yields a solution similar to the other two, where pure Nash equilibria always exist. However, in this case, it’s even nicer: the Nash equilibria are unique! This means there is an unambiguous best strategy for all players. Here is what I obtained in the case where $a=1$.

The uniqueness of the Nash equilibria is reflected in the fact that every region is solid; there is no overlap anywhere.

Inaccurate Abbott

Of course, I had to see what would happen in the case where Abbott is not perfectly accurate. Prepare to have your mind blown…

Here is the case of Coinflip-ball:

You’ll notice that when $a=0$ the optimal solution is just split along the line $b=c$, where the more accurate player wins. This makes sense; Abbott will always lose no matter what he does so it’s up to the remaining two players to duke it out.

Here is the case of Murder-ball:

This time, in the case $a=0$, Bob and Costello are not threatened by Abbott so they target each other. If both Bob and Costello are very accurate, then there is a good chance that they eliminate each other, and in this case Abbott wins!

Finally, here is the case of Random-ball:

Let’s call Player A’s number $x \in [0,1]$ and Player B’s number $y \in [0,1]$. We’ll assume a general mixed strategy for each player and compute each player’s best response. This approach is similar to the one I used in the war game puzzle, but the solution is more complicated this time.

For this solution, I’ll use similar notation and conventions to my solution to the baby poker (the discrete version of toddler poker). Define players’ strategies as follows:

• $p(x)$: probability that Player A will raise if their number is $x$.
• $q(y)$: probability that Player B will fold if their number is $y$.

Let’s call $E(x,y)$ the payoff for Player A when both numbers are revealed:
\[
E(x,y) = \begin{cases}
1&\text{if }x > y \\
-1&\text{if }x < y \end{cases} \]We don't consider the case $x=y$ because that case has a zero probability of occurring. If we let $W(x,y)$ be the winnings for Player A, we can compute this quantity as we did for the discrete problem: \[ W(x,y) = (1-p(x))E(x,y) + p(x)\bigl( k(1-q(y))E(x,y) + q(y) \bigr) \]Of course, $A$'s expected winnings averaged over all random numbers $x,y$ is simply the integral $\bar W = \int_0^1\int_0^1 W(x,y)\,dx\,dy$.

Player B’s best response

Let’s suppose that Player A uses strategy $p(x)$ and Player B somehow knows this in advance and gets to play the best possible response. What should this response be? For each $y$, $q(y)$ should be chosen to minimize A’s expected winnings. In other words, we should solve:
\[
q(y) = \arg\underset{q}{\min} \int_0^1 \biggl[
(1-p(x))E(x,y) + p(x)\bigl( k(1-q)E(x,y) + q \bigr) \biggr]\,dx
\]The expression on the right is linear in $q$ and the constant terms don’t affect the argmin. So we conclude that
\[
q(y) = \begin{cases}
1 & \text{if } \int_0^1 p(x)(1-kE(x,y))\,dx < 0 \\ 0 & \text{otherwise} \end{cases} \]Splitting the integral for $x\in[0,1]$ into $x\in[0,y]$ and $x\in[y,1]$, we can substitute the definition of $E(x,y)$ and obtain: \begin{align} \int_0^1 p(x)(1-kE(x,y))\,dx &= \int_0^1 p(x)dx + k\left( \int_0^y p(x) dx - \int_y^1 p(x) dx \right) \\ &= (1-k)\int_0^1 p(x)dx + 2k \int_0^y p(x)dx \end{align}So our final formula for $q(y)$ is:

$\displaystyle
q(y) = \begin{cases}
1 & \text{if } \int_0^y p(x)dx < \frac{k-1}{2k}\int_0^1 p(x)dx \\ 0 & \text{otherwise} \end{cases} $

This formula already tells us a lot. If $k \le 1$, the inequality never holds so $q(y)=0$ (always call). If $k > 1$, then $0 < \frac{k-1}{2k} < \tfrac{1}{2}$. Since $\int_0^y p(x)dx$ is a monotonically increasing function no matter what $p$ is, there is a unique $y$ that yields equality. We deduce that $q(y)$ must be a threshold strategy: \[ q(y) = \begin{cases} 1 & \text{if } 0 \le y < c \\ 0 & \text{if } c < y \le 1 \end{cases} \]where $c$ is chosen such that $\int_0^c p(x)dx = \frac{k-1}{2k}\int_0^1 p(x)dx$. So fold if your hand is bad, and call if your hand is good. Makes sense!

Player A’s best response

Let’s suppose that Player B uses strategy $q(y)$ and Player A somehow knows this in advance and gets to play the best possible response. What should this response be? For each $x$, $p(x)$ should be chosen to maximize A’s expected winnings. In other words, we should solve:
\[
p(x) = \arg\underset{p}{\max} \int_0^1 \biggl[
(1-p)E(x,y) + p\bigl( k(1-q(y))E(x,y) + q(y) \bigr) \biggr]\,dy
\]The expression on the right is linear in $p$ and the constant terms don’t affect the argmin. So we conclude that
\[
p(x) = \begin{cases}
1 & \text{if } \int_0^1 \bigl( -E(x,y) + k(1-q(y))E(x,y) + q(y) \bigr) \,dy > 0 \\
0 & \text{otherwise}
\end{cases}
\]Splitting the integral up as $[0,1] = [0,x] \cup [x,1]$ as we did when we computed Player B’s best response and simplifying the algebra, we obtain a more complicated formula than last time:

$\displaystyle
p(x) = \begin{cases}
1 & \text{if }\,\, \frac{k-1}{k}(\tfrac{1}{2}-x) + \int_0^x q(y)dy < \frac{k+1}{2k}\int_0^1 q(y)dy \\ 0 & \text{otherwise} \end{cases} $

This is a bit trickier than last time because the left-hand side of the inequality isn’t a simple increasing function in $x$. It contains both an increasing and a decreasing part! So $A$’s best response might be more complicated than a simple threshold strategy. However, we can leverage the fact that we have a formula for $q(y)$…

Combining both best responses

Substituting Player B’s threshold response into the formula for Player A’s best response, we obtain:
\[
p(x) = \begin{cases}
1 & \text{if }\,\, \frac{k-1}{k}(\tfrac{1}{2}-x) + \min(x,c) < \frac{k+1}{2k}c \\ 0 & \text{otherwise} \end{cases} \]Working out the cases $ x < c $ and $ x > c $ separately, we deduce that:
\[
p(x) = \begin{cases}
1 & \text{if }\,\, 0 < x < \frac{k+1}{2}c-\frac{k-1}{2} \\ 0 & \text{if }\,\, \frac{k+1}{2}c-\frac{k-1}{2} < x < \frac{c+1}{2} \\ 1 & \text{if }\,\, \frac{c+1}{2} < x < 1 \end{cases} \]So Player A still plays a threshold strategy... but with two thresholds rather than one! We can now solve for $c$ by substituting $p(x)$ back into the formula $\int_0^c p(x)dx = \frac{k-1}{2k}\int_0^1 p(x)dx$ we derived earlier. This is relatively easy to do because $c$ is always in the middle portion of the interval. i.e. $p(c)=0$. The result is: \[ \left( \tfrac{k+1}{2}c-\tfrac{k-1}{2} \right) = \tfrac{k-1}{2k}\left[ \left(\tfrac{k+1}{2}c-\tfrac{k-1}{2}\right) + \left(1-\tfrac{c+1}{2}\right)\right] \]After simplifications, we obtain: \[ c = \frac{(k-1)(k+2)}{k(k+3)} \]We can go back and compute the expected winnings of Player A by integrating $W(x,y)$ using the optimal policies we derived. Upon doing this, we find that the expected winnings for Player A are: \[ \bar W = \frac{k-1}{k(k+3)} \]

Optimal policies

The optimal policy for Player A is:
\[
\text{Player A: } \begin{cases}
\text{raise} & \text{if } 0 < x < \frac{k-1}{k(k+3)} \\ \text{call} & \text{if } \frac{k-1}{k(k+3)} < x < \frac{k^2+2k-1}{k(k+3)} \\ \text{raise} & \text{if } \frac{k^2+2k-1}{k(k+3)} < x < 1 \end{cases} \]The optimal policy for Player B is: \[ \text{Player B: } \begin{cases} \text{fold} & \text{if } 0 < y < \frac{(k-1)(k+2)}{k(k+3)} \\ \text{call} & \text{if } \frac{(k-1)(k+2)}{k(k+3)} < y < 1 \end{cases} \]The expected payout for Player A is given by the expression: \[ \text{Expected payout for Player A:}\quad \frac{k-1}{k(k+3)}\quad\text{dollars}. \]Here are plots that show the optimal strategies:

For the case $k=2$, Player A should raise if $x>0.7$ or if $x<0.1$ (a bluff). Meanwhile, Player B should call if $y > 0.4$ and fold otherwise. On average, Player A wins \$0.10 per game. A fascinating twist is that as $k$ increases, Player A will bluff more aggressively at first, but then will eventually not bluff at all.

The case $k=3$ is special; it corresponds to when Player A is most aggressive (bluffing happens whenever $x < \tfrac{1}{9} \approx 0.111$). This also coincides to when the game is most advantageous to Player A; the expected winnings are also \$0.111. Put another way, if Player A gets to choose how much the raise should be, they should choose \$3! When $k>3$ and as $k$ gets larger, Player A becomes increasingly conservative; raising only very rarely (when a win is all but assured). In this limit, the expected payout for Player A decreases monotonically and converges to \$0 in the limit.