Bottom N and Bottom 2 Runoffs are Equivalent

[cfrank]

Bottom 2 Runoff (B2R) is a Smith-compliant cardinal-Condorcet method. We can describe it generally by considering two independent "score" and "head-to-head" functions over a candidate set.

To be precise, if Z+ is the set of natural numbers, let s:Z+ to R ("score") and hth:Z+xZ+ to R (“head-to-head”) be fixed real-valued functions, 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”). In our case we consider a set C of “candidates” to be a finite subset of Z+.

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 set of N lowest-scoring candidates, starting with the full set C, and eliminating any Condorcet loser among them (if none, update N↦N−1 and retry, resetting to the full remaining set with each elimination), until one candidate (the winner) remains.

Both B2R and RCLE are Condorcet compliant and Condorcet loser compliant methods. It also turns out that for fixed score and head-to-head functions with no ties, they are equivalent.

PROOF:

We can proceed by induction on the size of C. With 1 or 2 candidates, the equivalence is trivial. So we consider |C|>=3.

Without loss of generality, we can assume that there is no Condorcet winner in C—with a Condorcet winner, B2R automatically coincides with RCLE, since both methods 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).

Now, 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 is the Condorcet loser in the set of bottom-N scorers for some N >= 3. That is, RCLE1 loses head-to-head against every other candidate in that bottom-N scoring set.

In particular, RCLE1 loses head-to-head against every candidate whose score is lower than its own score. This means that in B2R, no matter which of the candidates whose scores are lower than RCLE1's emerges to face RCLE1, that candidate is guaranteed to 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 we also know that by definition, RCLE(C)=RCLE(C omitting RCLE1) as well. By the inductive hypothesis, B2R(C omitting RCLE1) = RCLE(C omitting RCLE1), and this 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.

This means that, while RCLE superficially appears to be more conservative than B2R, this is actually not the case. B2R is always just as conservative as RCLE, since they are equivalent. B2R is actually just a more efficient implementation of RCLE.