[EM] Re: Equivalent defeat strength for Approval Sorted Margins / Approval Margins

[Araucaria Araucana]

On  5 Apr 2005 at 11:12 UTC-0700, Forest Simmons wrote:
> Ted,
>  
> I've been working on that, but the answer is not yet clear.
>  
> Part of the problem is that only pairs that are currently adjacent in
> the list are considered for swapping (the equivalent of firming up the
> defeat ).
>  
> So if at some time the current list order is A>B>C>D>E>F, and (A,B) is
> the out-of-order adjacent pair with the smallest approval difference
> (a-b), while the approval difference (b-d) is even smaller, the B>A
> defeat would be set in stone before (or ultimately instead of?) the
> D>B defeat.
>  
> Whether this ultimately causes a problem, I do not know.  Forest

You're right, Ranked Pairs with defeat strength in increasing order of
approval margin would not be equivalent.  We've got to get the total
approval ordering in there somehow.

Are you familiar with Minimum Degree reordering?  It's a sparse direct
solver (AKA Gaussian elimination) method, intended to reduce matrix
fill-in.  ASM is somehow reminiscent.  Here's one reference:

http://www.mathworks.com/access/helpdesk/help/techdoc/math/sparse17.html

I should note that MD is neither the sparsest or most stable LU
decomposition method.  Most commercial sparse solvers use METIS
instead:

http://www-users.cs.umn.edu/~karypis/metis/metis/

Of course we're not interested in fill-in here -- the pairwise array
with defeated scores set to zer always has density (N+1)/(2N), not
sparse at all.  But in some sense we're also looking for the most
stable reordering, with no zeroes on the upper off-diagonal.

-- 
araucaria dot araucana at gmail dot com