Creating a ranked list from pairwise comparisons and ratings
I developed an application that allows users to rank distinct objects on a scale from 0-2 as well as compare the current object that they're ranking to the previous object that they ranked (i.e. a user gives A a 1, then gives B a 1, then says B>A). The order of the objects given is completely random and may contain repeat objects for a given user. In the end, 18 users make approximately 40 comparisons and 40 rankings each, for a set of 60 objects (number of users and objects may vary, but each object receives approximately 12 rankings and 24 comparisons in total).
What would be the easiest and most accurate way to create a ranked list from this data?
I've tried simply adding up the ratings for each object, but each user may have their own rating scale and biases, which leaves mid-tier objects grouped together. On the other hand, comparing adjacent elements of that list and swapping them if one was compared to be better than the other (essentially bubble sort) didn't significantly change the order, as the number of comparisons is a lot less than the number of two-object combinations. Searching online on this topic also yields very mathematical approaches to the problem, most of which I'm not familiar with.
For those wondering and familiar with FIRST Robotics, I'm trying to create a robot-ranking system for FRC, integrated into our scouting system. Thanks in advance for any responses!
Posted Aug 16, 2018, 10:59 PM UTC · edited
I assume this is supposed to say B>A?
How do you propose dealing with contradictory information? It’s possible to say A=1, B=2, and A>B.
I don’t have any experience in this area, but maybe I can give you some ideas. It would be possible to produce an ordering of all objects for each user, then aggregate the positioning of a given object across all orderings. There are many ways to do that - average position, scoring, etc.
Topological sort might help you here, and it can also tell you which sets of objects are “tied.”
Yes, thanks for the correction.
Right now, as I'm figuring out the best ordering method, I'm considering comparisons and rankings independent of each other, though a comparison will take precedence over ranking (unless B's ranking is significantly higher than A's), as a user's rating "scale" and standards might evolve as he/she observes more objects.
The problem with producing an ordering of all objects for each user is that each user doesn't compare/rate all objects in my application, but only a random subset of them. The comparisons are also made independently (the user doesn't input a ranked list, but just X {<, =, >} Y), so I could run into contradictions again.
The aggregate positioning idea sounds pretty good though, but I guess the main problem is a limited dataset and potential outlier rankings/comparisons for each object.
As long as there are no contradictions, topological sort will produce an ordering that satisfies all the information given. There may be more than one possible ordering, and if you wanted to get really complex you could use it to assign the same position to the objects that are “tied.” I’m not really sure what to do about objects that have no information from that user though. You could leave them out of that user’s contributions and say that the aggregate rating is the sum of all rank positions divided by the number of users that supplied information for that object. But this depends on getting a roughly equal number of users to supply info for each object - it wouldn’t be ok if one object only has a single user who supplied any info for it.