2. Ordinal Rating Systems 

Ratings on an ordinal scale are commonly referred to as ranks. The process of ranking is based on the dominance relation, which does not admit of draws or multiple scores.  Assuming at least one pairing between player and opponent, the player is either dominant or subordinate with respect to the opponent.  The classic ranking problem is to assign ranks so as to minimize violations, in this case dominance by lower-ranking players. The problem has been shown to be NP-complete [GJ].  That is, barring an earth-shaking breakthrough, there is simply no ranking algorithm to be found that is both exact and efficient for data of significant quantity.  Rankings of a dozen or so players can be optimized by brute force, but as the number of ranks increases, the degree of complexity increases exponentially and a solution soon becomes impractical, even for a high-speed computer.  

For some NP-complete problems, difficulties can be overcome by restating the conditions of the problem, though perhaps at the risk of trivializing it.  It turns out that there is an efficient algorithm for ranking so as to minimize the sum of directed rank differences.  A directed (signed) difference in rank is taken from the rank of the subordinate player to the rank of the dominant player, 

          rank (dominant)  -  rank (subordinate) .

For expected results the direction is negative since the higher ranks are smaller.  Such results are desirable from the standpoint of ranking because they tend to minimize directed rank differences.  For upsets the direction is positive.  The algorithm for minimizing directed rank differences is simply to sort the players in descending order according to the difference W - L for each player, where W is the number of opponents dominated by the player and L is the number of opponents who dominate the player.  (The notation suggests "wins" and "losses" only as a mnemonic device.)  It is desirable, though not always possible, to apply the same algorithm as a tiebreaker to successively smaller subgroups.

Proof of the efficiency of sorting by W - L to minimize directed rank differences tends to be long-winded and will only be sketched here.  Note that when a player moves up in rank, directed rank difference decreases for each instance of W associated with the player and increases for each instance of L.  Similarly, when a player moves down in rank, directed rank differences increase for W and decrease for L.  For any adjacent pair of players, A and B, where A is the higher ranked, if

               W(A) - L(A)  <  W(B) -  L(B) ,

a swap will produce an overall decrease in directed rank difference.

It will not have escaped the notice of chess veterans that the algorithm described here is essentially the method used in deciding tournaments.  If tournament results require theoretical explanation, the theory can be put to good use.  Its usefulness is more apparent in so-called partial tournaments, where rankings are not based on complete interplay among the contestants. An example from chess is the popular Swiss System for pairings, which could conceivably bear improvements.  In the language of graphs, sorting by number of directed edges may be used as a rudimentary rating system in situations where the graph of competition is incomplete.