Three way duel: which gun to choose?

Question

Three shooters compete in three way duel game.

Game 1

Rules:

1. Shooters take turns to shoot.
2. If it's your turn, you have to choose one other person to shoot, and cannot pass your turn or shoot in air, etc..
3. For the sake of fairness, shooters draw lots to decide who shoots first, second and third. They then fire in this order repeatedly until only one survives.
4. Everyone is rational and calculates to maximize his survival probability.

Before the game starts, there're three guns available to choose from, whose hitting probabilities are not revealed, but are known to have been drawn from $U[0,1]$ independently. The gun with the highest hitting probability is labeled "1", the one with the 2nd highest is labeled "2", and worst one is labeled "3". Shooters understand what the labels mean. After each chose his gun, the guns' exact hitting probabilities $g_1,g_2,g_3$ are reveal to all, and the game starts (aka Players draw lots and start shooting).

Question: If you're the first one to choose a gun, which one should you choose to maximize your surviving probability? Which gun gives you the least surviving probability?

Game 2

Rules:

1. Each turn, a fair dice is flipped to decide who should shoot in this turn.
2. If it's your turn, you have to choose one other person to shoot, and cannot pass your turn or shoot in air, etc..
3. Step 1 and 2 are repeated until only one survives.
4. Everyone is rational and calculates to maximize his survival probability.

Guns have to be chosen before the game starts as in Game 1.

Question: If you're the first one to choose a gun, which one should you choose to maximize your surviving probability? Which gun gives you the least surviving probability?

---

Game 0

This is an update. It just occurred to me that allowing the shooter with the worst gun to hold fire in Rule 2 Game 1 will not add much to the computation complexity. This is also more consistent with the spirit of the classical truel game, and is perhaps more reasonable. So while we're at game 1, might as well think about this case.

Rules:

Same as game 1 but with rule 2 changed, so that the shooter with the worst gun is allowed to hold fire/pass turns.

Analysis for game 0:

Holding fire can only happen when all 3 shooters are alive. If he should choose to hold fire, the worst shooter (call him #3) is essentially waiting to duel with the winner of the duel between #1 and #2. This gives $$P_{hold}(3,3\vert 3,2,1)=P(2,2\vert 2,1)P(3,3\vert 3,2)+P(1,2\vert 2,1)P(3,3\vert 3,1)$$ $$=\frac{g_2}{g_2+g_1-g_2g_1}\frac{g_3}{g_2+g_3-g_2g_3}+\frac{g_1(1-g_2)}{g_2+g_1-g_2g_1}\frac{g_3}{g_1+g_3-g_1g_3}$$
$$P_{hold}(3,3\vert 3,1,2)=P(1,1\vert 1,2)P(3,3\vert 3,1)+P(2,1\vert 1,2)P(3,3\vert 3,2)$$ $$=\frac{g_1}{g_2+g_1-g_2g_1}\frac{g_3}{g_1+g_3-g_1g_3}+\frac{g_2(1-g_1)}{g_2+g_1-g_2g_1}\frac{g_3}{g_2+g_3-g_2g_3}$$ where the notation $P(1,2\vert 2,1)$ means #1's survival probability when its #2's turn to shoot, given the current set of shooters are ordered in $\vert 2,1)$, for instance. To decide whether to hold or not, #3 only needs to compare $P_{hold}(3,3\vert 3,1,2)$ with $P_{shoot}(3,3\vert 3,1,2)$, and $P_{hold}(3,3\vert 3,2,1)$ with $P_{shoot}(3,3\vert 3,2,1)$, where $P_{shoot}$ is computed by game 1. This is the only additional computation you need to perform for game 0.

---

Some motivations for formulating the games as such:

In simpler versions of the classic three way duel game, hitting probabilities are given and you're asked to solve for surviving probabilities for the players. In the above games that goal is in some sense reversed, because I want to know how important is your accuracy (or hit probability) in a somewhat fair setting.

Conclusions drawn from just one set of hit probabilities and one set of firing order don't tell much, because they are highly sensitive to those parameters. So you can think of the games as a kind of framework to answering the big picture question: overall, does a better shooter generally have higher survival rate? Unlike solving for instances of the game, questions like this are meta questions for the game, and actually give you more insights about the nature and structure of the game itself. (Meta questions are generally more interesting and challenging, I think. Think of the halting problem as a meta question about algorithms and Godel's incompleteness Theorems as meta questions about arithmetics! I'd better stop before I'm carried too far away by this :-p).

