It's even more difficult to thwart player collusion. The challenger for the world chess championship used to be decided at a round-robin tournament. Bobby Fischer complained that the Russians dominated the tournament, and gave each other easy draws, while playing hard against non-Russian opponents. He demanded a binary tree (of one-on-one matches), and the Chess Federation agreed. Knuth has a long discussion of the number of binary compares needed to select the top K players. Rich ---- Quoting Phil Carmody <thefatphil@yahoo.co.uk>:
From: Warren Smith <warren.wds@gmail.com>
There was recently a scandal in the Olympics where some badminton teams were intentionally trying to lose.
Now with certain tournament designs, such as the one they used in the Olympics, and also "Swiss system" chess tournaments, it is possible for situations to arise, where intentionally losing your game, increases your expected amount of prize-rewards.
But other tournament designs are immune from this problem. ... PROBLEM: devise other schemes...
One example would be a "tree of round-robins" where the players are partitioned into disjoint subsets, each subset plays a round robin, then the top-K from each subset enter a "round robin of champions" round.
That seems to be very common. Online, when I'm playing abstract strategy games online (at littlegolem), and in real life too (tiddlywinks, don't laugh).
Double-elimination seems to work well for smallish numbers of competitors. You can slip up once. The way I've seen such things organised there does seem to be chances for the same people to play each other multiple times. I'm not sure if that can be mostly avoided by clever permutation of how the losers get inserted in the lower tree. It can't be avoided entirely, as if you have 2 entrants who basically never lose to anyone else, the only way they'll be eliminated is if they play each other multiple times.
If ~2N is too few matches, can double-elimination be generalised to k-times-elimination for a suitably chosen k? The double-elimination tree is at least (if you don't care about repeated matches) trivial to organise, barely more complex than single elimination. I'm not sure it generalises so easily though.
Phil
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun