Bottom N and Bottom 2 Runoffs are Equivalent

[cfrank]

Let s:N to R and hth:NxN to R be fixed functions (“score” and “head-to-head”), where s is injective, and where hth(y,x)=-hth(x,y) and hth(x,y)=0 if and only if x=y (“no ties”).

For a finite subset C of N (“candidates”), let B2R(C) denote the “Bottom 2 Runoff” winner in C, determined by repeatedly pitting the bottom two scoring candidates against each other in a head to head, and eliminating the loser until one candidate (the winner) remains.

Also, let RCLE(C) denote the “Recursive Condorcet Loser Elimination” winner in C, determined by repeatedly looking at the N lowest-scoring candidates, and eliminating any Condorcet loser among them (if none, update N↦N−1 and retry), until one (the winner) remains.

Both B2R and RCLE are Condorcet compliant and Condorcet loser compliant methods. It also turns out that they are equivalent.

PROOF:

We can proceed by induction on the size of C. With 1 or 2 candidates, the equivalence is trivial.

Otherwise, without loss of generality, we can assume that there is no Condorcet winner in C (in that case B2R automatically coincides with RCLE, since both are Condorcet compliant). We can also assume that there is no Condorcet loser in C, because that Condorcet loser will immediately be eliminated in RCLE, and will have no material effect on B2R. More formally, if L is the Condorcet loser in C, then B2R(C)= B2R(C omitting L), and RCLE(C) = RCLE(C omitting L).

Consider the first candidate eliminated by each method, and call them B2R1 and RCLE1, respectively. If B2R1=RCLE1, then we will be done by the inductive hypothesis. Thus, we have to examine the case where B2R1 differs from RCLE1. In that case, the only option is that RCLE1 loses head-to-head against every other candidate in the set of bottom-N scorers for some N >= 3. In particular, RCLE1 loses head-to-head against every candidate whose score is lower than its own. In B2R, no matter which of the candidates whose scores are lower than RCLE1's emerges to face RCLE1, it will beat out RCLE1 head-to-head. Therefore, the presence of RCLE1 in the candidate pool is immaterial to the outcome of B2R. Formally, it follows that B2R(C)=B2R(C omitting RCLE1). But necessarily, RCLE(C)=RCLE(C omitting RCLE1) as well. And by the inductive hypothesis, B2R(C omitting RCLE1) = RCLE(C omitting RCLE1), which implies that B2R(C)=RCLE(C).

QED

This is true no matter which scoring or head-to-head functions are used, as long as they are static functions and no ties are involved.