[EM] Re: lotteries

[Ted Stern]

On 5 Jan 2005 at 15:15 PST, Forest Simmons wrote:
>
        snip
>
> Ted Stern gets the credit for finding an efficient sprucing up procedure 
> by finding an existing clone collapsing algorithm in the literature.

        another snip
>
> Here is Lottery in the form of Spruced Up Random Ballot:
>
> 1. Cross out strategically dominated candidates (so that only Dutta 
> candidates remain).  This ensures the satisfaction of the Generalized 
> Condorcet Criterion. [If we were doing Random Ballot Dutta, our final step 
> would be to elect the highest reamining candidate on a randomly drawn 
> ballot.]
>
> 2. Collapse all remaining proper beat clone sets.  This makes the method 
> beat clone free, which implies clone free. [Ted Stern has found an 
> efficient way of doing this clone collapsing step.]

What I did was ask a well-published expert in numerical linear algebra who
works at my company.  He picked a book out of his bookcase and showed me the
technique.  It's a fast algorithm for determining the Block Tridiagonal form
of a matrix with non-zero diagonal.  The algorithm is applied to the symbolic
form of the pairwise matrix.  Construct M such that M(i,j) is 

     1      if   i != j and candidate i defeats candidate j
     0      if   i != j and candidate j defeats candidate i
     1      if   i == j

>
> 3.  If the result is a single candidate, we're done.  Otherwise it is a 
> (collapsed) cyclical clone set.  Pick a member of this cycle at random. 
> If that member is a single candidate, we're done.  Otherwise, it is a 
> (collapsed) cyclical clone set. Continue in this manner until a candidate 
> is chosen.
>

The block tridiagonalization method is Tarjan's algorithm, described in
"Direct Methods for Sparse Matrices", I. S. Duff, A. M. Erisman and
J. K. Reid. Oxford University Press, 1986.  Chapter 6, I believe.

You can find the original article here:

    http://portal.acm.org/citation.cfm?id=355785

but since it was printed in 1978 it is probably in your nearest university's
math library.  If not, you can request either the ACM issue or the book via
interlibrary loan.  I would recommend the Duff/Erisman/Reid book over the
original article.

Fortran (f77) code for the algorithm, in sparse matrix format, is on netlib,
but probably not readable by many of the readers here:

    http://www.netlib.org/toms/529

The following site has slides describing reordering schemes in the context of
sparse matrix solvers and contains a brief description of Tarjan's algorithm.

    http://www.csit.fsu.edu/~gallivan/courses/NLA2/S04/set4.pdf

Ted
-- 
Send real replies to
	ted stern at u dot washington dot edu

Frango ut patefaciam -- I break that I may reveal