<div dir="auto">Here's something in the same spirit that can be done.<div dir="auto"><br></div><div dir="auto">Initialize with the strongest pair c1>c2.</div><div dir="auto"><br></div><div dir="auto">Now suppose c2>c3 is the next strongest pair, and that c1>c3 is also a valid pairwise defeat.  Then since the second strongest pair is transitively consistent with the previous progress ... we incorporate it to get</div><div dir="auto"><br></div><div dir="auto">C1>c2>c3</div><div dir="auto"><br></div><div dir="auto">We skip over the Pairs that cannot be entirely & consistently accomodated into the transitive chain.</div><div dir="auto"><br></div><div dir="auto">It takes O(n^2) steps to check (and reject or incorporate) each of the n^2 pairs. So altogether O(n^4) steps ... typically drastically fewer steps.</div><div dir="auto"><br></div><div dir="auto">Is this a maximal chain?</div><div dir="auto"><br></div><div dir="auto">Yes! If another candidate C could by itself be accomodated into the chain H>....>T, then why did we skip over both H>C and C>T when those two pairs came up in the sequence of pairs?</div><div dir="auto"><br></div><div dir="auto">Now what is the significance of what we have accomplished?</div><div dir="auto"><br></div><div dir="auto">Suppose we reversed the chain by swapping it end for end.  That would reverse every defeat pair in the sequence of incorporated Pairs. </div><div dir="auto"><br></div><div dir="auto">Suppose the cost of reversing the j_th pair is set at 1/2^j.</div><div dir="auto"><br></div><div dir="auto">Then the cost of reversing the chain we have constructed is maximal.  It would be cheaper to reverse any other maximal chain.</div><div dir="auto"><br></div><div dir="auto">Think of the j_th pair as a magnetic dipole of strength 2^(-j). We  have constructed the chain of maximal magnetic moment out of the Lego's we were given ... the moment is (kind of) a measure of how much torque it would take to rotate it in a uniform field of unit strength. [To be  approximately correct, we would have to connect the dipoles side by side rather than lengthwise]</div><div dir="auto"><br></div><div dir="auto">Anyway, the head of a maximal transitive chain of candidates like this is (by definition) a Banks candidate.</div><div dir="auto"><br></div><div dir="auto">This version of Ranked Pairs  is extremely easy to carry out in practice, because in practice the top cycle has only three members of Banks to consider. The head of the strongest of the three Pairs will be the winner we are looking for.</div><div dir="auto"><br></div><div dir="auto">fws</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sat, Oct 28, 2023, 4:58 AM Kristofer Munsterhjelm <<a href="mailto:km_elmet@t-online.de">km_elmet@t-online.de</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On 10/28/23 01:21, Forest Simmons wrote:<br>
> For each pair P of candidates, let Strength(P)=cov(P)+epsilon*wv(P), <br>
> where cov(P)=One If one member of P covers the other one, Else zero <br>
> EndIf, and wv(P) is the number of ballots on which the member of P that <br>
> pairbeats the other outranks the other.<br>
<br>
A related thought:<br>
<br>
Let a certain sequence S of pairwise victories' score be the sorted <br>
vector of their magnitudes, from greatest to least, and let S_1 > S_2 if <br>
leximax, the sorted vector for S_1 is greater than that for S_2.<br>
<br>
Then Ranked Pairs consists of finding the sequence corresponding to the <br>
maximal such vector subject to that the induced ordering of the sequence <br>
is transitive.<br>
<br>
How about finding the maximum sequence subject to that the winner should <br>
come from some desirable set? Your method is a way to do this for the <br>
uncovered set... I think (I'd have to prove that the sequence is maximal <br>
subject to the winner being uncovered). Is there a natural extension for <br>
other sets like Banks?<br>
<br>
If we just brute-forced it, would the Banks-restricted method be <br>
monotone? It's probably very hard to say.<br>
<br>
Or say we brute-forced it with the winner being part of the resistant <br>
set. This would be burial resistant and shouldn't have the high other <br>
strats effect of CTE or beat chain methods. Perhaps it would be <br>
monotone? Maybe there is some more natural way to phrase it than just <br>
"try every possible ordering and see which maximizes the leximax <br>
measure, and has a winner in the resistant set".<br>
<br>
In a way, election method questions are like number theory ones: so easy <br>
to ask, sometimes incredibly hard to answer.<br>
<br>
-km<br>
</blockquote></div>