Sunday, June 07, 2020

[ggdjngrm] Sequential simulated single elimination after round robin

First, play a round-robin tournament among all contestants.  For simplicity, assume every game has a decisive result (no ties).  This is the only part of the whole tournament that has the players actually playing.  The next steps determine a ranking from the round-robin results.  The method is probabilistic: the output ranking incorporates an element of chance.

After the round robin, we run a series of simulated single-elimination tournaments, using the round-robin results to decide who advances.

Set up the first single-elimination bracket, seeding uniformly randomly.  Seeding must be uniformly random, or else there will be incentive to collude during the round robin.

Simulate the bracket, using the round-robin results to decide who advances.  Seeding of course has a huge influence on the outcome of the single elimination, so the seeding could be done at a ceremony, filling in the bracket in an order that makes it most suspenseful.

What order is most suspenseful?  Consider the following.  Write the numbers in order in binary, reverse the bits, then reinterpret as a number: 0 1 2 3 4 5 6 7 -> 000 001 010 011 100 101 110 111 -> 000 100 010 110 001 101 011 111 -> 0 4 2 6 1 5 3 7.  Number the bracket positions in order straight down.  Assign bracket positions to contestants in the bit-reversed order, each time uniformly sampling among remaining contestants without replacement.

One additional twist: the bracket is a losers' tournament.  For each game in the simulated single-elimination tournament, the loser (based on the the round-robin head-to-head result) advances.  The final loser of this first bracket gets overall last place.

If there are byes (because the number of contestants is not a power of 2), the bye does not advance.  Equivalently, some contestants are seeded into the second round (which is not a good thing since you want to lose).  Byes do not advance because if a bye could lose, i.e., advance, then a bye would become the final loser of the bracket.  Where to put the byes in a single-elimination tournament is a topic that has been covered by others.  I think the first (or last) few seeds in the bit-reversed order get byes.

Eliminate this overall last place contestant as determined by the first bracket, then set up another randomly seeded single-elimination bracket with one less contestant.  This next bracket decides overall next-to-last place.

Repeat, with smaller and smaller single-elimination brackets until all standings are determined.

We assign standings from last to first (with losers' single elimination) to maximize suspense.  Does it matter that we do it this way instead of doing it first to last (doing single elimination with winners advancing)?  It might take some effort to define and quantify, "does it matter?".  Maybe compare probability distributions over possible overall standings.

The goal of this method of determining ranking is to make every game during the round robin count.  Any game from the round robin could become used to determine the outcome of a matchup in some single elimination bracket.  Without some postseason, round robin often ends up with the situation where the last rounds don't matter because the standings are already set.  Round robin with no subsequent playoff also invites collusion, which we are also trying to prevent.  Does our proposed system accomplish these goals?

To investigate the behavior of this ranking system, simulate the postseason many times.  What is the range of outcomes?  Which round-robin games get referred to often?  These were the important games.

Instead of a round robin to determine results in the simulated single-elimination tournaments, consider using a more complicated probabilistic model.  Such a model can deal with ties, contestants not meeting, or meeting multiple times during the regular season.  The model should output win probabilities for matchups that occur in the simulated single elimination playoff brackets.  (If contestants didn't meet, I think the probabilities have to be 50-50, or else it allows collusion.)  Each simulated game in each bracket randomly chooses a winner, weighted by the win probabilities emitted by the regular season model.  This would add to the randomness already present in the random seedings.


No comments :