The duel problem - MathOverflow

The duel problem

2011-09-13T15:11:59Z

The following duel problem is due to Ben Polak (maybe there's earlier origin, which I'll be glad to be informed about). The rule is as follows:

Two players 1 and 2 start a duel $N$ steps away from each other. They take turns to act. When it's somebody's turn, he must make one of the two choices:

Choice A: Shoot at his opponent with probability ${p}_{i}(d)$ of hitting the target, where $i=1,2$, and $d$ is distance (measured in steps) between them.

Choice B: Forsake the opportunity to shoot, and make one step forward toward his opponent.

Now the distribution of ${p}_{i}(d)$ is such that ${p}_{i}(0)=1$, and ${p}_{i}(d)>{p}_{i}(d+1)$ , $d=0,1,2,...,N-1$, $i=1,2$. There're no other restrictions. Both players are assume to be rational and intelligent. A player's goal is to maximize his probability of killing the opponent. Player 1 act first.

My question is: For all possible distributions of ${p}_{i}(d)$, $i=1,2$ described above, is there a simple and uniform decision rule according to which both players can make their choices at each distance?

(For example, the decision rule could be something like: "if ${p}_{1}(d)+{p}_{2}(d-1)>1$ , then player 1 should shoot at distance d when it's his turn to move; otherwise step forward")

Edit: the original statement "a player's goal is to maximizing his surviving probability" is changed to "A player's goal is to maximize his probability of killing the opponent", due to Emil.

Answer by Robert Israel for The duel problem

2011-09-13T18:24:51Z

Note that the distinction between the objectives of survival and killing the opponent can be important. Suppose some $p_i(n) = 0$ (for both 1 and 2) while $p_i(n-1) > 1/2$. The player who steps forward first is very likely to be killed, so to maximize your probability of survival your best strategy at distance $n$ is always to shoot. The opponent, also wanting to survive, will also shoot, and the game will go on forever without anybody getting hurt.

But if your objective is to kill the opponent, this strategy is clearly sub-optimal: it would be better to step forward and have a positive probability of killing the opponent. But that's not optimal either: there's no need to step forward right away, you could wait a while in the hope that the opponent steps forward first. Waiting $k+1$ turns before stepping forward dominates waiting $k$ turns, so there is no optimal strategy.

To avoid such problems, let's assume $p_i(d) > 0$ for all $d$. This will ensure that the probability of both players surviving indefinitely is 0. Then an optimal strategy can be found using dynamic programming. Let $V_i(d)$ be player $i$'s probability of winning under optimal strategies, starting with distance $d$ and $i$'s turn to shoot. Then $V_i(0) = 1$, otherwise $V_i(d) = \max(1 - V_{3-i}(d-1), W_i(d))$, where $W_i(d)=\min\left(\frac{p_i(d)}{p_1(d) + p_2(d) - p_1(d) p_2(d)}, p_i(d) +(1 - p_i(d)) V_i(d-1))\right)$. It is optimal to shoot if $W_i(d) > 1 - V_{3-i}(d-1)$, to step forward if $\lt$, and both are equally good if $=$.

Answer by Omer for The duel problem

2011-09-13T18:24:55Z

Let $p_n,q_n$ be the two players chance of hitting at distance $n$, and $P_n,Q_n$ their chance of winning under optimal play if it is their turn. Then $P_0=Q_0=1$ and we have the recursion

$ P_n = \max(Q_{n-1}, p_n + \overline{p_n} \overline{Q_n}) $

and similarly with p,q switched. Plugging the formula for $Q_n$ into that for $P_n$ gives an identity for $P_n$ in terms of $p_n,q_n,P_{n-1},Q_{n-1}$ that is easy to solve, and has a unique solution. The optimal strategy given $P_n,Q_n$ is obvious.

(Above, $\bar{x}= 1-x$.)