[EM] Favorability Sorted Ranked Pairs

[Forest Simmons]

Here's something in the same spirit that can be done.

Initialize with the strongest pair c1>c2.

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

C1>c2>c3

We skip over the Pairs that cannot be entirely & consistently accomodated
into the transitive chain.

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.

Is this a maximal chain?

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?

Now what is the significance of what we have accomplished?

Suppose we reversed the chain by swapping it end for end.  That would
reverse every defeat pair in the sequence of incorporated Pairs.

Suppose the cost of reversing the j_th pair is set at 1/2^j.

Then the cost of reversing the chain we have constructed is maximal.  It
would be cheaper to reverse any other maximal chain.

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]

Anyway, the head of a maximal transitive chain of candidates like this is
(by definition) a Banks candidate.

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.

fws

On Sat, Oct 28, 2023, 4:58 AM Kristofer Munsterhjelm <km_elmet at t-online.de>
wrote:

> On 10/28/23 01:21, Forest Simmons wrote:
> > For each pair P of candidates, let Strength(P)=cov(P)+epsilon*wv(P),
> > where cov(P)=One If one member of P covers the other one, Else zero
> > EndIf, and wv(P) is the number of ballots on which the member of P that
> > pairbeats the other outranks the other.
>
> A related thought:
>
> Let a certain sequence S of pairwise victories' score be the sorted
> vector of their magnitudes, from greatest to least, and let S_1 > S_2 if
> leximax, the sorted vector for S_1 is greater than that for S_2.
>
> Then Ranked Pairs consists of finding the sequence corresponding to the
> maximal such vector subject to that the induced ordering of the sequence
> is transitive.
>
> How about finding the maximum sequence subject to that the winner should
> come from some desirable set? Your method is a way to do this for the
> uncovered set... I think (I'd have to prove that the sequence is maximal
> subject to the winner being uncovered). Is there a natural extension for
> other sets like Banks?
>
> If we just brute-forced it, would the Banks-restricted method be
> monotone? It's probably very hard to say.
>
> Or say we brute-forced it with the winner being part of the resistant
> set. This would be burial resistant and shouldn't have the high other
> strats effect of CTE or beat chain methods. Perhaps it would be
> monotone? Maybe there is some more natural way to phrase it than just
> "try every possible ordering and see which maximizes the leximax
> measure, and has a winner in the resistant set".
>
> In a way, election method questions are like number theory ones: so easy
> to ask, sometimes incredibly hard to answer.
>
> -km
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20231028/13cfee3e/attachment.htm>