Three people, A, B and C, are each given a gun with one bullet, and all are perfect shots.

Truel # 1: A's best and only strategy is to fire at one of his
opponents.  He survives alone if and only if his opponents fire at
each other.  The odds of that happening are one in four, or 25%.

Truel # 2: There is no reason to fire in the air in this scenario.
Firing in the air won't increase one's own chances of survival, and
aiming to kill may decrease the number of survivors, which is
advantageous.  A's strategy and chances of survival remain the same:
fire at a random opponent, 25%.

Truel # 3: Player A will die, with 100% probability.  He must kill one
of his opponents, and the survivor will then kill him.

Truel # 4: Player A would be an idiot to fire at one of his opponents,
as the survivor would then kill him.  After he fires in the air, the
next to go (I'm assuming they follow a sequential order) would have the
best strategy "kill the opponent who is not A".  The reason for this is
that if he were to kill A, truellist number 3 would then kill him.
Player A will survive with one other truellist, with probability 100%.

Truel # 5: Whoever goes first will die, with 100% possibility.  He must
take one of his opponents with him.  There is a 50% chance it will be
A.  A will survive alone with probability 50%, or be killed with
probability 50%.

Truel # 6: Similar to #4.  Whoever goes first will fire in the air,
whoever goes second will kill A.  Player A dies, with probability 100%.

Truel # 7: If player A fires first, he dies with 100% probability.  If
he fires simultaneously with B and C, he will have a 75% chance of
death, and a 25% chance of surviving alone.  If he fires last, he will
survive alone with 50% probability or be killed with a 50% probability.
His best bet is to fire last.

Truel # 8: His optimal strategy can't be determined without knowing
whether he'd prefer certain survival with one other truellist or a 25%
shot at surviving alone with a 75% chance of death.

-- Jonathan Haas <positron@quip.eecs.umich.edu>

[ Editor: David Seal considered the reading in which B and C fire
simultaneously after (or before) A. ]

Truel # 4: An alternative interpretation of this truel is that B and C
will fire simultaneously after A has fired.  In this case, the
solution is:

If A shoots one of B and C, the other will kill him with probability
100%, which is the worst possible result for him.  If he shoots into
the air, B and C will have no reason to follow suit: firing at another
truelist can only improve the outcome from their point of view.  B's
reasoning should then go: if C fires at me, I die with probability
100%, and it doesn't matter to me which of the others I shoot; on the
other hand, if C fires at A, I survive with one companion if I fire at
A as well, and I survive with no companions if I fire at C.  So C is an
equally good target in one case, and better in the other: I should fire
at C.  C reasons similarly and so fires at B.

So assuming all three truelists use their optimal strategies, the net
result is that A should fire into the air, and then he survives with no
companions with probability 100%.

Note though that this runs into a "Prisoner's Dilemma": if B and C both
choose their apparently non-optimal strategy of firing at A, they both
survive with one companion, and this result is better for *both* of
them than the result above.  If this were a game that was played
repeatedly for points, they would do well to adopt a strategy like "tit
for tat": this would be bad news for A.  However, the analysis above is
probably right in this case, since by the very nature of the puzzle,
they're not going to play repeatedly :-)

Truel # 5: Or, assuming that B and C fire simultaneously: B reasons
that he loses unconditionally if C fires at him.  If C fires at A, he
survives with one companion if he shoots A as well and with no
companions if he shoots C.  So as before, his best strategy is to shoot
C.  C reasons similarly and shoots B.  A finishes the truel by firing
at one of the corpses (just to make certain he abides by the rules of
the truel :-) and survives with probability 100%.

Again, there is the possibility of a "Prisoner's Dilemma" here, but
given the inherent "one game only" nature of the problem, I don't
believe it will occur.

Truel # 6: With B and C firing simultaneously, this gets complicated.
Each of B and C have three strategies: fire into the air, fire at A and
fire at the other.

From B's point of view, firing at A is always equal to or better than
firing into the air, because:

  * if C fires into the air, B will certainly survive with one
    companion if he shoots A, whereas if he also fires into the air, A
    will shoot him with a 50% chance and so he will survive with one
    companion with only a 50% chance.

  * if C fires at A, B will certainly survive with one companion
    whether he shoots at A or into the air (shooting at C is even
    better in this case, but all I'm trying to do at present is prove
    that shooting at A is equal to or better than shooting into the
    air).

  * if C fires at B, B's going to die whatever he does.

So B can reject the "shoot into the air" strategy.  So can C, for the
same reason.  At this point, this reduces to truel 5, and so A survives
with no companions, with probability 100%.

Truel # 7: There are two ambiguities in this question: firstly, do B
and C always fire simultaneously, or do they only do so when A chooses
the "fire simultaneously" option; secondly, does A announce to B and C
what choice he has made?  If he does announce the choice, your analysis
is right if B and C don't always fire simultaneously; if they do always
fire simultaneously, the same analysis shows that he should choose to
fire last and will then survive with 100% probability.

If he doesn't tell them his decision, we still know that firing first
is suicidal for him.  Offhand, the following reasoning looks attractive
to B and C: if A chooses to fire simultaneously with us, our strategy
makes no real difference; if he chooses to fire last, we should each
fire at the other.  So we should each fire at the other.  At this
point, of course, A's choice no longer makes any difference: he
certainly survives with no companions.

I'm not at all sure of this argument, though: game theory can do some
funny things!

-- David Seal <dseal@armltd.co.uk>

[ Editor: a reply to Haas that disagreed on several points: ]

Truel # 2: You overlook the possibility of cooperation.  This is the
oft-hashed-over Prisoner's dilemma, and the best way I can think to
explain it is to point out that A, B and C are in the same boat, faced
with the same problem.  If you assume that there is an optimal
strategy, then you must conclude that they _all_ will come to it.
Therefore if the best strategy is to shoot to kill, each player has a
25% chance of survival, but if the best strategy is to decamp, each
player's odds rise to 100%.  The next step, which is far more subtle,
is to prove that they will therefore all fire into the air out of pure
self-interest.

Truel # 3: But the survivor _could_ shoot the dead truelist.  Why in
the world might he do that?  Because A will shoot the one who does
_not_ resolve to do so.  This is more difficult than the last, mostly
because of the symmetry of A's position.  He is not really doing any
favor to anyone.  Now if B were not perfectly rational then A could
form an alliance with C quite easily.

Truel # 4: Agreed.

Truel # 5: But note that the rules do not state who fires first.  I
interpret this to mean that B and C fire together, in which case they
should fire at A.

Truel # 7: I disagree, see above.

Truel # 8: I interpret his motives to be survival above all else.

-- THOMPSON BENJAMIN RHINELANDER <thompson@spot.Colorado.EDU>

In article <CK1tFM.30G@cnsnews.Colorado.EDU>,
thompson@spot.Colorado.EDU writes:

> If you assume that there is an optimal strategy, then you must
> conclude that they _all_ will come to it. [...]
> The next step, which is far more subtle, is to prove that they
> will therefore all fire into the air out of pure self-interest.

I strongly suspect that the reason this argument is so "subtle" is that
it's simply not true.  What you have appears to be a classic fallacy of
composition---the strategy that works best for the individual does not
work well when everyone takes it.

Make the very realistic assumption that no shooter has any special
insight into how either of the others will act.  (This is not Newcomb's
Paradox.)  So neither B nor C is going to change their actions based on
where A fires.  Work out the possible combinations of choices made by B
and C vs. the three choices available to A, and you'll find that
shooting at B or C *never* makes A any worse off and often makes him
better off.  In other words this is a dominant strategy and there is
every reason to take it and none not to.

> [Truel # 3] But the survivor _could_ shoot the dead truelist. Why in
> the world might he do that? Because A will shoot the one who does
> _not_ resolve to do so.

Now you're assuming that A can read minds.  A has no idea if B intends
to shoot the dead truellist, and even if B makes a promise to do so, A
has every reason to believe B is lying (besides which, if C has any
brains, C also will make the same promise ...).

> [Truel # 8] I interpret his motives to be survival above all else.

That was my reading of the problem as well.  Each shooter will attempt
to minimize the expected number of survivors, but only when his or her
own survival has been maximized and remains maximal.

Under that assumption, if all three shooters fire simultaneously, each
one's choice has no effect on his or her own survival, so the primary
goal is maximized no matter what.  So each shooter shoots at someone
else in order to minimize the number of survivors.  The same logic
applies to B and C if A has already fired.

This gives us 25% chance of A's survival if all fire simultaneously.
If A fires first at B or C, A dies for certain.  If A fires last, B
faces the following possibilities:

   C shoots at B.  B dies for certain regardless of his or her choice,
      moreover there will be exactly one survivor.

   C shoots at A.  B lives for certain no matter what he or she
      chooses.  If B shoots A or in the air there are two survivors, if
      B shoots C there is one survivor.

   C shoots in the air.  If B shoots in the air, B dies (shot by A)
      with probability 50%.  If B shoots C, B dies with probability
      100%.  If B shoots A, B survives with probability 100%.

My interpretation is that the third scenario takes precedence since
it's the only one where B's choice affects B's survival; hence B will
shoot A.  Of course, B must also figure that C reasons the same way; if
C does and shoots A, then B would be better off to shoot C.  But this
is an unstable solution and there is no way B could be 100% sure of it,
so B must shoot at A to maximize B's survival just in case.  This gives
A a (nearly) zero chance of survival if A shoots first.

[ Editor: from the context, "if A shoots first" in the last sentence
means "if A fires last". ]

The only remaining case is where A fires first into the air.  In that
case, B faces the following possibilities:

   C shoots at B.  B dies for certain regardless of his or her choice.
      If B shoots either A or C, there will be exactly one survivor,
      otherwise there will be two.

   C shoots at A.  B lives for certain no matter what he or she
      chooses.  If B shoots A or in the air there are two survivors, if
      B shoots C there is one survivor.

   C shoots in the air.  B lives for certain.  If B shoots either A or
      C, there will be exactly two survivors, otherwise there will be
      three.

In each case, B's best outcome occurs when B shoots C, and in one case
this is the only way to optimize the outcome for B.  So B will shoot C.
By similar reasoning, C will shoot B.  So A survives with (near) 100%
probability.  (The "near" is to cover the cases where either B or C
act irrationally.)

Of course this assumes that there is no incentive B can give C to shoot
at A instead of B.  But I take the problem statement to have listed
already all the incentives that each shooter might have.

So A should go first and fire into the air.

-- David Karr <karr@cs.cornell.edu>

In complicated situations like these it pays to define carefully what
is meant by an "optimal strategy."  Let S1, S2 and S3 be the strategies
of the three players.  At first one might be tempted to say that a
triplet (S1,S2,S3) of strategies is "optimal" only if, for each i, Si
is better for player i than any other strategy regardless of what the
other two strategies are.  While this is clearly a sufficient
condition, it is so strong that in practice no "optimal" strategy of
this kind exists.  I believe this is true in the case of the "truel."

In light of this we might back off a bit and look at necessary
conditions instead of sufficient ones.  In order for the triplet
(S1,S2,S3) to be "optimal" it seems that it should at least satisfy the
condition that if we fix any two of the strategies and perturb the
third one slightly, the new situation will be worse for the player
whose strategy has been perturbed.  I believe that this condition is
called "Nash equilibrium."

If you allow "mixed strategies," i.e., the players can randomly choose
a strategy at each turn based on a (fixed, prespecified) probability
distribution, and if you impose a few other conditions (e.g., the
players can't form coalitions), then one can show that a Nash
equilibrium always exists.

If there is a unique Nash equilibrium, then it is pretty reasonable to
postulate that "rational players" (who have no "special knowledge" of
the biases of the other players) will notice this and will choose the
Nash equilibrium strategy.  However, Nash equilibria are not always
unique.  I believe that in the case of the "truel" there is more than
one Nash equilibrium.  Hence one must amplify one's definition of
"optimal solution" in order to get a unique answer.

Somebody's already hashed out the game theory of the truel in great
detail (Golomb?).  Anyone have a reference?

-- Timothy Y. Chow <tycchow@math.mit.edu>

> If you assume that there is an optimal strategy,

I forgot to object to this before.  The assumption needs to be
justified at some point.  I don't think it can be.

> fallacy of composition---the strategy that works best for the
> individual does not work well when everyone takes it.

Oops.  This is the usual fallacy of composition but I wanted to invert
it.  "All fire into the air" seems to be best (or at least very good)
for the three shooters as a group when everyone takes it, but it is not
the best for each one individually, in the sense that each individual
could improve his or her outcome by shooting someone.

Thanks to Timothy Y. Chow for explaining the "Nash equilibrium," which
I think is a much better formulation for what I was trying to put
across.  After a quick calculation, I believe there is no Nash
equilibrium in which each shooter has a non-zero probability p_i of
shooting into the air.  If there were, you could perturb any shooter's
strategy, say shooter j, by reducing p_j, and the shooter would be
better off.

-- David Karr <karr@cs.cornell.edu>

As long as both of the other players are still alive, fire into the
air.  If all three players are rational, and use this strategy,
everybody survives.  Anybody who deviates from this strategy risks
killing one opponent and then being killed by the other.  (This has
been given as a reason why global stability requires exactly three
superpowers.  Probably in one of Martin Gardner's columns.)

-- Karl Heuer <karl@ursa-major.spdcc.com>

[ Editor: after a long exchange with Thompson, Karr summed up (February
1994): ]

I think the various arguments we've seen so far *have* been finished
off -- at least logically, leaving only aesthetic considerations.  So
far each argument has had an unsupported assumption somewhere along the
line, such as the premise that there must be a unique optimal solution
that all rational players must take.

"Survival first, and after that kill the bastard" is a crude but
accurate assessment of the goal.  And clearly the truellists are not
going to be influenced by any extraneous goals like pacifism.  On the
other hand, there is no absolute assurance that whatever A thinks will
be thought by B and C as well.  Under these conditions, each shooter
has something to gain and nothing to lose by shooting at another, and
that is what they will do, as various people from Poundstone to Seal
have explained.

Now if you equip each shooter with a special machine that continually
scans the other shooters' minds, predicts their thoughts and actions
for the next few seconds, and displays these in a readout visible to
the shooter, then you might have a different problem.  In this case it
is conceivable (to me, at least) that if I am shooter A, my reasoning
(and resulting decision) *might* affect the reasoning (and resulting
decisions) of B and C.  But that's a variation on the Newcomb problem,
which is a whole different can of worms.

-- David Karr <karr@cs.cornell.edu>

[ Editor: see also decision/truel for the classic truel with unequal
marksmen. ]