The same question can even be asked for cases more than 3 players. For more than 3 players a closed form solution may be impractical to obtain, although simulations could always help. For game 1 for example, Simulation for 4 shooters with guns' hit probabilities $g_1\gt g_2\gt g_3\gt g_4$ randomly chosen shows that $P_{g_3}\gt P_{g_1}\gt P_{g_4}\gt P_{g_2}$. For 5 shooters, $P_{g_4}\gt P_{g_3}\gt P_{g_1}\gt P_{g_5}\gt P_{g_2}$. Not intuitive at all. Effective simulation of 6 shooters would take hours. So it seems small teens may be the most you can manage (if you have a super computer at hand). This means you can't go meta on the meta question again. Questions like "If many shooters play game 1, choosing top notch guns never give you highest survival probability" just rest safely beyond the ceiling of your computation power.

Answer 1

I've been working on game $2$. I've gotten expressions for the probabilities of survival in terms of $g_1,g_2,g_3$. I've gone over my calculations, but I'd appreciate it if someone would check them.

First, we consider a game with only two players. Let $p_i$ be the survival probability of the player with gun $i$, for $i=1,2.$ Then $$ \begin{align} p_1 &= \frac12g_1+\frac12(1-g_1)p_1+\frac12(1-g2)p_1\\ &=\frac{g_1}{g_1+g_2} \end{align} $$
This is because half the time player $1$ gets to shoot. If he hits, of course he survives. If he misses, he's back in the original position, since the next shooter will be determined by a coin toss. Half the time, player $2$ shoots first, and he must miss if player $1$ is to survive. If he does miss, then once again player $1$ is pack in the original position. Of course, we have $$p_2=\frac{p_2}{p_1+p_2}$$

Now for the $3$-player game. Let $p_i$ be the survival probability of the player with gun $i$, for $i=1,2.$ In this game player $1$ will shoot at player $2$, and players $2$ and $3$ will shoot at player $1$. To make things a little less ugly, let $q$ be the probability that the first shooter misses:$$q= 1-\frac{g_1+g_2+g_3}{3}$$ Then $$\begin{align} p_1&= \frac13g_1\left(\frac{g_1}{g_1+g_3}\right)+qp_1\\ &=\boxed{\frac{g_1}{g_1+g_2+g_3}\left(\frac{g_1}{g_1+g_3}\right)}\\ p_2 &= \frac13g_2\left(\frac{g_2}{g_2+g_3}\right)+ \frac13g_3\left(\frac{g_2}{g_2+g_3}\right)+qp_2\\ &=\frac13g_2+qp_2\\ &=\boxed{\frac{g_2}{g_1+g_2+g_3}}\\ p_3 &=\frac13g_3\left(\frac{g_3}{g_2+g_3}\right)+ \frac13g_2\left(\frac{g_3}{g_2+g_3}\right)+ \frac13g_1\left(\frac{g_3}{g_1+g_3}\right)+ qp_3\\ &=\frac{g_3}{3}+ \frac13g_1\left(\frac{g_3}{g_1+g_3}\right)+ qp_3\\ &=\boxed{\frac{g_3}{g_1+g_2+g_3}\left(1+\frac{g_1}{g_1+g_3}\right)} \end{align}$$

