Counting Votes Is Hard

http://blog.forcerank.it/counting-votes-is-hard

by jdwyah • 12 years ago

28 59 12 years ago

blog.forcerank.it

tunesmith8• 12 years ago

I've always thought that descriptions of Condorcet methods are harder than they need to be. Even the wikipedia page describes them badly.

The Condorcet criteria itself is easy. If a candidate would beat every other candidate in a one-on-one matchup, that candidate should be the winner. There, that's it.

That's really how it should be described. And then as a next step, we can then describe "tiebreakers". Instead, wikipedia (and others) describe Condorcet only in terms of their tiebreakers, making Condorcet methods themselves appear flawed[1].

You see, loops are possible. In a vote, it's possible that A would always beat B, B would always beat C, and C would always beat A. And the various Condorcet tiebreakers (like Schulz) are ways to resolve those situations.

But the point is, if that happens, the vote really is accurately uncovering an indecisiveness that actually exists in the voting population. So it makes sense that a "tiebreaker" would be non-ideal in some sense. And they all are in some way. The problem is not with the tiebreaking methods. The problem is with the voting population.

I've always thought a good voting system would be the following:

First, rank the votes. If a Condorcet winner exists, the election is over. If not, restrict the candidate pool to the Schwartz set, and start a new round of campaigning so the voting population can research more and better educate themselves.

[1]. Yes, we can argue that the Condorcet criteria is "perfect" if a Condorcet Winner exists, with one caveat: it implies the value that all votes have equal value. If you have that value, it's a logical implication that the Condorcet Winner (if it exists) should be the winner. But other values are possible, such as a utilitarian mindset of wanting to meet greatest social utility, such as some voters being far more passionate or educated than others. Following those implications bring up other tricky problems, though.

eli• 12 years ago

That's still pretty tough to explain.

I had a friend who worked advocating for simple runoff voting initiatives, but gave up because it was too much work having to explain it to be people.

tunesmith8• 12 years ago

I dunno - Instant Runoff got a lot of traction, and that one is even harder to explain/count and can come up with crazier results, too. I've always thought Condorcet could get more traction if it were rebranded as "Instant Round Robin" or something. People understand round robin tournaments.

chongli2• 12 years ago

Why not ditch the ordinal voting and go with a cardinal system? People have seen and understood the system used in judging competitions such as figure skating, diving and gymnastics for many years. Wouldn't it be completely straightforward for them to see it on a ballot? Range voting is the name of that system and, unlike Condorcet methods, it is not subject to Arrow's impossibility theorem.

bradbeattie• 12 years ago

Because range voting devolves to approval voting. Why rate a candidate 4/10 if you don't want them to win? You insincerely rate them 0/10. Why rate a candidate 8/10 if you want them to win? You insincerely bump them to 10/10.

On top of that, you then have to consider the potentially lower popularity of your favourite choice against that of the current lead contenders. Do you reduce your vote for the better of two evils so that your sincere preference has a better chance? Ugh.

I'm not trying to suggest tactical voting doesn't exist in other systems, but to suggest that it doesn't in Range voting is either misinformed or disingenuous.

YokoZar3• 12 years ago

Because range voting embraces the property of valuing votes differently per voter. Implicitly, range voting gives more weight to voters who are aware of the top two candidates and can strategically rate one much lower than the other, even if their opinions of them are approximately the same.

Valuing one voter over the others like that is a dangerous road to travel down.

dragonwriter6• 12 years ago

Why not ditch the ordinal voting and go with a cardinal system?

Because whereas ordinal rankings at least arguably mean the same thing when different voters give them, cardinal scores don't have a consistent meaning, making all cardinal voting systems subject to GIGO problems in addition to any other issues.

Range voting is the name of that system and, unlike Condorcet methods, it is not subject to Arrow's impossibility theorem.

No system that is not a form of ranked ballot system is "subject to Arrow's impossibility theorem", nevertheless, range voting is, beyond the GIGO problem faced by all cardinal methods, demonstrably subject to the same classes of tactical voting as approval voting, which means that while it is not in the class of of systems to which Arrow's theorem applies, it has flaws (from the perspective of the Arrow criteria) of the type that Arrow's theorem states that all the systems to which it applies must have. So the fact that Arrow's theorem doesn't apply to it doesn't actually make it any better.

baddox5• 12 years ago

I agree. For many of the attributes of voting systems, you can actually remove the voting analogy altogether and think of any competition between individuals, like tennis. In a tennis tournament, you could easily have non-transitive results, where A defeats B, B defeats C, and C defeats A. So how do you organize a tournament to determine the "best" tennis player? Round robin tournaments (where every player plays every other player) can have non-transitive results. Of course, there's usually not enough time to do that anyway, so tournaments go with a bracket system. Brackets have their own problems, namely that it's very possible that the bracket winner would lose to a player who was knocked out of the bracket earlier by some third player.

kybernetikos7• 12 years ago

I've written a system that allows condorcet voting with small numbers of voters (we used it to decide a HackDay winner recently), and with small numbers of voters you have to allow ties. None of the discussions of condorcet methods on wikipedia seem to talk much about allowing ties.

