[EM] question about Schulze example (A,B,M1,M2)

[Kristofer Munsterhjelm]

capologist wrote:
>> See section 5 of my paper:
> 
> Not quite what I'm looking for. That section describes a
> non-deterministic method for generating a complete linear order.
> 
> I don't require a linear order. I'm OK with a partial ordering.
> 
> I'm looking for a deterministic method for generating a "picture"
> (partial ordering) of how the voters, in aggregate, feel about the
> preferability of the available options.  (What we're doing at this
> stage is more akin to a poll than an election.)  It seems to me that
> the A>(M1,M2)>B ordering does not reflect the voters' preferences as
> well as the A>M1>M2>B ordering.
> 
> I'm open to the possibility that the Schulze method is the wrong tool
> for this purpose.
> 
> I'm also open to the possibility that the Schulze method is the right
> tool for this purpose, and is serving that purpose effectively in
> this scenario. That would imply that, in some meaningful sense,
> A>(M1,M2)>B is at least as good or a better picture of the voters'
> preferences than A>M1>M2>B. This is counterintuitive but perhaps it
> makes sense and I don't yet understand why.
> 
> I think the latter is likely the case. M1 and M2 are beatpath tied.
> What's going on in this example is that there is a beatpath of
> strength at least 2 (using margins) from every candidate to every
> candidate. Since M1's pairwise win over M2 is not stronger than this
> value, it has no effect. Is this a case of a meaningful but weak
> signal being lost in "noise"? Or is the strength-2 cycle itself a
> meaningful signal that, for good if inscrutable reason, overrides the
> weak preference between the clones?

The Schulze method works in a manner that's akin to shortest path 
(strongest beatpath). Now it might be that the shortest path to two 
different places from all other places being considered are the same, 
but if you consider every possible path, not just the shortest ones, 
it's possible to get to one of the places more quickly than the other.

The analogy in Schulze is that even though the strongest beatpaths don't 
discriminate between M1 and M2, other non-strongest beatpaths might. 
Schulze, however, doesn't take these into consideration.

There are two reasons for this. First, I think, is to make it more 
robust to noise and strategy. The second is that Schulze is intended to 
be somewhat of "the closest method to minmax that we can have while also 
having Schwartz and independence of clones". Minmax also uses a similar 
"best worst" (strongest/shortest) strategy, and so scores M1 = M2.

I imagine it would be possible to extend Schulze just as I have extended 
Minmax. My extended Minmax breaks ties (best worst defeat) by 
considering next-to-worst, then next-to-next-to-worst, and so on. The 
problem is that doing this with Schulze would involve finding not just 
the strongest beatpath, but the next-to-strongest, etc, down to the 
weakest; and if strongest beatpath is similar enough to shortest path, 
then weakest beatpath is similar to longest path, which is NP-hard as an 
optimization problem and NP-complete as a decision problem.

So, to sum all of that up: Schulze ties M1 and M2 because it 
deliberately only considers the strongest complaints against putting 
candidates at a certain position. It does this to be similar to Minmax, 
which is like that (as far as I understand) to deter strategy. If you 
want to break ties, you could make an extended Schulze (but it could run 
for a very long time), or you could (for instance) break them in Ranked 
Pairs order.

A Ranked Pairs tiebreak is fully deterministic. Sort the victories in 
order of magnitude, then if M1 > M2 comes before M2 > M1, set M1 above 
M2. It may feel hackish to transplant parts of Ranked Pairs into 
Schulze, however.