Tuesday, December 22, 2015

An abstract ranking system

Ranking systems seem to be all the rage these days, especially in sports. Here are just some jumbled thoughts on what we might want from a ranking system:

Abstractly, we want a function RANK(G), where

Input: G is a (possibly multi-)directed graph on N vertices
Output: A "ranking" of the N vertices. That is, a total ordering of the N vertices with ties.

We probably want the following properties:

(ISO) If $G_1$ and $G_2$ are isomorphic graphs, then this isomorphism should also take RANK($G_1$) to RANK($G_2$)
(ADDEDGE) Let $H = G\cup\{u\rightarrow v\}$ for some $u,v\in G$. Then the ranking of $u$ in RANK($H$) is no worse than the ranking of $u$ in RANK($G$) (that is, no teams that are ranked behind $u$ get moved in front of $u$ as a result of $u$ beating $v$), and the ranking of $v$ in RANK($H$) is no better than the ranking of $v$ in RANK($G$). In addition, if $u$ and $v$ were ranked the same in RANK($G$), then $u$ should be ranked strictly higher than $v$ in RANK($H$). Conversely, if $u$ and $v$ are equal in RANK($H$), then $v$ must have been ranked strictly higher in RANK($G$).

Perhaps the following would also be nice?

(MIRROR) Suppose $G'$ is the result of mirroring all of the edges of $G$. Then RANK($G'$) is just RANK($G$) reversed.

One ranking system that satisfies (ISO), (ADDEDGE), and (MIRROR) is the ranking system where we just rank teams based on winning percentage, with 0-0 teams coming in at 50%. And when $n = 3$, this is the only ranking system satisfying (ISO), (ADDEDGE), and (MIRROR). However, this is definitely not a satisfactory ranking systems in many situations, such as the FBS.

One thing that college football analysts like to harp over is "Strength of Schedule". There is some merit in this: suppose we had the following situation: There are two groups (call them SEC and ACC for no reason in particular) such that every team plays each other team in the same group, and every team in the ACC beats every team in the SEC that they play (and suppose the density of games between the two groups is reasonably high.) Then it makes sense that an ACC team that doesn't beat any other ACC teams should still be ranked higher than an SEC team that beats every other SEC team, which wouldn't necessarily be reflected if we just ranked by winning percentage.

So maybe these are two other properties that we care about:

(WEAKDOM) Suppose $S_1$ and $S_2$ are two different strongly connected components in $G$ such that 1) no team in $S_2$ has beaten $S_1$ and 2) At least 1 team in $S_1$ has beaten a team in $S_2$. Then every team in $S_1$ should be ranked higher than every team in $S_2$ in RANK($G$).

(STRONGDOM) Suppose $S_1$ and $S_2$ are two different strongly connected components in $G$ such that every $S_1$ has beaten every team in $S_2$. Then every team in $S_1$ should be ranked higher than every team in $S_2$ in RANK($G$).

(STRONGDOM) is probably too strong to be practical. (WEAKDOM) can be scary but it's probably reasonable to have in all practical situations.

2 comments :

  1. What are the best casinos to play in 2021?
    Which 1xbet login casinos wooricasinos.info offer 바카라 사이트 slots? — Casino Sites. casinosites.one Best casino sites are those that allow players to try a game 바카라 사이트 from anywhere. The most common online slots

    ReplyDelete
  2. If you’re looking for the most effective on-line casinos in the UK, you’re in luck. Our staff of consultants have reviewed the most effective gambling websites in the thecasinosource.com UK to play slots, roulette, blackjack, bingo, poker, and more. The greatest UK on-line casinos provide selection of|quite a lot of|a wide range of} high-quality casino video games, quick payouts, selection of|quite a lot of|a wide range of} banking options, and beneficiant welcome bonuses. The greatest gambling websites will of course have video games software program from high developers, corresponding to Playtech, BetSoft and Microgaming. You can certain to|make positive to|remember to} discover slots with nice graphics and loads of dynamic options that may run easily, whether it’s a desktop, iPhone or mobile system that you’re using.

    ReplyDelete