Ernie and the literary criticism

Question

When I dropped in on Ernie over the weekend he commented that he hadn’t seen me for a while. I had to confess that my evenings had been very busy recently - first at the local Community College doing a course on creative writing, and then at home writing my first novel.

“It is a spy story – dramatic and gripping but imbued with a sense of gritty realism!” I expounded proudly. I went on to explain how the protagonists were three agents of the Kzijekistanian Secret Service (KSS) who had discovered a sinister plot hatched in the neighboring dictatorship of Spoznikia. The Spoznikians were planning to assassinate the co-chairs of the Kzijekistanian Ruling Triumvirate and replace them with puppet leaders. The agents had indisputable evidence of the plot, but they had been betrayed by a Spoznikian double agent and, after a ferocious gun-battle, were now barricaded in a small room at the top of the radio tower of Spoznikia’s Department of Propaganda, with enemy agents in close pursuit.

“Very dramatic “, commented Ernie. “What happens next?”, so I continued with my plot summary. “The agents, known only by their initials A, B, and C, realize they cannot fight their way out as they have less than a handful of bullets left. But they have a single pair of Acme Inc.® Wing-Suit-Underwear™ (one size fits all) – so one of them could glide from the tower into the Spozkzij River, swim through the rapids, ascend the cliffs below, cross the border minefield, and get the evidence to the Kzijekistanian authorities. But, by use of truth serum, the Spoznikians will gather vital information from the other two if they surrender. So they decide on the ultimate sacrifice – two must die before the Secret Police can break down the barricaded penthouse door”.

“Gritty too”, broke in Ernie, “Who should the survivor be?”, so I continued with my summary. “The Spozknikians will almost certainly see the wing-suit and try to guard the escape route – but they are short of soldiers after a recent army purge and won't only be able to guard the river, the cliffs, and the mine-field simultaneously. The Kzijekistanian agents, who coincidentally are all brilliant mathematical logicians, combine that information with their own respective individual expertise at swimming, cliff-scrambling, and sneaking and use game theory to calculate that the most successful strategy is that escaping agent should be chosen randomly, with the relative probabilities p:q:r, for agents A:B:C respectively”.

“Game theory!”, exclaimed Ernie. “So it is a gripping story as well. How do the agents choose the survivor?”. “I’m glad you asked”, I replied. “The agents will choose via a truel”. I went on to explain how that worked – “The three duelists are named A, B, and C and have accuracy of a%, b%, and c% and...”

“Well – that’s a pity”, Ernie broke in, “you just failed on the realism side of things. The KSS is renowned for the marksmanship of its agents – they always shoot with an accuracy of 100%. But even if you ignored that – with only a ‘handful of bullets left’ they could run out of bullets before completing your truel!”

My heart sank as I realized that Ernie’s criticism was completely justified. “But maybe there is a solution”, Ernie continued. How about the three agents compete in a Круговая дуэль”. When I asked what that was Ernie said that he wasn’t sure how it translated into English – but that it was a traditional historic pastime for Kzijekistanians when they got depressed sharing snowed-in huts during long and bleak winters. “But I can explain the rules”, he continued:

Rules of Круговая дуэль for $n$ players

1. The $n$ players sit in a small circle, so that in clockwise order they are labelled $1,2,3...n$ (note that player $1$ is of course clockwise to player $n$).

2. Each player $i$ has a revolver with $C_{i}$ chambers, that is initially loaded with $B_{i}$ bullets

3. Player $1$ has the first turn, after which the turn goes to the first living player clockwise to the player who has just played. This continues until only one player is left alive.

4. A turn consists of the following three steps:

   a. The player spins the chamber of their revolver.

   b. The player aims their revolver at the living opponent with the highest chance of firing a bullet on that opponent's turn (on the assumption that the opponent will still be alive at that time). If two or more opponents have the same maximum chance then the player aims at the first such opponent in the circle (counting clockwise from the player's position).

   c. The player pulls the trigger once (inevitably killing the opponent if the revolver fires).

That sounded like a perfect solution to me (especially with the added bonus of historical accuracy) so I asked for him to help with the details.

“OK Ernie”, I started, “I want a solution guaranteed to achieve an $A:B:C$ ratio of $1/6:1/3:1/2$ (that matches the game theory results that I had imagined them calculating).” -- “No problem”, Ernie replied.

