Friday, May 31, 2013

The Upset, Part III: Min-V

A league's B-team higher than A-team?  What're (insert team here) doing so far down/up?  That ranking makes no sense!

What the heck is that Min-V ranking doing?


Well, like both ranking written about last week, European Roller Derby Rankings and Derby Chart, the Min-V system doesn't consider A and B teams as related.  One's ranking doesn't affect the other.

As well, the Min-V doesn't consider scores.  It only considers who won and lost.


The system works like this:

If the Qarth Rollers defeat the Vaes Dothrak Rolling Horde, then QR should be ranked above VDRH in all future rankings.  That is, QR should have more ranking points than VDRH.  If that's not the case, the bout is a violation.

The computer takes a table of all the bouts and results, as well as a list of all teams, and uses an efficient trial-and-error method to compute the minimum number of violations possible, hence Min-V.

[Details and theoretical basis thanks to Dr. Coleman can be found in this pdf file.]


The computer then outputs a table with each team and its ranking points.  This is only one possible solution; there are an infinite set of ranking point tables which produce the same number of violations.  As well, there are several orderings of teams which will not change that number.

Due to this, the ranking can be optimized.  Optimization is the process of adjusting the ranking points values for each team to more closely match what other ranking systems produce.  For example, it doesn't matter mathematically if LRG[A] or Gent[B] are ranked #1.  Since neither played the other, changing that order will not cause a violation.

LRG[A] will be optimized to #1, and Gent[B] lower in the table.  However, Gent[B] cannot be moved below Paris without causing a violation.  They, in turn, cannot go below Bear City, etc.  The knock-on effects in a Min-V system can be massive, so optimization must be done carefully.

In this case, optimization was done attempting to match the Derby Chart ranking.  It could be done to approach any ranking scheme using the same Min-V basis.


Min-V has been used effectively in the US College Football system for years, with great predictive and retrodictive results.  As was shown last week, retrodictivity in other derby rankings is spotty at best.  ERDR rankings say that 1 in 5 bouts were upsets, Derby Chart's say 1 in 4.  The Min-V ranking table, as odd as it looks, only has 1 in 30 bouts as upsets.

It's the most retrodictively correct ranking by more than a factor of 6.

But is it the best ranking?


The answer to that question is a question itself: "How is best measured?"

And to set those two questions into perspective, consider this one: "Why care about rankings?"


As there's no trophy awarded on rankings, and no Champions League in European derby (yet???), the choice is yours.  Min-V is presented here to show just how impossible it is to conclusively put all European leagues in a ranked order.

If they're properly used, rankings can be a helpful source of information.  ERDR has an archive of past rankings, and Derby Chart has bout records for each team.  But don't become too dependent on them.  Even the most theoretically precise system is wrong 1 out of 30 times, and the most trusted are 1 in 4 or 1 in 5.


Keep rankings in perspective.  They're to inform and educate, not to dictate.

4 comments:

  1. Nice :) Out of interest, what method / software do you use for the optimization? (My background is in large-scale LP optimization using barrier methods).

    ReplyDelete
    Replies
    1. Linux LP_solve It does well with 6 months' worth of bouts, but craps out at about 9.

      Delete
  2. What sort of matrix size are you looking at? As far as GPL optimizers go I've used CLP previously and it has been pretty reliable for relatively big problems. It doesn't seem to be under active development though. We use MOSEK now and have been playing with Gurobi - but they're commercial :(

    ReplyDelete
    Replies
    1. It's a 275-line lp file, 273 constraints, 437 separate variables.

      Delete