Talk:Schulze method

Archives
September 2004 – May 2006

Ranking?

Could somebody please add an example of how the Schulze method creates a ranking (as stated in the intro) instead of just determining a single winner? Thanx. 88.73.116.159 (talk) 20:09, 21 October 2008 (UTC)

Done. Markus Schulze 21:31, 21 October 2008 (UTC)

Implementation Question

The article doesn't seem to be in line with the original paper.

The article says to start the path search with:

 1 for i : = 1 to C
 2 begin
 3    for j : = 1 to C
 4    begin
 5       if ( i ≠ j ) then
 6       begin
 7          if ( d[i,j] > d[j,i] ) then
 8          begin
 9             p[i,j] : = d[i,j]
10          end
11          else
12          begin
13             p[i,j] : = 0
14          end
15       end
16    end
17 end

However, the paper says to start the path search with:

 1 for i : = 1 to C
 2 begin
 3    for j : = 1 to C
 4    begin
 5       if ( i ≠ j ) then
 6       begin
 9             p[i,j] : = d[i,j] - d[j,i]
15       end
16    end
17 end

See Article 1, page 8 and Article 2, page 3.

Also, some of the provided articles have yet another way of writing this step, which adds to my confusion. See Article 3, page 24.

Are the two different ways equivalent? Which one is correct? And, does Article 3 have a typo in it? —Preceding unsigned comment added by 208.124.58.110 (talk) 21:19, 15 October 2007 (UTC)

Paper1 is only a short summary of paper2. As paper1 should be as short as possible, it discusses only margins as a measure for the strength of a pairwise defeat (This means: The pairwise defeat CD is stronger than the pairwise defeat EF if and only if d[C,D] - d[D,C] > d[E,F] - d[F,E].) because for this measure the proofs are very short and simple.

However, as winning votes is the most frequently used measure for the strength of a pairwise defeat in those organizations that are using the Schulze method and as Wikipedia articles don't contain mathematical proofs, the Wikipedia article uses winning votes. Winning votes means that the pairwise defeat CD is stronger than the pairwise defeat EF if and only if at least one of the following conditions is satisfied:

1. d[C,D] > d[D,C] and d[E,F] ≤ d[F,E].
2. d[C,D] ≥ d[D,C] and d[E,F] < d[F,E].
3. d[C,D] > d[D,C] and d[E,F] > d[F,E] and d[C,D] > d[E,F].

Paper2 discusses the Schulze method in a more general manner and treats the definition for the strength of a pairwise defeat as a parameter. Markus Schulze 11:22, 16 October 2007 (UTC)

Three questions

Hello, I want to translate this article in french and I have three questions

About path heuristic

This condition

1. For i = 1,...,(n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)].

seems very strong . What happens if d[C,Y] ≤ d[Y,C] for every candidate C. Is there no path from X to Y ?

The definition says:

A path from candidate X to candidate Y of strength z is an ordered set of candidates C(1),...,C(n) with the following four properties:

1. C(1) is identical to X.
2. C(n) is identical to Y.
3. For i = 1,...,(n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)].
4. For i = 1,...,(n-1): d[C(i),C(i+1)] ≥ z.

If there is a p such that there is a path from candidate A to candidate B of strength p and no path from candidate B to candidate A of strength p, then candidate A disqualifies candidate B.

Therefore, if there is a path from candidate A to candidate B and no path from candidate B to candidate A, then candidate A disqualifies candidate B. Markus Schulze 14:47, 23 June 2006 (UTC)

What about p[X,Y] ?

If there is no path from candidate A to candidate B, then p[A,B] : = 0. Markus Schulze 15:56, 23 June 2006 (UTC)

About Schwartz heuristic

I don't know how to respect the rules in this example (10 voters; 5 candidates):

3 ABCED

4 DECBA

1 BADCE

1 CBAED

1 EADCB

