9
$\begingroup$

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.

$\endgroup$
17
  • 12
    $\begingroup$ Is there any explanation why would two rational and intelligent players go shooting at each other in the first place? $\endgroup$ Sep 13, 2011 at 15:32
  • 3
    $\begingroup$ Was the title a pun on "dual problem"? $\endgroup$ Sep 13, 2011 at 16:16
  • 3
    $\begingroup$ @unknown: What I meant is that the whole setup looks self-contradictory to me, because rational and intelligent players would not involve themselves in a duel. Don’t assume the players are rational and intelligent, just assume that they will do whatever it takes to maximize their probability of winning. $\endgroup$ Sep 13, 2011 at 16:22
  • 3
    $\begingroup$ @Emil: I don't see anything wrong... they are rational and intelligent under the rule, not to a higher level beyond the game. Anyway, I appologize if it offended you to use those words in this setup. $\endgroup$
    – Eric
    Sep 13, 2011 at 16:34
  • 4
    $\begingroup$ Well, it may happen that intelligent and rational people get involved in a dual. At least, Évariste Gallois did, ... and died. $\endgroup$ Sep 13, 2011 at 19:54

2 Answers 2

6
$\begingroup$

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 $=$.

$\endgroup$
3
  • $\begingroup$ @Robert: Nice. The inequality ${V}_{i}(d)>1-{V}_{3-i}(d-1)$ can be obtained by just appealing to intuitive reasoning, because it says "shoot iff shoot now is better than to step forward". Anyway there's probably no simple rule in terms of ${p}_{i}(d)$. There's simple rule if each player is given a single bullet, which is "shoot iff ${p}_{i}(d)>1-{p}_{3-i}(d-1)$". $\endgroup$
    – Eric
    Sep 14, 2011 at 2:05
  • 1
    $\begingroup$ The inequality $V_i(d)< 1-V_{3-i}(d-1)$ never holds, because $\max(a,b)\ge a$. I’ve corrected the criterion for shooting accordingly. $\endgroup$ Sep 14, 2011 at 10:11
  • 2
    $\begingroup$ Also, I think it is worth pointing out one special case which follows from Robert’s analysis. Namely, if the marksmanship of the two players do not differ too much in that $\left|\frac1{p_1(d)}-\frac1{p_2(d)}\right|\le1$ for every $d$, then $V_i(d)=p_i(d)/(p_1(d)+p_2(d)−p_1(d)p_2(d))\ge1/2$ for every $d$ (i.e., the player whose turn it is has always a better chance than the other), and the optimal strategy for both is to always shoot. $\endgroup$ Sep 14, 2011 at 10:20
4
$\begingroup$

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$.)

$\endgroup$
1
  • 3
    $\begingroup$ I hope if you'll forgive me if I don't find everything quite as obvious. What you wrote makes perfect sense to me, but once you have the identity (which is really a recurrence relation involving nested maxes, or am I missing something?), it's not so clear to me that it can be be solved easily. In particular, can you extract from it simple decision rules that the OP was writing about? In particular, can we draw conclusions without solving for $P_n$ and $Q_n$? I haven't had much chance to think about it, so maybe my questions are dumb, but I think there is room for clarification anyway. $\endgroup$ Sep 13, 2011 at 20:20

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.