3
$\begingroup$

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.]

$\endgroup$
  • $\begingroup$ Welcome to social choice theory, an entire area which studies similar questions. $\endgroup$ – Yuval Filmus Mar 4 at 18:08
  • 1
    $\begingroup$ "50 fantasy characters" with "face-to-face matchups". Do you imply that are 50*49 different atom data, two of which are "Spiderman beats Jon Snow" and "Jon Snow bests Spiderman"? $\endgroup$ – Apass.Jack Mar 4 at 19:48
  • $\begingroup$ A good starting point is Sorting with noisy information. $\endgroup$ – Yuval Filmus Mar 4 at 21:03
  • $\begingroup$ Thank you! This is just what I needed. And yes, either Spiderman or Jon Snow can win... $\endgroup$ – Chris Wilson Mar 4 at 22:54
1
$\begingroup$

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:

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.