County Highpointers Difficulty Ranking Project

The Schulze Method

Overview

The County Highpointers Difficulty Ranking Project uses the Schulze Method to process the votes and generate an output ranking. The Schulze Method is a Condorcet method, which means that if more voters rank A above B than B above A, then A will be ranked above B in the output ranking, if at all possible. Thus while no voter may agree to the whole output ranking, a majority of voters will agree on the relative rank of any two highpoints.

Under some circumstances it will be mathematically impossible to rank every pair of candidates consistently with the majority vote. Sometimes a majority of voters will rank A above B, a (different) majority will rank B above C, and a (still different) majority will rank C above A. Any two of these conditions, when combined, contradict the third condition. This situation is called a majority rule cycle. Majority rule cycles are possible, though their risk is smaller, even when no voter casts a ranking with a majority rule cycle. For this reason, and because it is simply illogical and contradictory anyway, ballots that contain a majority rule cycle are rejected in the County Highpointers Difficulty Ranking Project.

Although a particular candidate has a relatively low probability of being involved in a majority rule cycle, the large number of highpoints in the Difficulty Ranking Project does result in a significant number of cycles. Most of them occur when a single rogue voter, the only one to include a particular pair of highpoints in his vote, ranks that pair opposite their order in the outcome, and that ranking is insufficient to overturn the more firmed-up order implied by other voters.

Why Schulze?

There are several reasons why the Schulze Method is particularly appropriate for the County Highpointers Difficulty Ranking Project:

The Whole is Greater than the Sum of its Parts

No county highpointer will have first-hand experience with all potentially difficult county highpoints, thus no county highpointer will be eligible to include all of them in his ranked vote. We can, however, use each highpointer's ranking of some highpoints to rank those highpoints relative to each other. While different highpointers will be able to rank different highpoints, rankings of multiple highpointers will inevitably include some highpoints in common. It is possible to use these common highpoints as "benchmarks" to make relative rankings of other highpoints even though no highpointer was able to compare them directly, because both highpoints can be compared to the benchmark. Condorcet methods do a good job of this.

For example, suppose that one voter ranks A above B, and another voter ranks B above C. The output order would have to rank A above B and B above C, i.e. it will rank A above B above C. Although no voter was eligible to compare A and C directly, it can be reasonably implied that A should be ranked above C, and that is exactly what happens automatically with any Condorcet method.

By combining overlapping rankings from different highpointers in this way, it is possible to assemble a meaningful, group-consensus ranking of all highpoints, even though any individual highpointer could have ranked only a fraction of them.

Robust Partial Ballots

Since any county highpointer will be eligible to rank only a fraction of difficult highpoints, it is imperative that the algorithm used to process the votes not inadvertently favor or disfavor any highpoint not mentioned on a ballot.

A na´ve designer of a vote-processing algorithm might be tempted to assign a score, or "power rating", to each highpoint included in the ranking of each voter, based on their relative rankings. The scores of each highpoint would then be summed over all voters. (The Borda count is an example of such a method.) Unfortunately this approach will fail for partial ballots, because whatever score is implicitly given to unranked highpoints, even if it is zero, will be different than some ranked highpoints. Hence the method will implicitly (and inappropriately) alter the comparison between a ranked highpoint and an unranked highpoint. Any vote-compilation method that works by summing scores will necessarily fail in this way.

Condorcet methods, however, do not suffer from this pitfall. A voter who ranks A above B (and abstains on all other highpoints) makes no implicit comparison of A or B to any other highpoint. It does not imply that A is the hardest highpoint or that B is the easiest. As a result of this vote, the Schulze method will try to rank A above B in the outcome if a majority of voters agree that A is harder than B, but the vote contains literally no other implication.

It can be a challenge to design a vote-processing algorithm that favors A over B without inadvertently favoring or disfavoring either A or B relative to some third candidate. Condorcet methods, however, accomplish this goal nicely.

Resistance to Strategic Voting

Mathematicians define strategic voting as the practice of voting contrary to one's true belief in order to achieve a more desired outcome. A voter who really prefers a minor party candidate might vote for a major party candidate instead, because the minor candidate has little chance of winning anyway. In the presidential election of 2000, for instance, many voters who really preferred Ralph Nader voted for Al Gore, since most voters who most preferred Nader preferred Gore over Bush, and a vote for Gore would be more likely to get him elected (instead of Bush) than a vote for Nader would be to get Nader elected.

The Schulze Method, while not wholly immune to strategic voting, is quite resistant to that practice. A highpointer who believes that the difficulty of a certain highpoint is overrated may be tempted to rank that highpoint artificially low, in the hopes of "weighing it down" to where he believes it should be. However, that practice will probably fail, in a way illustrated by the following example.

