[EM] Centrifugal Margins -- A Few Additional Notes

[Joshua Boehme]

I realize Centrifugal Margins is not a practical method in general due to the runtime -- barring some unexpected breakthrough in efficiency -- unless you're guaranteed to only ever have a small number of options. There are still a few other things worth noting about it, though.


First, consider the tournament graph, with one slight change from the usual treatment: for head to head ties, we draw edges running both ways. Centrifugal margins will allocate 100% weight to Hamiltonian paths on that graph. Ranked pairs is another example of a method that always selects a Hamiltonian path (and in that case, it's also a stack).

This is a nice property to have, and not just because it automatically gives you Condorcet winner, Condorcet loser, and Smith. Suppose a method selects an ordering X. Every tournament graph has at least one Hamiltonian path, and if X isn't one of them, then the method is inefficient in some sense. That is, there exists an ordering that satisfies all the edges that X does, plus at least one additional edge.


In addition, at least one variant of centrifugal margins provably has a unique solution in every case. Specifically, any variant that also considers the losing tuples as it leximaxes the solution, and not just the non-losing ones, will have a unique solution. For losing edges, you're looking at how much below the actual ballot weight your solution ends up. For example, if A beats B 60-40, the surplus of AB is [solution weight of AB]-60% and the surplus of BA is 40%-[solution weight of BA]. For tuples of 3 or more candidates that's not trivial, and you might not be able to take a losing tuple all the way to zero due to higher-priority tuples. As a reminder, a k-tuple is losing if its ballot weight is less than 1/k!.

Considering the losing tuples is sufficient, but I don't know if it's necessary. Even without it, I don't know of any examples with non-unique solutions. It would be nice to avoid putting the losing tuples in the mix if possible since it makes an already slow method that much slower.