Counting Votes Is Hard 28 points by jdwyah on Feb 9, 2014 | hide | past | web | favorite | 59 comments

 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.
 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.
 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.
 Shouldn't it be possible to remove the Schwartz Set candidates and then re-run the count to find out the remaining relative rankings?
 That's probably a nice way of doing it - iteratively work out all schwartz sets (if there are multiple roots, there can be multiple schwartz sets) and remove them until there are none left to work out the rankings.Now I have to go back to the code!
 I did something semi-related with beatpaths.com when it was active. I created a cyclic graph of NFL team wins. There would obviously be loops (such as two teams in a division splitting the series). So I'd simply remove the loops from the graph; smallest loops first. Eventually you'd end up with a DAG (perhaps with multiple roots), and I'd run a modified tsort (with various tiebreakers) to come up with a power ranking. It was kind of a silly website but I wanted to see how accurate NFL picks could be using only wins and losses. (Answer: somewhat competitive with other methods, but not very - but still, fun, and with pretty pictures!)Anyway, yes - you can come up with a full ranking of candidates in a Condorcet method by finding the condorcet winner (or schwartz set), removing, and running again, and keep going until you've fully ranked all candidates.
 No. Assuming no changes in preferences among the members of the Schwartz set, re-running an election among the Schwarz set won't change anything.
 I meant remove the Schwartz set candidates from the ballots, and then recount the ballots to find the next ranked candidate.
 Why didn't you use the http://en.wikipedia.org/wiki/Schulze_method method? I'm not grokking the essential difference with yours.
 The essential difference between Schultze and Ranked Pairs is that cycles are resolved based on strongest beat path versus the number of approvals or victory margin. Schultze is just as reasonable as Ranked Pairs for this, but I find it easier to justify to people that an option that trounces another option should have that reflected in the final ranking rather than that an option with a stronger beat path should have that reflected.The essential difference between Schultze and what I like these days is that Schultze will try to resolve cycles, whereas I think it's better just to accept them and call it a tie. If you can't have ties, then I really like the earlier suggestion of rerunning the voting on just the ones in the Schwartz set.
 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.
 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.
 IRV is very simple to explain to people familiar with Majority/Runoff, since its basically a way of automating majority/runoff.
 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.
 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.
 Now suppose there's a candidate I like pretty well, not as much as my favorite, but better than several others. Do I vote 10/10 or 0/10? Which is more tactical? It's a little hard to say.With approval voting I have to make that decision, setting some kind of threshold of approval. With range voting it might be easier to just vote honestly.At worst, everybody votes tactically and you get approval voting, which is still a good system. But sometimes the tactical decision is difficult, in which case range voting gives you the option of just voting honestly.
 but to suggest that it doesn't in Range voting is either misinformed or disingenuous.It's a good thing I didn't suggest it, then.
 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.
 > 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.
 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.http://www.math.ucla.edu/~tao/arrow.pdfhttp://www.politico.com/news/stories/0609/24383.htmlhttp://www.amazon.com/This-Is-Not-Florida-Minnesota/dp/08166...
 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.
 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.
 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.
 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.
 Range voting still has its issues - every voting methodology has some issues - but range voting pretty well dominates plurality voting IMO.
 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.
 The point of bringing up Arrow's theorem is to debunk people who claim that certain voting systems are "more democratic" or "better" in some objective sense. What they should be saying is that they prefer a certain voting system because they value certain attributes of voting systems over others.
 > The point of bringing up Arrow's theorem is to debunk people who claim that certain voting systems are "more democratic" or "better" in some objective sense.That's actually an invalid use of it; while the concept of "better" is inherently subjective ("democratic" has multiple definitions, but many of them are objective) Arrow's theorem has nothing to do with that one way or the other.Arrow's theorem says that a certain set of binary criteria that applies to voting systems that map from a set of ranked preferences to a single preference ranking cannot be met simultaneously, but it does not say anything one way or the other about the ability to differentiate objectively among voting systems on continuous-valued axes, including various operationalisations of "democratic".
 Well if that's the point, I definitely disagree with it.Some voting systems genuinely are more democratic or better than others in an objective sense. For example, a voting system where one person determined by their status in society has their vote count and everyone elses is discarded is objectively less democractic than a voting system where a ballot is selected at random from all voters and is taken to determine the result.Neither of these systems is as democratic as a system where everyone votes for their favourite and the one with the most votes wins, and that in turn is not as democratic as a condorcet-loser system, where it's not possible for a candidate that the majority rank last to win.Just because all of the options have problems, it doesn't mean that there aren't options that are completely dominated by others.
 > For example, a voting system where one person determined by their status in society has their vote count and everyone elses is discarded is objectively less democractic than a voting system where a ballot is selected at random from all voters and is taken to determine the result.Obviously this is true, but this is rarely one of the voting systems being considered in any discussion about voting systems.
 I'm responding to your claim that Arrows theorem debunks attempts to paint some voting systems as objectively more democratic or better than other voting systems.If you think that Arrows theorem really does this, then you should stand by that assertion and defend all voting systems that Arrows theorem applies to as not objectively better than any other voting system that Arrows theorem applies to.And yes, Arrows theorem applies to Dictatorship/Random Ballot/Plurality/Condorcet-loser methods which are the ones I used in my example.
 It applies to dictatorship, but doesn't actually tell you anything about it.
 I'm not sure the stochastic method you describe, if followed honestly (a big assumption, in practice) would be less democratic than plurality. Your general point stands, though, for sure.
 There are reasonable and unreasonable definitions of "fair" and "better". Some voting systems have to have very very unreasonable (to a normal human) definitions of "fair" to be considered superior by any sort of consistent logic.
 Arrow's theorem does not say no voting system can be better than any other in an objective sense. It says there is no voting system that is better than every other in every respect.
 No, it doesn't say that, either. It says that there is no ranked-ballot voting system that meets a particular set of criteria. (Or, alternatively and perhaps more to the point, it says that the particular set of criteria it sets up are logically mutually contradictory.)
 It does say that (about ranked-ballot voting systems), when you consider that each of those criteria does seem a positive attribute of a voting system if nothing else had to be traded away, and which can therefore quite reasonably be viewed as respects in which one voting system can be better than another. It's true that it doesn't apply to scoring systems, but Condorcet's Other Paradox says that no scoring system can be Condorcet consistent so that's a respect in which some ranked ballot voting systems are better in at least one respect than any scoring method.The general point stands that there is no voting method that dominates every other voting method, but that there can be voting methods that dominate individual other voting methods.
 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.
 I think this is insufficiently talked about in discussions of voting systems. For some situations it's better to have a divisive winner with passionate support and in other situations it's better to have a compromise winner that nobody hates too much.Different voting systems can give you different angles on picking the option with the most direct support versus avoiding picking options that stir up a lot of dislike in the voting body.
 While that's true and important, plurality doesn't do as good a job as other methods at either.
 With strategic voting, that is not what plurality voting gives you.
 Range voting is also vulnerable to strategic voting.
 Yes, but less so. Range voting with an expressive range can quickly devolve to the special case of approval voting, but that isn't disastrous. But that's an aside - my point was that plurality voting does not do what you said in the presence of strategic voting.
 > Yes, but less so.The one actual concrete attempt to test this I've seen shows it, in the tested scenario, more vulnerable to strategic voting than plurality (or any other tested method.)[1] http://rangevoting.org/ElectionByMajorityJudgmentExptEvidenc... [The method is referred to as "point summing" rather than "range voting".]
 The very site where you link to places that link in an article describing in detail why they call that entire paper "insanely wrong-headed"I think that paper is misguided and incorrect as an attack on range voting. Here's the page where that link occurs: http://www.rangevoting.org/MeasTheory.htmlHere's the anchor: http://www.rangevoting.org/MeasTheory.html#numbersallowedFinally, if you sum the scores, you are NOT doing range voting as is generally suggested. The idea of range voting is to average the scores. That is a totally different thing, especially when you (as you should) allow for no-opinion votes.I can only conclude that the paper in question is not addressing actual range-voting as proposed. That said, I did not read it completely (nor am I especially interested in doing so, although someone could summarize the issues perhaps if any exist I have not addressed here)
 I'll have to dig into that when I've more time. It doesn't change the main thrust of the above - that plurality voting does a poor job picking the "candidate most ranked first" in the presence of strategic voting, because you're picking the candidate most ranked first amongst votes cast which - in strategic ballots - will typically not match the candidate ranked first among voter preferences.
 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?
 The short answer is that plurality voting is a scoring method (give one candidate one point) and so has all the weaknesses of a scoring method, and it is a rank-order method (which only considers the top) and so has all the weaknesses of a rank-order method, and it isn't very expressive. I intend to put together a more complete answer at some point.
 For reference, the issues on range voting are thoroughly discussed at http://rangevoting.org/
 Funny how the website authors failed to do research on voting systems _before_ writing the website.
 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 :)
 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. ;-)
 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."
 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.
 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.
 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?
 (this is Jeff from ForceRank)The thing to note about our particular situation is that we're really only a little interested in the #1 result. The app is primarily about helping groups prioritize things, for instance "What features do we need to build next".Rating systems are a no go, because the whole point is to force people to choose and hence consider the tradeoffs (hence "ForceRank" :)In this case, some of the voting system criteria such as "susceptibility to burying" play out a bit different than in a regular election. eg If everyone thing "Project C" is a great idea but Frank _hates_ Project C, we want to do what we can to highlight that fact, not just continue on our merry way with the majority vote.
 The thing is, first choice doesn't really answer any question other than "Who is the most common favorite?" That's not necessarily the same answer as what the community of voters would be most universally accepting of, or which candidate would provide the most social utility, etc, or which candidate is most preferred, etc.The most common favorite is not the definition of democracy - it's just the method of choosing that is most common. It's sort of self-justifying; "it's what we've always done, so we should keep doing it". But, things change over time, and we have the ability to better understand large groups of preferences than we used to (when counting first choices was the only possible way to vote), which means a better ability to provide social utility and help a group of voters help themselves in the most useful way.Anyway, ordinal method doesn't actually apply any "weight" to a 4+ choice. The concept of "weight" doesn't actually apply to a Condorcet method. All you're really communicating is that you prefer candidate #4 to candidate #5, and to candidate #6, etc. There's no extra proportional "power" or weight given to higher-ranked candidates, though, because you've already communicated that you prefer candidate #1 to all of them.It really is the same thing as if someone gave you (n(n-1))/2 ballots of one candidate against one other, with you picking your favorite. It's just faster to communicate in ranked form. It also doesn't run afoul of "one-person, one-vote", because no voter has extra power compared to another voter.Finally, yes - say that 49% prefer A, have B as a close second, and hate C. 49% prefer C, have B as a close second, and hate A. 2% prefer B and hate both A and C. B's definitely just the "least objectionable", but also should definitely win as the consensus choice, even though B only got 2% first-place votes.
 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.

Applications are open for YC Winter 2020

Search: