[EM] Election-methods digest, Vol 1 #388 - 7 msgs

[Markus Schulze]

Dear Mike,

you wrote (20 Dec 2003):
> What started this discussion was when Markus said that my BeatpathWinner
> algorithm wouldn't work, because it isn't the Floyd algorithm, whatever
> that is.

Craig Carey claimed that my implementation of my method doesn't work
(presumably because it makes only one pass through the triple-loop).
I explained to Craig that it is true that when I had considered the
possible short cuts in that order that has been proposed by you then
my implementation would not have worked. But it has been proven by
Floyd that when the possible short cuts are considered in that very
special order that is used in my paper then it is guaranteed that one
pass through the triple-loop is sufficient to find all strongest paths.

******

You wrote (28 Feb 2001):
> This is the Floyd algorithm for making an array of greatest beatpath
> magnitudes between each pair of options:
>
> 1.Have a 2-dimensional array of defeat magnitudes between the pairs
> of options. Have 2 copies of that, one called defeats(i,j), and the
> other called beatpaths(i,j).
>
> 2.In both arrays, if i beats j, then the ij element is equal to the
> magnitude of i's defeat of j. If j beats i, then the ij element is
> zero. "ij" refers to the ij element of the beatpath(i,j) array.
>
> 3.For every 3-option permuation (i,j,k) that can be taken from the
> entire option set: If min(ij,jk) > ik then write min(ij,jk) to replace
> ij at the "ij" place in the beatpath(i,j) array.
>
> 4. Repeat #3 till that repetition doesn't change any of the entries
> in the beatpath(i,j) array.
>
> [end of greatest beatpath magnitude algorithm]

You wrote (17 Dec 2003):
> I re-emphasize that I didn't get our strongest beatpaths algorithm from
> you [= Markus] or Floyd, or anyone but Steve Eppley, who suggested it.

If you really got your strongest beatpaths algorithm from Steve Eppley
and not from Floyd or me then why did you call it "Floyd algorithm"?
I have explained the Floyd algorithm in a private mail (30 April 2000)
to David Catchpole, Blake Cretney, Steve Eppley, Rob Lanphier, Norman Petry,
and you. I don't remember that Steve Eppley called his implementation
"Floyd algorithm". Therefore, I guess that you have got your algorithm
from me, but that you have never understood this algorithm sufficiently
to implement it in such a manner that it has a runtime of O(N^3).

Markus Schulze