The matrix of pairwise defeats looks as follows:

	d[*,A]	d[*,B]	d[*,C]	d[*,D]	d[*,E]
d[A,*]		4	5	6	5
d[B,*]	6		4	5	5
d[C,*]	5	6		4	5
d[D,*]	4	5	6		5
d[E,*]	5	5	5	5

Here, the Schwartz set is ABCDE (yes ?), there are some defeats (yes ?), and I dont know what is the weakest defeat

Yes, the Schwartz set is ABCDE. The weakest defeats are A:D, B:A, C:B, and D:C each with a strength of 6:4 votes. If the weakest defeat is not unique, then all defeats that are tied for weakest defeat are dropped simultaneously. Therefore, the defeats A:D, B:A, C:B, and D:C are dropped simultaneously. Now, all candidates are tied with each other; thus, all candidates are tied for winner. Markus Schulze 15:56, 23 June 2006 (UTC)

Or, easier, what is the weakest defeat in the example 1 (path heuristic)? Wich candidate must be eliminated ?

In example 1 (path heuristic), the weakest defeat is E:A = 23:22. Markus Schulze 15:56, 23 June 2006 (UTC)

Name

The two heuristics are very different. Why are they both called "Schulze method" ?

Thanks (please I'm french, write your answer in simple english). HB, 22 Jun 2006

Both heuristics, the path heuristic and the Schwartz heuristic, have been proposed by Markus Schulze. Both heuristics describe the same method, in so far as they always find the same winner. As the properties of the Schulze method don't depend on the heuristic used, it makes sense simply to use the term "Schulze method" to refer to both heuristics. Markus Schulze 14:47, 23 June 2006 (UTC)

You wrote:

Ils sont fous ces wikipediens!!! Déjà que Condorcet lui-même trouvait sa méthode compliquée. Avec Schulze méthode du chemin, c'est la prise de tête garantie. Je ne suis pas sûre que ceux qui ont voté pour Condorcet Schulze aient bien lu l'article en anglais, sinon ils auraient au moins posé la question "Schulze méthode du chemin (argh....) ou Schulze méthode Schwartz?"

Both heuristics for the Schulze method always choose the same winner. Therefore, when an organization discusses whether the Schulze method should be adopted, there is no need to discuss which of these heuristics should be adopted. It is sufficient to say that the Schulze method should be adopted. Markus Schulze 06:33, 24 June 2006 (UTC)

Thanks for your very clear answers. HB, 24 Jun 2006

Heuristic + restructuralization of the article

I thing this is a very bad word leading to confusion (I will use the word algorithm instead, but may be there is something better). For the article to be written clearly I would suggest the following schema:

First paragraphs with general definition od SSD (roughly as it is now).

Than the paragraph which briefly sumarizes the ideas used to solve the circular ambiguities (I mean ideas common to all heuristics). I leave to discussion if more exact definition of the method should be included here (other than the equivalence to either of algorithms).

Than some sentence like: There are more algorithms which reach always identical results, therefore all of them can be refered as Schulze method. The algorithms are following:

Than subchapters describing all (both) algorithms in detail.

What do you think?

--Gorn 03:41, 24 September 2006 (UTC)

Examples

In the Path Heuristic, there is a number in front of the ordering of the votes. "3 ABCED". Maybe I'm missing something, but the text doesn't seem to explain what those number are and what they mean, or at least it doesn't do so near the first example. I'd like to see that improved because it's interfering with my understanding of the explanation of the examples. Hu 07:04, 30 October 2006 (UTC)

The numbers mean how many voters have chosen that order of the candidates. -- Jokes Free4Me (talk) 21:55, 30 December 2007 (UTC)

4th example

I see that in the 4th example, both B and D are potential winners. What happens next? -- Jokes Free4Me (talk) 21:55, 30 December 2007 (UTC)

There are many ways to solve situations with more than one potential winner. For example, Debian's constitution says in appendix A ("Standard Resolution Procedure"), article A6 ("Vote Counting"), section 8: "If there are multiple options, the elector with the casting vote chooses which of those options wins."

In section 5 of my paper, I recommend that, when there is more than one potential Schulze winner, then the ranked pairs method should be used to calculate a complete ranking of all candidates (and not only of the potential Schulze winners) and the final winner should be that potential Schulze winner who is ranked highest in this ranked pairs ranking. However, in example 4, also the ranked pairs method is indecisive between the rankings BCDA, BDAC, and DABC. Markus Schulze 15:38, 2 January 2008 (UTC)

I guess B could still argue for a win because he would beat D in a run-off, and he also has a better wins/defeats matchup (2-1 while D has 1-2). Are there any arguments for D winning? :-) -- Jokes Free4Me (talk) 17:20, 4 January 2008 (UTC)

