Puzzle:
Call an N-player
round-robin tournament "super-bad" if every player A loses pairwise to some other
player, who loses to another,... who loses to player B, i.e. there is a path
of pairwise defeats leading from A to B, for every A and B.
This seems about as bad as things possibly could be (from the
standpoint of determining who should be
the "winner") but we shall see that it is an extremely common state of affairs.
(a)
Prove a tournament is super-bad if and only if each player is a member of
at least one "cycle" of K defeats, for every value of K from 3 to N
simultaneously.
(b)
Assuming each pairwise defeat-or-victory is determined by a coin flip,
find the probability P(N) that an N-node tournament is super-bad.
In particular, compute P(20) accurate to 8 decimals.
(c)
Let us say that a player who either pairwise-defeats,
or "defeats" via a 2-long path, each other player,
has "bragging rights."
In the same probabilistic model as in (b), show that,
with probability tending exponentially toward 1 as N→∞,
every player has bragging rights.
(d)
Show that not only does every player A "defeat" every player B via a 2-hop defeat-path AXB,
indeed this happens (with probability→1 exponentially as N→∞)
for at least N/5 distinct 2-defeat paths.
Further, there are (again with probability→1 exponentially as N→∞)
at least
Answer: John W. Moon, in his lovely book Topics on Tournaments (Holt Rinehart Winston 1968) solves both parts of this exercise early on, e.g. see his page 3. (Note: what we call "super-bad," Moon instead calls by the names "strong," "Hamiltonian," "pancyclic," and "irreducible," all of which are equivalent.) His proof for (a) involves proving a 3-cycle containing any desired player exists (otherwise Moon deduces a contradiction with irreducibility) and then inductively proving it may be expanded by local changes to increase K→K+1. To solve (b), Moon starts with the obvious P(1)=1, P(2)=0, P(3)=1/4 and then deduces the recursion formula
Actually I found Moon's derivation of this formula to be hard to understand; a much easier way is just to note that an n-tournament is reducible if and only if it consists of a t-vertex irreducible "bottom" part, separated by a moat of (n-t)t defeats to a (n-t)-vertex "top" part. That is all you need to know. From this formula we may compute the table of exact rational values
| n | P(n) |
|---|---|
| 3 | 1 |
| 4 | |
| 4 | 3 |
| 8 | |
| 5 | 17 |
| 32 | |
| 6 | 1395 |
| 2048 | |
| 7 | 104843 |
| 131072 | |
| 8 | 230979 |
| 262144 | |
| 9 | 500203817 |
| 536870912 | |
| 10 | 132159805455 |
| 137438953472 |
For large n, P(n) approaches 1 exponentially, as may be seen by considering just a few terms in the recursion formula. We have, for example (accurate to 8 decimals) P(20)=0.99992371.
If we consider n-player tournaments arising as the n×n pairwise-defeat matrices in random rank-order-vote elections with V→∞ voters and n candidates (note: this is not the same thing as Moon's notion of a "random tournament" – different probability distribution), then the probability of pan-cyclicity also approaches 1, as was proven by Colin E. Bell: A random voting graph almost surely has a Hamiltonian cycle when the number of alternatives is large, Econometrica 49,6 (1981) 1597-1603.
Answer (c) comes from S.B.Maurer in his article The king chicken theorems, Mathematics Magazine 53,2 (1980) 67-80. Let B(N) be the probability that every player has bragging rights. Then 1-B(N) is the probability some player does not. Player X does not have bragging rights if there is some player Y who pairwise-beats X, and such that for every player Z who beats Y, Z also beats X. This quantity obeys
(d) Three extensions of Maurer's "king chicken theorem": Essentially the same proof will also show the following. First, each player "defeats" each other via not just one 2-defeat path, but in fact by at least N/5 different such paths (with probability that goes to 1 exponentially as N→∞). That is because, for any given 2-edge path AXB from A to B, the probability is 1/4 that both coin-tosses are defeats. Hence of the N-2 such paths, we expect 1/4 of them to be 2-defeat paths. We however only asked for "at least 1/5" of them. This happens with probability exponentially near 1. This may be shown using standard properties of the binomial distribution to see that at least 1/2-ε of the N-2 possible AX hops are defeats (with probablity exponentially near 1, for any fixed ε>0) and then for each X, at least 1/2-ε of the N-2 possible XB hops are defeats. The exponential factors overwhelm any polynomial(N) factors that might be introduced.
Second, let L=⌊log2N⌋. One also can show that each player "defeats" each other via at least
Third, if the defeats are correlated rather than statistically independent – i.e. A defeating B makes it less likely that B defeats C and more likely that A defeats C (see puzzle #99) – then it can still be possible to establish results of both these sorts, just with weaker constants. To make that clearer, consider the "coin tosses" being of 2:1 biased coins, where each bias's direction is chosen every time to maximally-hurt the validity our arguments. This would still lead to "king chicken theorems" now with at least N/10 distinct 2-defeat AB paths; and using L-long paths but now with L=⌊log3N⌋.
Fourth: finally, as an extra bonus, we point out that with probability→1 as N→∞ every player has "bragging rights" even in Bell's random-voting model, not merely the "random round robin tournament" model. That follows trivially, once you know about puzzle 99.