3 ms·
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 vote
by kybernetikos 13y 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/ 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.
- dragonwriter 13y agoNo. Assuming no changes in preferences among the members of the Schwartz set, re-running an election among the Schwarz set won't change anything.
- tunesmith 13y agoI meant remove the Schwartz set candidates from the ballots, and then recount the ballots to find the next ranked candidate.
- jdwyah 13y agoWhy didn't you use the http://en.wikipedia.org/wiki/Schulze_method http://en.wikipedia.org/wiki/Schulze_method method? I'm not grokking the essential difference with yours.
- kybernetikos 13y agoThe 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.