9 ms·
Counting Votes Is Hard
- tunesmith 13y agoI'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 13y agoThat'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.
- tunesmith 13y agoI 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.
- dragonwriter 13y agoIRV is very simple to explain to people familiar with Majority/Runoff, since its basically a way of automating majority/runoff.
- chongli 13y agoWhy 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 13y agoBecause 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.
- DennisP 13y agoNow 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.
- chongli 13y agobut 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.
- YokoZar 13y agoBecause 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.
- baddox 13y agoI 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.
- kybernetikos 13y agoI'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/ http://kybernetikos.github.io/graff/demo/ was me playing around with the ranked pairs way of removing cycles compared to just grouping them.
- tunesmith 13y agoShouldn't it be possible to remove the Schwartz Set candidates and then re-run the count to find out the remaining relative rankings?
- kybernetikos 13y agoThat'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!
- tunesmith 13y agoI 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.
- amishforkfight 13y agoI 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 13y agoGriefer 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.
- amishforkfight 13y agoI 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?
- jdwyah 13y ago(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.
- lowry 13y agoFunny how the website authors failed to do research on voting systems _before_ writing the website.
- jdwyah 13y agoI 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 :)
- tunesmith 13y agoAs 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. ;-)
- tokenadult 13y agoNeither 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 https://en.wikipedia.org/wiki/Arrow's_impossibility_theorem http://www.math.ucla.edu/~tao/arrow.pdf http://www.math.ucla.edu/~tao/arrow.pdf [2] http://latimesblogs.latimes.com/washington/2008/11/franken-coleman.html http://latimesblogs.latimes.com/washington/2008/11/franken-c... http://www.politico.com/news/stories/0609/24383.html http://www.politico.com/news/stories/0609/24383.html http://www.amazon.com/This-Is-Not-Florida-Minnesota/dp/0816670382 http://www.amazon.com/This-Is-Not-Florida-Minnesota/dp/08166... [3] http://marginalrevolution.com/marginalrevolution/2009/11/range-voting.html http://marginalrevolution.com/marginalrevolution/2009/11/ran... [4] http://www.math.cornell.edu/~mec/Summer2008/anema/approval.html http://www.math.cornell.edu/~mec/Summer2008/anema/approval.h...
- _dps 13y agoI 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/3540600647 http://www.amazon.com/Basic-Geometry-Voting-Donald-Saari/dp/...
- jellicle 13y agoEvery 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 13y agoHeh, 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."