[EM] "Margins Sorted Approval" poll candidate

[Joshua Boehme]

A method that picks a Hamiltonian path has, in some sense, only reversed the minimal number of edges to produce a directed acyclic graph. If you have an ordering that's not a Hamiltonian path, somewhere you have a strict pairwise loser directly ahead of a winner and you can reverse them without affecting any other relative comparisons. That means it reversed an edge when it didn't have to.

Split Cycle is a good example of a method that splits more edges than are strictly necessary to produce a DAG. Consider this margin matrix (example 4.6 in the Split Cycle paper; entries are row candidate over column candidate):

     A   B  C  D
A   0  12  4 -6
B -12   0 -2 10
C  -4   2  0  8
D   6 -10 -8  0

There are three distinct cycles: ABDA, ACBDA, ACDA. Split Cycle breaks the DA, CB, and AC edges respectively, leaving A and C as the members of the winning set. However, that breaks more edges than are necessary! Here are the minimal sets of edges you need to remove (I think these are called "minimum feedback arc sets" in graph theory)...

1: AB and AC
2: AC and BD
3: AB, CB, and CD
4: BD and CD
5: DA

So it chose #5, but also broke two extra edges. #5 by itself leaves A as the unique winner


I suspect you probably can't modify Split Cycle to only break necessary edges compromising the weak forms of participation that it satisfies. As it stands, the resolution of an ABCA cycle depends only on the three edges in question and nothing else.


On 4/22/24 21:19, Closed Limelike Curves wrote:
> Oh, hmm, that sounds like Split-Cycle maybe?
> 
> On Mon, Apr 22, 2024 at 1:16 PM Joshua Boehme <joshua.p.boehme at gmail.com>
> wrote:
> 
>>
>> A graph theorist would call it a Hamiltonian path over the tournament
>> graph (provided that pairwise ties are drawn as edges in both directions
>> instead of the usual no-edge convention). That isn't standard terminology
>> when talking about voting methods, though.
>>
>>
>> One nice thing about Hamiltonian-path/beat-chain methods -- which also
>> include Ranked Pairs and Kemeny-Young -- is that they automatically satisfy
>> Smith. Moreover, they do so successively: first come all Smith set members,
>> then the members of the Smith set over the remaining candidates, then...