How to achieve the best outcome by a single statement in this game?

Question

This game is taken from Schelling's Game Theory: How to Make Decisions by R.V. Dodge, in which contenders practice brinksmanship to their own advantages. It goes as follows:

Anderson, Barnes, and Cooper are to fight a gun duel. They will stand close to one another, so that each can kill one of the others in one shot or deliberately miss. The first to fire will be chosen at random, and they will rotate in the order Anderson, Barnes, and Cooper, each firing one shot at a time.

If there is more than one survivor after a number of rounds, one of the contenders will be chosen at random and forced to kill one of the others, and this will be repeated if there is still more than one alive after a few more rounds.

Before the duel starts, Anderson may make any statement, followed by a statement from Barnes, and finally one from Cooper. They will adhere to the following rules:

1. Statements are irrevocable. A contender may not act to contradict his statement.
2. He will act in his own best interest when it does not conflict with Rule One.
3. He will act randomly when it does not conflict with Rules One and Two.

There are referees to ensure that the rules are followed. If a contender commits himself to a mixed strategy (for example, to miss with a probability of 1/3), the probability will be determined objectively (by tossing dice, etc.).

Q1: What statement will Anderson make? What's his best strategy and his probability of surviving?

Q2: If three contenders are to make their statements in the order of ACB, what would be the best statement for Anderson?

Q3: If there're more than three contenders, does this game become simpler or more difficult? Can we say anything about the $N$ contenders case for $N\gt 3$?

---

Notice that if no one makes any statement, no one will shoot, and everyone has a surviving chance of 1/3. If only Anderson is allowed to make a statement, he can guarantee near certain survival by making this statement to B and C: "If you don't kill each other at your first opportunities, I will kill the first of you who fail to do so at my first opportunity; otherwise, I'll shoot at the survivor of you with 1% chance of missing."

In the book, a suggested best solution for Q1 is for A to say:"If B does not commit to unconditionally shooting C, I will shoot him." The argument is that B has no choice but to accept, because refusing A's proposal would result in certain death for B. But that is clearly erroneous! Because B can say: "If C doesn't promise to kill A at his first opportunity, I will kill C at mine; if C does, I will kill A at my first opportunity and shoot at C with 1% chance of missing if he kills A first." By refusing B's proposal C has 2/3 chance to survive (1/3 for A shooting first and 1/3 for C shooting first); by accepting he has 2/3+0.33% chance (1/3 for A shooting first, 1/3 for B shooting first and 0.33% for C shooting first). So C will accept. Then A is doomed, bound by his own inconvenient statement.

Answer 1

A caveat, this is not really an answer, more of an extended comment--that's why I've put it as community wiki. This is a cool game, one of commitment.

I'll try to formalize the problem. This is a first pass, so people should edit as they see fit.

It's probably easiest to solve the case where, $T$, the number of rounds before a forced execution is $1$. Let each player get $1$ if they shoot someone else and $-1$ if they are themselves shot.

There are two stages of the game, the commitment stage and the shooting stage. The sequential stage is (fittingly) sequential move and the commitment stage is not really a game persay, since the players are automata (their strategies are predetermined). I'll return to this shortly.

An easy result: there is an equilibrium in which rules 2 and 3 are rendered superfluouous since each player can commit to every possible contingency.

There is a source of exogenous randomness, a random state of the world $\Theta = \Theta_{1} \times \Theta_{2}$, $i = 1,2$, where $\Theta_{i}$ is the set of permutations of $\left\{A,B,C\right\}$. These are the possible orders in the shooting portion.

The set of actions for player $A$ is $\mathcal{A} = \mathcal{A}_{1} \times \mathcal{A}_{2}$ where $\mathcal{A}_{i} = \left\{B,C,\emptyset\right\}$ for $i = 1,2$ (corresponding to "shoot $B$," "shoot $C$," and "shoot nobody," respectively). The sets of actions for the other two players, $\mathcal{B}$ and $\mathcal{C}$, are defined analogously.

A (mixed) commitment strategy of $A$ is a mapping $$\sigma_{A}: \Theta \times \Sigma_{B} \times \Sigma_{C} \to \Delta\left(\mathcal{A}\right)$$ where $\Sigma_{i}$, $i = A, B, C$ is the set of all (feasible) mixed strategies. An example of an infeasible strategy for player $A$, say, is one that does not have $\emptyset$ played with probability $1$ when the state and mixed strategies of the other players are such that $A$ has been shot for certain.

