Is River O(n^2 log n) worst case?
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?
Hi Kristofer,
Le jeudi 23 janvier 2020 à 17:19:01 UTC−6, Kristofer Munsterhjelm km_elmet@t-online.de 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 tothe 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, torepresent the magnitude of the vote on each side) but given that the River graph willbe directed (with a clear root) I wonder if it must be different, or if that is just a cosmeticissue.
Kevin
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.