This is a continuation (part 2) of my response to Steve Eppley from a few weeks ago. N. ********** Steve Eppley wrote: > But in what sense of "majority" can it be said that a > majority has "rejected" A, without also being able to say > a majority has "rejected" B? A's only defeat is EA51, > which is shaky (smallest majority in a cycle). Compare > that to B's CB65 defeat, which isn't counted against B. > (Blake Cretney made a similar analysis of this issue > on 1/24/2000, noting that the Schulze method neglects > "extra" information contained in the votes which may > undermine links in a beatpath chain. Markus considers > this neglect a "feature" of the Schulze method, but it > makes sense to view it as a minor bug.) > I don't think this is a strong argument. All of the candidates are beaten by pairwise majorities, yet we must pick one. The magnitude of B's loss to C is of no particular consequence, unless there would be some good reason why C could reasonably be considered a potential winner. Otherwise, it may well be irrelevant information. Furthermore, candidate B is tied with candidate E, which beats A by one vote. Therefore, I don't see A's win against B to be particularly convincing (and it isn't even the opinion of an absolute majority, apparently). > An argument might be made that a beatpath is not just an > abstraction, that it is comprised of real voters too. > But that's a dubious argument. Consider this simple > scenario to illustrate: > 35: ABC > 33: BCA > 32: CAB > Majorities: BC68,AB67,CA65 > The strongest beatpath of length two or more is ABC67. > Who are the "real voters" counted in the ABC beatpath? > The AB67 link includes 32 voters who rank C over A, and > the BC68 link includes 33 voters who rank C over A. The > strength of a beatpath depends on voters who would oppose > the beatpath, and thus are not real voters. (This sort of > example is one of the concerns I have about how hard it may > be to convince people about the merits of the Schulze method, > because there's something "smelly" about counting for a > beatpath some voters who oppose the beatpath.) > I agree with you that the beatpath is an abstraction which cannot really be justified on the basis of actual votes. However, one way to think of beatpaths is as part of an algorithm for resolving ties in methods like SD and SSD, which are methods that _do_ have a rationale that is as straightforward as Tideman. Schulze's beatpath method is equivalent to both these methods when there are no tied values in the matrix, and can be shown to perform better than either of those methods when there are ties. One can also argue for Schulze's method simply on the basis of criteria compliance -- some electorates might not care if the abstraction is meaningful, so long as the method is guaranteed to give good results. [...] > >Here's another criterion which might not be considered very >important. But it seems desirable and it distinguishes between >MTM and Schulze: > > Define the "1st place finisher" as the given method's winner. > Define the "Nth place finisher" as the alternative which > would be chosen by the given method if preferences for the > 1st thru (N-1)th place finishers were neglected. > > Immunity From Squawking criterion: The 2nd place finisher > must never beat the winner pairwise. > >Another criterion which distinguishes between MTM and Schulze is >the Subsequence Invariance criterion I posted in February (which >Markus kindly informed us was not original, indicating there are >other people who place some value on it). > >There is a weaker form of Subsequence Invariance which Schulze >also fails: "The outcome must not change if preferences for the >last place finisher are neglected." Assuming that a candidate >who expects to finish last has the least incentive to compete, >it would be nice if the outcome is unaffected by his/her >decision whether or not to compete. Thus, this appears to be a >desirable criterion (though it might not be considered very >important). I agree that these criteria are somewhat desirable. It is not surprising that Tideman satisfies them and Schulze doesn't since all these criteria have to deal with social rankings. Since the goal of Tideman is to find a single winner by constructing an optimal social ranking, and choosing the candidate at the head of it, one would expect Tideman to do better than Schulze. However, as Markus has pointed out, the goal of single-winner methods is to elect a single winner, not construct a social ranking, so I don't really attach too much importance to these criteria. With Schulze's method, there is no 2nd-place finisher, merely 1 winner and a bunch of losers. One or more of the losing candidates may beat the winner pairwise, but when this happens the 'squalking' candidate will also have been majority-beaten, so doesn't really have much of a case, imho. If I was choosing a method to determine a social ranking, I would definitely prefer Tideman over Schulze, because it does have the desirable properties you mention. However, the applications for social rankings are quite limited. If a group needs to choose a single-winner, the social ranking is irrelevant. If a group needs to choose multiple winners, a PR system like STV is almost always more appropriate. The only use I've thought of so far for social rankings is when one needs to determine in advance a list of people from which only one person at a time will be chosen to carry out some function. For example, if a group had a system of elected kingship, the citizens could create a social ranking of all the eligible citizens. Should the (top-ranked) king be killed or otherwise eliminated between elections, the next in line could be chosen. Are there any other good uses for a social ranking? [...] > >> whereas Schulze's method is the only method (that I'm aware >> of) that has been proven to satisfy one strong formulation of >> Clone Independence criteria. Tideman satisfies a weaker >> definition of clone independence, SD is 'mostly' clone >> independent, but fails in rare cases; > >I'm not aware that IBCM or Tideman fail to satisfy the stronger >form of clone independence. I do recall that a couple of years >ago there was a discussion in EM about Tideman, which didn't use >the RandomVoterHierarchy tie-breaker discussed later for >Schulze's method. Also, that discussion may have been about >Tideman's 1987 version, not the better version defined in Zavist >& Tideman's paper, "Complete Independence of Clones in the >Ranked Pairs Rule." (Social Choice and Welfare, 1989). If >RandomVoterHierarchy is the tie-breaker, aren't IBCM and MTM >completely independent from clones, in whatever "strong" >formulation Norm referred to? > >Markus tweaked Tideman's definition of clones and demonstrated >independence of "tweaked" clones of the Schulze method. But >that tweak was not a strengthening of the independence >criterion. It was a weakening. It seems to me that MTM and >Tideman and BCM and IBCM completely satisfy it (when coupled >with a tie-breaker such as RandomVoterHierarchy which completely >satisfies it). > I don't see how Markus' definition of clones weakened it. Markus used a definition of clones that allows for ballots which contain candidates outside clone sets to be ranked equal to clone sets. That is, if {A1,A2,A3,B,C} are candidates and {A1..A3} are clones, ballots like [A1=A2=A3=B>C], [C] are permissible, whereas under Tideman's more restrictive definition they are not. Therefore, Markus' definition of clones is the stronger, more general purpose, and more useful definition. Note that I am not saying that Tideman's method with an appropriate tiebreaker will not also satisfy Schulze's definition of clones! It may be that it does, but I haven't yet seen proofs of this. Here is what Markus wrote about the two definitions of clone criteria on 26 Aug 1998: ***** Quoting Tideman, Norman wrote (25 Aug 1998): > "A proper subset of two or more candidates, S, is a set > of clones if no voter ranks any candidate outside of S > as either tied with any element of S or between any two > elements of S." To my opinion, Tideman's definition is too weak. I prefer the following definitions (3 Oct 1997): Definition ("clones"): A[1],...,A[m] are a set of m clones if & only if for each pair (A[i],A[j]) of two candidates of the set of m clones, for each voter V, and for each candidate C outside the set of m clones the following statements are valid: V prefers A[i] to C, if & only if V prefers A[j] to C. V prefers C to A[i], if & only if V prefers C to A[j]. Definition ("Generalized Independence of Clones Criterion"): A voting method meets the "Generalized Independence of Clones Criterion" if & only if additional clones cannot change the result of the elections. [If one clone is elected instead of another clone of the same set of clones, then this is not regarded as a change of the result.] The aim of clone criteria is to verify, whether a method can be manipulated by presenting additional candidates with absolutely identical opinions. Tideman's definition of clones is too strong (because he supposes that clones must no be ranked identically to non-clones by any voter), so that his definition of clones is -to my opinion- not meaningfull enough. Markus Schulze ***** >I'd like to see an example showing incompleteness of the clone >independence of Tideman//RandomVoterHierarchy, if there is one. >(Preferably an example for the majoritarian version of Tideman.) > Since Tideman proved 'complete' independence of clones based on his own, inferior definition, I would like to see proofs that Tideman's method satisfies Markus' definition of clones before I'd consider it equally good in this regard. If I have time, I'll try to construct an example of Tideman violating Markus' version of clone independence, although I have no particular reason to think it does. >> IBCM and Tideman both violate Beatpath GMC, etc. > >Why place any importance on Beatpath GMC? It's a criterion >lacking a reasonable justification -- see above. Mike Ossipoff, >the "father" of GMC, has repudiated both GMC and Beatpath GMC, >concluding that they are overly strong. > What I found appealing about the GMC criteria was that they offered additional guarantees to the voter that seemed reasonable. Regular GMC, for example, sets a higher standard for majority rule -- if a method is going to elect someone, then that candidate should not be opposed by an overall majority unless all candidates are. Beatpath GMC is less intuitive, but provides a similar guarantee without requiring violation of reversal symmetry criteria, Smith, etc. As you say, Mike has repudiated these criteria, and I understand that they were promoted primarily for the strategy protections they provided (which are satisfied by BC), and not the above benefit, per se. [lots of math...] >So, assuming no significant errors have been made in the lemmas >or the propositions, it is accurate to say that IBCM is >completely independent of clones (recognizing that a tie-breaker >which is completely independent of clones is implied by the >claim). > Sounds good. >> 2) is IBCM monotonic? (Markus suggested that it might not be) > >No, IBCM is not completely monotonic. (BCM is monotonic, but no >one is advocating BCM. Proof of BCM monotonicity is available >upon request.) > Sounds bad (for IBCM I mean). >So it makes sense to lower IBCM and consider MTM #1. For one >thing, like IBCM, MTM has a significant edge over Schulze in the >head-to-head comparison. (See my data above.) > I agree with you that majoritarian Tideman is an excellent method. I'm not convinced it's superior to Schulze, but I currently think it is probably about equally good. [...] > >I think Norm has misjudged Tideman technically on clones. (See >above.) Also, I think there is no reasonable justification for >Beatpath GMC. (See above.) So MTM (majoritarian Tideman) is >better than Norm has suggested. > You might be right about the clone issue. I still want to see proofs or counterexamples that Tideman satisfies (or does not satisfy) Markus' definition of clones, in addition to Tideman's. >I agree with Norm's conclusion that Tideman (more specifically, >MTM) and SD might make better public proposals than Schulze. > >SD & SSD are not completely independent of clones, but I think >they are practically independent in large public elections. I >think SD is not completely monotonic (example below) but is >practically monotonic. I don't know if SSD is completely >monotonic, but below I provide an argument against proposing SSD. > You raise an interesting question about clone independence and SSD. One advantage that Mike cited for SSD being possibly better than Schulze was that it was decisive in situations like this: A>B>C>D 4 B>C>A>D 2 C>A>B>D 3 D>A=B=C 9 (Mike actually described an example with 2, 3-candidate cycles that are tied, but this is simpler and illustrates the same point). In this example, SSD will decisively choose D, whereas Schulze can only reduce the winner to {A,D} before having to rely on a random ballot tiebreaker. However, it appears to me that this is a stochastic violation of clone independence. {A,B,C} are clones, and are tied 9:9 with a non-clone. The only solution which preserves clone independence is to choose between A (or a clone of A) and D with equal probability. Therefore, I think that SSD is inferior to beatpath Schulze precisely because it is decisive when it shouldn't be, and violates clone criteria as a result. >It would also be useful to know whether [Schulze] & [MTM] are >monotonic, since [MTM] is more decisive than MTM, and [Schulze] >is more decisive than Schulze. (The [] notation is defined in >the accompanying message "Useful Propositions...") > >Here's an example which, if I haven't erred, shows that SD is >not completely monotonic: > > Definition of SD: > Repeat while no alternative is unbeaten: > Discard the non-discarded defeat(s) which is smallest > in some unbroken cycle. > Elect the unbeaten alternative(s). > > Example of SD non-monotonicity: > Small majorities: AC51,CB52,BA53,DB53,GA54 > Larger majorities: AD,FC,CE,EF,AH,HG > (All other pairings are pairties.) > > First AC51 is dropped. Then BA53 and DB53 are dropped. > (CB52 is not dropped because the cycle it is in was broken > by the dropping of AC51.) Then GA54 is dropped and A has > become unbeaten, so SD chooses A. > > Assume that at least 3 voters ranked A just below C. > Suppose 3 of them uprank A over C, giving AC54. > Now AC is not the smallest majority of any cycle; > CB52 is the smallest majority of the A>C>B>A cycle. > First CB52 is dropped. Then BA53 and DB53 are dropped > and B has become unbeaten, so SD chooses B. > > (I didn't attempt to find an example having fewer > alternatives or fewer pairties.) > In my implementation of Sequential Dropping, I always assume that defeats within cycles are broken one at a time. If there are multiple defeats of the same strength (such as your BA53, DB53 in the example above), a tbrc is used to select only one of the defeats at a time for removal. This is needed anyway in order to eliminate the possibility of more than one candidate being elected. If this is done, then depending on the tiebreaker, the SD winner in the above example will either be: 1) A before *and* A after, or 2) C before and B after. In neither case is there a violation of monotonicity. I also checked a variety of other methods with this example, and came up with the following results: Tideman: C->B, or A->A == monotonic SSD: C->B always == monotonic Goldfish: C->A, or C->B == monotonic Schulze: C->B always == monotonic IBCM: A->B always == not monotonic! Schulze and SSD produce the most consistent results with this example, but only IBCM violates monotonicity. This example illustrates how the Schulze method has an advantage over the alternatives, in that the tiebreaker is applied very sparingly, and only once after the beatpath calculation is complete. In most cases, it won't be needed at all despite the presence of pairties in the matrix. In contrast, Tideman, SSD, SD, and Goldfish may all require the tiebreaker to be repeatedly applied at various points as a solution is sought, and the result is less consistency in outcomes. Particularly in small-scale elections where pairties will be common, the results will be more dependent on the tiebreaker and less dependent on the core of the method, and this seems undesirable to me. I think this is a potential problem for Tideman, SD, and SSD, because although it may be easy to get voters to agree with the base method, they may balk at using a particular tiebreaker. For example, is it going to be easy to explain the rationale for using a random ballot tiebreaker? If anything else is used, then Tideman is no longer clone independent. Schulze on the other hand is inherently clone independent *and* very decisive, so that the tiebreaker chosen is relatively unimportant. A random ballot tiebreaker is still desirable (for perfect, stochastic clone independence), but not strictly necessary. This may make the Schulze method more easy to promote. For example, the Debian Project (http://www.debian.org) has a pairwise voting method which includes a constitutional rule that states: "In the case of ties the elector with a casting vote will decide. The casting vote does not count as a normal vote; however that elector will usually also get a normal vote." (the 'elector with a casting vote' is usually the Debian Project Leader). If they were to consider adopting one of our best methods (Tideman, Schulze), I wouldn't feel the need to press them to replace this rule with a random ballot tiebreaker if Schulze was proposed, but I would be reluctant to recommend Tideman without scrapping this rule, due to the importance of the random ballot in making Tideman a high-quality method. I think this is a serious concern with groups like Debian, since their elections normally have 100-200 voters (or less), so there is a reasonable probability of ties. In committee work it would be absolutely essential. >SD's definition says that cyclicity is recalculated each >iteration, to identify the "unbroken" cycles. Another method >can be defined which is similar to SD, except that it calculates >cyclicity only once, at the beginning: > > Definition of SD2: > Repeat while no alternative is unbeaten: > Discard the non-discarded defeat(s) which is smallest > in some broken or unbroken cycle. > Elect the unbeaten alternative(s). > >SD2 may be worth examining. I expect it will behave similarly, >but not identically, to TopCycle//PC(wv), and it is probably >monotonic. It clearly satisfies top cycle, and perhaps it >performs as well as SD on clones (practical independence of >clones in large public elections.) > I'll try adding this one to my simulator when I find some free time, and let you know how it performs. >It would be advantageous if the method proposed for large public >elections is also the method proposed for small groups. It will >probably be the case that some private groups would choose to >adopt a good method before it's adopted by the public, and would >then spread knowledge about their experiences with it. So there >may be useful synergies if the same method is proposed for both. >This consideration implies that IBCM & SD, which are not as good >for small groups, should not be the public proposal. This >leaves MTM, Schulze, and perhaps SSD. (Also [MTM] and [Schulze] >since they are more decisive, assuming they are monotonic, and >maybe even if they're not completely monotonic since the extra >decisiveness may be more important in small groups.) > I agree that there is some advantage to promoting the same method for all uses. However, Schulze can be seen as simply a refined form of SD or SSD, so I think if it is presented that way, there wouldn't be that much problem extending support from using Schulze on the small scale to SD for public uses. Schulze can be seen as a way to resolve ties in SD which preserves clone independence. In the same way, the random-ballot tiebreaker needed for Tideman probably wouldn't be discussed as part of the public proposal, one could ignore the Schulze refinement when discussing SD. All that needs to be said is that SD elects the same winner as Schulze when there aren't any ties. I do concede that this is a (perhaps small) advantage of Tideman's method. >SSD's definition doesn't seem nearly as simple as other methods, >since it refers to the (dynamically recalculated) Schwartz set. >Given that plus its iteration, people may find SSD hard to >understand, maybe even harder than Schulze, and if that's true >then SSD offers nothing Schulze doesn't offer. Mike said that >he found a person who liked SSD's definition more than SD's, but >that's not a large enough sample to reach a conclusion. > I agree that SSD isn't simple enough for a public proposal, and isn't quite good enough (compared to Schulze) for committee work. It does offer an alternate way of understanding the Schulze method, however so is still useful as a tool for explanation. Mike could be right about SSD being more appealing than SD, but as you say, we would need more test cases. I think that SSD is perhaps easier to understand visually, but is quite difficult to understand when described on paper. Because it is defined in terms of sets rather than cycles, that may make it easier to understand. However, I do not see how you can explain the Schwartz or Smith sets without explaining beatpaths, and once you've done that, the possibility of cycles needs to be considered anyway. At this point, SD offers the easiest solution. Norm Petry > >---Steve (Steve Eppley [EMAIL PROTECTED]) > > > >