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 ---- Election-methods mailing list - see http://electorama.com/em for list info
