Who Will Win The Politicians’ Secret Vote?

Five politicians, Anders (A), Blinton (B), Cubio (C), Drump (D) and Eruz (E), pick their candidate by a sequence of votes. First A is paired against B; the winner is paired against C, that winner against D, and that winner against E, with the survivor of the last vote becoming the candidate. All five vote in every round, everyone wants to be the candidate, and the full preference orderings are common knowledge: $$\begin{aligned} &A: A\!>\!B\!>\!C\!>\!D\!>\!E, \qquad B: B\!>\!A\!>\!E\!>\!D\!>\!C,\\ &C: C\!>\!D\!>\!A\!>\!E\!>\!B, \qquad D: D\!>\!B\!>\!A\!>\!E\!>\!C,\\ &E: E\!>\!D\!>\!B\!>\!C\!>\!A. \end{aligned}$$ Everyone votes strategically. (1) Who is chosen? Now suppose A has the flu and must miss the meeting, but may transfer his vote to another politician (who still votes in her own interest). (2) To whom should he give it? (3) Who wins then? (4) Should A have got the flu vaccine?

The Riddler, FiveThirtyEight (Thomas Schelling, via Barry Nalebuff and Laura Feiveson)(original post)

Solution

The one idea is that a strategic voter does not vote for whom she prefers now, but for whichever contestant leads to the final nominee she prefers. That makes the agenda solvable from the last vote backwards: once you know what eventual nominee each survivor produces, every earlier vote is just a comparison between two known nominees.

Start at the last vote, where a survivor $X$ faces $E$. Each voter backs $X$ or $E$ by their own ordering, and the majority decides: $$A\text{ beats } E,\quad B\text{ beats } E,\quad E\text{ beats } C,\quad D\text{ beats } E.$$ So reaching the final produces nominee $A,B,E,D$ when the survivor is $A,B,C,D$ respectively. Note the trap already visible here: letting $C$ into the final hands the prize to $E$. Carrying this comparison back through the vote against $D$, then $C$, then the opening $A$ versus $B$, every round resolves to a single nominee, and the chain ends at $$\boxed{D}.$$ Now remove A as a voter and let him hand his vote to one ally. Trying each recipient, only one bends the chain his way: giving his vote to $E$, his least favourite, tips a pairwise contest so that the agenda now resolves to $A$ himself. So he should transfer it to $\boxed{E}$, the winner becomes $\boxed{A}$, and since being absent makes him the nominee while attending only makes $D$, he should skip the vaccine: $\boxed{\text{no}}$. Throwing his weight behind his worst rival is exactly what clinches his best outcome.

The computation

Encode the agenda and let the voters reason backwards. For any standing contestant facing the remaining challengers in order, compare the eventual nominee produced by each side of the next vote, let every voter (with a weight, so a transferred vote counts twice) back the side it prefers, and recurse on the round’s winner.

prefs = {'A':'ABCDE','B':'BAEDC','C':'CDAEB','D':'DBAEC','E':'EDBCA'}
rank = {v:{c:i for i,c in enumerate(o)} for v,o in prefs.items()}

def outcome(standing, remaining, weight):
    if not remaining:
        return standing
    ch, rest = remaining[0], remaining[1:]
    win_keep = outcome(standing, rest, weight)     # eventual nominee if standing survives
    win_take = outcome(ch,       rest, weight)     # eventual nominee if challenger wins
    keep = sum(w for v, w in weight.items()
               if rank[v][win_keep] < rank[v][win_take])
    total = sum(weight.values())
    winner = standing if keep * 2 >= total else ch
    return outcome(winner, rest, weight)

base = {v: 1 for v in 'ABCDE'}
print("Q1:", outcome('A', list('BCDE'), base))
for r in 'BCDE':                                    # A absent, vote weight 2 to r
    w = dict(base, A=0); w[r] = 2
    print("  give to", r, "->", outcome('A', list('BCDE'), w))
# Q1: D
#   give to B -> B
#   give to C -> D
#   give to D -> D
#   give to E -> A      <- best for A, so transfer to E; A wins; skip the vaccine