9 Jan 2011 JoeNotCharles   » (Journeyer)

The Best Albums of 2010, part, uh, 4: Twelve Ways to Count Votes

Part 1

Part 2

Part 3. (Ha ha. That post starts with the correction that I’m using VoteEngine and not pyvote – but I didn’t actually fix the post title! And nobody wrote to correct me. Shows how much attention you’re paying.)

Whew. Going back to work did a number on the amount of thinking and typing I feel like doing in my off hours. Sorry for the delay.

In the first three posts, I showed how to turn a list of data into a ballot file for VoteEngine. Now I’ll run that ballot file through a bunch of voting systems and see what comes out. Here are the twelve voting methods I’ll be using. Ten of them just happen to be the methods supported by VoteEngine, and two of them are popular methods that I can count (and dismiss) just by looking at the list.

Before I list the methods, though, I need to explain an important concept in voting: the Condorcet Criterion. The Condercet Criterion was invented by the Marquis de Condorcet in the 18th century. It’s an attempt to answer the question, “Does this voting system always give a reasonable winner?”

The Condorcet Winner is the one candidate that would beat all other candidates in head-to-head races. That is, take a pair of candidates (for example, Arcade Fire and LCD Soundsystem). Look at all the ballots, comparing only those two candidates. (Looking back at the original lists, Mojo has Arcade Fire in 2nd and LCD Soundsystem in 36th, so Arcade Fire wins on this ballot – the fact that there was else somebody in 1st is irrelevant at the moment, because we’re only looking at a context between those two candidates. Q has Arcade Fire in 1st and LCD Soundsystem in 36th, so again Arcade Fire wins. In total, 8 of our 9 ballots have Arcade Fire ahead of LCD Soundsystem, and only 1 – Pitchfork – has LCD Soundsystem ahead. So, overall, Arcade Fire beats LCD Soundsystem.) Now repeat that for every possible pair of candidates. (Arcade Fire vs. Beach House, Arcade Fire vs. Vampire Weekend, Beach House vs. Vampire Weekend, etc.) When you’re finished you’ll have a list of exactly which candidates win, lose and tie against which other candidates in head-to-head (or “pairwise”) elections.

Now, if there’s one candidate that beats all other candidates, that’s the Condorcet Winner. It seems reasonable that this should be the overall winner – after all, if a voting system says that LCD Soundsystem is the overall winner, you have to justify why it beats Arcade Fire overall when 8 out of 9 voters preferred Arcade Fire! So the Condorcet Criterion says, “If a Condorcet Winner exists, does this voting method guarantee that they will be chosen?” (There isn’t always a Condorcet Winner. There could easily be a bunch of candidates all tied for first – they each beat the same number of other candidates, but not all other candidates. The Smith Set is all the candidates that are tied in this way – again, it seems reasonable that one of them should be the overall winner, but it’s not always clear which. You could also look at the Condorcet Winner as being a Smith Set with only candidate in it.) The Condorcet Winner and Smith Set are good ways to precisely define the common sense notion of “the candidates whose winning wouldn’t be ridiculous”.

Of course, the Condorcet Criterion isn’t the last word in evaluating a voting system. Even if a method passes the Condorcet Criterion, there are a lot of other things it could do poorly.

Officially, a Condorcet Method is a method of counting votes that passes the Condorcet Criterion. A method that doesn’t pass it is not a very good method, because it will sometimes elect the wrong person – a person who doesn’t make any sense as the winner. (Some people disagree that this is all that important – maybe it could theoretically happen, but doesn’t happen often in practice, and the system has some other property, like simplicity, that makes it attractive. I’ve even seen people argue that the Condorcet Winner tends to be a middle-of-the-road candidate who is many people’s second choice but few people’s first choice, and they would prefer to elect a candidate that is loved by a faction even if they’re hated by another faction. I – disagree – with this opnion.)

I will be using Condorcet Method more specifically, though: there are a lot of voting methods that are defined as, “Count up all the head-to-head elections between every possible pair of candidates, as defined above, to find the Condorcet Winner and, if it doesn’t exist, the Smith Set. If a Condorcet Winner exists, that’s the winner. Otherwise, use some tie breaking procedure to pick a member of the Smith Set to be the winner.” You don’t have to actually count the votes this way to get a method that satisfies the Condorcet Criterion, you just need a method that returns the same winner as you would get if you counted the votes this way. By the true definition, any method that satisfies the Condorcet Criterion is a Condorcet Method, but I’ll use the term only to describe methods that start out by finding the Condorcet Winner explicitly as described above. The only difference between all the different Condorcet Methods, by my definition, is what procedure they use to break ties if there’s no Condorcet Winner.

By the way, according to the 9 best-of lists we’re looking at, Arcade Fire is the Condorcet Winner. It’s the only band whose album was ranked above every other album on the majority of the lists. So we’d better hope that every voting system says it’s #1! It’s obvious just by looking at the lists that Arcade Fire had the most popular album of 2010 – it’s near the top of almost every list, and even on the Rough Trade and Pitchfork lists, it’s near the middle. The other obvious contender, Kanye West, is #1 on the lists that love him but doesn’t even appear on some lists. So the more interesting question is who else gets ranked at the top according to each system (and specifically, where does Kanye end up?)

