Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
11  
Is there any explanation why would two rational and intelligent players go shooting at each other in the first place? –  Emil Jeřábek Sep 13 '11 at 15:32
2  
Was the title a pun on "dual problem"? –  Qiaochu Yuan Sep 13 '11 at 16:16
2  
@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. –  Emil Jeřábek Sep 13 '11 at 16:22
3  
@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. –  user16033 Sep 13 '11 at 16:34
3  
Well, it may happen that intelligent and rational people get involved in a dual. At least, Évariste Gallois did, ... and died. –  Denis Serre Sep 13 '11 at 19:54
show 12 more comments

2 Answers

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

share|improve this answer
    
@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)$". –  user16033 Sep 14 '11 at 2:05
1  
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. –  Emil Jeřábek Sep 14 '11 at 10:11
2  
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. –  Emil Jeřábek Sep 14 '11 at 10:20
add comment

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

share|improve this answer
3  
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. –  Thierry Zell Sep 13 '11 at 20:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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