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

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

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

Kristofer Munsterhjelm-3
The electowiki says that determining the River winner is O(n^3) worst
case, but I think I've found a way to make it n^2 log n.

In River, you have a list like Ranked Pairs, but a new pairwise entry
A>B is only added if both:
        - it produces no cycle
        - B is not already defeated by someone else.

So start River by creating a boolean "already defeated" array of length
equal to the number of candidates, all initialized to false. Also
initialize a disjoint-set structure containing every candidate as a
separate set, and sort the pairwise preferences in order of magnitude.

This takes O(n), O(n) and O(n^2 log n) time respectively.

Then go down the pairwise preference list and for each pairwise victory
A>B, add it if the "already defeated" boolean for B is false and A and B
belong to different sets of the disjoint set structure. If both of these
properties hold, then:
        - Add A>B to the output list
        - Set B's already defeated boolean to true
        - Merge the sets containing A and B.

Determining whether A and B is in the same set takes O(alpha(n)) time,
and determining if the already-defeated boolean is set takes constant
time. The operations that are part of admitting A>B takes constant time,
constant time, and O(alpha(n)) time respectively, where alpha(n) is the
inverse Ackermann function; for all intents and purposes, it's constant.

My idea is that if A and B are in the same set, then either A beats
someone who beats B, or B beats someone who beats A. If it's the former,
then admitting A>B would mean make B twice defeated, which is not
allowed. If it's the latter, then admitting A>B would create a cycle,
which is not allowed either. So, unlike Ranked Pairs, we don't need to
know which is the case, because either situation implies A>B should not
be admitted. So a disjoint set structure suffices.

Finally, the winner is the candidate who is not defeated at the end of
the process. Finding who that is obviously comes out to O(n) due to the
defeat array.

Supposing I'm right, the total runtime comes out to:

O(n^2 log n) for the setup stage
O(n^2 alpha(n)) for the admission stage,

and since log(n) > alpha(n), O(n^2 log n) for the method as a whole.

Does that sound right?

(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?
----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

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

Kevin Venzke
Hi Kristofer,

Le jeudi 23 janvier 2020 à 17:19:01 UTC−6, Kristofer Munsterhjelm <[hidden email]> a écrit :
>My idea is that if A and B are in the same set, then either A beats
>someone who beats B, or B beats someone who beats A. If it's the former,
>then admitting A>B would mean make B twice defeated, which is not
>allowed. If it's the latter, then admitting A>B would create a cycle,
>which is not allowed either. So, unlike Ranked Pairs, we don't need to
>know which is the case, because either situation implies A>B should not
>be admitted. So a disjoint set structure suffices.

This seems right. Every candidate in a set, except one, has a path of losses back to
the one exception. So no defeat between any of these candidates can be admitted.

I can't speak to the O notation...

>(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.

Kevin



----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

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

Kristofer Munsterhjelm-3
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.
----
Election-Methods mailing list - see https://electorama.com/em for list info