Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.