4
$\begingroup$

Equivalent to finding three heaviest coins in order of weight, on a balance that holds one coin on each side.

(Simplified, with some Wikipedia references corrected, from the original puzzle. The intended solution is essentially the same:)

How to most efficiently and fairly determine gold, silver and bronze medalists from a field of 8 contestants who play one-on-one matches?

Talent is presumed to be strictly ordered. A better contestant always beats any weaker one.
 The eventual gold medalist does not lose to anyone.
 The eventual silver medalist loses only to gold medalist.
 The eventual bronze medalist loses to silver medalist, perhaps also to gold if they are in a match, but wins every other match.
 All other contestants lose to the silver medalist, or to another contestant who loses to silver, or to another contestant who loses to another who loses to silver, and so on.

The tournament need not have a predetermined number of matches. For the solution found by this puzzle's poser for 8 contestants, the worst case requires 11 matches while the best case requires 9 matches.

Round-robin, for instance, can result in inconclusive loops is extremely inefficient. For 8 contestants, 28 matches are played.

A recent Winter Olympics event used a hybrid approach that resulted in no medal for the presumed third-best skier (Langenhorst?) as she lost to the eventual gold medalist during the single-elimination first stage. She never got to challenge the eventual silver or bronze medalists. That unfair system has a fixed number of 8 matches:

$\endgroup$
  • 2
    $\begingroup$ Are we to assume that games have consistent winners and follow the transitive property, e.g., each contestant has a real number ability and the one with the higher ability always wins? $\endgroup$ – noedne Apr 2 at 4:34
  • 1
    $\begingroup$ "The system as solution minimizes the average number of matches for the sake of fair results." What are we averaging over? $\endgroup$ – noedne Apr 2 at 4:37
  • 1
    $\begingroup$ In your link, it doesn't look like Langenhorst lost to the eventual gold medalist. $\endgroup$ – noedne Apr 2 at 4:45
  • 2
    $\begingroup$ "Round-robin can result in inconclusive loops." Does this refer to intransitivity, e.g., A beats B, B beats C, and C beats A? $\endgroup$ – noedne Apr 2 at 4:54
  • 1
    $\begingroup$ Exactly, @noedne. $\endgroup$ – humn Apr 2 at 4:55
3
$\begingroup$

[EDIT: After this was answered, the puzzle was restricted to $8$ players. In this case, $8+3+3-3=11$ games are required in the worst case.]

The following method requires up to

$n+\lceil\log_2n\rceil+\lceil\log_2(n-1)\rceil-3$

games.

Suppose $n=2^k$. First,

conduct a typical $k$-round $(n-1)$-game single-elimination tournament to determine first place.

Then,

the only candidates for second place are those who lost to first place. Let $a_i$ be the loser to first place in round $i+1$ for $i=0,\dots,k-1$. Conduct a sequential single-elimination tournament where the initial "contender" is $a_0$. In round $i$ for $i=1,\dots,k-1$, the current contender plays against $a_i$, the winner of which becomes the new contender. This determines second place in $k-1$ games.

Finally,

the only candidates for third place are those who lost to second place in either tournament. Conduct any single-elimination tournament among them to determine third place. Observe that if $a_i$ is second place, then they beat $i$ players in the first tournament, $(k-1)-i$ players in the second tournament while they were the current contender, and at most $1$ contender in their first game of the second tournament. (If $a_0$ wins the second tournament, then this contender does not appear in the third tournament, saving one game. This is used in the $n=2^k+1$ case below.) This gives at most $i+(k-1-i)+1=k$ candidates for third place, so at most $k-1$ games are played to determine it.

In total, at most

$(n-1)+(k-1)+(k-1)=n+k+k-3=n+\lceil\log_2n\rceil+\lceil\log_2(n-1)\rceil-3$

games are played.

Suppose we add Alice so that $n=2^k+1$. Modifying the above method:

First, Alice plays the winner after the first tournament. In the worst case, she loses. Then, she plays $a_0$ before the second tournament. In the worst case, she loses. If $a_0$ wins the second tournament, then Alice must play a game in the third tournament, but this just offsets the one game savings mentioned earlier. Then only $2$ games must be added to the $2^k+2k-3$ games from above to include Alice: $$(2^k+2k-3)+2=(2^k+1)+(k+1)+k-3=n+\lceil\log_2n\rceil+\lceil\log_2(n-1)\rceil-3.$$

