Monday, June 9, 2014

Resolving ties in a round-robin tournament

Let's consider a round-robin tournament. Arrows point to the loser in each match.

A is 4-1; B, C, and D are 3-2; E is 2-3, and F is 0-5. How to break the three-way tie for second place? Most round-robin tournaments would use total speaker points, but I think this is unnecessary. (And all sorts of weird things can happen if you use total points to decide tournaments.)

There are four different methods I would like to consider. The first is a method of my own invention, weighted wins and weighted losses. While this method is very simple and easy to use, it is better for incomplete tournaments (regular tournaments) than it is for a complete tournament (a round robin). One key bias to note is that the method will prefer multiple smaller upsets than one big upset. In the running example, the weighted wins will rank the teams {A, B, C-D tie, E, F}. This means C's win over A, D's win over B, and E's win over D are all ties.

The second method and third methods both require using the point differentials to order the teams. I invented the following differentials in speaker points:

The second method is the ranked pairs method. The wins are ranked in order of margin, in this case, speaker point differentials. (Let's say the speaker points are adjusted by each judge's typical points. For example, a differential of 4 speaker points might be nudged up to 4.1 if 4 is actually quite a large point differential for that judge. Low point wins could be entered as zeros or a small positive number, and they should not be entered as negative numbers.)

This means the wins go A over F, A - E, B - F, D - F, D - C, C - E, A - D, C - F, B - C, B - E, A - B, D - B, E - F, C - A, and E - D. One applies the wins in order. Wins that create a contradiction (a cycle) are ignored. For example, the first win, A over F, is applied first:

{A, F} {B, C, D, E unranked}

Then next A over E:

{A, E-F tie} {B, C, D unranked}

And so on. In this particular tournament, one does not reach a contradiction until the last two wins, so one ignores C over A (A beat B, B beat C, so acknowledging C beat A would create a cycle). Same thing for E over D. Without these two results, A has 4 wins and 0 losses, B has 3 wins and 2 losses, C has 2 wins and 2 losses, D has 3 wins and 1 loss, E has 2 wins and 3 losses, and F has 0 wins and 5 losses. This sets up the ranking: {A, D, B, C, E, F}.

The third method is the Schulze method. The key idea is to look at the strongest path from each team to each opponent. The path may go through intermediaries, but it has to follow the directions of wins. For example, if a team is undefeated, no opponent would have any path back to that team, so all entries to the undefeated team would be scored zero. The strongest path is scored by its weakest link. In our running example, every path to A would go through C, so the paths would all have a strength of 1.1, for the weakest link, C over A.

Here is the path strength matrix, with the strongest of each pair (e.g., A over B vs. B over A) highlighted:

As you can see, A emerges the overall winner. The path from A to C is stronger than the path from C to A, even though the latter was an actual win, whereas the former is a pathway through D. The final ranking with the Schulze method would be {A, D, B, C, E, F} again.

The final method I would like to look at is a modified version of the Kemeny-Young method. First, one would generate a list of every possible ranking consistent with the results. Since the original tournament generated a three-way tie between B, C, and D, the possible rankings are:

{A, B, C, D, E, F}
{A, B, D, C, E, F}
{A, C, B, D, E, F}
{A, C, D, B, E, F}
{A, D, B, C, E, F}
{A, D, C, B, E, F}

Then, each ranking is scored, and the highest score ranking is preferred. (Earlier, I looked at minimizing upsets, but the effect is exactly the same.) The highest score ranking is 13:

Two results are "upsets": C over A and E over D. But this ranking is consistent with all the other results, thus earning the highest score.

To avoid ties, one could modify the wins by including decimal values for point differentials and judge variance. For example, A's win over D could be given a score of 1.028 (the 0.028 for the point differential in that win), whereas A's win over F could be given a score of 1.05. Adding tiny decimal values will not change how many upsets there are in the final, highest scored ranking -- the tiny decimals would never be worth enough points to offset an additional upset. All that the decimal values would do is allow one to chose between two otherwise tied rankings, i.e., two rankings with equal numbers of upsets.

Ranked pairs, Schulze, and Kemeny-Young all agree on the best ranking in my example: {A, D, B, C, E, F}. They do not have to, but they do. My weighted wins method disagrees, but I see this as a weakness of my method when applied to a round-robin tournament.

Conceptually, Kemeny-Young is the easiest method of all. It looks for the ranking that is most consistent with the actual wins and losses, and then if we want, at point differentials as a tie-breaker. It is an easy method to code. It would be easy to use this method for multiple-ballot rounds. My recommendation would be to use Kemeny-Young to break round-robin ties, not total speaker points or total judge variance.

No comments:

Post a Comment