[EM] Re: Sprucing up MMPO and other methods

[Ted Stern]

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