# Duel problem

• Sep 9th 2011, 07:20 PM
godelproof
Duel problem
This is a problem from Ben Polak's Yale open course lectures (lecture 16):

A and B start a duel \$\displaystyle N\$ steps away from each other. The rule is as follows:

A and B take turns to act. When it's somebody's turn, he must make one of the following choices:

1. Shoot at his opponent with probability \$\displaystyle {p}_{i}(d)\$ of hitting the target, where i=A or B, and d is distance (measured in steps) between them.
2. Forsake the opportunity to shoot, and make one step forward toward his opponent.
Now the distribution of \$\displaystyle {p}_{i}(d)\$ is such that it's a strictly decreasing function of d, and that \$\displaystyle {p}_{i}(0)=1\$ for i=A, B. There's no other restrictions. Both players are intelligent enough.

Question: When should a player shoot? When should he move forward?

------------------------------------------------------------------------------

Now Ben Polak's solution is, when distance is d, player A should choose to shoot iff \$\displaystyle {p}_{A}(d)+{p}_{B}(d-1) \geq 1\$ (for all\$\displaystyle d>0\$), with player B's strategy defined similarly. I'm really suspicious of this solution! Just think of a case where \$\displaystyle N=2\$. Direct calculation seems to suggest Ben's solution to be incorrect.

Maybe I'm wrong? Any ideas on this?