# Question on the Condorcet Ranking (Schulze Method) Algorithm

I've been doing some research on ranking algorithms, and I've read theresearch with interest. The aspects of the Schulze Algorithm that appeals to me is that respondents do not have to rank all options, the rank just has to be ordinal (rather than in order), and ties can be resolved. However, upon implementation, I'm having trouble showing that ties do not occur when using the algorithm.

I've put together a below real-life example, in which the result looks to be a tie. I can't figure out what I'm doing wrong. Is the solution simply to randomly select a winner when there is a tie? Could you somoene please have a look and offer any advice?

Thanks very much,

David

Who do you think are the best basketball players?

_ Kevin Garnett

_ Lebron James

_ Josh Smith

_ David Lee

_ Tyson Chandler

5 users (let’s just call them User A, User B, User C, User D and User E) answer the question in the following way:

User A :

1.Kevin Garnett

2.Tyson Chandler

3.Josh Smith

4.David Lee

5.Lebron James

User B:

1.Kevin Garnett

2.David Lee

3.Lebron James

4.Tyson Chandler

5.Josh Smith

User C:

1.David Lee

2.Josh Smith

3.Kevin Garnett

4.Lebron James

5.Tyson Chandler

User D:

1.Lebron James

2.Josh Smith

3.Tyson Chandler

4.David Lee

5.Kevin Garnett

User E:

1.Tyson Chandler

2.David Lee

3.Kevin Garnett

4.Lebron James

5.Josh Smith

If you put together the matrix of pairwise preferences, it would look like:

p[*Kevin Garnett]

p[*Tyson Chandler]

p[*David Lee]

p[*Lebron James]

p[*Josh Smith]

p[*Kevin Garnett]

-

3

2

4

3

p[*Tyson Chandler]

2

-

3

2

3

p[*David Lee]

3

2

-

4

3

p[*Lebron James]

1

3

1

-

3

p[*Josh Smith]

2

2

2

2

-

To find the strongest paths, you can then construct the grid to look like:

Now, the strongest paths are (weakest links in red):

…to Kevin Garnett

…to Tyson Chandler

…to David Lee

…to Lebron James

…to Josh Smith

From Kevin Garnett…

-

Tyson Chandler (3)

Tyson Chandler (3) – David Lee (3)

Lebron James (4)

Josh Smith (3)

From Tyson Chandler…

David Lee (3) – Kevin Garnett (3)

-

David Lee (3)

David Lee (3) – Lebron James (4)

Josh Smith (3)

From David Lee…

Kevin Garnett (3)

Kevin Garnett (3) – Tyson Chandler (3)

-

Lebron James (4)

Josh Smith (3)

From Lebron James…

Tyson Chandler (4) – David Lee (3) – Kevin Garnett (3)

Tyson Chandler (4)

Tyson Chandler (4) – David Lee (3)

-

Josh Smith (3)

From Josh Smith…

0

0

0

0

-

So the new strongest paths grid is:

p[*Kevin Garnett]

p[*Tyson Chandler]

p[*David Lee]

p[*Lebron James]

p[*Josh Smith]

p[*Kevin Garnett]

-

3

3

4

3

p[*Tyson Chandler]

3

-

3

3

3

p[*David Lee]

3

3

-

4

3

p[*Lebron James]

3

4

3

-

3

p[*Josh Smith]

0

0

0

0

-

Kevin Garnett and David Lee would tie in this case.

-

There isn't necessarily a unique winner. However, the following statements can be proven:

• There is always at least one winner (section 4.1).

• Unless there are pairwise links of equivalent strengths, there is a unique winner (section 4.2.1).

• When there is not a unique winner, then it is sufficient to add a single ballot to get a unique winner (section 4.2.2).

In section 3.2, I give an example without a unique winner.

See:

http://m-schulze.webhop.net/schulze1.pdf

-

There's no reason to believe that the method can't result in a tie; in fact it's easy to think of much simpler examples where it does, e.g. when two people vote on two items and have opposite preferences. The Wikipedia article also has a section on ties, which explicitly states that they occur.

-

You can see that ties are not avoidable with a simpler example. Consider this election with three candidates and three votes:

A>B>C (1 single vote)
B>C>A (1 single vote)
C>A>B (1 single vote)


The result will be a cycle, the Smith set contains all candidates, and you will need to break the tie.

-

I have developed a simple voting app using Schulze algorithm. Assuming I did input your data correctly the results are as follows:

$$\mathbf{Choices}= \begin{pmatrix} KG & LJ & JS & DL & TC\\ \end{pmatrix}$$

$$\mathbf{D}= \begin{pmatrix} 0 & 4 & 3 & 2 & 3\\ 1 & 0 & 3 & 1 & 3\\ 2 & 2 & 0 & 2 & 2\\ 3 & 4 & 3 & 0 & 2\\ 2 & 2 & 3 & 3 & 0\\ \end{pmatrix}$$

$$\mathbf{P}= \begin{pmatrix} 0 & 4 & 3 & 3 & 3\\ 3 & 0 & 3 & 3 & 3\\ 2 & 2 & 0 & 2 & 2\\ 3 & 4 & 3 & 0 & 3\\ 3 & 3 & 3 & 3 & 0\\ \end{pmatrix}$$

With final ordering of Choices being undetermined as there is indeed a tie between DL and KG, and also between LJ and TC. The Schulze algorithm does not seem to resolve those ties and there does not seem to be an intuitive ordering as DL has the same number of votes in total as KG.

It would be great if someone could provide more insight into this matter.

-
Maybe this should be a separate question? – Asaf Karagila Aug 19 '14 at 10:40