[EM] Simmons' "solution" of voting system design puzzle is inadequate
Warren Smith
wds at math.temple.edu
Sat Jan 20 12:01:23 PST 2007
Here is the current CRV web page about this problems and its (lack of) solution
We are speaking about puzzle #5 at
http://www.rangevoting.org/PuzzlePage.html
---
Puzzle #5: Voting systems immune to clones and avoiding favorite-betrayal
Puzzle:
Two desirable properties of a voting system - both of which Range Voting has - are "immunity to candidate-cloning" (ICC) and "avoiding favorite betrayal" (AFB).
AFB: voters should never have strategic incentive to "betray" their favorite candidate by voting him below some other.
ICC: political parties should be unable to usefully manipulate an election by running clones of their own, or of an opposed, candidate; voters here are assumed to vote honestly and to have only tiny preferences (which they may express in their votes, if they exist) among the clones.
In contrast: the USA's present "plurality" voting system fails both tests: It was strategically unwise in Florida in 2000 to vote for Nader even if he was your favorite; and by sponsoring extra "clones" of one's top opponent, that can cause their vote to be split and hence cause both clones to lose, and you to win.
Question: Is range voting (and obvious variants of it) the only nontrivial single-winner voting system to satisfy both properties? (A "voting system" inputs a set of votes and outputs the name of a winner. The votes are numerical scores for some-or-all candidates, or rank-orderings of some-or-all candidates.)
Note: Many voting systems are known (beyond just variants of range voting) which satisfy AFB, and many also are known (such as Schulze beatpaths, IRV, BTR-IRV, Woodall-DAC, and Heitzig River) that satisfy ICC. But I do not know of any systems besides range voting variants which satisfy both simultaneously.
Partial credit: Must any such system employ continuum votes? What if the probem is restricted to systems based on pure-rank-order ballots (with candidate-equalities forbidden)?
Inadequate Answer 1 (Warren D. Smith, 2005): Sorry, I do not know the answer! I've been unable either to construct a new voting system satisfying both properties, or prove none exist. If no such voting system based on rank-order ballots exists, then in principle it would be possible to prove that purely mechanically by simply examining every possible election and every possible voting system with some given fixed number of candidates and voters (e.g. ≤7 candidates and with 15 voters) and seeing that no voting system (aside from trivial ones like "do whatever voter #12 says" or ones that disregard unanimous voter preferences) does the job. (This is a finite number of configurations. This computer-proof, if it existed, would solve the "partial credit" problem.) However, unfortunately your computer would need to be a heck of a lot faster than my computer, or you will need some new ideas that go way beyond mere brute force search!
Inadequate Answer 2 (Forest W. Simmons, January 2007): MCA satisfies both conditions (clone free and avoidance of favorite betrayal). Method: It uses range-style ballots, but it elects the candidate with the greatest median rating. If there are several candidates tied for greatest median rating, it elects the one with the greatest number of ballots that rate it at that level or above.
Response by WDS: This is in my view merely another "range-voting variant" and hence not a solution to the puzzle. Indeed, range voting but where you a candidate's score is the mean of his score's but with the top X% and the bottom Y% of his scores excluded also qualifies for any X,Y with X≥0, Y≥0, X+Y≤100; and so does any positive linear combination of the above infinity of systems.
Inadequate Answer 3 (Forest W. Simmons, January 2007): In that case, a better contender for the title of "solution" would be "ER-Bucklin (whole)" based on rank-order ballots with equal-rankings allowed. The rules of this system are as follows (basically copied from electorama):
First choice votes are first counted. If the candidate with the most votes has a majority, that candidate wins. (A "majority" is defined as half the number of voters, or more, i.e. ≥V/2.) Otherwise the second choices are added to the first choices. Again, if the candidate with the most votes has a number ≥V/2, he wins. We continue on with more rounds until a majority-winner exists – in the kth round we add on the kth-choice votes of all voters. (If after all rounds finish there still is no winner, then the candidate with the most votes wins; but this issue cannot arise if ballot truncation is not allowed.)
About rank-equalities on ballots: If a ballot lists n candidates as tied in kth place, count that ballot as a whole point for all n candidates beginning in the kth round.
Here a candidate is "ranked in kth place" on a given ballot if there are k-1 candidates who are ranked strictly higher. For example, a ballot marked A>B=C=D>E>F=G=H=I>J should be considered to rank A to in 1st place, B, C, and D in 2nd place, E in 5th place, F, G, H, and I in 6th place, and J in 10th place. Thus, the ballot would not count in favor of E until the 5th round, and it would not count in favor of J until the 10th round.
Response by WDS: That answer does not work because ER-Bucklin(whole) is not clone-immune. It is clone immune if all cones are required to the rated equal, but both the problem and the usual definition of cloned immunity require it to work if there are "slight preferences" among the clones.
Another comment: And the question remains open for voting systems based on strict (equality-forbidding) rank-order ballots.
Warren D Smith
http://rangevoting.org
More information about the Election-Methods
mailing list