Note that I am using the fact that the shooting portion of the game can be viewed as a instantaneous (random) outcome of the commitment portion, which is the real game.

I'm not quite sure about the commitment strategies for $B$ and $C$, due to the sequential move nature of the commitment stage. I suspect that that does not matter, and that they are defined analogously. I'm not completely sold on this and open to being convinced otherwise.

Each player's payoff is defined in the obvious way.

Answer 2

Schelling himself gave an answer for Q1 in which A can achieve a surviving probability arbitrarily close to 5/6. I quote the book below. The wording is painfully tortuous at times. But the answer seems right. I don't know if it's THE BEST result A can achieve.

Professor Schelling offered a solution that guarantees Anderson near certainty of survival, by including probabilities in his shots. In this solution Anderson commits to shoot with a small probability of missing at whoever has killed the other, but if Cramer fails to kill Barnes, to kill Cramer. He must include something to prevent any unilateral commitments either Barnes of Cramer could make to top his, so he would add that if either of them makes a commitment other than to accept his, he will kill that person in his turn or shoot in the air if the person is dead. If both make unilateral commitments, Anderson guarantees to kill Cramer or if Cramer is already dead, shoot in the air (rules of duel will be enforced). Schelling’s answer:

Anderson has to forestall a commitment by Barnes that gives Cramer a better chance of surviving, which he could do by saying, “If you do not accept my proposal I shall kill you at my turn. If you accept it, I guarantee you a two-thirds chance of living, as follows: If Anderson is committed to kill me upon your accepting my proposal, then I promise to kill Anderson if you promise to kill Anderson. If Anderson is uncommitted as to whom he shoots once you have accepted my offer, there is a 50–50 chance he will shoot me. If you are the one to kill him, I will shoot at you with a 50% chance of killing you. Finally if Anderson is committed to kill each of us with specific probabilities such as .8 he will shoot you and .2 he will shoot me if we both commit, then I will shoot at you with a probability of .2 of killing you after you have killed Anderson.”

If Anderson does not make as good an offer to Cramer, Barnes’ offer will be accepted and Anderson will surely be dead. If Anderson makes the equivalent offer to Cramer, Cramer has a 2/3 chance of surviving or accepts Barnes’ offer. If he accepts Barnes’ offer there is a 1/3 chance Anderson will kill him, otherwise he lives because he kills Anderson if Barnes is killed first. If he does not accept Barnes’ offer Barnes will kill him if he gets the chance, otherwise Anderson will kill Barnes. Since Cramer’s chances are the same whether or not he accepts Barnes offer, rule three says he decides at random, so Barnes has a 50–50 chance of achieving a 1/3 chance of living if he accepts this.

If Anderson cannot top Barnes’s 1/6 chance of living that would come with equal proposals he cannot forestall the commitment, which leaves him with the same probability. He must do better for Barnes to keep his mouth shut.So. Anderson’s statement: “If Barnes makes an offer and Cramer accepts it, I will kill Cramer in my turn or shoot in the air if Cramer is already dead. If Barnes makes an offer and Cramer does not accept it I will kill Barnes in my turn or shoot in the air if he is already dead. If anyone makes a unilateral commitment not depend- ing on a response, I will kill the last one to do that, or shoot in the air if he is already dead. Otherwise, if Cramer fails to kill Barnes at his first opportunity, Barnes being still alive, I shall kill him. If Cramer kills Barnes I will shoot at him with a 1% probability of missing. If Barnes kills Cramer I shall shoot at him with a 27% likelihood of missing.”

If Barnes and Cramer keep their mouths shut there is a 2/3 chance of their firing first. If Anderson is first he will shoot in the air and Barnes will kill Cramer and have a 27% possibility of surviving. If Cramer is first Barnes is dead, so Barnes probability of survival is 2/3 of 27% or 18%. Cramer keeps quiet and has a 1% chance of surviving if he is first to shoot, and .33% chance overall. That leaves Anderson with 71.67% chance of surviving.

Schelling concludes that by giving Cramer an even smaller likelihood than 1% and Barnes an increment on top of 1/6 Anderson can make his own chances as near to 5/6, or 84%, as he wishes.

Answer 3

Here is a proof that the response given by Schelling in Eric’s answer is (as good as) the best A can do.

A can only do so much in retaliation for B and C teaming up against him. He can threaten to shoot B with certainty, threaten to shoot C with certainty, or some mix of the two. Let’s call y the probability he will shoot C if they team up against him, where he’ll shoot B with a probability of 1-y (there isn’t much point to him shooting neither of them).

Regardless of what A has said, B can always make the statement:

"If C commits to shooting A in the first round, I will do the following:

-If I am the first to shoot I will shoot A with x accuracy (where x is some number between 0 and 1)

-If I am second to shoot I will shoot A with perfect accuracy.

-If I am third in the order (meaning A will already be dead) I will fire in the air and let C win the duel.

If C does not commit to shooting A I will shoot C no matter what."

If C follows B’s plan they will have at least a $\frac{2+x-y}{3}$ chance of survival, while B will have at least a $\frac{1-x+y}{3}$ chance of survival. If C ignores B’s plan they will have at best a 2/3 chance of survival, since if B is chosen to shoot first C will die for certain. If C is indifferent between teaming up and ignoring they will randomize and choose to team up half the time, while ignoring the other half of the time.

For any y, B can choose x=y which guarantees that C will accept the offer at least half the time, and B will have at least a 1/6 chance of survival. Since B can guarantee themselves a 1/6 chance of survival, it cannot be the case that A can guarantee himself a greater than 5/6 chance of survival.

Answer 4

If only one player is allow to make a statement, we have the following Theorems:

Theorem 1: If $N\gt 3$, then survival probability for that contender must be strictly less than $\frac{N-1}N$.

Proof:

WLOG, suppose only player $1$ can make a statement and players $2$~$N$ must keep silent. Notice that by killing player $1$ in their turns, players $2$~$N$ will bring the game to a subgame where $N-1$ players are alive and no one has made any statement. In this subgame each player has $\frac1{N-1}$ survival probability. So in the original game players $2$~$N$ each have a survival probability at least $\frac1{N(N-1)}$. This means player $1$ has survival probability strictly less than $1-\frac{N-1}{N(N-1)}=\frac{N-1}N$. QED

Theorem 2: For $N=4$, Theorem 1 gives the least upper bound, i.e. $\forall \varepsilon\gt 0$, there's a statement for player $1$ such that his surviving probability $P_{1}^{4}=3/4-\varepsilon$.

Proof: Similar as the proof for Theorem 3.

Theorem 3: For $N=5$ we can prove there's a statement for player $1$ such that $P_{1}^{5}=3/5-\varepsilon$, $\forall \varepsilon\gt 0$. The statement for player $1$ will be too long to put into actual words, but it works as below.

Proof:

Name the players $A_i$ for $i=1$ to $5$. $A_1$'s strategy is to persuade whoever is currently shooting to shoot a player after him, by promising him a surviving probability of $\frac1{M-1}+\varepsilon$, until only $3$ players remain, where $M$ is the number of players alive. When players are reduced to three, $A_1$ can then allocate the probabilities he promised to the other two players. There're 5 possibilities corresponding to who's chosen to shoot first by the referees. We'll illustrate with the case where $A_2$ is first to shoot.

$A_1$ will have stated that in this case, $A_2$ must kill $A_3$, after that, $A_4$ must kill $A_5$. For this to happen, he must promise them surviving probabilities $\frac1{4}+\varepsilon$ and $\frac1{3}+\varepsilon$ respectively, otherwise they will be better off killing $A_1$ (if promised probabilities are less than $\frac1{4}$ and $\frac1{3}$), or by Rule 3 randomize (if promised probabilities are equal to $\frac1{4}$ and $\frac1{3}$). The promised probabilities can be realized in the three way duels between $A_1$, $A_2$, $A_4$ by some appropriate commitment such as this: "$A_2$ shall shoot at $A_3$ with $\frac1{4}+\varepsilon$ probability of killing. If he kills, I'll miss and let him kill me too; if he misses, $A_3$ must kill him, then I'll shoot at $A_3$ with $\frac{\frac1{3}+\varepsilon}{\frac3{4}-\varepsilon}$ probability of killing. I shall kill anyone who first violates this proposal at my first opportunity." This leaves $A_1$ with surviving probability $\frac5{12}-2\varepsilon$.

Other 4 possibilities are calculated similarly, yielding surviving probabilities for $A_1$ as $\frac5{12}-2\varepsilon$, $\frac3{4}-2\varepsilon$, $\frac3{4}-2\varepsilon$, $\frac2{3}-2\varepsilon$ corresponding to $A_3$, $A_4$, $A_5$, $A_1$ shooting first respectively. Summing them up and dividing the result by 5 yields $P_{1}^{5}=3/5-2\varepsilon$. QED