DanielBolef
commented
8 years ago Issue moved to new arena repo.
Closed DanielBolef closed 8 years ago
DanielBolef
commented
8 years ago Issue moved to new arena repo.
Idea from Goldman:
Basic Idea
Run a single elimination tournament. There is someone at the top. "Pop" them from the tournament by replacing them with the "bye" player. Redo all effected matches. There is someone new at the top. Repeat until no one is left in tournament or you have awarded enough places.
Advantages
In order to complete a single elimination tournament, you have to play N-1 matches, where N is the number of players. In order to pop someone out of the tournament you have to play log(N) matches. This means to award three places you have to play N-1 + 3log(N) matches. By contrast you have to play nearly 3N matches to award three places in triple elimination. Furthermore, you can award more than 3 places by continuing to pop players. Similarly, if an ineligible team is on top, you simply pop them from the tournament and continue on. When visualizing you can show all matches, and only perform one tournament, in contrast with triple elimination. Less matches also means you can play more games per match in the same amount of time. At any given time, the only teams who cannot play more games are those who have already placed. As such, no one should leave early because they have been eliminated.
Properties
Consider team Alpha. In the final ranking, the team ranked directly above Alpha beat Alpha in the tournament, and similarly the team ranked directly below Alpha lost to Alpha in the tournament. All teams that beat Alpha in the tournament are ranked above Alpha, and all teams that lost to Alpha in the tournament are below Alpha. As such, if there is a strict ordering (A>B>C>D>E) then heap tournament will find that ordering in Nlog(N) matches.
Degenerate Cases
Consider teams Alpha and Zeta. Alpha beats everyone but Zeta, and Zeta loses to everyone but Alpha. If Alpha plays Zeta in the first round (as they should be using best vs worst seeding), Alpha will be ranked last in the heap tournament.
In general if a generally good team loses to a generally bad team and those two play each other, the ranking will skew. A potential preventative measure is to seed based on rank left to right (IE, 1 plays 2, 3 plays 4... N-1 plays N in the final tournament) as this minimizes the chance of a bad player progressing enough to eliminate a significantly better player. Unfortunately this means the most interesting matches are at the very start of the tournament, with the championship games usually being blowouts (best of the top half versus best of the bottom half). Note when using this seeding, top ranked players should still get the "bye" opponents in the first round.
A better seeding alternative is to let teams determine their opponents based on rank. Basically if for all teams I have an expected ranking and expected quality versus all opponents then I can construct a seeding such that players with high rank play people they can beat early and people they can't beat until late, if ever. Note this is the same as how normal elimination does seeding, except this attempts to factor in pairwise quality not just overall rank.
(This also came from the Wiki)