(1) You wrote: "B would beat D in a run-off." Simply re-applying the Schulze method among the potential winners could result in a violation of monotonicity [1].

(2) You wrote: "B has a better wins/defeats matchup." B and C are clones. When we shrink them to a single candidate B, example 4 looks as follows:

3 ABD

2 DAB

2 DBA

2 BDA

The matrix of pairwise defeats looks as follows:

	d[*,A]	d[*,B]	d[*,D]
d[A,*]		5	3
d[B,*]	4		5
d[D,*]	6	4

Now, all candidates have the same wins/defeats matchup.

(3) You wrote: "Are there any arguments for D winning?" Yes! Reversal symmetry! Original situation:

There are three candidates. Candidate B pairwise beats candidate D. Candidate D pairwise beats candidate A. Candidate A pairwise beats candidate B. The pairwise defeats B:D and A:B have the same strength. The pairwise defeat D:A is stronger.

When the individual ballots are inverted, then we get:

There are three candidates. Candidate D pairwise beats candidate B. Candidate A pairwise beats candidate D. Candidate B pairwise beats candidate A. The pairwise defeats D:B and B:A have the same strength. The pairwise defeat A:D is stronger.

The original situation and the inverted situation are identical; only the roles of candidate D and candidate A have been exchanged. So if candidate B was the unique winner in the original situation, then he must also be the unique winner in the inverted situation. But this would be a violation of reversal symmetry.

I recommend that, in situations where both the Schulze method and the ranked pairs method are indecisive, random ballot should be used to decide who of the potential winners should be elected. That means: A ballot is chosen randomly; the winner is that potential winner who is ranked highest on this randomly chosen ballot. In example 4, B would be elected with a probability of 5/9 and D would be elected with a probability of 4/9. Markus Schulze 11:36, 6 January 2008 (UTC)

Non-strict ordering

If it is not too much trouble, i'd like to see one example that features non-strict orderings of the candidates, something like:

• A, then D, then C, with B and E not ranked
• B and C ranked the same for 1st position, then D, then A, then E

Thank you. -- Jokes Free4Me (talk) 21:55, 30 December 2007 (UTC)

Section 3.9 of my paper contains an example with non-strict orderings. Markus Schulze 17:29, 5 January 2008 (UTC)

Criteria

The criteria section of the article is complex. I was wondering if someone had a good idea on how to group the criteria. For example, half of the criteria on the list are implied by local IIA: non-imposition, non-dictatorship, majority, mutual majority, Condorcet and Condorcet loser, Smith, and LIIA itself.

I thought that an implication list would work

1. Schwartz criterion → Smith criterion → mutual majority criterion → majority criterion → non-imposition

but the limitation of the format in not allowing multiple inheritance was unfortunate. Perhaps a sub-list?

1. Schwartz criterion
   1. Smith criterion
   2. Mutual majority criterion
   3. Condorcet criterion
   4. Condorcet loser
   5. Majority criterion
   6. Non-dictatorship
   7. Non-imposition
2. Independence of clones

