Schulze's beatpath voting method

This is a short explanation, written by Markus Schulze & Warren Smith, of why Schulze invented his beatpath voting method. It mentions some of its non-obvious theoretical properties.

The Condorcet "Least Reversal" (CLR) method (often thought to be the method Condorcet himself had in mind) minimizes the number of "overruled voters." That is, if there is a "Condorcet Winner" candidate who pairwise-beats every opponent, he wins. Otherwise, reverse the minimimum possible number of voter pair-relation opinions in order to cause a Condorcet Winner to exist, then declare him the winner.

A related idea, which many people consider the best Condorcet method, is the Simpson-Kramer MinMax method. It selects as winner the candidate with the smallest worst-pairwise-defeat.

Unfortunately, both CLR and Simpson-Kramer MinMax have some deficiencies. One of the most embarrassing is that they both can elect a Condorcet loser who loses pairwise to every candidate. I.e. these methods are not self-consistent: the candidate they regard as "unambiguously the best" can be the same as the one they regard as "unambiguously the worst." (This is a severe type of reversal symmetry failure.) Also, both MinMax and CLR violate clone-immunity and majority for solid coalitions (that is: if every member of some subset S of the candidates is preferred by a voter-majority over every member of the complement set, then a member of S should win).

It is possible to fix both the "elects loser" and majority-for-solid-coalitions problems in a rather ugly way by prefacing MinMax or CLR with restriction to the "Smith set." That is, you first find the smallest candidate subset S such that each member in S is preferred by a voter-majority over every member of the complement set, then you eliminate all candidates not in S, then you apply MinMax or CLR to the remaining candidates. Call these Smith-prefaced methods Smith//CLR and Smith//MinMax.

Tideman's Ranked Pairs method was the only single-winner election method known in 1997 that satisfies Condorcet, monotonicity, clone-immunity, majority for solid coalitions, and reversal symmetry. However, frequently the Tideman Ranked Pairs winner has a very strong worst pairwise defeat.

Therefore, my aim was to find a method that satisfies Condorcet, monotonicity, clone-immunity, majority for solid coalitions, and reversal symmetry, and that tends to produce winners with weak worst pairwise defeats (compared to the worst pairwise defeat of the winner of Tideman's Ranked Pairs method).

Thorough computer calculations by Norman Petry and Jobst Heitzig have shown

  1. That the Schulze-beatpaths winner is almost always identical to the Smith//MinMax winner – more evidence of this is in Wright's 2009 PhD thesis (pdf) which finds on pages 67-70 that the Schulze and MinMax winners are identical in N-candidate elections with these probabilities:
    N=3N=4N=5N=6N=7
    100%99.7%99.2%99.1%98.9%
  2. That the worst pairwise defeat of the Schulze winner is almost always as weak or weaker than the worst pairwise defeat of the winner of most other methods (except, of course, for the MinMax and Smith//MinMax methods).

The reason for this is that the MinMax method and the Schulze method can be rewritten (it is true, but not obvious, that these rewritings are valid) in ways that make it clear they both are based on very similar concepts:

MinMax method:
Eliminate successively the weakest pairwise defeat until there is a candidate whose defeats have all been eliminated.
Schulze beatpaths:
Eliminate successively the weakest pairwise defeat that can be eliminated such that the remaining defeats still contain an arborescence. The winner is that candidate whose defeats have all been eliminated.

Return to main page