Cycle Cancellation//Condorcet
-
@cfrank said in Cycle Cancellation//Condorcet:
Does this end up being different from ranked pairs? It has a kind of a co-“ranked pairs” flavor.
Yes, it's slightly different. Very roughly (this isn't actually a correct characterization), you can think of it as being "all the places where Ranked Pairs, River, and Schulze agree" (all three methods return a winner selected by Split Cycle).
TBC, Split-Cycle isn't resolute (it often—and by often I mean like 1% of elections :p—returns multiple winners). So it's more of a way to winnow down the set of potential winners.
@cfrank said in Cycle Cancellation//Condorcet:
Identify the kth weakest edge. If it is part of a cycle, remove it. Otherwise, set k—>k+1.
This is different from Split-Cycle. Actually, I think it's equivalent to Minimax.
-
@lime yes they’re different. I’ll have to understand split cycle.
Still, the concept of shrinking the weakest edges in a common cycle into single nodes is interesting to me just mathematically. If the collapsed nodes are labeled as candidate subsets, you get a new marginal victory graph between over candidate subsets, and applying the same algorithm to these “meta nodes” by aggregating marginal victories between them can eliminate groups of candidates. I don’t know if that’s equivalent to any known method. It is a Condorcet method and satisfies the Condorcet loser criterion, which means it can’t be Minmax.
Smith//Minmax is also somewhat interesting. Is the following equivalent to split cycle voting?:
- If there is a Condorcet winner, elect them.
- If there is a Condorcet loser, remove them, repeating until there are no Condorcet losers.
- Of all edges that belong to cycles, identify those of minimum weight. Create a new tournament without those edges.
- Repeat step (3) on the newest tournament until no cycles remain. Then remove all candidates who are defeated (preserve only the undefeated candidates).
- Return to the original graph including only the undefeated candidates. Repeat from (1).
-
@cfrank said in Cycle Cancellation//Condorcet:
Of all edges that belong to a cycle, identify those of minimum weight. Create a new tournament without those edges.
I think this step needs to be modified slightly to preserve those edges if they're part of another simple cycle where they're not the minimum-weight edge. In other words, we only eliminate an edge if it's the minimum-weight edge in every simple cycle it's a part of. If it's the minimum-weight edge in one cycle, but a very strong edge in another cycle, you don't want to eliminate it.
-
@lime since we would be iterating through the edges that belong to cycles in order of ascending weight, any edge under consideration would automatically be the minimum weight edge of every cycle it is a part of. I think maybe it wasn't clear that equivalently, we can ask for each edge, "Is there some cycle to which this edge belongs?" If yes, it is in the search space of edges, and then we identify the edges in the search space of minimum weight.
Generally, whether an edge (u,v) belongs to a cycle can be checked by removing the edge and doing a (depth-first) search for a path from u to v, since (u,v) belongs to a cycle if and only if such a path exists.
But in any case it's just a concept, similar to Young's method and Dodgson's method, since it tries to perturb the ballot set in a conservative way until a Condorcet winner emerges.
-
Just bumping this again. Since cycle removal works quite cleanly for 3 candidates, you could have a STAR-type method where the top 3 by score go into the run-off instead of 2, and with the top 3, you then remove cycles and find the Condorcet winner.
Alternatively you might want to come up with a cloneproof measure to find the top 3, perhaps similar to the score excess method that I posted here, based on Chris Benham's approval opposition.