Hi Forest, Summarizing: "sprucing up" is essentially a combination of short beatpath + clone reduction. Or am I missing something?
I have a question about the first stage, eliminating covered candidates: On 21 Dec 2004 at 16:09 PST, Forest Simmons wrote: > 1. Eliminate covered candidates until each remaining candidate has a short > (length one or two) beat path to each of the other remaining candidates. > [...] > > In step one form a matrix M whose (i,j) element is one if candidate i > beats candidate j pairwise (as well as in the case if i=j), but is zero > otherwise. Then form the matrix A=M^2. > > The (k,n) element of A will be zero if and only if there is no short > beatpath from candidate k to candidate n, which means that candidate k is > not among the uncovered candidates. Accordingly, we eliminate row k and > column k from the matrix M. After taking care of all of the rows of A that > have zero entries in this manner, we repeat the procedure with the new > matrix M', and new matrix A', etc. until each remaining candidate has a > short beatpath to each of the other remaining candidates, if there is more > than one candidate left. For 4 candidate elections, there are 64 combinations of possible defeats, ignoring ranking. By A-B symmetry you can look at just the 32 cases in which A defeats B ("AB", to use Jobst Heitzig's notation), and of those, only 8 lead to 4 candidate cycles. Take for example the (unordered) case AB BC CD DA DB AC which has cycles A>B>C>D>A, etc. This implies that M equals 0 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 Then M^2 = 0 0 1 1 0 0 0 1 1 1 0 0 0 1 2 0 According to your description above, I should be able to eliminate A because it doesn't have a length-2 path to B, even though there is a length-1 path from A to B! Don't you mean to consider the matrix M + M^2 instead? In this case, M + M^2 equals 0 1 2 1 0 0 1 1 1 1 0 1 1 2 2 0 B is the only candidate that has a zero off-diagonal entry, (2,1), implying that there is no length 1 or length 2 beatpath to A. So you could eliminate B and would be reduced to a 3 candidate case. I think it is possible to show that every 4-candidate cycle can be reduced to 3 candidates this way. Can you verify this? This would take care of all RP/BP/River differences in the 4 candidate case. Five candidates might be tougher, but you get the general idea, right? You could determine which sets of 10 cyclic defeats are short-beatpath irreducible or reduce to 4 candidates, and then examine only the ranked permutations of those sets. Sounds like a job for Jobst ... Ted -- Send real replies to ted stern at u dot washington dot edu Frango ut patefaciam -- I break that I may reveal ---- Election-methods mailing list - see http://electorama.com/em for list info