I've been doing some research on ranking algorithms, and I've read your research 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 somone 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:
To find the strongest paths, you can then construct the grid to look like:
Now, the strongest paths are (weakest links in red):
So the new strongest paths grid is:
Kevin Garnett and David Lee would tie in this case.
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 somone 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.