Are comparison sort algos appropriate for SUBJECTIVE sorting?

Question

I've been tasked with creating an online feature that ranks 50 fantasy characters from a variety of domains based on combat acumen and polls users one which one is the most powerful based on their votes on a series of face-to-face matchups. (Spiderman vs. Jon Snow, etc. etc.). If this is designed well, we hope to attract a large audience and high participation.

My first instinct was to use some variety of comparison sort--probably Bubble or Heap, given the manageable size. But as I brush up on the mechanics, all the literature I can find seems to be oriented toward stochastic sorts in which any pair of items can be definitely compared.

Another curveball here is that, as more people participate, the ordered list can (but needn't mustn't) be informed by all the people who have already weighted in. This will probably be necessary since we can't expect every user to weigh for hundreds of matchups. I'm not clear on how to tell the algorithm which items are already somewhere near their appropriate place in the list thanks to a lot of preexisting votes.

I'm sure I'm not the first to confront this issue since comparison algos are commonly used exact crowd wisdom on the best of, say, a few dozen photographs. I'm just not quite sure where to start. Am I looking for a variation on comparison sort with some addition search phrase for Google, or a different approach entirely?

Thanks![Insert favorite fantasy sign-off.]

Answer 1

I suggest reading about the theory on rating systems and ranking systems. There are many standard algorithms and methods for this. I would recommend reading the following resources, to get you started and to give you an entry-point and overview and let you figure out which might be best-suited for your particular situation:

• The Bradley-Terry model

• Pairwise comparison

• The Elo rating system, and other rating systems (TrueSkill, Glicko, etc.)

• Resources on Stats.SE: https://stats.stackexchange.com/q/30976/2921, https://stats.stackexchange.com/q/71297/2921, https://stats.stackexchange.com/q/15776/2921, https://stats.stackexchange.com/q/6379/2921

• Finally, there is work on experiment design: how to sequentially select which pair of characters to compare, based on the results of comparisons so far. (Think of this like matchmaking in chess, where you want to figure out which pairs of players to have play each other, based on their results so far.) I can't remember pointers right now, but I remember that I've seen some material on Stats.SE about this as well, so do some searching there and you might find additional references and resources.

I suspect it is likely that one of these will be a reasonable choice for you.

There is a major caveat. It is important to understand is that there may not be any linear ordering of characters that has the property you want.

Think of the game rock-paper-scissors; there is no linear ordering of these three choices that ranks them in order of "power", and polling people about pairs of them won't let you find a linear order. In particular, none of those three choices are any more powerful than any other; rock beats scissors, paper beats rock, and scissors beats rock. This can show up in fantasy settings, too.