<html><head></head><body><div class="ydpa6468abyahoo-style-wrap" style="font-family:Helvetica Neue, Helvetica, Arial, sans-serif;font-size:16px;"><div></div>
<div dir="ltr" data-setdir="false">Hi Kristofer,</div><div><br></div>
</div><div id="ydpf49da7b2yahoo_quoted_1876581546" class="ydpf49da7b2yahoo_quoted">
<div style="font-family: Helvetica Neue, Helvetica, Arial, sans-serif; color: rgb(38, 40, 42);">
<div style="font-size: 13px;">
Le vendredi 14 février 2020 à 15:38:21 UTC−6, Kristofer Munsterhjelm <km_elmet@t-online.de> a écrit :
</div>
<div style="font-size: 13px;">On 14/02/2020 21.26, Kevin Venzke wrote:<br></div><div><div dir="ltr"><span style="font-size: 13px;">> This issue makes me wonder, between these approaches:</span><br clear="none"><span style="font-size: 13px;">> 1. Resolve ALL legal ways of forming the hierarchy for RP and declare</span><br clear="none"><span style="font-size: 13px;">> a tie among all possible victors.</span><br clear="none"><span style="font-size: 13px;">> 2. Same as #1 but with River.</span><br clear="none"><span style="font-size: 13px;">> 3. Resolve Schulze, without handling a tie in the outcome.</span><br clear="none"><span style="font-size: 13px;">> </span><br clear="none"><span style="font-size: 13px;">> Do we expect differences in decisiveness? My hunch is yes... River</span><br clear="none"><span style="font-size: 13px;">> admits fewer contests than RP so fewer ties can have an effect. For</span><br clear="none"><span style="font-size: 13px;">> Schulze I'm not sure. It may be just an imaginary advantage, that the</span><br clear="none"><span style="font-size: 13px;">> Schulze beatpath algorithm doesn't have to resolve tied contests</span><br clear="none"><span style="font-size: 13px;">> mid-evaluation. On the other hand, maybe the defeat locking process</span><br clear="none"><span style="font-size: 13px;">> (with the effect of dropping out some contests) has more potential to</span><br clear="none"><span style="font-size: 13px;">> disrupt the outcome than exists in Schulze.</span><br clear="none"><br clear="none"><span style="font-size: 13px;">Unfortunately, determining whether some candidate X can be made the</span><br clear="none"><span style="font-size: 13px;">winner of Ranked Pairs by breaking ties a particular way is NP-complete:</span><br clear="none"><a shape="rect" href="https://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/download/5018/5461" style="font-size: 13px;" rel="nofollow" target="_blank">https://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/download/5018/5461</a><br clear="none"><br><font size="3">[Kevin:]</font></div><div dir="ltr"><font size="3">Because you might have to check a high percentage of all the rankings? I guess that's bad, and I certainly wouldn't advocate a method that involves forking the process at each tie in any case. But one could still do a decisiveness comparison.</font></div><div dir="ltr"><font size="3"><br></font></div><div dir="ltr"><font size="3"><br></font></div><div dir="ltr"><span style="font-size: 13px;">Schulze does have a fairly high tie rate because it's based on Minmax,</span><br clear="none"><span style="font-size: 13px;">which does tie a lot in small elections. I'm reminded of my Ext-Minmax</span><br clear="none"><span style="font-size: 13px;">tiebreaker. The Ext-Minmax winner is the candidate whose minimal victory</span><br clear="none"><span style="font-size: 13px;">is the greatest. In the case of ties, look at the next-to-minimal</span><br clear="none"><span style="font-size: 13px;">victory, then the third-to-minimal, etc.</span></div><div dir="ltr"><span style="font-size: 13px;"><br></span></div><div dir="ltr" data-setdir="false"><font size="3"><span><span style="color: rgb(38, 40, 42); font-family: Helvetica Neue, Helvetica, Arial, sans-serif; font-size: medium;">[Kevin:]</span></span></font></div><div dir="ltr" data-setdir="false"><font size="3">Not so clone-proof though, if I understand.</font></div><div dir="ltr" data-setdir="false"><font size="3"><br></font></div><div dir="ltr" data-setdir="false"><font size="3">I guess I am a little surprised if the ties creating issues under Schulze don't cause similar issues under RP or River.</font></div><div dir="ltr" data-setdir="false"><font size="3"><br></font></div><div dir="ltr" data-setdir="false"><font size="3">A possible result of a comparison, that occurred to me, would be if Schulze proved to be more decisive. That would mean, in other words, that it's more decisive than methods that actually get interrupted in the middle in order to handle ties.</font></div><div dir="ltr" data-setdir="false"><br></div><div dir="ltr" data-setdir="false"><br clear="none"><span style="font-size: 13px;">I've been thinking that there must be some way of applying the same</span><br clear="none"><span style="font-size: 13px;">logic to Schulze, but I haven't been able to find a good generalization.</span><br clear="none"><span style="font-size: 13px;">It might be easier to do so to the CSSD formulation of Schulze. The CSSD</span><br clear="none"><span style="font-size: 13px;">formulation is this:</span><br clear="none"><br clear="none"><span style="font-size: 13px;">1. Calculate the Schwartz set based only on undropped defeats.</span><br clear="none"><span style="font-size: 13px;">2. If there are no defeats among the members of that set then they</span><br clear="none"><span style="font-size: 13px;">(plural in the case of a tie) win and the count ends.</span><br clear="none"><span style="font-size: 13px;">3. Otherwise, drop the weakest defeat among the candidates of that set.</span><br clear="none"><span style="font-size: 13px;">Go to 1.</span><br clear="none"><br clear="none"><span style="font-size: 13px;">Perhaps you could break ties in #3 in a somehow analogous way to</span><br clear="none"><span style="font-size: 13px;">Ext-Minmax, e.g. drop the weakest pairwise contest and if there are more</span><br clear="none"><span style="font-size: 13px;">than one with the same strength, drop the X>Y contest where X's next</span><br clear="none"><span style="font-size: 13px;">weakest pairwise contest is weakest, and so on up. But that's just a guess.</span></div><div dir="ltr" data-setdir="false"><span style="font-size: 13px;"><br></span></div><div dir="ltr" data-setdir="false"><font size="3"><span><span style="color: rgb(38, 40, 42); font-family: Helvetica Neue, Helvetica, Arial, sans-serif; font-size: medium;">[Kevin:]</span></span></font></div><div dir="ltr" data-setdir="false"><span style="font-size: medium;">That feels a little painful, that to improve decisiveness in Schulze you would use the formulation that can have ties during the calculation.</span></div><div dir="ltr" data-setdir="false"><br clear="none"><br clear="none"><span style="font-size: 13px;">And as for River, I've been thinking about a River-ish method that would</span><br clear="none"><span style="font-size: 13px;">simplify the tie problem a lot, and where you could easily declare a tie</span><br clear="none"><span style="font-size: 13px;">among winners. It's related to the observation that running River is</span><br clear="none"><span style="font-size: 13px;">like calculating a maximum spanning tree.</span><br clear="none"><br clear="none"><span style="font-size: 13px;">Many of River's properties seem not to depend upon the resulting tree</span><br clear="none"><span style="font-size: 13px;">being a maximum spanning tree, but that it's a maximum bottleneck</span><br clear="none"><span style="font-size: 13px;">spanning tree. A maximum bottleneck spanning tree is one where the</span><br clear="none"><span style="font-size: 13px;">minimum strength is maximized. Every maximum spanning tree is also a</span><br clear="none"><span style="font-size: 13px;">maximum bottleneck spanning tree, but vice versa is not true.</span><br clear="none"><br clear="none"><span style="font-size: 13px;">I *think* that River passing independence of strongly dominated</span><br clear="none"><span style="font-size: 13px;">candidates is a consequence of the bottleneck property, but I could be</span><br clear="none"><span style="font-size: 13px;">wrong: I only started thinking about this after writing my last post. In</span><br clear="none"><span style="font-size: 13px;">any case, the directed graph version of a maximum bottleneck spanning</span><br clear="none"><span style="font-size: 13px;">tree is a maximum bottleneck spanning arborescence, and there are</span><br clear="none"><span style="font-size: 13px;">algorithms for calculating the MBSA with the provision that the</span><br clear="none"><span style="font-size: 13px;">arborescence has to grow from a certain root. The simple interpretation</span><br clear="none"><span style="font-size: 13px;">of such a root is that the root node is the candidate who remains</span><br clear="none"><span style="font-size: 13px;">undefeated, i.e. the winner.</span><br clear="none"><br clear="none"><span style="font-size: 13px;">So all you'd have to do to implement this new method (Bottleneck River</span><br clear="none"><span style="font-size: 13px;">or what you might call it) is to run Tarjan's algorithm with each</span><br clear="none"><span style="font-size: 13px;">candidate as root in turn. For each candidate you get a different tree.</span><br clear="none"><span style="font-size: 13px;">The candidate whose tree has the maximal minimal locked edge weight</span><br clear="none"><span style="font-size: 13px;">(locked victory) is the winner, and if there's more than one, you can</span><br clear="none"><span style="font-size: 13px;">either break ties by considering the next-to-minimal edge weight, or</span><br clear="none"><span style="font-size: 13px;">just use a coin toss (or whatever).</span><br clear="none"><br clear="none"><span style="font-size: 13px;">Tarjan's algorithm is here:</span><br clear="none"><a shape="rect" href="https://en.wikipedia.org/wiki/Minimum_bottleneck_spanning_tree#Gabow_and_Tarjan_algorithm_for_MBSA" style="font-size: 13px;" rel="nofollow" target="_blank" class="enhancr_card_2189888595">Minimum bottleneck spanning tree</a><br clear="none"><span style="font-size: 13px;">Note that it's specified in terms of a minimum bottleneck spanning</span><br clear="none"><span style="font-size: 13px;">arborescence: you can go from maximum to minimum by just turning all the</span><br clear="none"><span style="font-size: 13px;">victories negative and adding the total number of voters (and then the</span><br clear="none"><span style="font-size: 13px;">winner is the candidate with the minimal maximal edge weight).</span><br clear="none"><br clear="none"><span style="font-size: 13px;">This pretty much kills all the elegance of the River method, though.</span></div><div dir="ltr" data-setdir="false"><span style="font-size: 13px;"><br></span></div><div dir="ltr" data-setdir="false"><font size="3"><div><div dir="ltr" data-setdir="false" style="color: rgb(38, 40, 42); font-family: Helvetica Neue, Helvetica, Arial, sans-serif; font-size: 16px;"><font size="3">[Kevin:]</font></div></div>Yes although I do like the idea of "proposing" each candidate in turn, as the winner, and measuring what gets fouled up by going with that as the outcome.</font></div></div><div dir="ltr" data-setdir="false"><font size="3"><br></font></div><div dir="ltr" data-setdir="false"><font size="3">Kevin</font></div><div dir="ltr" data-setdir="false"><font size="3"><br></font></div>
</div>
</div></body></html>