The duel problem - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T21:26:15Z http://mathoverflow.net/feeds/question/75318 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/75318/the-duel-problem The duel problem unknown (google) 2011-09-13T15:11:59Z 2011-09-14T10:09:32Z <p>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:</p> <p>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:</p> <p><strong>Choice A</strong>: 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. </p> <p><strong>Choice B</strong>: Forsake the opportunity to shoot, and make one step forward toward his opponent.</p> <p>Now the distribution of <code>${p}_{i}(d)$</code> is such that ${p}_{i}(0)=1$, and <code>${p}_{i}(d)&gt;{p}_{i}(d+1)$</code>, $d=0,1,2,...,N-1$, $i=1,2$. There're no other restrictions. Both players are assume to be rational and intelligent. <strong><em>A player's goal is to maximize his probability of killing the opponent</em></strong>. Player 1 act first.</p> <hr> <p>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? </p> <p>(For example, the decision rule could be something like: "if <code>${p}_{1}(d)+{p}_{2}(d-1)&gt;1$</code>, then player 1 should shoot at distance d when it's his turn to move; otherwise step forward") </p> <hr> <p>Edit: the original statement "a player's goal is to maximizing his surviving probability" is changed to "<strong><em>A player's goal is to maximize his probability of killing the opponent</em></strong>", due to Emil.</p> http://mathoverflow.net/questions/75318/the-duel-problem/75339#75339 Answer by Robert Israel for The duel problem Robert Israel 2011-09-13T18:24:51Z 2011-09-14T10:09:32Z <p>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.</p> <p>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.</p> <p>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 $=$.</p> http://mathoverflow.net/questions/75318/the-duel-problem/75340#75340 Answer by Omer for The duel problem Omer 2011-09-13T18:24:55Z 2011-09-13T18:24:55Z <p>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> <p>$P_n = \max(Q_{n-1}, p_n + \overline{p_n} \overline{Q_n})$</p> <p>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.</p> <p>(Above, $\bar{x}= 1-x$.)</p>