Wednesday, July 25, 2018

A different justification for the Schulze Method

This is a different way to think about the Schulze Method, which might convince people who don't like the "beatpath" construction. 

I wrote about the Schulze method in the previous post, giving a justification that is based on the standard presentation of the method using beatpaths.


This is a different look at the same method, implemented a different way.

Suppose you first looked for a Condorcet winner: so you look at all the pairwise matchups, and find out who is preferred to who.  You make a matrix of pairwise preferences, and maybe for convenience subtract the number of voters who preferred Y to X from the number who preferred X to Y to get the margin of pairwise preferences.  (These matrices are in the example in the Wikipedia link to the Schulze method above -- if I were more detail-oriented, I'd put an example here.) 

Any row that's all positive means that candidate beats all others head-to-head: that's a Condorcet winner!  

But suppose there isn't a row that's all positive.  What do we do?  Well, first, we can eliminate any Condorcet loser: a candidate that is not preferred in any head-to-head matchup. (We'll spot a Condorcet loser in the matrix because it's got a row of margins that's all negative, or equivalently a column that's all positive.)[see footnote]

Then, since we want the closest thing to a Condorcet winner, let's "grade on a curve", and do one of the following (these are equivalent):


  • add something to all the margins: add 5 (for example) to all the margins of pairwise preferences  (add more if you haven't changed anything from negative to zero/positive, add less if you've changed too many elements) OR
  • find the negative margin that's closest to zero (-3 is closer than -10) and set it to zero.
Is there a row with no negatives now?  If so, that's our winner.  If not, our curve might've produced a definite loser (with a column that's all positive or zero), so eliminate that candidate [see footnote again] and curve some more, either adding more or zeroing out another negative margin, until you've got a row with no negatives.  It isn't a Condorcet winner, but it's the next best thing -- the candidate that started with the smallest pairwise "unpreferences".

[ Here's the footnote: ] technically, you want to eliminate every candidate not in the "Schwarz set", which is not just a Condorcet loser, but any group of candidates that loses to everyone outside the set.  (In other words, it doesn't matter if candidate D beats candidate E, if D and E both lose to A, B, and C, eliminate both of them - clearly the winner should be A, B, or C.)   But in terms of justification, this is a technical point; the idea is that you're looking for the "closest to Condorcet" winner.


Click here to see the rest of this post...

Voting Methods: Making the case for the Schulze Method

If you're curious about voting methods, and/or want to make a case for a Condorcet method to your friends and co-voters, this post is for you!  

First, I think the Condorcet criterion is pretty compelling on its own.  (The Condorcet criterion is: if there's one candidate that is preferred in head-to-head matchups to every other candidate, that candidate wins.)  It's easy to come up with examples where the plurality method (this is the method that gets applied most often - whoever gets the most votes wins, even if that isn't more than half the votes -- boo plurality!) doesn't give you what seems the right solution.  If there is a Condorcet winner (there isn't always), it's the one that seems like the right answer.

So what if there isn't a Condorcet winner?  What voting method do you pick?  This is a case for the Schulze method: if there isn't a Condorcet winner, that's because there's a "rock-paper-scissors" cycle where candidate A is preferred (head-to-head) to candidate B, B is preferred to C, ... , Y is preferred to X, and X is preferred to A.  (The cycle can be size 3, like rock-paper-scissors, or can be longer - the point is it circles back on itself.)

At first glance, a cycle like that seems intractable - how do we rank any of the candidates in the cycle higher than the other?  But this is ignoring the strength of the preference:

Suppose 90% of voters prefer Rock to Scissors, 85% prefer Scissors to Paper, and 51% prefer Paper to Rock.  The cycle is there, but clearly the Paper > Rock preference is the weakest link.  The preference path Rock > Scissors > Paper has a "strength" of 85%, much higher than the 51% for Paper > Rock.  Based on path "strength", we can rank these Rock>Scissors>Paper.

Is Rock a Condorcet winner?  No.  But it's the closest thing to a Condorcet winner, in the sense that its pairwise loss is the weakest.

That's the Schulze method.  It's written in terms of "beat paths", but those are just breaking a cycle into two parts, like we did splitting "Rock>Scissors>Paper>Rock" into "Rock>Scissors>Paper" and "Paper>Rock" and comparing them.  There's some added detail to deal with multiple cycles between the same candidates, but that's really all there is to the idea of the method.

Next I hope to show another case to be made for the Schulze method, which might be more intuitive.


Click here to see the rest of this post...