[EM] Floyd-Warshall algorithm - variations

[Markus Schulze]

Dear Ernest,

you wrote (20 Dec 2003):
> Ah, okay, that was hard for me to deduce from the original algorithm, 
> where it seemed like you were primarily calculating margins.

In Section 4 of my paper, I use margins. In Appendix 3 of my paper,
I use absolute numbers of votes for the winner. The pseudo-code for
the Dijkstra algorithm that I posted to you yesterday corresponds
to the algorithm in Appendix 3.

You wrote (20 Dec 2003):
> My implementation of this for object-oriented Dijkstra (using real
> Python code this time) is at the end.    The relevant section is here,
> where 'rstrength', or relative strength, is used for the margin:

Sorry, but I don't know Python.

You wrote (20 Dec 2003):
> Are you asserting that there is no deterministic tie-breaking algorithm
> that resists clones?  Does this mean that we really do need to keep
> track of all the actual ballots, and not just the Condorcet matrix?

I chose the "random ballot" tie-breaking strategy in such a manner that
the proofs that the proposed method satisfies Pareto, monotonicity,
independence from clones, etc. are as simple as possible. I am not
linked to this tie-breaking strategy.

Another possible tie-breaking strategy is to calculate a complete
ranking of all candidates (and not only of the potential winners)
with Tideman's ranked pairs method and to choose that potential
winner that is ranked highest in this ranking. With this tie-breaking
strategy none of the desirable properties of my beatpath method gets
lost.

However, for every anonymous and neutral single-winner election method
there are situations where this method doesn't find a unique winner.
Random ballot is sometimes the only way to get a winner without
having to violate independence of clones. But I don't think that
it is such a big problem when independence of clones is violated in
these extreme cases.

Markus Schulze