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 |
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 |
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 |
Free forum by Nabble | Edit this page |