On 10/01/2012 04:05 AM, robert bristow-johnson wrote:
On 9/30/12 6:13 PM, Juho Laatu wrote:
On 30.9.2012, at 15.41, Kristofer Munsterhjelm wrote:
As far as intrinsically Condorcet methods go, Ranked Pairs feels
simple to me. The only tricky part is the indirect nature of the
"unless it contradicts what you already affirmed" step.
yeah, it's not immediately obvious to me how i would code up Ranked Pairs.
Easy to code is not necessarily the same thing as easy to understand.
Schulze is rather easy to code once you know the trick (use a suitable
adaptation of the Floyd-Warshall algorithm), but it's not very easy to
understand without going into detail about beatpaths.
As for how to code Ranked Pairs, a simple way is to have a depth-first
(or breadth-first) search routine that tries to go from, say, A to B
when you want to affirm B to A. If it's possible to go from A to B, then
you can't affirm B to A, so you skip it, otherwise you affirm B to A and
go to the next one.
More complex structures can lower the time complexity to O(n^3), I
think. For River, there are even more clever tricks (that I don't recall
at the moment) to speed it up further by observing that one doesn't need
a directional graph for the candidates already locked in.
----
Election-Methods mailing list - see http://electorama.com/em for list info
