A, B, and C are to fight a three-cornered pistol duel.
decision/truel Added material
Problem
A, B, and C are to fight a three-cornered pistol duel. All know that A's chance of hitting his target is 0.3, C's is 0.5, and B never misses. They are to fire at their choice of target in succession in the order A, B, C, cyclically (but a hit man loses further turns and is no longer shot at) until only one man is left. What should A's strategy be?
Show solution
This is problem 20 in Mosteller _Fifty Challenging Problems in Probability_
and it also appears (with an almost identical solution) on page 82 in
Larsen & Marx _An Introduction to Probability and Its Applications_.
Here's Mosteller's solution:
A is naturally not feeling cheery about this enterprise. Having the
first shot he sees that, if he hits C, B will then surely hit him, and
so he is not going to shoot at C. If he shoots at B and misses him,
then B clearly {I disagree; this is not at all clear!} shoots the more
dangerous C first, and A gets one shot at B with probability 0.3 of
succeeding. If he misses this time, the less said the better. On the
other hand, suppose A hits B. Then C and A shoot alternately until one
hits. A's chance of winning is (.5)(.3) + (.5)^2(.7)(.3) +
(.5)^3(.7)^2(.3) + ... . Each term corresponds to a sequence of misses
by both C and A ending with a final hit by A. Summing the geometric
series we get ... 3/13 < 3/10. Thus hitting B and finishing off with
C has less probability of winning for A than just missing the first shot.
So A fires his first shot into the ground and then tries to hit B with
his next shot. C is out of luck.
As much as I respect Mosteller, I have some serious problems with this
solution. If we allow the option of firing into the ground, then if
all fire into the ground with every shot, each will survive with
probability 1. Now, the argument could be made that a certain
strategy for X that both allows them to survive with probability 1
*and* gives less than a probability of survival of less than 1 for
at least one of their foes would be preferred by X. However, if
X pulls the trigger and actually hits someone what would the remaining
person, say Y, do? If P(X hits)=1, clearly Y must try to hit X, since
X firing at Y with intent to hit dominates any other strategy for X.
If P(X hits)<1 and X fires at Y with intent to hit, then
P(Y survives)<1 (since X could have hit Y). Thus, Y must insure that
X can not follow this strategy by shooting back at X (thus insuring
that P(X survives)<1). Therefore, I would conclude that the ideal
strategy for all three players, assuming that they are rational and
value survival above killing their enemies, would be to keep firing
into the ground. If they don't value survival above killing their
enemies (which is the only a priori assumption that I feel can be
safely made in the absence of more information), then the problem
can't be solved unless the function each player is trying to maximize
is explicitly given.
--
-- clong@cnj.digex.com (Chris Long)
OK - I'll have a go at this.
How about the payoff function being 1 if you win the "duel" (i.e. if at some
point you are still standing and both the others have been shot) and 0
otherwise? This should ensure that an infinite sequence of deliberate misses
is not to anyone's advantage. Furthermore, I don't think simple survival
makes a realistic payoff function, since people with such a payoff function
would not get involved in the fight in the first place!
[ I.e. I am presupposing a form of irrationality on the part of the
fighters: they're only interested in survival if they win the duel. Come
to think of it, this may be quite rational - spending the rest of my life
firing a gun into the ground would be a very unattractive proposition to
me :-)
]
Now, denote each position in the game by the list of people left standing,
in the order in which they get their turns (so the initial position is
(A,B,C), and the position after A misses the first shot (B,C,A)). We need to
know the value of each possible position for each person.
By definition:
valA(A) = 1 valB(A) = 0 valC(A) = 0
valA(B) = 0 valB(B) = 1 valC(B) = 0
valA(C) = 0 valB(C) = 0 valC(C) = 1
Consider the two player position (X,Y). An infinite sequence of misses has
value zero to both players, and each player can ensure a positive payoff by
trying to shoot the other player. So both players deliberately missing is a
sub-optimal result for both players. The question is then whether both
players should try to shoot the other first, or whether one should let the
other take the first shot. Since having the first shot is always an
advantage, given that some real shots are going to be fired, both players
should try to shoot the other first. It is then easy to establish that:
valA(A,B) = 3/10 valB(A,B) = 7/10 valC(A,B) = 0
valA(B,A) = 0 valB(B,A) = 1 valC(B,A) = 0
valA(B,C) = 0 valB(B,C) = 1 valC(B,C) = 0
valA(C,B) = 0 valB(C,B) = 5/10 valC(C,B) = 5/10
valA(C,A) = 3/13 valB(C,A) = 0 valC(C,A) = 10/13
valA(A,C) = 6/13 valB(A,C) = 0 valC(A,C) = 7/13
Now for the three player positions (A,B,C), (B,C,A) and (C,A,B). Again, the
fact that an infinite sequence of misses is sub-optimal for all three
players means that at least one player is going to decide to fire. However,
it is less clear than in the 2 player case that any particular player is
going to fire. In the 2 player case, each player knew that *if* it was
sub-optimal for him to fire, then it was optimal for the other player to
fire *at him* and that he would be at a disadvantage in the ensuing duel
because of not having got the first shot. This is not necessarily true in
the 3 player case.
Consider the payoff to A in the position (A,B,C). If he shoots at B, his
expected payoff is:
0.3*valA(C,A) + 0.7*valA(B,C,A) = 9/130 + 0.7*valA(B,C,A)
If he shoots at C, his expected payoff is:
0.3*valA(B,A) + 0.7*valA(B,C,A) = 0.7*valA(B,C,A)
And if he deliberately misses, his expected payoff is:
valA(B,C,A)
Since he tries to maximise his payoff, we can immediately eliminate shooting
at C as a strategy - it is strictly dominated by shooting at B. So A's
expected payoff is:
valA(A,B,C) = MAX(valA(B,C,A), 9/130 + 0.7*valA(B,C,A))
A similar argument shows that C's expected payoffs in the (C,A,B) position are:
For shooting at A: 0.5*valC(A,B,C)
For shooting at B: 35/130 + 0.5*valC(A,B,C)
For missing: valC(A,B,C)
So C either shoots at B or deliberately misses, and:
valC(C,A,B) = MAX(valC(A,B,C), 35/130 + 0.5*valC(A,B,C))
Each player can obtain a positive expected payoff by shooting at one of the
other players, and it is known that an infinite sequence of misses will
result in a zero payoff for all players. So it is known that some player's
strategy must involve shooting at another player rather than deliberately
missing.
Now look at this from the point of view of player B. He knows that *if* it
is sub-optimal for him to shoot at another player, then it is optimal for at
least one of the other players to shoot. He also knows that if the other
players choose to shoot, they will shoot *at him*. If he deliberately
misses, therefore, the best that he can hope for is that they miss him and
he is presented with the same situation again. This is clearly less good for
him than getting his shot in first. So in position (B,C,A), he must shoot at
another player rather than deliberately miss.
B's expected payoffs are:
For shooting at A: valB(C,B) = 5/10
For shooting at C: valB(A,B) = 7/10
So in position (B,C,A), B shoots at C for an expected payoff of 7/10. This
gives us:
valA(B,C,A) = 3/10 valB(B,C,A) = 7/10 valC(B,C,A) = 0
So valA(A,B,C) = MAX(3/10, 9/130 + 21/100) = 3/10, and A's best strategy is
position (A,B,C) is to deliberately miss, giving us:
valA(A,B,C) = 3/10 valB(A,B,C) = 7/10 valC(A,B,C) = 0
And finally, valC(C,A,B) = MAX(0, 35/130 + 0) = 7/26, and C's best strategy
in position (C,A,B) is to shoot at B, giving us:
valA(C,A,B) = 99/260 valB(C,A,B) = 91/260 valC(C,A,B) = 7/26
[ Corrected 2026. The original posting gave valA(C,A,B) = 57/260 and
valB(C,A,B) = 133/260. If C hits B, A shoots first in the duel (A,C)
and gets 6/13; if C misses, play returns to (A,B,C), worth 3/10 to A
and 7/10 to B. So valA = (1/2)(6/13) + (1/2)(3/10) = 99/260 and
valB = (1/2)(7/10) = 91/260. The three values now sum to 1. ]
I suspect that, with this payoff function, all positions with 3 players can
be resolved. For each player, we can establish that if their correct
strategy is to fire at another player, then it is to fire at whichever of
the other players is more dangerous. The most dangerous of the three players
then finds that he has nothing to lose by firing at the second most
dangerous.
Questions:
(a) In the general case, what are the optimal strategies for the other two
players, possibly as functions of the hit probabilities and the cyclic
order of the three players?
(b) What happens in the 4 or more player case?
-- David Seal <dseal@armltd.co.uk>
In article <1993Mar25.022459.10269@cs.cornell.edu>, karr@cs.cornell.edu (David Karr) writes:
> The Good, the Bad, and the Ugly are standing at three equidistant
"P" "Q" "R" -- allow me these alternate names.
> points around a very large circle, about to fight a three-way duel to
> see who gets the treasure. They all know that the Good hits with
> probability p=.9, the Bad hits with probability q=.7, and the Ugly
> hits with probability r=.5.
>
> Yes, I know this sounds like decision/truel from the rec.puzzles
> archive. But here's the difference:
>
> At some instant, all three will fire simultaneously, each at a target
> of his choice. Then any who survive that round fire simultaneously
> again, until at most one remains. Note that there are then four
> possible outcomes: the Good wins, the Bad wins, the Ugly wins, or all
> are killed.
A multi-round multi-person game can get complicated if implicit
alliances are formed or the players deduce each other's strategies.
For simplicity let's disallow communication and assume the players
forget who shot at whom after each round.
>
> Now the questions:
These are not easy questions, even with the simplifying
assumptions I've made.
>
> 1. What is each shooter's strategy?
Each player has two possible strategies so there are eight cases
to consider; unfortunately none of the players has a strictly
dominant strategy:
P aims at Q aims at R aims at P survival Q survival R survival Noone lives
--------- --------- --------- ---------- ---------- ---------- -----------
Q P P 0.0649 0.0355 0.7991 0.1005
Q P Q 0.1371 0.0146 0.6966 0.1517
* Q R P 0.3946 0.0444 0.1470 0.4140
Q R Q 0.8221 0.0026 0.0152 0.1601
R P P 0.0381 0.8221 0.0152 0.1246
* R P Q 0.1824 0.3443 0.0426 0.4307
R R P 0.1371 0.5342 0.0027 0.3260
R R Q 0.6367 0.0355 0.0008 0.3270
(The similarity of, say, the 4th and 5th lines here looks wrong:
the intermediate expressions are quite different. I can't
explain *why* P_survival(q,r,q) = Q_survival(r,p,p) = 0.8221
but I *have* double-checked this result.)
If I *know* who my opponents are going to aim at, I should shoot
at the better shooter if they're both aiming at me or neither is
aiming at me. Otherwise I should aim at whoever is *not* aiming
at me. There are two equilibrium points (marked "*" above):
Good aims at Bad; Bad aims at Ugly; Ugly aims at Good.
and
Good aims at Ugly; Bad aims at Good; Ugly aims at Bad.
Here, unlike for zero-sum two-person games, the equilibria
are *not* equivalent and "solution", if any, may lie elsewhere.
Perhaps a game-theorist lurking in r.p can offer a better comment.
Note that the probability all three shooters die is highest at
the equilibria! This seems rather paradoxical and rather sad :-(
>
> 2. Who is most likely to survive?
Good, Bad, or Ugly, depending on the strategies.
>
> 3. Who is least likely to survive?
>
Bad or Ugly, depending on the strategies.
> 4. Can you change p, q, and r under the constraint p > q > r so that
> the answers to questions 2 and 3 are reversed? Which of the six
> possible permutations of the three shooters is a possible ordering
> of probability of survival under the constraint p > q > r?
Yes. Of the six possible survival-probability orderings,
five can be obtained readily:
p q r P_surv Q_surv R_surv Order
--- --- --- ------ ------ ------ -------
0.255 0.25 0.01 0.408 0.413 0.172 Q P R
0.26 0.25 0.01 0.412 0.406 0.173 P Q R
0.75 0.25 0.01 0.675 0.076 0.242 P R Q
0.505 0.50 0.01 0.325 0.324 0.344 R P Q
0.505 0.50 0.02 0.314 0.320 0.353 R Q P
Unlike the p=.9, q=.7, r=.5 case we are given, the five cases
in this table *do* have simple pure solutions: in each case
p shoots at q, while q and r each shoot at p. (I've found no
case with a "simple pure" solution other than this "obvious"
p aims at q, q aims at p, r aims at p choice.)
>
> 5. Are there any value of p, q, and r for which it is ever in the
> interest of one of the shooters to fire into the ground?
No. It can't hurt to shoot at one's stronger opponent.
This is the easiest of the questions ... but it's still
not easy enough for me to construct an elegant proof
in English.
>
> -- David Karr (karr@cs.cornell.edu)
>
Speaking of decision/truel, I recall a *very* interesting
analysis (I *might* have seen it here in rec.puzzles) suggesting
that the N-person "truel" (N-uel?) has a Cooperative Solution
(ceasefire) if and only if N = 3. But I don't see this in the
FAQL; anyone care to repost it?
-- James Allen
In article <1993Apr1.123404.18039@vax5.cit.cornell.edu> mkt@vax5.cit.cornell.edu writes:
>In article <1993Mar25.022459.10269@cs.cornell.edu>, karr@cs.cornell.edu (David Karr) writes:
[...]
>> 5. Are there any value of p, q, and r for which it is ever in the
>> interest of one of the shooters to fire into the ground?
>>
> Yes, p=1, q=1, r=1. The only way for one to survive is to have the other
> two shoot at eachother. Shooting at anyone has no effect on ones personal
> survival.
I assume by "has no effect on" you mean "does not improve."
> If all follow the same logic, they will keep shooting into the
> ground and thus all live.
I was very pleased by this answer but I had to think about it. First
of all, it assumes that continuing the fight forever has a positive
value for each shooter. My preferred assumption is that it doesn't.
But even if each shooter is simply trying to maximize his probability
of never being shot, I wonder about the "has no effect" statement.
Suppose that in round 1 the Good fires into the ground and the Bad
shoots at the Good. Then the Ugly lives if he shoots the Bad and dies
if he does anything else. (The Bad will surely shoot at the Ugly if
he can in round 2, since this dominates any other strategy.) So it
definitely makes a difference to the Ugly in this case to shoot at the
Bad.
But all this is under the assumption that no shooter can tell what
the others are about to do until after all have shot. This isn't
entirely unreasonable--we can certainly set up a game that plays
this way--but suppose we assume instead:
All three start out with guns initially holstered.
Each one is a blindingly fast shot: he can grab his holstered gun,
aim, and fire in 0.6 second.
A shooter can redirect his unholstered gun at a different target and
fire in just 0.4 second.
The reaction time of each shooter is just 0.2 second. That is, any
decision he makes to act can be based only on the actions of the
other two up to 0.2 second before he initiates his own action.
The bullets travel between shooters in less than 0.1 second and
stop any further action when they hit.
Then I *think* the conclusion holds for p=q=r=1: The best strategy is
to wait for someone else to grab for their gun, then shoot that
person, therefore nobody will shoot at anyone. At least I haven't yet
thought of a case in which you improve your survival by shooting at
anyone. Of course this is only good if you don't mind waiting around
the circle forever.
-- David Karr (karr@cs.cornell.edu)
In article <1993Apr5.210749.2657@cs.cornell.edu>,
karr@cs.cornell.edu (David Karr) writes:
> In article <1993Apr1.123404.18039@vax5.cit.cornell.edu> mkt@vax5.cit.cornell.edu writes:
>>In article <1993Mar25.022459.10269@cs.cornell.edu>, karr@cs.cornell.edu (David Karr) writes:
> [...]
>>> 5. Are there any value of p, q, and r for which it is ever in the
>>> interest of one of the shooters to fire into the ground?
>>>
>> Yes, p=1, q=1, r=1. The only way for one to survive is to have the other
>> two shoot at eachother. Shooting at anyone has no effect on ones personal
>> survival.
>
> I assume by "has no effect on" you mean "does not improve."
>
>> If all follow the same logic, they will keep shooting into the
>> ground and thus all live.
>
> I was very pleased by this answer but I had to think about it. First
> of all, it assumes that continuing the fight forever has a positive
> value for each shooter. My preferred assumption is that it doesn't.
> But even if each shooter is simply trying to maximize his probability
> of never being shot, I wonder about the "has no effect" statement.
>
> Suppose that in round 1 the Good fires into the ground and the Bad
> shoots at the Good. Then the Ugly lives if he shoots the Bad and dies
> if he does anything else. (The Bad will surely shoot at the Ugly if
> he can in round 2, since this dominates any other strategy.) So it
> definitely makes a difference to the Ugly in this case to shoot at the
> Bad.
>
Here's where the clincher comes in! If we "assume" the object of the game
is to survive, and that there exists _one_ unique method for survival, then
all the shooters will behave in the same fashion. Obviously the above case
will not hold. How do we distinguish between the good, the bad and the ugly?
If the command is "Shoot" then all will shoot and somebody is going to wind up
lucky (Prob that it is you is 1/3). If the command is "No Shoot", then all
will fire into the ground (or just give up and go home--no sense waitin' around
wastin' time, ya know)...
But wait, you cry! What if there exists _more than one_ solution for optimal
survival. Then what? Will the Good the Bad and the Ugly each randomly decide
between "Shoot" and "No Shoot" with .5 probability? If this is true, then is
it in your best interest to shoot someone? If it is, then we arrive back at
square one: since we assume all shooters are geniouses, then all will shoot--
arriving at an optimal solution of "Shooting". If the answer is "No Shooting",
we arrive at an optimal solution of "No Shooting". If there is no effect on
your personal survival, then do we analyze this with another .5 probability
between the chances of soemone shooting or not shooting? If the answer to this
is "Shoot" then we arrive at square one: all will Shoot; if no, then all will
withold. If there is no effect, then we arrive at another .5 probability...
Obviously you can see the recursion of this process.
Perhaps this would be easier to discuss if we let p=1, q=1, r=0. Obviously, in
terms of survival, shooting at the ugly would be wasting a shot. Thus we have
made a complex problem more simple but retaining the essence of the paradox:
If there are two gunmen who shoot and think with perfect logic and are kept
inside a room and are allowed to shoot at discrete time intervals without
being able to "see" what your opponent will do, what will happen?
Let's say that you are one of the gunmen (the Good). You reason "My probability
to survive the next round is independent on whether or not I fire at him." So
you say to yourself, "Fire at the opponent! I'll get to stop playing this
blasted game." But then you realize that your opponent will also think the same
way...so you might think that you might as well not shoot. But if your
opponent thinks that way, then you know that: 1. You can survive the next
round. 2. You can shoot him if you wish on this round (if you like). So you
say to yourself, "Fire at the opponent!". But you know the opponent thinks the
same way so... you're dead. But really, you say. Is there a way of "knowing"
what the opponent thinks? Of course not. You reason that you can know your
probability of shooting your opponent (either 1 or 0). You reason that your
opponent has a variable probability of shooting you. Thus from your
perspective, p=1 and r<1. We already discussed this case and said "Shoot!".
But wait you cry! What if the opponent figures this out too: p<1, r=1? Sorry,
you're both dead. 'nuff said! This applies to the p=r=q=1 case as well.
> But all this is under the assumption that no shooter can tell what
> the others are about to do until after all have shot.
Ay, there's the rub!
>This isn't entirely unreasonable--we can certainly set up a game that plays
> this way--but suppose we assume instead:
>
> All three start out with guns initially holstered.
> Each one is a blindingly fast shot: he can grab his holstered gun,
> aim, and fire in 0.6 second.
> A shooter can redirect his unholstered gun at a different target and
> fire in just 0.4 second.
> The reaction time of each shooter is just 0.2 second. That is, any
> decision he makes to act can be based only on the actions of the
> other two up to 0.2 second before he initiates his own action.
> The bullets travel between shooters in less than 0.1 second and
> stop any further action when they hit.
>
> Then I *think* the conclusion holds for p=q=r=1: The best strategy is
> to wait for someone else to grab for their gun, then shoot that
> person, therefore nobody will shoot at anyone. At least I haven't yet
> thought of a case in which you improve your survival by shooting at
> anyone. Of course this is only good if you don't mind waiting around
> the circle forever.
Hmmn...alternate ploy:
0.0 You begin to unholster your gun
0.2 Opponents begin unholstering guns. You aim into the ground for .2 sec.
0.4 Opponents are unholstered you are unholstered. They note you aren't
aiming at them. They haven't aimed at anyone yet.
What happens now? I'll have to think about it, but I haven't seen anything
fundamentally different between this and the above case yet.
More ideas to consider:
You begin unholstering your gun but only for .1 sec (you place it by .2 )
You begin unholstering your gun but only for .09 sec (you place it by .19)
You start to aim for .1 sec and then stop aiming.
You start to aim for .1 sec and then turn and aim at another.
You start to aim for .09 sec and then stop aiming (or aim at another)
-Greg
Looking at the answer for decision/truel, I came across the following:
>Each player can obtain a positive expected payoff by shooting at one of the
>other players, and it is known that an infinite sequence of misses will
>result in a zero payoff for all players. So it is known that some player's
>strategy must involve shooting at another player rather than deliberately
>missing.
This may be true but it's not obvious to me. For example, suppose A, B,
and C are passengers in a lifeboat in a storm. If they all stay aboard,
the lifeboat is certain to sink eventually, taking all three to the
bottom with it. If anyone jumps overboard, the two remaining in the
boat are guaranteed to survive, while the person who jumped has a 1%
chance of survival.
It seems to me the lifeboat satisfies the quoted conditions, in the
sense that if nobody jumps then the payoff for all is zero, and the
payoff for jumping is 0.01 which is positive. But it is not clear to
me that the three shouldn't just all sit still until someone goes nuts
and jumps overboard despite everything, for this strategy gives a 67%
chance of survival (assuming everyone is equally likely to "crack"
first) vs. only 1% for jumping by choice. Even if there is a wave
about to swamp the boat, I'd wonder if the situation wouldn't just
reduce to a game of "chicken," with each person waiting until the last
minute and jumping only if it seems the other two have decided to sink
with the boat if you don't jump.
On the other hand, this situation is set up so it is always worse to
be the first person to jump. In the truel I don't think this is true,
but only because of the asymmetry of the odds, and to determine
whether *anyone* shoots, it is easiest to proceed directly to
considering B's point of view.
Whenever it is B's turn to shoot, B can divide the possible courses of
action into four possibilities (actually there are seven, but three
are ruled out a priori by obvious optimizations of each individual's
strategy):
Nobody ever shoots (expected value 0)
A shoots first (at B, expected value <= .7)
C shoots first (at B, expected value <= .5)
B shoots first (at C, expected value .7)
In fact the value of "A shoots first" is strictly less than .7 because
in case A misses, the same four possibilities recur, and all have
expected payoff < 1.
So the value of "B shoots first" uniquely maximizes B's value function,
ergo B will always shoot as soon as possible.
The rest of the analysis then follows as in the archive.
-- David Karr (karr@cs.cornell.edu)
> Looking at the answer for decision/truel, I came across the following:
>
> >Each player can obtain a positive expected payoff by shooting at one of the
> >other players, and it is known that an infinite sequence of misses will
> >result in a zero payoff for all players. So it is known that some player's
> >strategy must involve shooting at another player rather than deliberately
> >missing.
>
> This may be true but it's not obvious to me. For example, suppose A, B,
> and C are passengers in a lifeboat in a storm. If they all stay aboard,
> the lifeboat is certain to sink eventually, taking all three to the
> bottom with it. If anyone jumps overboard, the two remaining in the
> boat are guaranteed to survive, while the person who jumped has a 1%
> chance of survival.
>
> It seems to me the lifeboat satisfies the quoted conditions, in the
> sense that if nobody jumps then the payoff for all is zero, and the
> payoff for jumping is 0.01 which is positive. But it is not clear to
> me that the three shouldn't just all sit still until someone goes nuts
> and jumps overboard despite everything, for this strategy gives a 67%
> chance of survival (assuming everyone is equally likely to "crack"
> first) vs. only 1% for jumping by choice. ...
Yes and no. Yes in the sense that if you treat the game as a psychological
one, the best strategy is as you say. But treating it as a mathematical
game, you've got to adhere to your strategy and you've got to assume that
others will adhere to theirs.
I.e. as a mathematical game, "Don't jump at all" and "Don't jump unless I
crack" are different strategies, and the first one is often (not always)
superior - e.g. if I take "Don't jump at all" and the others take "Don't
jump unless I crack", I'm certain to survive and the others each have a
50.5% chance, which is better from my point of view than a 67% chance of
survival for all of us. As a psychological game, some of the mathematical
strategies may simply not be available - i.e. you cannot control what you
will do if you crack, and so we commonly use "Don't jump" to mean "Don't
jump unless I crack", since "Don't jump at all" is not an available strategy
for most real humans. But for mathematical analysis, the problem has to tell
you what strategies you are not allowed to take.
What the argument above shows is that "Don't jump at all" is not a stable
strategy, in the sense that if everyone takes it, it is in everyone's
interest to change strategy. I.e. it shows that someone will jump
eventually, even if it's only the result of someone actually having taken
"Don't jump unless I crack".
Applied to the truel, the argument above *does* show that someone's strategy
will involve shooting at another player: the strategy "Don't shoot at all"
is unstable in exactly the same way as "Don't jump at all" was. But I agree
it allows for a lot of leeway about how and when the deadlock gets broken,
and your argument showing that it is always in B's interest to shoot is more
satisfactory.
David Seal
UPDATE (2026): PAYOFFS, EQUILIBRIA, AND WHEN MOSTELLER IS RIGHT
In July 2026 Chris Long returned to his objection above. He had two
AI models, Claude Opus 5 and GPT-5.6 Sol Pro, audit this archive entry
and check each other's work. What follows summarizes the points on
which they agreed, together with his own notes from 2008 and 2013.
Every number below was rechecked by an independent exact calculation.
The audits also found the arithmetic error in (C,A,B) corrected above.
1. What has to be specified
Death is permanent, so every play of the game ends with a definite set
S of survivors (possibly all three, if the shooting stops). A complete
statement of the problem gives each player i a utility u_i(S) for every
such set:
u_i(S) = 0 if i is not in S, u_i({i}) = 1,
and, for monotonicity, fewer surviving rivals is never worse. That
leaves three free values per player, for example for A
0 <= u_A(ABC) <= u_A(AB) <= 1, 0 <= u_A(ABC) <= u_A(AC) <= 1,
or nine in all. Players are assumed to maximize expected utility, to
know all accuracies and utilities, and to see who fires at whom.
Chris Long's original complaint was that the problem never says what
the players want. Pure survival (u_i(S) = 1 whenever i survives) and
David Seal's winner-take-all payoff (u_i(S) = 1 only for S = {i}) are
two different games. But fixing the payoffs is still not enough. One
must also say which equilibrium concept is meant: Nash, subgame-perfect
(SPE), or stationary "Markov-perfect", where a player's choice depends
only on who is alive and whose turn it is. Even fully specified
payoffs can admit several equilibria.
2. Duels
Let X and Y have accuracies x and y, with X shooting first. If both
always shoot,
W_X = x / (x + y - xy), W_Y = (1 - x) y / (x + y - xy).
"Always shoot" is an equilibrium of the duel for every monotone payoff.
A stationary truce (both always pass) is an equilibrium only when
u_X(XY) = u_Y(XY) = 1. But consider a trigger truce: both pass until
someone fires, and then both shoot every turn. This is subgame-perfect
whenever
u_X(XY) >= x / (x + y - xy) and u_Y(XY) >= y / (x + y - xy).
For two 50% shooters the threshold is 2/3, which is Chris Long's 2008
example: if each values a draw above 2/3 of a win, both should pass.
3. Mosteller's numbers
Take A = 0.3, B = 1, C = 0.5, with every two-man duel fought to the
end. The value to the shooter of a hit, given that the survivor of his
target then gets the first shot at him, is
A kills B: 3/13 B kills C: 7/10 C kills B: 7/13
A kills C: 0 B kills A: 1/2 C kills A: 0
so each player, if he shoots, aims at the stronger opponent. Under
Mosteller's profile (A passes, B shoots C, C shoots B), the values of
the three positions are
(A,B,C): A 3/10 B 7/10 C 0
(B,C,A): A 3/10 B 7/10 C 0
(C,A,B): A 99/260 B 91/260 C 70/260
and each player's options on his turn are worth to him
pass best target other target
A 3/10 B: 363/1300 C: 21/100
B 7/20 C: 7/10 A: 1/2
C 0 B: 7/26 A: 0
so all three prescribed choices are strict best replies.
4. When Mosteller's answer is right
(i) Mosteller's profile is a subgame-perfect equilibrium for every
monotone payoff. Against the other two players' strategies, no single
player can bring about lasting coexistence by changing his own play, so
the intermediate payoffs never come into it.
(ii) Under the winner-take-all payoff it is the unique subgame-perfect
equilibrium, even allowing randomized and history-dependent strategies.
The proof needs care. Whatever the others do, B can guarantee 7/10 on
his turn by shooting C. C can guarantee 7/26 on his turn by shooting
B, and A can guarantee 9/130 on his. Now suppose B passes. Then B and
C together would need at least 7/10 + 7/26 = 252/260. But whatever C
then does, A still gets at least 9/130, which caps B and C together at
251/260. So B shoots C. Given that, A's best move is to pass (3/10
against 363/1300 and 21/100), and C's is to shoot B (7/26 against 0).
This argument replaces the step "some player must shoot", which David
Karr's lifeboat example showed was unjustified, and it completes his
argument from B's point of view.
(iii) For other payoffs, other equilibria appear:
- Three-way ceasefire. Suppose all pass while three are alive, and
the duel after the first hit is fought out. Writing t_i = u_i(ABC),
this is a Markov-perfect equilibrium exactly when
t_A >= 3/13, t_B >= 7/10, t_C >= 7/13.
For pure survival (all t_i = 1) this holds, and everyone firing
into the ground forever is an equilibrium that is better for all
three. Mosteller's profile remains an equilibrium too, so pure
survival turns the puzzle into a coordination problem rather than
refuting Mosteller. Strictly monotone payoffs can also have both
equilibria, for example (t_A, t_B, t_C) = (0.4, 0.8, 0.6) with
every two-man survival worth 0.9.
- A and C truce. Let u_A(AC) = 0.80 and u_C(AC) = 0.85, with every
three-way value 0.5 (so no three-way ceasefire is possible). A
trigger truce between C and A is subgame-perfect, since a deviation
is worth only 0.4615 to A and 0.7692 to C. So A opens the truel by
shooting at B: 0.3(0.80) + 0.7(3/10) = 0.45, which beats the 0.30
he gets by passing. Mosteller's profile is still an equilibrium,
but it is no longer the only one, and in this other equilibrium A
shoots B on his first turn.
The Claude audit gives conditions under which Mosteller's play is the
unique subgame-perfect outcome:
u_B(ABC) < 7/10, u_A(AC) + u_C(AC) <= 1 + 9/130 = 139/130,
and no two-man survival worth exactly 1. The B condition is robust
because B never misses: no one ever gets a chance to retaliate
against him.
5. General accuracies
For stationary (Markov-perfect) equilibria the problem is a finite
computation. Solve every duel, then try each of the 3^3 = 27 pure
profiles of pass / shoot X / shoot Y for the three positions. For each
profile, solve three linear equations for the position values. Keep
the profiles in which no player can do better by changing his own
choice. If at least one of the three players shoots, the position
values are
V(A,B,C) = (q_A H_A + m_A q_B H_B + m_A m_B q_C H_C)
/ (1 - m_A m_B m_C).
Here q_i is player i's hit probability if he shoots and 0 if he
passes, m_i = 1 - q_i, and H_i is the vector of values after i's hit.
V(B,C,A) and V(C,A,B) follow by rotating the players. If every q_i is
0, nobody is ever shot and each player gets his three-way value
u_i(ABC). Under the winner-take-all payoff the check was run on 20,000
random accuracy triples. Every triple had exactly one pure stationary
equilibrium, and whenever someone abstained it was the least accurate
player. That is numerical evidence for David Seal's question (a), not
a proof.
Once strategies may depend on history (punishments, triggers), no
finite enumeration exists. The set of subgame-perfect payoffs is the
solution of a recursive fixed-point problem, and multiple equilibria
are the rule. Specifying the payoffs makes the game well posed, but it
does not by itself make the answer unique.
6. Notes on the later postings
- p = q = r = 1 with sequential turns: under winner-take-all, whoever
kills one rival is then killed by the other, so every hit is worth
0 to the shooter. Eleven of the 27 pure stationary profiles are
equilibria, including everyone firing into the ground. This bears
out the "fire into the ground" answer for the sequential version.
- James Allen's table for the simultaneous truel recomputes
correctly. His puzzle, P_survival(Q,R,Q) = Q_survival(R,P,P) =
0.8221, holds only because r = 1/2. At r = 0.4 or r = 0.6 the two
probabilities differ by about 0.04.
- Open questions from Chris Long's notes. What if the players do not
know each other's payoffs? Passing or firing could then be used to
signal, and players might update their beliefs about each other as
the truel goes on. What if some players are not perfectly rational?
He suggests this leads to a "tragedy of the dueling commons" and is
related to the iterated prisoner's dilemma.
-- Chris Long (analysis with Claude Opus 5 and GPT-5.6 Sol Pro,
July 2026)
References:
"The Truel"
D. Marc Kilgour and Steven J. Brams
Mathematics Magazine 70, 5 (December 1997), p. 315
bibliography
earliest reference to puzzle is in:
C. Kinnaird
Encyclopedia of Puzzles and Pastimes
Citadel, Secaucus, NJ, 1946
"The Good, the Bad and the Weird: Duels, Truels and Utility Functions"
Christopher D. Long, The Angry Statistician, August 2013
http://angrystatistician.blogspot.com/2013/08/the-good-bad-and-weird-duels-truels-and.html
"The Good, the Bad and the Weird: Duels and the Gentleman's Draw"
Christopher D. Long, The Angry Statistician, September 2013
http://angrystatistician.blogspot.com/2013/09/the-good-bad-and-weird-duels-and.html
Additional material
[ Editor: later postings, 1996 and 1998. ]
The file in the archive that I'm talking about is
http://einstein.et.tudelft.nl/~arlet/puzzles/sol.cgi/decision/truel
I should confess that I have not read the entire file closely yet.
However, there are a few points I want to make.
1. With some difficulty, I tracked down the paper that argues that
"everyone passes" is optimal if and only if N = 3.
D. E. Knuth, "The triel: a new solution," Journal of Recreational
Mathematics 6 (1973), 1-7.
However, the argument given there is unsatisfactory. I corresponded
briefly with Knuth about it and he agreed that this paper is
seriously flawed. (Note the spelling "triel.")
2. There is a brief discussion of the truel in one of Martin Shubik's
books on game theory (I think it's _Game_Theory_in_the_Social_
Sciences:_Concepts_and_Solutions_) but he does not attempt to give a
complete analysis of the problem.
3. Much of the confusion surrounding this problem arises from the
implicit assumption that an "optimal" strategy for each player
exists and is unique. For N > 2 this is not at all obvious and may
not even be true. Any careful discussion must begin with a precise
definition of optimality and proofs of existence/uniqueness of
optimal strategies; otherwise this tacit assumption can slip in in
subtle ways to produce apparent paradoxes. I didn't see anyone take
this approach in the archive file when I skimmed it; did I miss
something?
-- Tim Chow <tchow@umich.edu> (December 1996)
I want to look at a fairly standard problem that comes up here quite
often - "the TRUEL".
It is usually worded something like this...
-------------------------------------
A, B and C fight a "truel".
Each in turn fires at his choice of opponent (or in the air),
in the order C,B,A,C,B,A,C,B,A,... etc.
P(A hits target) = 1/2
P(B hits target) = 1/3
P(C hits target) = 1/4
What is the optimal strategy for each player,
and thence what is the probability each player will survive?
-------------------------------------
The probabilities may vary, though keeping in the order above, and
never being 0 or 1.
Now I'm not interested in the particular solution, which can be worked
out without too much difficulty; (one typically gets that the weakest
player should fire into the air while there are still 3 alive, and
often has a better chance of surviving than the 2nd best!)
However, every now and then, some people say that the best answer is
that they should ALL fire in the air, and all survive.
Now this seems implausible to me. That is the best
"enforced-agreement" strategy, of course, but that is not the case
here. It's very reminiscent of the "prisoner's dilemma". My claim is
that A & B should always fire at each other, and the last two
survivors also.
Let's tidy up the scenario first.
Make it that the shots are kill-or-miss only, no wounding. Indeed, one
should make the situation into a mere gambling game:- Each pays $5 to
enter; and make their choices whence a random device tells the result.
Any ultimate survivors collect $10.
There is usually no mention of what is to happen if all fire in the
air for ever. If we made it that all died, (of starvation, or by
fiat), then my claim would easily hold, so let's avoid that. Let's say
that if all survive for N rounds, all get the prize; but that N should
be very large, so as not to upset the simple probability calculations;
say N = 10/P(C). Then if all always shoot honestly, a single survivor
is certain.
No mention is made of whether shots fired in the air are detectable as
such - it's possible to imagine this knowledge might affect one's
strategy; so let's assume that that's indetectable.
But my claim is still - A & B, (and the last two), should fire
honestly.
Let's look at the 2-survivor situation first.
If P(A) = 1/100, and P(B) = 1/101, there's a strong tendency to feel,
"Oh well, if they shoot honestly, it'll be ages before a survivor is
determined, and it's about 50/50, so why shouldn't two intelligent
truellers just both fire in the air, and be CERTAIN of surviving?"
The trouble is this: if P(A) = .999, and P(B) = .5, then when it's
A's turn he'll think, "I'm not sure if he's firing honestly or not -
if he is, I'll only survive with less than 50% probability if I air it
this time; so better to be (nearly) certain, and kill him now."
Then when it's B's turn, he'll see this line of A's reasoning, and
think "Oh well, I'm a goner if he gets to shoot, so I'll blast away now
and give myself an even chance."
This reasoning seems clear-cut to me. But now, in classic math style,
we can merely vary the parameters. Let P(A) and P(B) tend slowly
downward toward 1/100; playing the game (notionally) each time. There
doesn't seem to be any cut-off point anywhere. There's no apparent
point calculable by any obvious means, that shows there's a place where
the optimum strategy suddenly changes to "fire in the air". So thus I
claim they should always shoot to kill.
And with three players it's the same. Imagine P(A) = .999, P(B) = .5,
and P(C) = .001. Then A and B (and eventually C) should aim at the
strongest opponent. Same reasoning. Now vary the probs as before.
So am I missing anything? The first time I heard of this new-age
all-miss strategy, I thought "That can't be right", and the above
argument raced through my mind. Probably many others felt the same.
Does anyone have a counter-argument in favor of the "trusting"
strategy?
-- Bill Taylor <W.Taylor@math.canterbury.ac.nz> (March 1998)
If there are only two left, then they should fire at each other. But
in the 3-way duel, the correct strategy depends on the particular
probabilities. If these probabilities are high enough, then the "shoot
in the air" strategy becomes the best. For example, suppose the
probabilities are P(A) = .999, P(B) = .998, and P(C) = .997 and suppose
C shoots in the air. You claim that B should shoot honestly (not in
the air). If B is to aim at anybody, he should aim at the best shot,
namely A. But why should he try to kill A? If he kills A, then he
will almost surely die in the 2-way duel since C will get the first
shot at B. Killing any opponent amounts to virtual suicide in this
situation. Unless you want to commit suicide, there is no point in
trying to kill an opponent and hence, you should shoot into the air.
This same argument holds for all contestants. If I was in this
situation, I would shoot in the air and hope that neither of my
opponents was an idiot. Even if an opponent was stupid enough to
commit suicide by killing somebody, they might kill the other opponent
in which case you would still almost surely survive.
-- Glenn C. Rhoads <rhoads@paul.rutgers.edu>
To help reduce degeneracy in the problem, I'll assume that in addition
to desiring their own survival, the truelists have a wish to see their
opponents dead. To further reduce degeneracy I should really make this
wish different for different opponents, but that would complicate
things too much - I'll merely assume the convention that if you do
shoot at somebody (and have a choice of opponent) you choose the
stronger opponent. So you have a payoff of 1 if you survive, plus
delta for each opponent that dies.
Note also that you only said the N-round limit applies as long as all
three are alive; I presume if someone is killed, even in the N'th
round, the game goes on until there is just one survivor.
When you are in a duel, it is obviously in your interest to shoot
honestly, since you have no possible benefit from shooting in the air,
and some benefit from killing your opponent. Thus B's expected payoff
from shooting second in a duel against C (with no time limit) is
D(B,C) = delta + (1-p(C))p(B)(1+ delta)/(p(B)+p(C)-p(B)p(C))
In good dynamic-programming fashion, we work backwards starting with
A's turn in round N. Thus A should shoot (at B) in that round if
D(A,C) > 1. This may or may not be true; with the values p(A)=1/2,
p(B)=1/3 and p(C) = 1/4 it would require delta > 1/4. Otherwise A
would shoot in the air. Certainly if delta is small, A would shoot in
the air.
Next consider B's turn in round N, assuming D(A,C) < 1. Then since
D(B,C) < D(A,C) < 1, B will also shoot in the air, and since D(C,B) <
D(B,C) < 1, so will C. Now consider round N-1, and again we will have
all players shooting in the air. So we find that if D(A,C) < 1, all
players will always shoot in the air.
What if D(A,C) > 1? In round N, B will be looking at expected payoff
D(B,C) if he kills A but p(A) d + (1-p(A)) 1 = 1 - p(A)(1-delta)
[Editor: "(1-p(A) 1" in the original] if he does not, so B shoots at A
if D(B,C) > 1 - p(A)(1-delta). Again, this may or may not be true.
To keep things from getting too complicated, let's suppose p(A)=1/2,
p(B)=1/3, p(C) = 1/4 and 1/2 > delta > 1/4. Then
D(B,C) = (3 delta + 1)/2 > 1 - p(A)(1-delta) = (delta + 1)/2
so B does shoot at A in round N. As for C, his expected payoff is
D(C,B) = (4 delta+1)/3 if he kills A. If he doesn't, the payoff may be
1 (if A and B miss) or p(C)*(1+2 delta) + (1-p(C)) D(C,B) =
(3 delta + 1)/2 (if B kills A) or p(C)*(1+2 delta) + (1-p(C)) D(C,A) =
(2 + 7*delta)/5 (if A kills B). If delta < 1/2, it's certainly better
not to kill A. So C will shoot in the air in this case.
Now in round N-1, A has even more incentive to shoot at B (knowing that
B will shoot at him if he shoots in the air), B has even more incentive
to shoot at A, and again C will prefer to shoot in the air. These
results will again persist all the way down to round 1: C shoots in the
air, A and B shoot at each other, until someone is killed.
-- Robert Israel <israel@math.ubc.ca> (March 1998)
[ Editor: see also decision/truel.one.bullet for a version in which
each truelist has one bullet and never misses. ]