Talk:Schulze method/Archive 2

This is an archive of past discussions about Schulze method. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

Archive 1

Archive 2

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:

d[C,D] > d[D,C] and d[E,F] ≤ d[F,E].
d[C,D] ≥ d[D,C] and d[E,F] < d[F,E].
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

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:

C(1) is identical to X.
C(n) is identical to Y.
For i = 1,...,(n-1): d[C(i),C(i+1)] > d[C(i+1),C(i)].
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

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?

Schwartz criterion
1. Smith criterion
2. Mutual majority criterion
3. Condorcet criterion
4. Condorcet loser
5. Majority criterion
6. Non-dictatorship
7. Non-imposition
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:

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].
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)