“…And I want a solution that uses the smallest possible number of bullets, to emphasize how dire their situation is.” -- “No problem”, Ernie replied.

“…And I want the players to shoot in the order A-B-C…, because that matches the dialog I have already written.” -- “Sorry”, said Ernie, “that order of play isn't consistent with the smallest possible number of bullets.”

“OK”, I said – thinking that I could swap the dialog around a bit – “…how about they shoot in order B-A-C…?” -- “Theoretically possible”, said Ernie, ”but highly unrealistic. I doubt the KSS have revolvers with the required number of chambers in their arsenal.”

“Then”, I said – accepting that the dialog might require a more significant rewrite. “…how about they shoot in order B-C-A…?” -- “There is definitely a solution for that.” Ernie replied, and wrote down the numbers of chambers and bullets each of the three agents needed on the back of an envelope.

Unfortunately, the envelope slipped through a hole in my pocket while I was cycling home so I have lost the information I need to complete my novel. Can anyone help me recover it? It would also be nice to get my head around what precisely was wrong with the A-B-C… and B-A-C… scenarios.

Answer 1

First of all, how do we find the winning probabilities given the agents' numbers of bullets and chambers? This is pretty straightforward if there are only two agents. In this case, whoever first fires an actual bullet will win. Suppose they have probabilities $p,q$ of doing so on a given turn (so these are the ratios bullets/chambers for the two agents) and win probabilities $P,Q$ when going first; then $P=p+(1-p)(1-Q),Q=q+(1-q)(1-P)$, and we can solve these to find $P=\frac{p}{p+q-pq},Q=\frac{q}{p+q-pq}$. Call the first of these $P(p,q)$; we'll need to use that later, because after the first shot is fired the two surviving agents are in a 2-agent game.

With three agents (or more) things are made more complicated by the fact that each agent chooses which other agent to fire at in a way that depends on the ordering of their per-shot hit probabilities. Whatever that ordering is, we will get a set of simultaneous equations for the quantities $p_{AB}$ etc., where $p_{AB}$ is the probability that $A$ wins when $B$ goes first. Suppose, for instance, that $B$ has a higher per-shot hit probability than $C$, so that $A$ will fire at $B$ in preference to $C$. Write $p_A,p_B,p_C$ for those per-shot probabilities; it will also be useful to have names $q_A,q_B,q_C$ for the corresponding probabilities after using one bullet. Then one of our simultaneous equations is $p_AA=p_A(1-P(p_C,q_A))+(1-p_A)p_AB$, which says that with $A$ going first $A$ can win either by firing a shot (with probability $p_A$), killing $B$, and then winning the remaining game against $C$ (with probability $1-P(p_C,q_A)$ because $C$ plays first and $A$ has now used one bullet), or else by not firing a shot and then winning the game with $B$ playing first. We'll get nine of these equations, all having a similar form (except that three of them, the ones where the player whose winning probability we're asking about would be the target of the one whose turn it is, have a zero in place of the first term). These nine equations (we always get nine of them, though exactly what they are depends on that ordering of per-shot probabilities) are always linearly independent and determine a unique set of winning probabilities.

Filling in the details is a bit tedious and error-prone, so I taught my computer to do it, working with exact rational numbers to avoid numerical error; it builds up a 9x9 set of simultaneous equations and solves them by Gaussian elimination. And I take Ernie's remarks in the question to indicate that we are looking (at least for the final BCA ordering) for solutions using physically-plausible numbers of chambers in the revolvers. Real-life revolvers pretty much always seem to have between 5 and 12 chambers. I've allowed any number of chambers from 2 to 12, independently for each agent's revolver.

I've checked it against a more naive simulation that, instead of producing exact probabilities, just runs the "gunfight" many times and counts who wins how often. The results match, so if I've erred then I've erred the same way twice.

So, here are the relevant results.

If A,B,C start with 1/5, 2/5, 1/6 bullets (plausible numbers since 5-chamber and 6-chamber revolvers are both common) then in BCA order their probabilities are as required.

The same is true if they start with 2/2, 1/2, 1/2 and play in BAC order -- but that would require the agents to have 2-chamber revolvers, which I don't think exist and certainly aren't commonplace.

Those both use four bullets in total (and are the only 4-bullet configurations that yield the desired probabilities, with any order of play). With five bullets we can get ABC order, in exactly one way: 1/9, 3/12, 1/10. As well as being inconsistent with using the minimal number of bullets (as Ernie points out), these are not common revolver configurations. (Though I think all do exist.)

