[EM] Ideas for Schulze tie-breaking

[Kristofer Munsterhjelm]

Like minmax, Schulze sometimes has a lot of ties, particularly for
elections with few voters. But perhaps this way could work to break ties
in a consistent way:

Let p[A, B] be the strength of the strongest beatpath going from A to B.

Now do ext-Minmax on the p matrix. This is minmax (i.e. A's score is A's
weakest pairwise contest vs B), but ties are broken by looking at second
weakest pairwise contests, third weakest, etc.

Since there always exists a candidate A who is the "Condorcet winner"
according to p, and this is the same as the Schulze winner, and both
Minmax and ext-Minmax pass Condorcet, this method should agree with
Schulze when there are no ties.

But do we lose any criteria from this? I don't know; it's just a thought
that occurred to me as a way to make ext-Minmax more Schulze-like.
Possibly there exist situations where there's a tie according to
Schulze, and this breaks the tie in a way that (say) depends on clones;
but I'm not sure how to construct such an example.

Another possible drawback is that the social order may suffer, because
minmax doesn't pass Condorcet loser. So it might be that the social
ranking is A>B>C>D by Schulze, and this is strict (A has 3 strong
beatpaths, B has 2, C has 1, D has none), but D's weakest beatpath is
stronger than C's; and then the ext-Minmax modification returns a
different social order even though there are no ties at any point.

This might point to the idea being not entirely defensible. One could,
of course, only break the ties that exist by ext-Minmax, but that feels
rather like a hack.

Perhaps it would be doable to augment Floyd-Warshall to maximize the
leximin of the beatpath instead of just its minimum - among the paths
with the strongest weakest link, find the one with the strongest
second-weakest link, etc. Then comparing the full vectors of defeats
along the beatpath thus recovered could resolve ties in a way more
consistent with the Schulze method itself.

I'm still only working by intuition, though; I haven't rigorously
checked any of these ideas.

-km