It seems difficult to compare these probabilities analytically, (though I haven't really made an effort,) so I wrote a python script to simulate.

from random import random

trials =1000000
count = [0,0,0]

def first(g1,g2,g3):
    return g1/(g1+g2+g3)*g1/(g1+g3)

def second(g1,g2,g3):
    return g2/(g1+g2+g3)

def third(g1,g2,g3):
    return g3/(g1+g2+g3)*(1+g1/(g1+g3))

for _ in range(trials):
    g = [random(), random(), random()]
    g1 = max(g)
    g3 = min(g)
    g2 = sum(g)-g1-g3
    p1 = first(g1, g2, g3)
    p2 = second(g1, g2, g3)
    p3 = third(g1, g2, g3)
    m = max(p1,p2,p3)
    if m == p1:
        count[0] += 1
    elif m == p2:
        count[1] += 1
    else:
        count[2] += 1

print(count)

This produced the output

[521166, 194460, 284374]

for a million trials. This is typical. About $52\%$ of the time gun gun $1$ is best, about $20%$ of the time gun $2$ is best, and gun $3$ is best about $28\%$ of the time.

It's just occurred to me that I ought to write a script to simulate the dues and check if I get the same results. I'll let you know how that comes out.

EDIT

The script is computing the wrong thing, as Eric points out in the comments. It's computing the probability that choosing gun $1$ is best, whereas what we want to know is the probability that the player who chooses gun $1$ survives.

Answer 2

Let me summarize my progress with game 1.

Two shooters

Easy to show in this case $$P(1,1\vert 1,2)=\frac{g_1}{g_1+g_2+g_1g_2}$$ $$P(1,2\vert 1,2)=\frac{g_1(1-g_2)}{g_1+g_2+g_1g_2}$$ where $g_i$ is hit probability for gun i. The notation $P(1,2\vert 1,2)$ means survival probability for gun 1 user when it's gun 2 user's turn to shoot, given current set of players ordered as $\vert 1,2)$.

Other 2 players scenarios are calculated similarly.

Three shooters

Because shooting order is randomly determined, there are a total of six different orders with equal probability $1/6$: $$ (1, 2, 3)\qquad(1, 3, 2)\qquad(2, 3, 1)\qquad(2, 1, 3)\qquad(3, 2, 1)\qquad(3, 1, 2)$$

Assuming $g_1\gt g_2\gt g_3$, then for all those orders, $2$ and $3$ will shoot $1$, $1$ will shoot $2$. So we have $$P(1,1\vert 1,2,3)=g_1P(1,3\vert 1,3)+(1-g_1)P(1,2\vert 1,2,3)$$ $$P(1,2\vert 1,2,3)=g_2\cdot0+(1-g_2)P(1,3\vert 1,2,3)$$ $$P(1,3\vert 1,2,3)=g_3\cdot0+(1-g_3)P(1,1\vert 1,2,3)$$

These three equations can be solved for the three unknowns $P(1,1\vert 1,2,3)$, $P(1,2\vert 1,2,3)$ and $P(1,3\vert 1,2,3)$.

Similarly, we can solve for $P(1,1\vert 1,3,2)$, $P(1,2\vert 1,3,2)$ and $P(1,3\vert 1,3,2)$.

The six variables solved above correspond to $1$'s survival probability under each one of the six orders, for given $g_1,g_2,g_3$.

So $1$'s surviving probability (the integrand), is given by $$p_1=\frac{P(1,1\vert 1,2,3)+P(1,2\vert 1,2,3)+P(1,3\vert 1,2,3)+P(1,1\vert 1,3,2)+P(1,2\vert 1,3,2)+P(1,3\vert 1,3,2)}{6}$$

$p_2$ and $p_3$ can be calculated similarly.

Using Matlab to solve for 18 equations and 18 variables gives the following ugly monsters:

