[EM] Is River O(n^2 log n) worst case?

[Kristofer Munsterhjelm]

On 24/01/2020 03.22, Kevin Venzke wrote:

>>(Here I thought I had found a cloneproof O(n^2) Condorcet method. But I
>>found out it's *just* in excess of that, because of that log factor...)
>>
>>... actually, isn't this just Kruskal's algorithm?
> 
> It seems similar (if we say there are two edges between each pair of 
> vertices, to represent the magnitude of the vote on each side) but
> given that the River graph will be directed (with a clear root) I
> wonder if it must be different, or if that is just a cosmetic issue.

(Assuming I'm not wrong,) River treats the directed graph like an
undirected graph with two edges between each vertex pair, and then
constructs a maximal spanning tree based on it.

 From an election perspective, ignoring the direction seems to work
because, in isolation, if (A>B) > (B>A), then A>B gets locked first, and
then B>A would produce a cycle. The only way that can't happen is if
locking A>B would create a cycle or defeat B twice.

There is a directed analog of a minimum (maximum) spanning tree, and
that is the minimum (maximum) arborescence. Edmonds' algorithm finds
that one, and Warren suggested that it could be used as an election
method. He called it Maxtree. I don't know of anyone who has implemented
that method, though, since Edmonds' algorithm is pretty complex.

Some other observations: if River really does create a maximum spanning
tree from the "undirectified" directed graph of the election, then the
algorithm I gave is Kruskal's, and Prim's algorithm will find the
maximum spanning tree in O(n^2). Since both MST algorithms can find
every MST given the proper tiebreaks, that means we can find the River
winner in O(n^2) time, and thus we *do* have a cloneproof Condorcet (and
Smith) method with n^2 time complexity.

And River(wv) should be the same thing as River(PO). With wv, A>B will
be listed before B>A if A>B is stronger than B>A. But that's what would
happen with pairwise opposition too. It doesn't matter to the method
whether B>A is 0 or some positive value less than A>B, because A>B will
be locked first and then B>A can't be locked. (This is just a
consequence of the undirectified graph being, indeed, undirected.)

Come to think of it, the same should hold for Ranked Pairs. RP(PO) is
MAM? Looks like it. That would simplify a description of MAM: just sort
the pairwise contests directly, no need to preprocess them according to wv.