Puzzle:
Suppose there are C candidates (numbered 1,2,...,C) in a rank-order-ballot election,
and it is claimed, for some C×C matrix Z, that a random voter ranks A above B
with probability ZAB.
(Of course, these obey ZAB+ZBA=1 and
ZAB≥0.)
The lesson of parts (e) and (f) of this puzzle seems (vaguely speaking) to be that, with random voting, Condorcet cycles become exceedingly likely to exist in C-candidate elections when C→∞, but only weak cycles are likely. But it remains an open problem to close the substantial gap between the bounds in (e) and (f).
By Warren D. Smith Dec 2009
a. If ZAB=1/2 for all A,B (the "pure coin toss" case) then plainly this Z is realizable; just use random permutations (all equally likely) as votes.
Also, any matrix Z such that ZAB=1 (or 0) if A lies "above" B (or not) in some ordering of the C candidates, is realizable; just make all votes be identical to that ordering.
It will follow from the linear program in (b) – or more simply just by taking a "probabilistic mixture" – that any Z-matrix which is a convex linear combination of Z-matrices each known to be realizable, is realizable.
But any matrix Z containing a "3-cycle of strength>2/3," i.e. if min(Z12,Z23,Z31)>2/3, is unrealizable.
Actually, more generally, you cannot have a K-cycle of strength>(K-1)/K for any K with 3≤K≤C.
One may show that in the case of a 3-cycle a⊃b⊃c⊃a amongst 4 candidates {a,b,c,d} by explicitly writing down the linear program we shall describe below, and solving it. The linear program is (using 4-letter variable names) to maximize s subject toabcd+abdc+acbd+acdb+adbc+adcb+ cabd+cadb+cdab+dabc+dacb+dcab ≥ s+ cdba+cbda+cbad+dcba+dbca+dbac+ bacd+badc+bcda+bcad+bdac+bdca, an optimum solution is s=dbca=cabd=abcd=1/3, and all other variables 0. More generally the maximum min-strength K-cycle arises by making all permutations that order the K cycling candidates in a cyclic permutation of their original order, have equal probabilities, and all other permutations have zero probability. It is not hard to see this is a local-optimum to all tiny perturbations, and since for linear programs local optima are global optima, the proof is complete.
bacd+badc+bcda+bcad+bdac+bdca+ abcd+abdc+adbc+dabc+dbca+dbac ≥ s+ cabd+cadb+cbda+cbad+cdab+cdba+ acbd+acdb+adcb+dacb+dcab+dcba,
cabd+cadb+cbda+cbad+cdab+cdba+ bcda+bcad+bdca+dcab+dcba+dbca ≥ s+ abcd+abdc+acbd+acdb+adbc+adcb+ bacd+badc+bdac+dabc+dacb+dbac,
abcd+abdc+acbd+acdb+adbc+adcb+ bacd+badc+bcda+bcad+bdac+bdca+ cabd+cadb+cbda+cbad+cdab+cdba+ dabc+dacb+dbca+dbac+dcab+dcba=1
and all 25 variables nonnegative;
We remark that the maximum min-strength of any K-cycle, for all K combined, can be found in "polynomial time" by performing K steps of "breadth first search" in the directed graph with only arcs of strength>s included, and doing outer binary searches on s. We also remark that the existence of majority-preference cycles does not necessarily have anything directly to do with unrealizability, because you can add P times the ordering 1234...C to the mix and (1-P) times C...4321, and as a result you get a pairwise matrix which (if P>>1-P) is highly biased to favor a linear ordering of the candidates – this will "eliminate" all low-strength cycles.
b. Let the probability distribution on C-permutations π be Pπ. (There are C! quantities Pπ in all.) Matrix Z is realizable if and only if the linear program
(where the ZAB are regarded as known and the Pπ's as unknown) has a solution, and any such solution constitutes a realization. Any algorithm for solving linear programs, such as the "simplex method," will do, and indeed will enable finding the "best" realization, namely the one maximizing ∑πPπQπ for any desired provided C!-vector Q of permutation "qualities."
The only problem is that since C! grows very fast with C, this algorithm is slow. It also is a memory-hog.
The above linear program is already in "standard form." It has C! variables and (C-1)C+2 inequality constraints aside from the C! positivities. (An equality x=y is written as two inequalities x≤y and -x≤-y.)
The dual form of this linear program may be found by employing G.B.Dantzig's "duality theorem" for linear programming.
G.B.Dantzig: Linear Programming and Extensions, Princeton University Press 1963.
It has (C-1)C/2+1 variables, call them W and YAB with 1≤A<B≤C. It is
The dual problem is "bounded" (i.e. the quantity being minimized cannot be made arbitrarily hugely negative) if and only if there is a solution to the primal problem, i.e. if and only if Z is realizable.
c. It is a well known NP-complete problem ("optimum linear ordering," proved NP-complete by R.M.Karp in one of the first NP-completeness papers) to find the "best ordering" of the C coordinates such that ∑1≤A<B≤CMAB is maximized, where M is a given C×C matrix. From that it follows that, if all the Qπ are equal, that it is NP-complete even to decide, given a set of dual variables (W and the YAB) whether they violate a constraint! This suggests the conjecture that our realizability decision problem is NP-hard, and there is no polynomial time decision-algorithm. On the positive side, it also proves (using either the "ellipsoid algorithm" or "simplex algorithm" with a violated-constraint-finder constructed from an exhaustive searcher) that this problem lies in PSPACE.
Probably, however, there are many interesting theorems (please find them!) showing that various easily-identifiable classes of Z-matrices are or or not realizable, and yielding permutation random-generation algorithms in the former case. We shall find some ourselves in parts (e) and (f).
d. An inefficient (but it works) random generation algorithm is to solve the primal linear program, then generate each permutation π with probability Pπ.
e.
If the Z-matrix is close enough to the all-coin-toss case then I can prove it
is realizable and construct an efficient random generation algorithm.
To keep the description simple let us assume C is even.
As is well known to those who supervise round robin chess tournaments,
there are known ways, for any even C, to split the (C-1)C/2 games among C players into
C-1 "rounds" each consisting of C/2 games among disjoint pairs of players.
Let one of those rounds be candidate#1 vs candidate#2, 3 vs 4, 5 vs 6, etc.
If we simply generate a random permutation which is of the form
[12][34][56]... with probability 1/2 and
...[56][34][12] with probability 1/2, where by [AB] is meant "either AB or BA,
with probability
That solution arose essentially from transforming Stearns' solution to puzzle 28 to make it apply to the present problem. A more powerful solution arises from doing the same transformation of Erdös and Moser's asymptotically-better solution to puzzle 28. This shows every Z-matrix with the property that each entry is within ±O(logC/C) of 1/2, is realizable. It also shows a polynomial-time random-generator exists that demonstrates that Z's realizability – although it remains an open problem to find that generator efficiently (just because something exists, does not mean it is easy to find starting from Z; Erdös and Moser showed their graph-decomposition existed but did not provide an efficient algorithm to find it; does one exist?).
Actually, we can argue for any realizable Z there always is a polytime random generator (which may not be easy to find) because you can just use the tight constraints in the linear program, to get a poly-size set of simple generators such that the desired Z is a probability-mixture of them.
f.
One might conjecture, though, that all these results are very weak and ZAB
being
within ±0.01 of 1/2 suffices, no matter how large C is, for realizability.
Surprisingly, that is not so, and the O(logC/C) bound from part (e) cannot be
improved to
Let ε be any arbitrarily small positive constant. The proof idea is to consider Z-matrices that arise from using random ± signs in ZAB=1/2±jC2ε-0.5 for some sufficiently-large constant j, when 1≤A<B≤C.
We then consider the statistics of random numbers and the LP-dual formulation from part (b) [using all Qπ=1]. Let Y be (-k) times a matrix of the same random signs as were used to construct Z. This will cause the quantity being minimized in the LP-dual formulation, to become unboundedly hugely negative, as we take k→∞. Specifically, the sum in that expression almost surely (meaning, with probability→1 when C→∞) drops proportionally to -kjC1.5+2ε. One can argue from the statistics of random bits (even considering the "worst" C-permutation π among the C! possibilities) – specifically "Hoeffding's inequality" – that the probability is high (i.e. goes to 1 when C→∞) that none of the C! inequality constraints will be violated, provided we employ W=kC1.5+ε.
W.D.Smith: Tail bounds for sums of independent random variables, March 2005, available online as paper #85 at /WarrenSmithPages/homepage/works.html.
This value of W rises slowly enough when C→∞ that the quantity being minimized still goes to -∞. Hence with probability→1 the dual LP is unbounded and hence the Z-matrix unrealizable.
Q.E.D.
(Incidentally the same argument works if instead of random ± "coin tosses," we employ random normal "noise.")
Another interesting related problem is to decide whether the pairwise defeat probabilities ZAB are realizable by some set of C different K-faced "dice." A "die" means a (perhaps nonuniform) probability distribution on any fixed set of K distinct real values; die A will "defeat" (i.e. roll a higher value than) die B with probability ZAB. (See puzzle #6 and #67 about "intransitive dice.")
Such dice-realizability happens if and only if the following quadratic matrix equation:
supplemented by the following linear equalities and inequalities:
has a real-matrix solution P. Here P is a C×K matrix (the "dice probabilities"), PT is its transpose (which is K×C); Q is the constant K×K matrix such that QYX=1 if Y>X, =1/2 if X=Y, and =0 if X>Y; and the two all-1's vectors are K-long and C-long respectively.
This is not the same question because, e.g, it is known that no 3-cycle of strength>(√5-1)/2≈0.61803 is realizable in this dice-sense, whereas a 3-cycle of strength 2/3≈0.66667 is realizable in the original sense. In other words, dice-realizability⇒realizability but the reverse implication does not hold.
Dice-realizability is an algorithmically-decidable question ("existential theory of the reals," A.Tarski & successors). Indeed, it lies in PSPACE (since ETR does). But again, it is a totally open question how difficult this decision problem is. It's pretty unusual to have this relationship between a linear program and a quadratic matrix problem like this.
There seems to be a quite-simple iterative algorithm, however, for solving this provided one starts from a good enough initial guess. The idea is that a small additive perturbation of P causes a linear change in the left hand side of every equation and inequality (since we can neglect the quadratic term). We solve this linear program for the right perturbation, apply it, and continue on. The linear system is actually of special form – a "Sylvester matrix equation" – which means it can be solved especially fast. One could simply try this starting from some heuristically generated initial guesses; if we succeed in converging to a solution, then great, we have a random generator: simply "roll the C dice" defined by our solution to get one value for each candidate; then sort the candidates (breaking ties randomly) by their dice-values.