Of course perhaps this is a bad idea and the criteria should stay as-is, on which case the criteria not met should probably follow suit for consistency.

CRGreathouse (t | c) 04:48, 6 November 2007 (UTC)

The implications of the different criteria can be quite complex (e.g. see page 8 of my paper). Therefore, it makes more sense, in my opinion, to describe these implications in the corresponding voting system criterion articles rather than in the voting system articles.

By the way: Why did you delete the duplicate links? I believe that most readers do not read Wikipedia articles from top to bottom. They only read those parts they consider interesting. Therefore, it makes more sense, in my opinion, to wikify all occurrences of a given term in a given article rather than to wikify only the first occurrence of this term in this article. Is there a Wikipedia policy about duplicate links? Markus Schulze 20:35, 6 November 2007 (UTC)

The duplicate links I deleted were to aka, three links in 3-5 lines. I don't think that was needed even once, but three times was certainly over the top IMO. Wikipedia policy on duplicate links: link first occurrence in the article, and possibly the first occurrence in each section (editor discretion), but not more than one link to a given page per section. I apply this loosely; whatever serves the particular article works well enough for me. But I certainly don't like multiple links to the same thing in a section. I don't mind the ones like non-imposition and non-dictatorship both going to the same place -- that's where the ignore all rules policy comes in. :)

I have a chart similar to yours (with the eight majoritarian properties you have, plus five unanimity properties) on my website. I don't think the relations are all that complex. Maybe we could just combine those that follow from the Condorcet property? On this list that would be the mutual majority criterion, majority criterion, non-dictatorship, non-imposition, and the Condorcet criterion itself.

CRGreathouse (t | c) 21:12, 6 November 2007 (UTC)

Where is your website? Markus Schulze 22:22, 6 November 2007 (UTC)

I cringe to show it, as most of the pages are in progress. Here's the page with the chart: [2]. CRGreathouse (t | c) 21:52, 9 November 2007 (UTC)

If there are less than 3 voters, then near-unanimity doesn't make any sense. If there are 3 or more voters, then majority criterion implies near-unanimity. Markus Schulze 21:58, 9 November 2007 (UTC)

Yes, and Smith doesn't imply Condorcet loser unless there are at least 2 candidates. I have some decisions to make still, and I want to add more criteria. My problem at the moment is reconciling different systems -- I like the Pattanaik & Peleg random model, for example, but most of the criteria would need to be re-written to include such a model. Many of the criteria should be expanded in some way, or don't quite work in a general framework. For example strong Pareto is implied by a suitably generalized Schwartz criterion, but my version was taken from a paper using a single-winner version. Should I generalize? If so, how do I name the criteria? Smith's criterion (he calls it the "Condorcet criterion", though he notes that it's an extended version of same) is actually a multiple-winner version working on all unbeaten subsets of the set of candidates, not just the "Smith set" -- how should I expand to cover that? Again, lots of decisions to make. CRGreathouse (t | c) 22:12, 9 November 2007 (UTC)

I realize monotonicity is generally passed by almost all methods, but should it be added to the table? - McCart42 (talk) 23:47, 17 December 2007 (UTC)

Monotonicity is already added. Markus Schulze 23:53, 17 December 2007 (UTC)

Bringing BetterPoll to Facebook

If anyone wants to help with a Schulze method implementation on Facebook, feel free to contact Dave Scotese: http://www.facebook.com/profile.php?id=772980030 - McCart42 (talk) 23:54, 17 December 2007 (UTC)

Difference from Ranked Pairs

I'm new to the topic, and a bit confused about the difference between Ranked Pairs and the Schulze method... Would someone please provide (or link to) an example where they result in a different winner given the same votes? --Explodicle (talk) 21:00, 20 March 2008 (UTC)