Since my computer did the work, it seems only fair to provide the code. It's not very elegant. There are standard Python libraries for doing linear algebra, but I don't think they work with the exact rational numbers provided by the fractions module, so I wrote my own simple-minded Gaussian elimination code. Here it all is. The implementation of probs could be made less redundant (it does basically the same thing three times) but at some cost in clarity.

---

# we need to be able to solve linear equations
def solve(M,R):
  # sum_j M[i][j] var[j] = R[i]
  n = len(R)
  i,j = 0,0 # candidate pivot row,column
  while i<n and j<n:
    (pivot,ii) = max((abs(M[ii][j]),ii) for ii in range(i,n))
    if pivot==0:
      j += 1
      continue
    M[i],M[ii] = M[ii],M[i]
    R[i],R[ii] = R[ii],R[i]
    # pivot now in row i, col j
    for ii in range(i+1,n):
      f = M[ii][j]/M[i][j]
      M[ii][j] = 0
      for jj in range(j+1,n): M[ii][jj] -= f*M[i][jj]
      R[ii] -= f*R[i]
    i += 1
    j += 1
  # now matrix is in row echelon form; back-substitute
  # I claim the matrix is never singular, so in fact we will never have hit
  # a zero pivot and we have a nonzero diagonal
  vals = n*[0]
  for i in range(n-1,-1,-1):
    r = R[i]
    for j in range(i+1,n): r -= M[i][j]*vals[j]
    vals[i] = r/M[i][i]
  return vals

def win1(pA,pB):
  # A plays first; shot probs at this point are pA,pB
  # prob that A wins
  return pA / (pA+pB-pA*pB)

def win2(pA,pB):
  # B plays first; shot probs at this point are pA,pB
  # prob that A wins
  return (F(1,1)-pB)*pA / (pA+pB-pA*pB)