The other thing is, that I sometimes want to allow people not to rank an option at all (e.g. if they participated in a HackDay team, they shouldn't rank their own team), once you allow options to be unranked, you open up the possibility of multiple roots to the graph (e.g. one person votes that A > C and leaves B unranked, and another person votes that B > C and leaves A unranked), so you need to do something reasonable in that case too.

In my first implementation of ranked pairs, I would lock in results based on their victory margin, but if a number of results had the same victory margin, they would be locked in based on their order in the system - clearly wrong.

My favourite theory now is just to find all strongly connected components and collapse them into a group which is equally tied (not just the Schwartz set either - cycles can occur further down the graph and relative rankings are still interesting to competitors). The joint winners are all options in all groups that have no losses. http://kybernetikos.github.io/graff/demo/ was me playing around with the ranked pairs way of removing cycles compared to just grouping them.

tunesmith8• 12 years ago

Shouldn't it be possible to remove the Schwartz Set candidates and then re-run the count to find out the remaining relative rankings?

jdwyah3• 12 years ago

Why didn't you use the http://en.wikipedia.org/wiki/Schulze_method method? I'm not grokking the essential difference with yours.

amishforkfight2• 12 years ago

I don't do a lot of this kind of work, but as an interested party with sunday spare time, I think the problem here is that you're scoring anything other than the first picks.

If you just look at first picks, Newbie HBase wins 3 to 1. If for some reason Newbie HBase was in a 2/2 split with Mapreduce and KIR (flip James's top 2 votes), you then take into account 2nd rankings, which in this case means Newbie HBase wins again.

I don't believe you ever want to take into account someone's griefer vote, too much potential to game the system with no benefit to the group as a whole.

rspeer• 12 years ago

Griefer votes are hard to do in Condorcet.

You're proposing plurality voting (plus a weird tie-breaker), which is the worst method on basically every criterion except for "simplicity" and "familiarity to Americans". It leads to really obvious vote-splitting, and people will vote strategically, because they know perfectly well what happens to honest votes in plurality voting. They will also simply propose fewer things.

If the computer is counting votes for you, simplicity shouldn't be the highest priority.

There's a reason people have put years and years of research into voting methods. The best method is unlikely to be the one you think of off the top of your head and post in an HN comment.

amishforkfight2• 12 years ago

I don't believe there is anything 'weird' about the tie-breaker, it's a pretty standard technique - local elections, tournament tie-breaking, movie night voting. What's weird about using second and third choices to determine the best when there's a tie for the first choice?

What I think is really weird is why would a system put much weight, if any at all, on someone's 4+ choice? We might be coming up with a result that received the most points, but are we actually coming up with a result that the most people will be happy with, or is it the least boring thing that people will put up with?

lowry• 12 years ago

Funny how the website authors failed to do research on voting systems _before_ writing the website.

jdwyah3• 12 years ago

I totally did look into them, I just didn't think it would matter much for our use case. As a general rule I find that time spent with fun complicated algorithms is rarely connected to actually creating business value..

Just turned out I was wrong this time :)

tunesmith8• 12 years ago

As someone who spent time with the fun complicated algorithms, I quite like the UI and usability of your ballots - it matches up rather exactly with how I imagined doing it myself before I got distracted messing with more algorithms. ;-)

tokenadult3• 12 years ago

Neither the blog post kindly submitted here nor the comments (so far) nor the Wikipedia article mentioned in one comment mention the impossibility theorem proved by Kenneth Arrow,[1] which shows that we can't build a perfect voting system to take into account preferences among three or more candidates. As a voter in a state with as many as ten candidates on the ballot in a typical presidential election, and some amazingly close three-way statewide elections,[2] I'm surprised that the Arrow paradox (Arrow impossibility theorem) isn't more widely known. I learned about it in an article in Scientific American back in the 1970s. My state has three "major parties" that have automatic ballot access for nominated candidates, and I expect that this year we may add one more political party to the list of major parties by the rules established in state law. If voters have more than two choices, odd results can happen in elections.

AFTER EDIT: A comment posted while I was typing the first version of this comment mentions "range voting" as a response to the Arrow paradox. A commentary by an economist[3] and a problem set by a mathematician[4] may suggest to thoughtful readers here some issues to ponder while discussing whether or not range voting provides better trade-offs than our current voting system, and whether it indeed escapes the theorem proved by Arrow.

[1] https://en.wikipedia.org/wiki/Arrow's_impossibility_theorem

http://www.math.ucla.edu/~tao/arrow.pdf

[2] http://latimesblogs.latimes.com/washington/2008/11/franken-c...

http://www.politico.com/news/stories/0609/24383.html

http://www.amazon.com/This-Is-Not-Florida-Minnesota/dp/08166...

[3] http://marginalrevolution.com/marginalrevolution/2009/11/ran...

[4] http://www.math.cornell.edu/~mec/Summer2008/anema/approval.h...

_dps• 12 years ago