$$p_1=\frac{{g_1}^2(g_3-1)(3g_2+3g_3-2g_2g_3 - 6)}{6 (g_1 + g_3 - g_1 g_3) (g_1 + g_2 + g_3 - g_1 g_2 - g_1 g_3 - g_2 g_3 + g_1 g_2 g_3) }$$ $$p_2=\frac{g_2 (6 g_2 + 6g_3 - 3 g_1 g_2 - 3 g_1 g_3 - 12 g_2 g_3 + 3 g_2 {g_3}^2 + 7 g_1 g_2 g_3 - 2 g_1 g_2 {g_3}^2 )}{6 (g_2 + g_3 - g_2 g_3) (g_1 + g_2 + g_3 - g_1 g_2 - g_1 g_3 - g_2 g_3 + g_1 g_2 g_3)}$$ $$p_3=\frac{g_3(2{g_1}^2{g_2}^2{g_3}^2 - 2{g_1}^2{g_2}^2{g_3} - 7{g_1}^2g_2{g_3}^2 + 10{g_1}^2g_2g_3 - 3{g_1}^2g_2 + 3{g_1}^2{g_3}^2 - 3{g_1}^2g_3 - 7g_1{g_2}^2{g_3}^2 + 8g_1{g_2}^2g_3 - 3g_1{g_2}^2 + 24g_1g_2{g_3}^2 - 33g_1g_2g_3 + 12g_1g_2 - 12g_1{g_3}^2 + 12g_1g_3 + 3{g_2}^2{g_3}^2 - 12g_2{g_3}^2 + 6g_2g_3 + 6{g_3}^2)}{6(g_1 + g_3 - g_1g_3)(g_2 + g_3 - g_2g_3)(g_1 + g_2 + g_3 - g_1g_2 - g_1g_3 - g_2g_3 + g_1g_2g_3)}$$

For an intuitive grasp of these probabilities, We can plot, under random simulations of the $g$'s, when each $p_i$ is going to be the greatest.

Here green dots are where choosing gun 1 is best (i.e. $p_1\gt p_2,p_3$); red dots mean gun 2 is best choice; blue dots mean gun 3 is best choice. Notice how gun 2 is best only under very restricted cases, the red dots being a small thin wedge between green and blue, and once $g_3\gt 0.4$ or so, gun 2 can never aspire to be a best choice. Gun 3 is best choice along the diagonal of the g-cube, where the difference between everyone is small. Best choices for gun 1 occupy the edge where difference between hitting probabilities is more extreme.

Can these integrand $p_1,p_2,p_3$ be used to solve for exact result? I think in principle yes. But how would you do that? Say

$$P_1=\int_0^1\int_0^{g_1}\int_0^{g_2}\frac{{g_1}^2(g_3-1)(3g_2+3g_3-2g_2g_3 - 6)}{6 (g_1 + g_3 - g_1 g_3) (g_1 + g_2 + g_3 - g_1 g_2 - g_1 g_3 - g_2 g_3 + g_1 g_2 g_3) }\mathrm{d}{g_3}\,\mathrm{d}{g_2}\,\mathrm{d}{g_1}$$

Of course you can always do simulations to approximate for the result of $P_1,P_2,P_3$. Simulations of 10 million trials see $P_1,P_2,P_3$ converge beyond third decimal place, with values $0.417,0.292,0.291$. So it seems better gun does give you higher survival probability after all! Although difference between gun 2 and gun 3 are negligible.

On the other hand, the above integrations seem elementary and evaluable by software. Yet step by step evaluation using software yielded complex number as results. I have absolutely no idea what went wrong.

---

I list $p_1, p_2, p_3$ here below for anyone wanting to investigate further about the integrations to copy.

p1=(g1^2*(g3 - 1)*(3*g2 + 3*g3 - 2*g2*g3 - 6))/(6*(g1 + g3 - g1*g3)*(g1 + g2 + g3 - g1*g2 - g1*g3 - g2*g3 + g1*g2*g3))