With that out of the way, the ten voting systems supported by VoteEngine are (in alphabetical order):

  1. The Borda count (borda) – give each candidate points according to their position on the ballot, from 0 for a last place finish, 1 for second last, etc. up to N for a first place finish among N candidates. The winner has the most points.
  2. Borda Elimination (aka Baldwin’s Method) (borda-elim) – Like the Borda Count, except that instead of returning the candidate with the most points immediately, you keep eliminating the candidate with the least points (and then recounting as if that candidate had never been on the ballot) until you’re left with one winner.
  3. Copeland’s Method (copeland) – A Condorcet Method where ties are broken by the number of head-to-head victories minus the number of head-to-head defeats.
  4. Instant Runoff Voting (irv) – Look at only the first place votes on the ballots. If one candidate has a majority of votes (not just “the highest number of votes”; they need over 50%) then they’re the winner. Otherwise, eliminate the candidate with the fewest first place votes, and then recount as if that candidate had never been on the ballot. Repeat until one candidate has a majority.
  5. Minimax (minmax) – A Condorcet Method where ties are broken by choosing the candidate with the smallest margin of defeat. Actually, the candidate with the “minimum maximum” margin of defeat – hence minimax. (For example, Beach House loses to Arcade Fire 2 to 7. It also loses to LCD Soundsystem 4 to 5. Look at how a candidate compares with all other candidates and find it’s “maximum” margin of defeat – Beach House’s is probably that 2 to 7, but I haven’t looked at all of it’s contests by hand. Now the overall winner is the one whose maximum margin of defeat is smallest – the “minimum maximum”. Whew. And some people call this the simplest Condorcet method!)
  6. Nanson’s Method (nanson) – Like the Borda Count, except that instead of returning the candidate with the most points immediately, you keep eliminating all the candidates with less than the average number of points (and then recounting as if those candidates had never been on the ballot) until you’re left with one winner.
  7. Pairwise Elimination (pw_elim) – Like Minimax, except that instead of returning the candidate with the lowest maximum immediately, you keep eliminating the candidate with the highest maximum (and then recounting as if that candidate had never been on the ballot) until you’re left with one winner.
  8. Ranked Pairs (aka Tideman’s Method) (rp) – A Condorcet Method where ties are broken by ranking all pairs of candidates by margin of victory, and then adding them each to a graph (in order), skipping any pair that would create a cycle in the graph. The final graph will be a tree (since it has no cycles) so the root of the tree is the winner.
  9. Schulze’s Method (schulze) – A Condorcet Method where ties are broken by – um – something do to with graphs again. Really, it’s complicated, which is unfortunate as it seems to give the best results. I’ll describe it when I discuss the results in detail.
  10. Smith/Minimax (s//minimax) – Minimax has a problem, which is that if there’s no Condorcet winner, then the winner it returns isn’t guaranteed to be in the Smith Set. So, first get rid of all the candidates outside the Smith Set, then use Minimax to count the remainder.

The other two methods are:

  1. First-Past-the-Post (aka Winner-Take-All) – Each voter can vote for exactly one candidate. The winner is the candidate who gets the most votes, even if that’s not a majority. (Even though we have ballots with complete preferences on them, we can count them using first-past-the-post by only looking at the #1 preference.) Pretty much a terrible voting system; the only thing it has to recommend it is that it’s simple to explain.
  2. Approval Voting – Each voter can vote for as many candidates as they want, but all their votes have the same score. (That is, each voter either “approves” or “disapproves” of each candidate.) The winner is the candidate approved by the most voters. This has the advantage that it’s less restrictive than first-past-the-post, but at the same time it’s easier to explain and fill in a ballot than systems needing full preferential ballots. (Ballot instructions are basically, “Mark an X next to any candidate you find acceptable. You may choose as few or as many as you wish.”) For this sample, we can assume that any album that appears on a list would be “approved” by that list’s compilers.

Note that all these voting methods return a single winner. To get a complete ranked list, just take that winner out and count the votes again as if that candidate had never been on the ballot – whoever wins this time is in 2nd place. Then do it again to get the 3rd place winner, etc. (For the methods that already say, “Eliminate the candidate with the least number of votes and then recount,” the complete list is just the candidates in reverse order of elimination.) VoteEngine already does this for all the methods it supports above.

There are four other methods supported by VoteEngine, which I didn’t include, mostly because they only return one winner rather than a list. I could have written a wrapper to update the ballot file and run them again to find the list, but it was too much work. The other four methods are:

  1. Bucklin’s Method (bucklin) – Count only 1st place votes. If one candidate has a majority, that’s the winner. Otherwise, add the second place votes. Repeat, adding lower placed votes each time, until one candidate with a majority is found. (In this test, Arcade Fire gets the majority after adding second place votes, and then VoteEngine stops counting.)
  2. Condorcet/IRV (c//irv) – Return the Condorcet Winner if one exists, otherwise use IRV. In other words, a Condorcet Method using IRV to break ties. (In this test, it returns Arcade Fire, the Condorcet Winner, and then stops counting.) In theory this could return a winner outside the Smith Set, because if there’s no Condorcet Winner it throws away all the pairwise data it just counted up.
  3. Smith/IRV (s//irv) – Get rid of all the candidates outside the Smith Set, then user IRV to find the winner. In other words, a Condorcet Method using IRV on the Smith Set only to break ties. (In this test it works the same as c//irv since there is a Condorcet Winner.)
  4. UK Usenet (ukvt) – “apply the rules used by the uk.* usenet hierarchy”. I just ignored this one, because it’s not a standard voting method, so honestly who cares?

Tomorrow I’ll take a closer look at each of the twelve methods and talk about the results in detail.


Syndicated 2011-01-09 00:59:15 from I Am Not Charles

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!