Suppose that the outcome of a ranking vote is A above B above C. A voter believes that A should be ranked below B, but not below C. Hoping to "weigh down" A a little more and get it ranked below B, the voter artificially votes A below C. But in a Condorcet method, that strategic vote will only weigh down A relative to C and not to B, since the voter would have voted A below B anyway. The only effect that this strategic vote could have is to incorrectly rank A below C in the outcome, but only if it would have been ranked below B in the first place.

Condorcet methods are susceptible to strategic voting only in the presence of majority rule cycles. While such opportunities may occasionally exist, they take large amounts of time and effort to analyze the details so that the opportunity can be exploited successfully. If a voter with a differing view sees a strategic vote coming, he may cast a "counter-strategic" vote that may leave the original strategic voter even worse off than if he had voted according to his true preference. It's somewhat like playing scissors-paper-stone; the winning or losing play depends entirely on the other side's unpredictable play.

Implementation of the Schulze Method in the Difficulty Ranking Project

Beatpath Comparison

There are two different algorithms for executing the Schulze Method: Schwartz Sequential Dropping (SSD) and the Beatpath Method. The latter is preferred in the Difficulty Ranking Project because it produces a ranked list of all candidates, whereas SSD only provides a single winner (except in the case of a tie) without ranking any other candidates relative to each other. It has been mathematically proven that the winner provided by SSD is the same as the top-ranked candidate of the Beatpath Method.

A beatpath from X1 to Xn is a chain of defeats such that X1 beats X2, X2 beats X3, and so on until Xn-1 beats Xn. The strength of a beatpath is the margin of the weakest defeat in the chain. The beatpath strength from A to B is the strength of the strongest beatpath from A to B.

Although majority rule cycles can ruin the transitivity of pairwise defeats (i.e. A can beat B and B can beat C without A having to beat C), beatpath comparison does not share that defect. It has been proven that if the strongest beatpath from A to B is stronger than the strongest beatpath from B to A, and the strongest beatpath from B to C is stronger than the strongest beatpath from C to B, then the strongest beatpath from A to C is necessarily stronger than the strongest beatpath from C to A. This is true even if there is a morass of majority rule cycles. This unconditional transitivity can be used to rank the candidates without contradiction.

Beatpath Signature

While beatpath comparison can be used to order the candidates, ties are still possible, and beatpath comparison fails to make any recommendation between candidates that have no beatpath between them in either direction. Consider the following example: there are three candidates A, B, and C, and one voter who ranks A above C. The voter does not mention B. We know that A should be ranked above C in the output ordering, but how can we rank B relative to A and C? We can arbitrarily rank B above A, equal to A, between A and C, equal to C, or below C.

A sensible way to order A, B, and C is as follows. The only difference between A and B is that A beats another candidate, whereas B does not. Neither candidate is beaten by another candidate. Therefore it is reasonable to assume that A is probably superior to B. Similarly, C is beaten by another candidate, whereas B is not, therefore it is reasonable to assume that B is probably superior to C. This way of comparing B to A and C is questionable, but we might as well use it since there is nothing else to go on. We therefore rank B between A and C.

Enter beatpath signature, which would order A, B, and C as in the above example. The beatpath signature of A is defined as the number of other candidates, using raw beatpath comparison, that A would beat minus the number of candidates that would beat A. In the above example, A has a beatpath signature of 1, B has 0, and C has -1.

Beatpath signature is good not only as a tie-breaker to raw beatpath comparison, but also as a primary ordering criterion. It is mathematically proven that if A beats B by beatpath comparison, then A must also have a greater beatpath signature than B. This allows us to discard raw beatpath comparison completely, and replace it with beatpath signature. Beatpath signature will always order two unequal candidates the same as raw beatpath comparison, but beatpath signature then goes on to break some ties left behind by raw beatpath comparison.

In a perfect world with no ties and no majority rule cycles, the top-ranked candidate among n candidates has a beatpath signature of n-1 (since it beats every other candidate), the next has n-3, and so on until the lowest ranked candidate, which has a beatpath signature of -(n-1). Every candidate's beatpath signature equals that of the next higher ranked candidate minus 2. Ties and cycles will alter this pattern somewhat.

The Difficulty Ranking Project uses beatpath signature to order the highpoints. Beatpath signature does still occasionally have ties, which are broken by Condorcet signature. Beatpath signature is provided in the tables that list the outcome in each category. Several important characteristics of the outcome can be inferred from beatpath signature. A run of ranks in which beatpath signature differs by 2 for consecutively ranked highpoints usually indicates no ties or cycles. A brief run of tied beatpath signatures in the midst of a longer run of differences of 2 usually indicates a tie but still no cycles. A longer run of tied beatpath signatures usually indicates cycles, as does a run of irregular differences. A large jump in beatpath signature usually indicates a "clean break" at the top or bottom of a run that involves overlapping cycles.

Back to the County HP Difficulty Ranking Project home page