p2=(g2*(6*g2 + 6*g3 - 3*g1*g2 - 3*g1*g3 - 12*g2*g3 + 3*g2*g3^2 + 7*g1*g2*g3 - 2*g1*g2*g3^2))/(6*(g2 + g3 - g2*g3)*(g1 + g2 + g3 - g1*g2 - g1*g3 - g2*g3 + g1*g2*g3))

p3=(g3*(2*g1^2*g2^2*g3^2 - 2*g1^2*g2^2*g3 - 7*g1^2*g2*g3^2 + 10*g1^2*g2*g3 - 3*g1^2*g2 + 3*g1^2*g3^2 - 3*g1^2*g3 - 7*g1*g2^2*g3^2 + 8*g1*g2^2*g3 - 3*g1*g2^2 + 24*g1*g2*g3^2 - 33*g1*g2*g3 + 12*g1*g2 - 12*g1*g3^2 + 12*g1*g3 + 3*g2^2*g3^2 - 12*g2*g3^2 + 6*g2*g3 + 6*g3^2))/(6*(g1 + g3 - g1*g3)*(g2 + g3 - g2*g3)*(g1 + g2 + g3 - g1*g2 - g1*g3 - g2*g3 + g1*g2*g3))

Answer 3

I was trying to prove my intuition for Game #1 (choose best gun).

With rules prohibiting skipping the turn a player's strategy can only affect what duel they create by succeeding, they will always aim at the opponent with better of the remaining two guns, making sure to end up in a duel with a weaker opponent in case they succeed. If they fail the game leaves them no choices unless they end up back in the same state with three still alive.

In a duel with probabilities and shooting order $a,b$:

$$P(a\text{ wins})=a+(1-a)(1-b)P(a\text{ wins})\Rightarrow P(a\text{ wins})=\frac{a}{a+b-ab}=p_1(a,b)$$ $$P(b\text{ wins})=1-P(a\text{ wins})=\frac{b-ab}{a+b-ab}=p_2(a,b)$$

In a truel, with probabilities and shooting order $a,b,c$:

$$P(a\text{ is the first to succeed})=p_x(a,b,c)=a+(1-a)(1-b)(1-c)p_x(a,b,c)$$ $$\Rightarrow P(a\text{ is the first to succeed})=p_x(a,b,c)=\frac{a}{a+b+c-ab-ac-bc+abc}$$ $$P(b\text{ is the first to succeed})=\frac{(1-a)b}{a+b+c-ab-ac-bc+abc}$$ $$P(c\text{ is the first to succeed})=\frac{(1-a)(1-b)c}{a+b+c-ab-ac-bc+abc}$$

Average over all possible orders with probabilitiies $a,b,c$:

$$P(a\text{ is the first to succeed})=p_a(a,b,c)=\frac{a(6-3b-3c+2bc)}{3!(a+b+c-ab-ac-bc+abc)}$$ $$P(b\text{ is the first to succeed})=p_b(a,b,c)=\frac{b(6-3a-3c+2ac)}{3!(a+b+c-ab-ac-bc+abc)}$$ $$P(b\text{ is the first to succeed})=p_c(a,b,c)=\frac{c(6-3a-3b+2ab)}{3!(a+b+c-ab-ac-bc+abc)}$$

Now for the game outcome with $g_1>g_2>g_3$:

$P(g_1\text{ survives})=p_a(g_1,g_2,g_3)p_2(g_3,g_1)$

$P(g_2\text{ survives})=p_b(g_1,g_2,g_3)p_2(g_3,g_2)+p_c(g_1,g_2,g_3)p_1(g_2,g_3)$

$P(g_3\text{ survives})=p_a(g_1,g_2,g_3)p_1(g_3,g_1)+p_b(g_1,g_2,g_3)p_1(g_3,g_2)+p_c(g_1,g_2,g_3)p_2(g_2,g_3)$

I tried to ask Wolfram to integrate over those, but they don't want to add up to 1.