In example 1 of the Schulze method article, the Schulze method chooses E while Ranked Pairs chooses A. In example 2, the Schulze method chooses D while Ranked Pairs chooses A. In example 3, the Schulze method chooses B while Ranked Pairs chooses A. Markus Schulze 22:00, 20 March 2008 (UTC)

Sections 3.5, 3.8, and 9 of this paper might be interesting. Markus Schulze 21:36, 20 March 2008 (UTC)

The main difference between the Schulze method and Ranked Pairs is that the winner of the Schulze method is almost always identical to the winner of the MinMax method, while the winner of the Ranked Pairs method differs from the winner of the MinMax method needlessly frequently. Examples:

1. Norman Petry (who uses the term "Tideman" for Ranked Pairs and the term "plain Condorcet" for the MinMax method) made some simulations and observed that the number of situations, where the Schulze method and the MinMax method chose the same candidate and Ranked Pairs chose a different candidate, exceeded the number of situations, where Ranked Pairs and the MinMax method chose the same candidate and the Schulze method chose a different candidate, by a factor of 100 [3].
2. Jobst Heitzig (who uses the term "beatpath" for the Schulze method, the term "Tideman" for Ranked Pairs, and the term "plain Condorcet" for the MinMax method) made a thorough investigation of the 4-candidate case. In no situation, the Schulze method and the MinMax method chose different candidates. ("Beatpath and Plain Condorcet are unanimous in all these examples!") But in 96 situations, Ranked Pairs and the MinMax method chose different candidates [4].

In section 9 of this paper, I explain why the winner of the Schulze method is almost always identical to the winner of the MinMax method. Markus Schulze 11:32, 21 March 2008 (UTC)

Ok, now I see. Thanks! --Explodicle (talk) 18:02, 27 March 2008 (UTC)

Re: Comparison with other preferential single-winner election methods

I notice that there are no "No"s listed for the Schulze method. Are there really no criteria/properties that this method fails and others don't? If so, this should be stated explicitly and referenced, because otherwise the table looks suspect. 82.139.87.64 (talk) 04:13, 19 June 2008 (UTC)

All methods capable of choosing from among three or more alternatives fails some criterion. In regards to Schulze one criterion of interest is independence of strongly dominated alternatives a/k/a independence of pareto dominated alternatives. Both Schulze and ranked pairs fail it, but Heitzig's river method (which is often compared to Schulze and ranked pairs) passes. SgtSchumann (talk) 02:16, 21 June 2008 (UTC)

I have added participation and consistency to the table. Markus Schulze 10:43, 21 June 2008 (UTC)

Explanation

Could someone write an explanation section which would makes sense to poor saps like me who have to use it? The article as it stands is incomprehensible. It would be nice to have some idea of who this Schulze person is too. DuncanHill (talk) 18:13, 28 June 2008 (UTC)

Path heuristic implementation

• Is the code in the path heuristic "Implementation" section pseudocode or an actual programming language? --Explodicle (T/C) 16:52, 9 July 2008 (UTC)

• It is Pascal-like pseudocode. Markus Schulze 18:57, 9 July 2008 (UTC)

• Will the casual audience actually go over the code? Can we put it in a {{show}} template? --Explodicle (T/C) 16:52, 9 July 2008 (UTC)

• In my opinion, the {{show}} template confuses inexperienced readers too much. Therefore, it should be used only when the article would become too long otherwise. Markus Schulze 18:57, 9 July 2008 (UTC)

Referencing

The article as it stands has multiple referencing problems - I have marked some of them with the {{fact}} tag, and added a {{citations}} to the top of the whole article. DuncanHill (talk) 10:24, 31 July 2008 (UTC)

Later-no-harm criterion

I removed the later-no-harm criterion from the comparison table because of the following reasons:

1. The later-no-harm criterion isn't sufficiently well defined. It is rather a paradigm than a proper criterion. For example: Does the Coombs' method satisfy this criterion? Does anti-plurality satisfy this criterion? Does plurality satisfy this criterion?
2. Whether a given election method satisfies later-no-harm depends too much on the details of this method. For example: User:70.255.172.161 mentions that, when pairwise opposition is used as a measure for the strength of a pairwise defeat, then MinMax satisfies later-no-harm; but to be fair, you would then also have to mention that, when pairwise opposition is used as a measure for the strength of a pairwise defeat, then MinMax violates the Condorcet criterion; but to be fair, you would then also have to mention that, when pairwise opposition is used as a measure for the strength of a pairwise defeat, then also the Schulze method violates the Condorcet criterion; etc..

In my opinion, all these problems of the later-no-harm criterion should be highlighted at the later-no-harm criterion article and not at the Schulze method article. Markus Schulze 17:57, 1 October 2008 (UTC)

I disagree with the removal. Most methods list later-no-harm in their list of satisfied/unsatisfied criteria on their own article page. If its inclusion is inappropriate in the chart then its inclusion is inappropriate in the article pages. I think standard implementations should apply to the chart, not possible variations. MiniMax, as per your example, doesn't specify a typical implementation therefore 'Depends' was an appropriate response (barring three separate MiniMax entries). --129.115.251.22 (talk) 00:22, 2 October 2008 (UTC)

At least for 6 of the 15 methods, that are listed in the comparison table, it is disputed whether this method satisfies the later-no-harm criterion: It is disputed for Coombs' method and for anti-plurality voting, because it isn't clear how these methods are defined for incomplete individual rankings. It is disputed for plurality voting, supplementary voting, and Sri Lankan contingent voting, because it is disputed whether the later-no-harm criterion can be applied to election methods that restrict the number of cast preferences. It is disputed for the MinMax method, because the typical implementation of this method is disputed.

Adding the later-no-harm criterion to the comparison table would move the discussion of this criterion from Talk:Later-no-harm criterion to the Schulze method article. Markus Schulze 01:38, 2 October 2008 (UTC)

Later-no-harm actually is not disputed for plurality voting and anti-plurality voting. Neither system is preferential so later-no-harm is inapplicable (not a yes or no). The only real dispute is with MiniMax since its definition of score can change its satisfied criteria. The others are just unknown at this point. Tastywheat (talk - contribs) 14:43, 2 October 2008 (UTC)

(1) It is disputed whether plurality voting satisfies later-no-harm. For example, Woodall argues that plurality voting satisfies later-no-harm [5]. (2) You wrote: "The only real dispute is with MiniMax since its definition of score can change its satisfied criteria." Well, also whether e.g. the Borda count satisfies later-no-harm depends on its definition of score. (3) Furthermore, it is disputed whether the Coombs' method satisfies later-no-harm, since usually this method is defined only for complete individual rankings. Markus Schulze 16:15, 2 October 2008 (UTC)

understandable?

I don't want to edit it without discussion, but wouldn't a column on the comparison chart that indicates whether a voting method can be explained to an uneducated person in a few sentences. while the Schulze method seems clearly to be the best method, it certainly couldn't be introduced to many americans without saying "don't worry about it, We educated few have ensured that this is the fairest method." instant runoff seems to have an advantage in this while still being hugely more fair than our current method. —Preceding unsigned comment added by 216.73.248.58 (talk) 15:44, 28 October 2008 (UTC)

There is a difference between the question whether a method is understandable on the one side and e.g. the question whether a method satisfies monotonicity, clone independence or reversal symmetry on the other side. The difference is: Every reader can easily make his own opinion about how understandable a method is; so he doesn't really need someone else to answer this question for him. On the other side, it is not clear at first glance whether a method satisfies monotonicity, clone independence or reversal symmetry; thorough mathematical investigations are needed to answer this question; so for this question, the comparison chart is really helpful to the reader. Markus Schulze 19:25, 28 October 2008 (UTC)

schulze stv

I don't see information on how this method relates to the Schulze STV method.