| Bram Cohen ( @ 2008-04-13 14:49:00 |
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.
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.