# multiple comparison sorting

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 )
...
]
``````
• Some voting algorithms could be relevant, and not just due to the time of year (here in the states). – outis Nov 6 '14 at 5:07
• 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. – valenterry Nov 6 '14 at 8:50

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.

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.