I will add to your list of references an excellent book, "Basic Geometry of Voting" by D. Saari [1]. It covers all major alternative voting systems in an accessible mathematical framework that clearly highlights their tradeoffs (necessitated by Arrow's theorem) in simple diagrams.

I strongly recommend this book for anyone interested in multi-participant decision systems, or anyone looking for a fun mathematical excursion. Sadly, the paperback (which I bought in graduate school for $25) is no longer in print and the price has jumped quite a bit.

[1] http://www.amazon.com/Basic-Geometry-Voting-Donald-Saari/dp/...

tokenadult3• 12 years ago

Thanks for the tip on the book. It looks like the same mathematician author later wrote a more popular, less technical book on voting, Chaotic Elections! A Mathematician Looks at Voting, that may be of interest to several people following the thread here.

http://www.amazon.com/Chaotic-Elections-Mathematician-Looks-...

dllthomas10• 12 years ago

Range voting still has its issues - every voting methodology has some issues - but range voting pretty well dominates plurality voting IMO.

kybernetikos7• 12 years ago

This is definitely a point worth making. Arrows theorem is an extremely interesting result, but I'm fed up of hearing it brought out as an excuse for not changing from a plurality system.

Yes, every social choice mechanism has issues, but some have an awful lot more issues than others.

baddox5• 12 years ago

That depends on how much you value electing a candidate who is the top choice of the most voters. The value proposition is completely subjective.

tokenadult3• 12 years ago

Range voting still has its issues - every voting methodology has some issues - but range voting pretty well dominates plurality voting IMO.

Could you kindly let participants here know why your opinion has become that support for range voting? What issues did you consider along the way that you think are worthwhile for us to consider as we ponder which voting methodology to support in the various places where we live?

tunesmith8• 12 years ago

I don't often see this opinion, but I think the Impossibility Theorem is over-rated. It doesn't state you can't build a "perfect voting system". It states that you can't build a voting system that will always conform to the different criteria that Arrow chose for the theorem. But it doesn't attempt to prove or justify that those four criteria are absolutely required for a "perfect voting system".

"Independence Of Irrelevant Alternatives" is thought to be particularly problematic. There definitely are thought experiments that demonstrate that IIA is not as desirable a criteria (to rule out a voting system) as you would want. If a voting ballot runs afoul of IIA, it can point more to a confused voting population than a flawed voting method.

For instance, the Condorcet Criterion runs afoul of IIA. The Condorcet Criterion states that if a candidate would beat every other candidate one-on-one, that candidate would be the winner. Apparently it is possible to introduce additional candidates (that don't change the relative rankings between pre-existing candidates) such that a Smith Set is instead produced. However, it is not possible to introduce additional candidates such that a different Condorcet Winner is produced.

But let's think about what that says. A Smith Set is not a problem in itself. It means an indecisive or conflicted voting population. It is interesting that additional candidates can expose a conflicted voting population, a confusion that actually already was there; just covered up by the lack of candidates. In other words, if IIA changes a result from a Condorcet Winner to a Smith Set, it is an indication that the population was not given enough choice in the original ballot.

In that sense, IIA is actually useful, and not a flaw. It does not point out a flaw with the Condorcet voting mechanism; it points out a flaw with the limited choice of candidates (and time to research/understand those candidates) for that vote.

This is part of the problem with voting theory, is that they make unwarranted theoretical assumptions, such that a vote will always offer sufficient choice to a voting population. At any rate, I believe IIA is a flawed criterion, and therefore the Impossibility Theorem, while true, is less useful than it is celebrated to be.

YokoZar3• 12 years ago

Arrow's Theorem has to be one of the most over-celebrated yet uninteresting bits of math out there. I myself even thought it was a cool way of challenging alternative voting systems when I first started studying them.

But, as you say, Arrow's Theorem is simply too broad with it's definition of "fair". It's entirely reasonable for the voters to have a list of candidates they hate and a list of 3 candidates they would prefer, and for there to be a rock-paper-scissors situation among those top three candidates. It's entirely possible to have a voting system that only chooses from among the rock-paper-scissors options, and indeed every Condorcet system will make such a choice. Those options are the Smith set.

The tragedy is that Arrow's Theorem is often used to justify systems (like plurality or range voting) that often won't choose from among those top three, and might even choose the Condorcet loser! I'm not sure what a good definition of "fair" is, but I'd settle for not picking the candidate that would lose to literally every other candidate in a one-on-one election.

jellicle• 12 years ago

Every voting system incorporates certain preferences. They are built in, and cannot be removed from the system. In this case, the voting system used essentially incorporates the idea that relative ranking is important - something that the voter ranked #2 is more preferable to the voter than something the voter ranked #10.

So the idea that the algorithm ended up picking something ranked #2 by everybody over something ranked #1 by some people and #10 by some people is not actually crazy.

If you choose a system with ten gradations of voting, that's what you get - choices that are #2 for everyone are preferred over choices that are #10 for some people. If you don't like that result, don't choose that voting system. That's what a ten-point voting system is.

By the way, the images are wrong - the text implies that Matt ranked Newbie Hbase very low, but the image shows the opposite.

LarryMade2• 12 years ago

Heh, it always sounds easier in a meeting, "Bill, set up some sort of simple voting system, should be a cinch, by the end of the week should be plenty of time."

Counting Votes Is Hard

Related Stories