Even in a case of transitivity and stability (A beats B either 100% of the time, or 0% of the time), a "single elimination" tournament will only find the best, not the second best. "Double elimination" is required to find the second best, and even then, the third best won't necessarily be known. I think that this may have some applicability to the Olympics, where sometimes the bronze (3rd place) medal may not go to the 3rd best. If stability and/or transitivity is thrown out, then things get a lot more complicated, and you have to be much more precise about what you mean by "best", etc. At 09:14 AM 8/30/2004, David Gale wrote:
Thanks, Don, for the highly relevant reference. In fact, my great discovery that it's easier to find the top t players than the t'th highest player turns out not to be as profound as I'd thought. A bright fifth grader could probably see that you only need two matches to select the top 2 players from a set of 3, whereas it may take three matches to find the second best. In fact, (this may be tenth grade level), the latter will happen two thirds of the time assuming the first matching pair is chosen at random. Oh well, David
At 03:17 PM 8/27/2004 -0600, you wrote:
There doesn't seem to be any treatment of the top t problem in the literature. Knuth doesn't even mention it. But he does mention it. See TAOCP Volume III, section 5.3.3, problem 14; and especially the answer. -- Don Reble djr@nk.ca