def probs(a_bu,a_ch, b_bu,b_ch, c_bu,c_ch):
  # order of play is A->B->C->A->...
  pA,qA = F(a_bu,a_ch),F(a_bu-1,a_ch)
  pB,qB = F(b_bu,b_ch),F(b_bu-1,b_ch)
  pC,qC = F(c_bu,c_ch),F(c_bu-1,c_ch)
  # pA is A's shot prob now; qA is A's shot prob after shooting
  # we are computing pAB etc., where pAB means prob A wins when B shoots next
  # we'll work with a vector pAA pBA pCA pAB pBB pCB pAC pBC pCC
  # and construct a 9x9 matrix for solution
  iAA,iBA,iCA,iAB,iBB,iCB,iAC,iBC,iCC = 0,1,2,3,4,5,6,7,8
  M = [9*[0] for i in range(9)]
  R = 9*[0]
  # equation i says sum_j M[i][j] prob[j] = R[i]
  if pB >= pC:
    # A shoots at B rather than C; then
    # pAA = pA win2(qA,pC) + (1-pA) pAB
    # pBA = pA 0           + (1-pA) pBB
    # pCA = pA win1(pC,qA) + (1-pA) pCB
    M[0][iAA] = F(1,1); M[0][iAB] = -(1-pA); R[0] = pA*win2(qA,pC)
    M[1][iBA] = F(1,1); M[1][iBB] = -(1-pA); R[1] = F(0,1)
    M[2][iCA] = F(1,1); M[2][iCB] = -(1-pA); R[2] = pA*win1(pC,qA)
  else:
    # A shoots at C rather than B; then
    # pAA = pA win2(qA,pB) + (1-pA) pAB
    # pBA = pA win1(pB,qA) + (1-pA) pBB
    # pCA = 0              + (1-pA) pCB
    M[0][iAA] = F(1,1); M[0][iAB] = -(1-pA); R[0] = pA*win2(qA,pB)
    M[1][iBA] = F(1,1); M[1][iBB] = -(1-pA); R[1] = pA*win1(pB,qA)
    M[2][iCA] = F(1,1); M[2][iCB] = -(1-pA); R[2] = F(0,1)
  # now same cyclically for outcomes where B or C goes first
  # B first:
  if pC >= pA:
    # B shoots at C rather than A; then
    # pBB = pB win2(qB,pA) + (1-pB) pBC
    # pCB = pB 0           + (1-pB) pCC
    # pAB = pB win1(pA,qB) + (1-pB) pAC
    M[3][iBB] = F(1,1); M[3][iBC] = -(1-pB); R[3] = pB*win2(qB,pA)
    M[4][iCB] = F(1,1); M[4][iCC] = -(1-pB); R[4] = F(0,1)
    M[5][iAB] = F(1,1); M[5][iAC] = -(1-pB); R[5] = pB*win1(pA,qB)
  else:
    # B shoots at A rather than C; then
    # pBB = pB win2(qB,pC) + (1-pB) pBC
    # pCB = pB win1(pC,qB) + (1-pB) pCC
    # pAB = 0              + (1-pB) pAC
    M[3][iBB] = F(1,1); M[3][iBC] = -(1-pB); R[3] = pB*win2(qB,pC)
    M[4][iCB] = F(1,1); M[4][iCC] = -(1-pB); R[4] = pB*win1(pC,qB)
    M[5][iAB] = F(1,1); M[5][iAC] = -(1-pB); R[5] = F(0,1)
  # and C:
  if pA >= pB:
    # C shoots at A rather than B; then
    # pCC = pC win2(qC,pB) + (1-pC) pCA
    # pAC = pC 0           + (1-pC) pAA
    # pBC = pC win1(pB,qC) + (1-pC) pBA
    M[6][iCC] = F(1,1); M[6][iCA] = -(1-pC); R[6] = pC*win2(qC,pB)
    M[7][iAC] = F(1,1); M[7][iAA] = -(1-pC); R[7] = F(0,1)
    M[8][iBC] = F(1,1); M[8][iBA] = -(1-pC); R[8] = pC*win1(pB,qC)
  else:
    # C shoots at B rather than A; then
    # pCC = pC win2(qC,pA) + (1-pC) pCA
    # pAC = pC win1(pA,qC) + (1-pC) pAA
    # pBC = 0              + (1-pC) pBA
    M[6][iCC] = F(1,1); M[6][iCA] = -(1-pC); R[6] = pC*win2(qC,pA)
    M[7][iAC] = F(1,1); M[7][iAA] = -(1-pC); R[7] = pC*win1(pA,qC)
    M[8][iBC] = F(1,1); M[8][iBA] = -(1-pC); R[8] = F(0,1)
  # now solve the equations
  M0 = [row[:] for row in M]
  R0 = R[:]
  p = solve(M,R)
  # and we want pAA, pBA, pCA -- probabilities of various wins given A goes first
  return p[:3]

# there is a solution with "reasonable" numbers of chambers
# which I'm pretty sure is smaller than, say, 12 per revolver
# and obviously total #bullets <= total #chambers
# anyone with 0 bullets can never be last man standing; all probs > 0, so no 0s
# if all have 1 bullet then whoever has fewest chambers can't win, because
# both opponents would have to die, at most one killed by him, but the other two
# will always prefer to shoot at him
# if anyone has 1 bullet, 1 chamber then the same applies
for total_bu in range(1,37):
  print(f"trying #bullets={total_bu}")
  for a_bu in range(1,total_bu+1):
    for b_bu in range(1,total_bu-a_bu+1):
      c_bu = total_bu - a_bu - b_bu
      if min(a_bu, b_bu, c_bu) <= 0 or max(a_bu,b_bu,c_bu) <= 1 or max(a_bu, b_bu, c_bu) > 12: continue
      for a_ch in range(max(2,a_bu),13):
        for b_ch in range(max(2,b_bu),13):
          for c_ch in range(max(2,c_bu),13):
            p = probs(a_bu,a_ch, b_bu,b_ch, c_bu, c_ch)
            if p == (F(1,6),F(2,6),F(3,6)): print(f"ABC : {a_bu}/{a_ch} {b_bu}/{b_ch} {c_bu}/{c_ch}")
            p = probs(b_bu,b_ch, a_bu,a_ch, c_bu,c_ch)
            if p == (F(2,6),F(1,6),F(3,6)): print(f"BAC : {a_bu}/{a_ch} {b_bu}/{b_ch} {c_bu}/{c_ch}")
            p = probs(b_bu,b_ch, c_bu,c_ch, a_bu,a_ch)
            if p == (F(2,6),F(3,6),F(1,6)): print(f"BCA : {a_bu}/{a_ch} {b_bu}/{b_ch} {c_bu}/{c_ch}")```