multiple comparison sorting

Question

I have a set of songs where I want to sort them by a particular quality. In order to do this (by crowdsourcing) I will present users with a comparison between two songs. The user will then choose which one ranks higher.

What algorithm can I use to weight the different comparisons? Given that I'll have a data set of comparisons between two points such as...

[ A >= B : 2
 A <= B : 0
 A >= C : 1
 A <= C : 4
 ...
 ( two dimensional array of size 2 * |songs - 1|^2 )
 ...
]

• outis: Some voting algorithms could be relevant, and not just due to the time of year (here in the states).
• valenterry: I am not sure that a general ranking makes any sense here. Did you think about creating a sorted list for each user on his own and on demand depending on his past choices? I could imagine if user 1 votes song A over song B and user 2 votes song A over song B and song D over song E then this means user 1 could also vote D over E and therefore liking song D. However it could also be that user 2 dislikes both D and E so it would be best to get some other information involved.

Answer 1

One possible formalization is as a longest path problem. Construct a directed graph in which nodes are labeled with songs, and for each ordered pair of songs (A, B) there is a weighted edge A -> B with weight equal to the number of votes for A < B. Then the longest simple path is a total order that agrees with the maximum number of votes. If the longest path contains the edge A -> B, then the consensus is that A < B.

Unfortunately, this problem is NP-hard unless the graph is acyclic (ie. no inconsistent rankings in your database). You may still be able to solve it in a reasonable amount of time depending on how many songs there are.

Answer 2

The problem doesn't require an exact solution. And opinions are not an exact mesure anyway. You could simply count +1 every time a song is preferred and -1 every time it is not preferred.

 A B C
A >= B : 2 +2 -2 
A <= B : 0 0 0
A >= C : 1 +1 -1
A <= C : 4 -4 +4
 ----------
 -1 -2 +3

This would give the order C> A> B.