Bram Cohen ([info]bramcohen) wrote,
@ 2008-04-13 14:49:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Improving on Meek's Method
Fixing the problems in Single Transferable Vote is a subject of much research. Meek's Method does good job of fixing the most obvious problem, and I believe the approach is basically sound, but it still has some bad artifacts. Specifically, Meek's is used for electing only a single candidate, it will behave like instant runoff instead of picking the condorcet winner, and in an election with many candidates to get elected a candidate can appear second on almost every ballot and still be eliminated first.

Obviously those are very busted behavior. I have a simple, and I believe new, suggestion as to how to fix them.

The only part of the algorithm which is changed is the one for picking which candidate to put in the 'excluded' category. Meek's picks the candidate with the lowest weight, which is a simple but highly flawed approach. Here is an alternative algorithm: For every pair of candidates in the 'hopeful' category, calculate which of them would get more weight if all candidates except those two and the ones already elected were crossed off the ballot. Then move the condorcet loser based on the results of those two-way races into the 'eliminated' category.

This technique straightforwardly gets rid of the two artifacts I mentioned and also fixes the strategic voting which real political parties do in practice, an interesting technique which probably warrants its own separate post for explanation. I believe it is in all ways a clear improvement and should be adopted by anyone actually using Meek's (or STV for that matter) in practice.

The remaining artifacts which this technique leaves are quite deep and generally both unimportant and intractable. They are:

If a voter disagrees with the choices of the other voters who have the same first-place candidate, they can move their first-place candidate farther down the ballot and thus make their own vote count for more. This is a fundamental issue in proportional representation voting, and not a big problem in practice.

When there's no single condorcet loser, all the usual issues apply. These are fundamental issues for any voting system, using any algorithm and voting method, and the usual techniques have their usual pluses and minuses, and the choice of which one to use doesn't matter all that much because such situations rarely occur in practice, and when they do simply rolling a die to determine which member of the smith set to pick will work about as well as anything else.

There are some strange edge cases where the monotonic approach of my proposed algorithm is fundamentally limiting. In practice these are unlikely to occur all that much, and when they do the monotonic approach will do something suboptimal but entirely reasonable. CPO-STV basically fixes this but at a cost of much greater cognitive and computational complexity. I for one have a hard time intuiting what CPO-STV will do under some circumstances.

Those are all the artifacts which are left. Other than that, it just plain works.

I'd like to thank Philip Neustrom for reminding me of this subject in general and Meek's Method in particular.



(Post a new comment)

Any bright ideas..
[info]misterajc
2008-04-14 02:29 am UTC (link)
... for getting people in the US to actually use SVT? That seems like a far larger and more intractable problem than perfecting the algorithm.

Andrew (who actually proposed at an IJA annual meeting once that the board be elected by STV and was greeted by blank stares.)

(Reply to this) (Thread)

Re: Any bright ideas..
[info]codetoad
2008-04-14 03:47 am UTC (link)
You should look at FairVote (formally the Center for Voting and Democracy) http://fairvote.org. They have a lot of information on various efforts to get ranked choice voting in use.

(Reply to this) (Parent)

Re: Any bright ideas..
[info]bramcohen
2008-04-15 12:48 am UTC (link)
Replace our current crop of journalists with ones who aren't too stupid to understand ranked ballots? Seriously, every news story talks about the 'controversy' over whether they're 'undemocratic'.

(Reply to this) (Parent)


[info]ciphergoth
2008-04-14 07:47 am UTC (link)
except those two and the ones already elected - why do those already elected stay on the ballot? Why not just find the Condorcet loser (or Tideman loser or whatever) among the hopeful using the weighted ballots and eliminate them?

(Reply to this) (Thread)


[info]bramcohen
2008-04-14 04:22 pm UTC (link)
Because if they didn't stay on the ballot then it wouldn't have proportional representation. You do the usual Meek's weight-moving with everyone on the ballot, so that voters whose votes have already been used to elect someone count for less.

(Reply to this) (Parent)

BitTorrent Brain Actions :-)
[info]curiousharry
2008-04-27 01:05 am UTC (link)
Mr. Cohen: I am a s/w developer -- and an admirer of yours to have come up with BitTorrent -- a seemingly simple concept (albeit non-trivial implementation requiring many, many hours of work, no doubt) that noone thought to do this. I'd be interested in you posting here or as one of your essays, how it came to your mind to think of Bit Torrent. I heard the NPR interview about your Asperberger situation -- but I wonder how your thought processes work -- for example, do you find that books are a distraction and you prefer to spend time visualizing things (like BitTorrent before it became a reality) or is it more just an extension of your knowledgebase in dealing with download times and TCP/IP sockets and saying to yourself: there has to be a better way (or perhaps culling information about using multiple computers like the GNOME project or the next "perfect number" stuff on many contributing PCs) that simply triggered the notion of improved download times. Also, do you feel pressure to come up with the next idea or do you feel like you can rest on your laurels? I ask that in a respectful way, of course. Did you make any profit from BitTorrent or not? I realize the value of being know as the developer of BitToreent has intangible value/benefits, but still, I was curious. I first stumbled into you with some quotes attributed to you about the technical interview process, which I found encouraging as I am a very bright and productive person being subjected to technical questions in areas I have worked on before, understood well at the time, and would need about 60 seconds online to refresh my memory, and which I don't have in the rather low-value technical interview. Here is what you are attributed to have said: ************** • "In an interview you can tell if a person is a pleasant conversationalist, and you can give some technical questions to rule out the truly inept, but beyond that you might as well be rolling dice." • "I'd like to note that in an all-male work environment hiring an attractive female is probably good for morale." • "Even though work history doesn't correlate with job performance, being a lying sack of shit almost certainly does." ************** Mr. Cohen: so, so, so true. Regards, CuriousHarry

(Reply to this)


Create an Account
Forgot your login?
Login w/ OpenID
English • Español • Deutsch • Русский…