[EM] Ranked pairs summable?

[Kristofer Munsterhjelm]

On 14/02/2020 21.26, Kevin Venzke wrote:
> This issue makes me wonder, between these approaches:
> 1. Resolve ALL legal ways of forming the hierarchy for RP and declare
> a tie among all possible victors.
> 2. Same as #1 but with River.
> 3. Resolve Schulze, without handling a tie in the outcome.
> 
> Do we expect differences in decisiveness? My hunch is yes... River
> admits fewer contests than RP so fewer ties can have an effect. For
> Schulze I'm not sure. It may be just an imaginary advantage, that the
> Schulze beatpath algorithm doesn't have to resolve tied contests
> mid-evaluation. On the other hand, maybe the defeat locking process
> (with the effect of dropping out some contests) has more potential to
> disrupt the outcome than exists in Schulze.

Unfortunately, determining whether some candidate X can be made the
winner of Ranked Pairs by breaking ties a particular way is NP-complete:
https://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/download/5018/5461


Schulze does have a fairly high tie rate because it's based on Minmax,
which does tie a lot in small elections. I'm reminded of my Ext-Minmax
tiebreaker. The Ext-Minmax winner is the candidate whose minimal victory
is the greatest. In the case of ties, look at the next-to-minimal
victory, then the third-to-minimal, etc.

I've been thinking that there must be some way of applying the same
logic to Schulze, but I haven't been able to find a good generalization.
It might be easier to do so to the CSSD formulation of Schulze. The CSSD
formulation is this:

1. Calculate the Schwartz set based only on undropped defeats.
2. If there are no defeats among the members of that set then they
(plural in the case of a tie) win and the count ends.
3. Otherwise, drop the weakest defeat among the candidates of that set.
Go to 1.

Perhaps you could break ties in #3 in a somehow analogous way to
Ext-Minmax, e.g. drop the weakest pairwise contest and if there are more
than one with the same strength, drop the X>Y contest where X's next
weakest pairwise contest is weakest, and so on up. But that's just a guess.


And as for River, I've been thinking about a River-ish method that would
simplify the tie problem a lot, and where you could easily declare a tie
among winners. It's related to the observation that running River is
like calculating a maximum spanning tree.

Many of River's properties seem not to depend upon the resulting tree
being a maximum spanning tree, but that it's a maximum bottleneck
spanning tree. A maximum bottleneck spanning tree is one where the
minimum strength is maximized. Every maximum spanning tree is also a
maximum bottleneck spanning tree, but vice versa is not true.

I *think* that River passing independence of strongly dominated
candidates is a consequence of the bottleneck property, but I could be
wrong: I only started thinking about this after writing my last post. In
any case, the directed graph version of a maximum bottleneck spanning
tree is a maximum bottleneck spanning arborescence, and there are
algorithms for calculating the MBSA with the provision that the
arborescence has to grow from a certain root. The simple interpretation
of such a root is that the root node is the candidate who remains
undefeated, i.e. the winner.

So all you'd have to do to implement this new method (Bottleneck River
or what you might call it) is to run Tarjan's algorithm with each
candidate as root in turn. For each candidate you get a different tree.
The candidate whose tree has the maximal minimal locked edge weight
(locked victory) is the winner, and if there's more than one, you can
either break ties by considering the next-to-minimal edge weight, or
just use a coin toss (or whatever).

Tarjan's algorithm is here:
https://en.wikipedia.org/wiki/Minimum_bottleneck_spanning_tree#Gabow_and_Tarjan_algorithm_for_MBSA
Note that it's specified in terms of a minimum bottleneck spanning
arborescence: you can go from maximum to minimum by just turning all the
victories negative and adding the total number of voters (and then the
winner is the candidate with the minimal maximal edge weight).

This pretty much kills all the elegance of the River method, though.