Puzzle #28 –
In a ranked-ballot voting system,
(a)
Show that any "tournament" (i.e. configuration of (n-1)n/2 pairwise-beats relationships among
n candidates) is attainable where "A beats B"
when more voters say A>B than B>A in their ballots,
and there are enough voters.
(And let us agree not to allow "ties.")
(b)
Define M(n) to be the minimum number of rank-order-ballot
votes required to create any n-player tournament
in the this way (maximized over all such tournaments; elections with "ties" not permitted).
Then show M(2)=1, M(3)=M(4)=M(5)=M(6)=3, and M(n) is always an odd number, and M(n+1)≥M(n).
(c)
Show M(n)≤2n-1 and M(n)≤n+1.
(d)
Show M(n)≥Cn/lg(n)
for all sufficiently large n,
where lg(X)=log2X,
if C is any constant with 0<C<1/2.
(e)
Show M(n)≤Kn/lg(n)
for all sufficiently large n,
for some positive constant K.
(f)
But what if, to declare that "A beats B," we need, not a mere majority of voters,
but in fact a fraction-f supermajority (for some f=ε+1/2)?
prove then that unattainable tournaments exist (for each ε>0)
and indeed that an unattainable tournament with O(ε-2) players
exists – and not only exists, but in fact a random tournament of that size
is highly likely to be unattainable.
(a) Actually, (a) is an immediate consequence of (c) so I do not need to solve it. But the easiest way to prove (a) alone is to use randomness. That is, have some large number L of ballots that say A>B and order all the other n-2 candidates randomly, and by the "law of averages" the result will be (with high probability) the desired comparison A>B gets a large majority while all the other comparisons are small noise. Do this for every pair-relation you want (i.e. choose the right A and B each time) and make L large enough, and done.
(b) To show M(3)=M(4)=M(5)=3, see puzzle 25 to see that you cannot do it with one ballot since cycles can exist. But you can make a ballot that agrees with the target tournament except on 1, 1, and 3 arcs respectively. (And in the latter case, the 3 "bad" arcs cannot form a cycle.) The bad arcs may then be handled by 2 extra ballots which outweigh the badness by goodness 2:1, and which are structured to cancel out on, i.e. have no effect on, the non-bad arcs. To see M(n) is always odd: If M(n) were even then every pairwise majority would have margin ≥2 (since ties are forbidden) in which case we could delete a vote, a contradiction. To see M(n+1)≥M(n): just remove the extra candidate from all votes. To see M(6)=3 realize from puzzle 21 that any 6-vertex tournament agrees with particular ballot rank-order except on at most 4 arcs – and those 4 arcs cannot include a directed cycle. Then, by exhaustive manual consideration of every possible 4-arc acyclic digraph, realize that these 4 "bad" arcs can be handled by 2 ballots (which award 2 votes toward reversing each bad-arc to goodness, and which have zero effect on every other non-bad arc).
(c) To show M(n)≤2n-1, we take advantage of the well known fact that a round-robin n-player tournament can be played in either n or n-1 parallel rounds (whichever is odd), i.e, each round there are floor(n/2) pairwise contests and at the end every player has played every other exactly once. We are going to get the same effect as any given round of the tournament by using exactly 2 ranked-ballot votes. Namely, if in some round the pairwise-contest results were A>B, C>D, E>F, ..., Y>Z we capture that with the two votes A>B>C>D>E>F>...>Y>Z and Y>Z>...>E>F>C>D>A>B which, note, due to the reversal in the second vote, has an effect on all the other pairwise contests that exactly cancels out to zero. So we've just shown M(n)≤2n or 2n-2, but since we know M(n) is always odd, we know M(n)≤2n-1.
But we can do better. We shall show, constructively, that M(n)≤(the least odd number that is ≥n), i.e. M(n)≤n+1. This slightly improves the upper bound result by Richard Stearns: The voting problem, Amer. Math'l. Monthly 66 (1959) 761-763 while simultanously making it simpler and clearer. The idea is this: in the above solution, why were we using two ballots to handle a single tournament round? Why not 1 ballot? Certainly 1 ballot suffices to convey the needed information, it is just we needed the second ballot to "cancel out" spurious information. So the idea is to get rid of the second ballot and instead get the cancellations we need from the structure of the round robin schedule itself (which we cleverly devise). We shall use the standard "cyclic" method:
This java applet [based on one by Richard A. DeVenezia]
shows how it works for a 9-player round robin tournament (9 rounds required).
[Also if the "bye" artificial player, required when the number of players is odd, is
replaced with a genuine 10th player, then we produce a 10-player 9-round
round-robin tournament schedule.]
Press 'Go' or 'Step' to start rotating the reddish cells clockwise.
If n is odd (n=9 in the demo) this will produce a 9-round schedule, and we handle each round's "game results" in a single ballot in the obvious way, i.e. if the pairings are AB CD EF... we use the ballot AxB>CxD>ExF... etc. where each x is < or > depending onthe desired "game outcome." Of course, this introduces spurious relations such as B>C. But those automatically cancel out due to the dihedral symmetry of the tournament schedule structure. Note the unpaired player each round (who gets a "bye") is just placed at the top of the order every time.
We've described how to handle odd n. To handle even n we simply add an extra artificial (n+1)th "candidate" so we have n (now) odd, and proceed as usual (then at the end, delete the fake candidate from all ballots).
(d) This is just the "information-theoretic bound." That is, it takes (n-1)n/2 bits to specify the pairwise-beats relationships in an n-player tournament, and it takes lg(n!) bits to specify a rank-ordering of n items. Hence M(n)≥(n-1)n/(2lg(n!)) because otherwise there just could not be enough information in the votes to specify the tournament. For example, this shows M(19)≥3.01 so that M(19)≥5. Now Stirling's approximation that lg(n!) is asymptotic to nlg(n) gives M(n)≥Cn/lg(n) for any fixed C<0.5, if n is sufficiently large. Stearns gave the same argument but considered "directed graphs" rather than "tournaments" and hence got MDG(n)≥0.5n/log3n. For example, MDG(9)≥3.08. This causes us to suspect that M(9)≥5. It would be possible to get the exact M(n) value (or merely a strong lower bound) for any particular n and directed graph by solving an n!-variable integer (or linear) program.
(e) A result of this sort was first shown by P.Erdös & L.Moser: On the representation of directed graphs as unions of orderings, Publ. Math. Inst. Hungar. Acad. Sci. = Magyar Tud. Akad. Mat. Kut. Int. Köl. 9 (1964) 125-132; also reprinted pp.79-86 in Paul Erdös: The art of counting, Selected writings (ed. Joel Spencer) MIT Press 1973. They employed the following difficult and profound
Structure Lemma: There exists a (large) constant K (specifically, they proved K<70000) such that any n-node directed graph H can be expressed as the union of L arc-disjoint "bilevel" directed graphs, all of which have the same set of n nodes, where L<Kn/ln(n), and a bilevel digraph consists of the disjoint union of directed graphs GAB that consist of two node-subsets A and B and every arc a→b with a in A and b in B.
They prove the lemma (this will be a very vague description of their proof) by showing that it suffices to keep greedily removing the bilevel digraph inside H with the greatest possible number of arcs (breaking ties arbitrarily). There are two cases, depending on the density of H. If H is dense, i.e. has sufficiently many arcs compared to n2, then it contains a bilevel digraph with order nlog(n) arcs. If H is sparse with A arcs, then it contains a bilevel digraph with order √A arcs. (Actually there are three cases, because there are two dense cases "very dense" and "mildly dense" that they handled by different techniques.) You can prove the dense case by a Ramsey-theoretic argument like in our upper bound on R(n) in our answer to puzzle 27. You can prove the sparse case by a much more straightforward constructive argument involving considering the outvalencies of the vertices. They found it convenient to locate the borderline between the dense and sparse cases at A=n2/ln(n)13.
Once the structure lemma is known, the rest is easy, since we can represent any bilevel graph with just two rank-order ballots A>B>C and C>reversedA>reversedB, to obtain any n-node directed graph structure with at most Kn/ln(n) ballots with (now) K<140,000.
(f) Use the asymptotic understanding of F(n) from puzzle 21 and the realization that random tournaments with high probability satisfy both the asymptotic upper and lower bounds there on the extremal behavior (i.e. for our purposes, random is extremal). Since on the extremal tournaments there, every rank-order ballot yields at least a fraction 1/2-Kn-1/2 of "wrong way" beats-relations for some positive constant K, we conclude that getting every relation in the tournament with a 1/2+ε supermajority is not possible if n>>ε-2.
Miscellaneous extra notes: We can prove M(n+1)≤M(n)+4 by adding these 4 ballots: A>X>B, Areverse>X>Breverse, B>A>X, X>Breverse>Areverse where X is the new node, and A is the set of old nodes above X and B is the set of old nodes below X.
I find it a plausible conjecture that M(7)=3. That is because we can extend the "bilevel digraph" idea of Erdös & Moser as follows: any digraph that is bilevel plus with extra arcs among the As and among the Bs which form acyclic tournaments on disjoint A-subsets and on disjoint B-subsets, can be handled with two ballots. Now we know from puzzle 21 that there are exactly two 7-node tournaments with ≥7 arcs that are not compatible with a single well chosen rank-order ballot, namely QRgraph(7) and the variant graph got by reversing one of its 3-cycles. These are presumably the two most difficult 7-node tournaments to try to represent with 3 ballots. But it turns out in both cases that the 7 bad arcs form an "extended bilevel" digraph. So if these really are the two most difficult 7-node tournaments, since they can be handled with 3 ballots then it would follow that M(7)=3. This conjecture should certainly be within the reach of computers.
One might conjecture that the "greedy with lookahead 2" algorithm [seek the best 2-ballot combination for trying to represent the tournament; use the best of the two and continue on] always does well or perhaps even always succeeds in finding M(n). I have no idea if this conjecture is true but the Erdös-Moser proof demonstrates that it never overestimates M(n) by more than a constant factor.
Known lower and upper bounds (*=my guess at the truth):
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| M(n) | 0 | 0 | 1 | 3 | 3 | 3 | 3 | 3*, 5, or 7 | 3, 5, 7, or 9 | 3, 5*, 7, or 9 |