Algorithm for fuzzy sorting with probabilistic pairwise comparison

Question

Assume that there are n players to play a pair-wise game. Result of each match is mainly depend on two players' strength as well as a bit of luck.

How to obtain a more accurate ranking of each players with fewer games?

Answer 1

In the ideal case where the stronger player always wins you would be able to sort the list of players using a comparison sort like mergesort or quicksort, or even using a sorting network to require the fewest comparisons possible. Since this is not the ideal case (luck is involved), these algorithms might not yield the correct result due to a violation of the transitive property, however I believe there is a way you could detect and correct many of the instances of luck beating strength, as described below:

First, sort the players using something like mergesort (where violation of the transitive property isn't going to cause an infinite loop). Transform the comparisons executed into a directional graph, where each edge points to the winner of the match. Call this original graph G. Now, for each pair of connected edges in G, add a third edge (creating a triangle) by doing a comparison between the "end" vertices, and put the updated graph in G' (leave G unmodified). Once this is done, check G' for cycles- if any exists, they represent a violation of the transitive property. To resolve them, compare members of the cycle with other members of the graph, which inevitably will produce more cycles. The mutual edge between these cycles is quite likely the offender, and we may assume it was a "lucky" win. Mark all such edges for negation.

Once all cycles have been resolved, you may find that you cannot sort the graph topologically due to some ambiguities. Perform comparisons as necessary to resolve the ambiguities, but note that these new comparisons have nothing to guarantee their correctness (yet). To resolve this, repeat the above procedure with these new edges in a graph G1 recursively, until an unambiguous graph is produced. Insert these edges into G, and topologically sort.

You may modify the above algorithm for more speed or more accuracy if you wish. For accuracy, just compare each edge with more redundant edges to expose and clarify cycles more reliably. For more speed, test for larger groups of cycles- instead of trying to find cycles of length 3, compare "ends" of say- every 6 edges to find cycles of length 7, or so. If cycles / "lucky wins" are rare enough, you'll save considerable time by checking multiple edges at once although a) you may overlook a cycle if two violations "cancel" each other out, and b) you'll still spend a good deal of time locating the specific violating edge in a larger cycle.