Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am really confused about how to think about this question. It was presented as a challenge by a peer.

Two people seek to kill a duck at a location $Y$ meters from their origin. They walk from $x=0$ to $x=Y$ together. At any time, one of the two may pull out their gun and shoot at the duck, however, the probability that person A hits is $P_{A}(x)$ and the probability that person B hits is $P_{B}(x)$. It is also known that $P_A(0)=P_B(0)=0$ and $P_A(Y)=P_B(Y)=1$ and both functions are increasing functions.

What is the optimal strategy for each player?

share|improve this question
    
Do they know each other's probabilities? –  mixedmath Nov 4 '11 at 16:12
    
@mixedmath, yes, I would assume so. –  picakhu Nov 4 '11 at 16:14
    
Can they shoot more than once? –  Graphth Nov 4 '11 at 16:20
1  
@picakhu: I guess there should be a constraint on how far they have to be from the poor duck or you should mention that each person wants to shoot it first (if this is so). –  Emmad Kareem Nov 4 '11 at 16:36
7  
As person A, I think my optimal strategy would be to shoot person B and then use her gun to shoot the duck from up close. –  Greg Martin Nov 4 '11 at 19:20
show 6 more comments

4 Answers 4

up vote 9 down vote accepted

I believe both should shoot at $P_A(x)+P_B(x)=1$. If either shoots earlier, the chance of winning is reduced. If either shoots later, the other could wait half as much later and have a better chance of winning. But what happens if they both hit or both miss?

share|improve this answer
    
@picakhu: if A delays by $\Delta t$, B can delay by $\Delta t/2$ and win $P_B(x^*+\Delta t/2)>P_B(x^*)$ –  Ross Millikan Nov 4 '11 at 16:54
    
sorry, I just realized my error, your answer is correct-in my opinion. –  picakhu Nov 4 '11 at 16:56
    
Ross, there is one issue -- if A does not fire at this time $x^*$, B doesn't know what A's $\Delta t$ is, so he can't fire at $x^* + \Delta t/2$. This is why I think both adopt a mixed strategy. –  Craig Nov 4 '11 at 17:41
1  
@Craig: I think you should fire at any moment past $x*$ if both haven't already. The argument is symmetric. Whoever gets to fire past $x^*$ gets more than his share. So I don't think either should mix strategies. –  Ross Millikan Nov 4 '11 at 17:49
    
@RossMillikan: That's an unstable equilibrium, as each is indifferent between firing at time $x^*$ and not firing, knowing that the other one will. –  Craig Nov 4 '11 at 18:38
show 1 more comment

Suppose player $A$ takes a shot at distance $x$, before player $B$. He collects the price with $P_1 = p_A(x)$ probability, while player $B$ collects the price with probability $P_2 = 1-p_A(x)$.

If the player $B$ shoots first, then $A$ wins with probability $Q_1 = 1-p_B(x)$ and $B$ wins with $Q_2 = p_B(x)$.

The optimal strategy for $A$ is to shoot at the point minimizing $B$'s win, i.e. $x_A = \operatorname{argmin}_x \max(p_B(x), 1-p_A(X))$, while the optimal strategy of $B$ is to shoot at $x_B = \operatorname{argmin}_x \max(p_A(x), 1-p_B(X))$.


Here is a visualization, assuming duck is located at $Y=1$, and $p_A(x)$ and $p_B(x)$ are beta distribution cumulative distribution functions:

enter image description here

share|improve this answer
    
I think your method is correct, but Ross's is slightly easier. –  picakhu Nov 4 '11 at 16:57
2  
@picakhu Actually, my answer is equivalent to Ross's. Given that $p_A(x)$ and $p_B(x)$ are monotonic, it is easy to demonstrate that $x_A=x_B$, and at that point $p_A(x_A) + p_B(x_A) = p_A(x_B) + p_B(x_B) = 1$. –  Sasha Nov 4 '11 at 17:01
add comment

Suppose the probability functions $P_A, P_B$ are continuous, and that "increasing" means "non-decreasing". Then there is a unique maximal closed interval in which $P_A(x) + P_B(x) = 1$. Each player's strategy is identical: shoot at any time in this interval. (Ross Millikan simul-posted this answer.)

It gets a bit more complicated if $P_A$ or $P_B$ is not continuous. This is a realistic scenario $-$ for instance, the brow of a hill might obscure the duck up to a certain point (which might be different for each player). Then there might be a point $x$ before which $P_A + P_B < 1 - a$, and after which $P_A + P_B > 1 + b$, for some strictly positive $a,b$. There are two cases:

  1. $P_A$ is continuous at $x$, and $P_B$ is not. Then $P_A$ must shoot before $x$, but as shortly before $x$ as possible. Likewise if $A$ and $B$ are swapped.

  2. Neither $P_A$ nor $P_B$ is continuous at $x$. Then neither player wants to shoot before $x$, and neither player wants to allow the other to shoot after $x$. The situation becomes tense, and mathematics has little to say; in fact, the game should perhaps be called "chicken" in this case, rather than "duck".

share|improve this answer
    
What happens to the question if there are multiple shots allowed for each player? And what if the number of shots is not equal, so player A may shoot more times than player B? –  picakhu Nov 4 '11 at 17:05
1  
Frankly, picakhu, I don't give a damn. –  TonyK Nov 4 '11 at 22:06
add comment

I think that we should be explicit about the payoffs in the case they both hit simultaneously and about the concept of optimality. I suppose that we search for the Nash equilibrium.

Let's consider 3 versions:

Fair-hunters version. The first who hits the duck gets +1. If both hit simultaneously they get +1/2 each. No Nash equilibrium in pure strategies. Simultaneous shot can not be an equilibrium because both players want to deviate and shoot $\varepsilon$ earlier.

Hunters-enemies. The first who hits the duck gets +1. If both hit simultaneously they get 0 because of a quarrel. No Nash equilibrium as in fair-hunters version.

Brothers-hunters. The first who hits the duck gets +1. If both hit simultaneously they get +1 each (they are very surprised and happy). In this case any pair of strategy $(x,x)$ such that $P_A(x)+P_B(x)\geq 1$ is a Nash equilibrium.

share|improve this answer
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.