Date: Tue, 11 Jan 2005 23:40:47 +0100 From: Jobst Heitzig <[EMAIL PROTECTED]> Subject: [EM] Re: Approval/Condorcet Hybrids
<snip>
Forest has made [a plausibility argument] that in public elections it will be paramountly probable that there is either a CW or a three-element covering set, that is, a cycle of three candidates of which each other beats at most one.
However, keep in mind that one or more of these three "candidates" could be a collapsed beat clone cycle of three real candidates.
In an election without primaries there might be a beat clone set of three Republican candidates forming a cycle, for example, and if there are other uncovered candidates, this "collapsed" Republican cycle could be one of the three "candidates" in the main cycle.
Hence I think that he is right in suggesting that we should not only reduce to the uncovered candidates but even to the members of the minimal covering set (=Dutta set). I conjecture that this set can be found in O(n^3) time. Anyway, once found, it can easily be shown to be the minimal covering set. Once we have reduced everything to at most three candidates, we can proceed as we like by either dropping the weakest defeat in the cycle or by drawing random ballots or by maximizing approval, etc.
If the resulting winner turns out to be a collapsed clone set, then we unfold that clone set and (recursively) apply the same method to it.
So we see that the study of three candidate methods is of greatest importance for single winner methods in general.
Now it seems that we could reduce the study of three candidate methods to a decision tree depending on the relative sizes of the twelve possible factions
A, B, C, A=B, A=C, B=C, A>B, A>C, B>C, B>A, C>A, C>B, C>A
There are twelve factorial possile orderings of these factions by size, but neutrality will cut down on the number that we need to consider.
Also requiring some form of monotonicity would cut down on the possibilities.
How about Reverse Cancellation? This means that wife can cancel husband's vote with hers no matter how he votes.
The ballot pairs that (should) cancel are of the form
X>Y>Z cancels Z>Y>X, and X=Y>Z cancels Z>X=Y.
This condition would reduce every three candidate election down to a six faction case.
It's tempting to also require that certain triples cancel:
{A,B,C} or {A>B, B>C, C>A} or {C>B, B>A, A>C} or {A=B, B=C, C=A} .But there is a high price for this one. It leads irrevocably to Borda.
Still, Spruced Up Borda might not be so bad. It is just Black in the three candidate case.
How does the following three candidate proposal stack up?
First cancel reverse ballot pairs. Then between the most truncated (or worst rank in case of no truncations) candidate X and the candidate Y with the least top rank support, keep the one favored pairwise for the final pairwise comparison with the other candidate Z. If X=Y, then eliminate this candidate and take the pairwise winner from the other two.
Forest ---- Election-methods mailing list - see http://electorama.com/em for list info