$\endgroup$
  • 1
    $\begingroup$ What is $\lg$? Is that $\log$ or (what I presume to be) $\ln=\log_e$? Edit: this was a dumb question. I should have just looked at the inequality and intuitively figured out what $\lg$ was. My eye just first caught that notation, is all. $\endgroup$ – Mr Pie Apr 2 at 7:39
  • 1
    $\begingroup$ Interesting! When I can vote in at least $16$ hours, I will head to this answer ;) $\endgroup$ – Mr Pie Apr 2 at 7:44
  • $\begingroup$ Not excactly the way i found an answer. Worth studying. Stay tuned. Yes, you'll get a bounty too. $\endgroup$ – humn Apr 3 at 22:24
1
$\begingroup$

This is a way more hairy subject than it appears on the surface, so you are not getting a puzzle answer, but a real-world one instead.

TL;DR: The given requirements are logically incompatible with the statement "round-robin tournaments can end in a draw", so OP's question doesn't have a clear correct answer.

The difficulties arise, because you need a model for the thing you are measuring in the competitors, before you can judge whether a tournament system correctly measures that model.

If you keep to a very simple model (each player has one hidden number called "tournament performance for this tournament"; bigger number always wins), then it makes sense to run a (continued) knock-out tournament. To find out the 2nd place, have the players directly knocked out by the winner play another knockout, and then the players knocked out by the winner and second place compete for the third place.


However, you go on to say "Round-robin can result in inconclusive loops." Using the assumption of one hidden variable from above (which happens to be necessary for it being possible to fulfil the requirements), no, it absolutely cannot. Natural numbers don't go in loops.

This means that your model must be something else, like "one hidden variable (tournament performance), times a random fuzz factor (performance in a given match)". This seems quite a reasonable model, by the way.

The main problem with this assumption is that a knock-out tournament no longer makes sense. That's because the fuzz factor affects the results so that they aren't necessarily transitive anymore: if player A beats player B, and B beats C, that doesn't guarantee that A would have also won against C. This means, especially if the fuzz factor is relatively large, that there's no particular reason for you to declare A better than C without giving C the chance to play against A.

If you then add possible directional bias to the model (A's defensive style is good against B's aggressive style, but often loses to C's balanced style, which in turn is at a disadvantage against B), your chop suey is ready to serve.


Depending on your model, then, a different tournament format is the best choice for you. A round-robin is often the desired one, since it measures "everything" once, and being perfectly symmetrical, it doesn't introduce any pairing bias whatsoever. Also, whatever your model, having everyone play against everyone else will give you very good data on which to base the ranking.

If a round-robin ends up producing a tie (necessarily involving a result loop of one kind or another), this is not a symptom of the tournament system being bad, it's a symptom of the players showing equal performance in the bestest and fairest performance test known to man.

In this case, the correct conclusion is to reward tied players equally. You could also do tie breakers (rematches) if you want to, but keep in mind that if you demand a result that is different from what the round-robin gave you, you are searching for differences at where there weren't any.


For the particularly mentioned purpose of finding out the top three participants, I'd probably go with a Double Knock-out system; it strikes a nice balance, giving a very credible winner (anyone that lost twice didn't deserve to be the champion) without tie breaks, a very reasonable guess for second place, and a good candidate for the third place (especially if the tournament is reasonably seeded), while still being reasonably simple to organise.


Full disclosure: I may have some overly strong opinions on tournament systems, having battled (for and against) some international organisations and their rules commissions on these very issue for several years, so please take everything I say with a very unhealthy dose of Himalayan rock salt, and only do what makes sense to you yourself.

$\endgroup$
  • 1
    $\begingroup$ I interpreted the question as asking for a tournament where the results determine a clear first, second, and third place. In this regard, single-elimination only succeeds in determining a clear first place, and round-robin may fail to produce clear winners because of "inconclusive loops." $\endgroup$ – noedne Apr 2 at 13:34
  • 1
    $\begingroup$ @noedne almost this whole answer is about how those two statements ("single-elimination finds a clear first place" and "round-robin may produce a loop") are mutually exclusive. If you believe one, logically you must disbelieve the other. $\endgroup$ – Bass Apr 2 at 13:49
  • $\begingroup$ "If a round-robin ends up producing a tie (necessarily involving a result loop of one kind or another)...." "A double knockout system gives a very credible winner." Aren't these similar statements? $\endgroup$ – noedne Apr 2 at 14:01
  • $\begingroup$ @noedne I must be a bit dense, but I cannot make heads or tails about your last comment. Similar to what? $\endgroup$ – Bass Apr 2 at 14:37
  • $\begingroup$ Similar to "single-elimination finds a clear first place" and "round-robin may produce a loop" that you say are mutually exclusive. $\endgroup$ – noedne Apr 2 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.