Rankings based on “versus” style matchups? [closed]

Question

Let's say I have an application that, from a pool of items, presents a random two to the user. The user selects one as the "winner" and the result would be recorded like this:

INSERT INTO results (winner_id, loser_id) VALUES (26, 45);

What would be the best way to use the results table to rank the items?

This question has a theoretical/subjective component--i.e., there's more than one way to think about ranking them.

For example, this isn't that much different from, say, a season of baseball. Baseball chooses a winner simply by comparing win percentages. But in baseball you could end up with Cleveland with a better winning percentage than Detroit, yet Detroit beat Cleveland every time they played this year. So from another point of view besides winning percentage, you could say that Detroit is better than Cleveland.

It's that other point of view I'm interested in. If you start with two items--A and B--and know from the results table that B beat A 30 times and lost 5 times, you know B should be ranked above A. Then you look at C, which was 8-10 against B and 12-6 against A, and place it between B and A. And so on.

It seems like I'm describing a fairly simple formula, but when you start extending it, it seems like it would get really computationally heavy for large sets of items, and it would be problematic for an item that doesn't fall between two items that it would be expected to fall between based on the rankings up to that point.

Do you think such a ranking system is feasible? Does this concept already have a name? Would it be possible to set up a system of queries that could reasonably provide results in realtime in a web application for, say, 10,000 items?

Answer 1

This will always have the problem where A beats B, B beats C and C beats A. I don't know of any deterministic ways to define who ranks top in this case. Rock, paper, scissors and similar games exist because of this.

You're likely to get some form of circular dependency like this for any real sport, particularly when looking at a small number of games. There may be some algorithm to resolve this, but I'm not aware of it.

Assuming there is some algorithm to do what you'd like, changing your data model slightly will make it easier to do:

RESULTS (team_a_id, team_b_id, team_a_wins, team_b_wins, ties);

This will reduce the number of records you have to inspect as there will only be one entry for each pair of teams, instead one for each game for each pair of teams.

Answer 2

Ranking algorithms is a very deep subject. What type of ranking you choose depends upon many, many factors. Factors like:

1. Do you want to rank the players/teams based solely on win/loss record?

2. Is this a ranking system that keeps score? If so, do you want to take into account how badly someone was defeated? (E.g. a team winning by 75 points is much better than a win by 2 points.)

3. Is a tie possible? If so, how does your ranking handle that?

4. Is a win/loss by default possible? If so, how does your ranking count that?

5. Do you need to consider anomalous wins/losses?

There's too many factors to consider to just say "Here's how to implement a ranking system". Each ranking system is unique to the sport/activity that it's trying to rank. And, at that, there are generally many ranking systems per sport/activity.

If you're trying to model something specific, you need to include more information. Otherwise, you're opening yourself up to the entire field of statistcal mathematics.

Regarding databases, the complexity of the database design will be directly dependent upon the ranking algorithm you use.