[EM] MinLengthMaxStrengthCoveringChain

[Forest Simmons]

On Mon, Apr 24, 2023, 8:07 AM Forest Simmons <forest.simmons21 at gmail.com>
wrote:

> For our purposes  a chain is a list of alternatives on which every
> alternative is defeated by every higher listed alternative.
>
> If every alternative not in the chain is defeated by some member of the
> chain, it is said to be a "covering chain".
>
> The length of a chain is the number of alternatives comprising the chain.
>
> The head of the chain is the alternative that defeats all of the other
> members of the chain.
>
> The tail of the chain is the alternative defeated by every other chain
> member.
>
> Our proposed method is to elect the head of the covering chain of maximum
> strength among all those of minimum length.
>
> This method satisfies the ISDA criterion.
>
> In a public political election the MLMSCC chain will almost surely consist
> of fewer than three alternatives ... we can safely say never more than
> three.
>
> So the winner can be found by comparing the strengths of at most a few
> dozen chains.
>
> This would be the case, for example, if the top cycle were to be created
> by replacing each member of a rock-paper-scissors cycle with a different
> clone cycle of the same kind.
>
> In fact, in that case there would be exactly three dozen covering chains
> of length three to check.
>

Actually only 27 chains to check ... each of them isomorphic to
(r,r)>(r,s)>(s,s).

>
> To be continued (later today when I get another turn on the cell phone ...)
>
> -fws
>

Even the formidable "twisted prism" has only three chains to check ... the
three defeats from the upper deck are the only minimum length covering
chains.

For the sake of completeness we now specify how to find the winner even in
the statistically impossible case of more than 27 chains to check:

Each faction may propose a covering chain. Elect the head of the strongest
admissible proposal from among those tied for minimum length.

Which brings us to the question of "chain strength" ... how do we gauge it?

When the chain has only one link ... that is only one defeat ... the chain
strength is simply that defeat strength.

A chain of length three A>B>C has three defeats A>C, A>B, and B>C. To
preserve reverse symmetry we define the defeat strength to be

s(A>C) + min(s(A>B),s(B>C))*epsilon,

where s is some gauge of pairwise defeat strength ... and epsilon is a
positive infinitesimal that comes into play only when needed for tie
breaking purposes.

This definition of chain strength is extended indefinitely by recursion:

s(A>B>...Y>Z) is given by s(A>Z) plus ...
... min(s(A>...>Y),s(B> ...>Z))*epsilon

That's it!

For basic defeat strength of a sinle pair of alternatives, I highly
recommend

s(A>B)=approval(A)+disapproval(B),

where approval X becomes disapproval X when all preferences are reversed.

One such approval/disapproval pair is Equal Top Whole / Bottom Count Whole.

EQTop(X) is the number of ballots on which X is not outranked.  BotCount(X)
is the number of ballots on which X outranks no candidate.

Here's another example:

approval(X) is the number of ballots on which some candidate outranked by X
defeats every candidate that outranks X,

... while disapproval(X) is the number of ballots on which some candidate
that outranks X defeats every candidate outranked by X.

If range/score ballots are used, then [disapproval, respectively, approval]
of X is the number of ballots on which X is rated [below, resp, above]
midrange.

Now that you see how to respect the reverse symmetry, you can make up your
own symmetric defeat strength gauge.

Example:

48 C
28 A>B
24 B

The MinLentthMaxStrengthCoverinChain is C>A with strength
EQTop(C)+BotCount(A)=48+72.

Note also approvalC+disapprovalA is the same sum 120.

By comparison, approvalB+disapprovalCis 52+52=104.

Example 2

a A>B(sincere A>C)
b B>C
c C

s(A>B)=approvalA+disapprovalB
=a+c
s(B>C)=a+b+a
s(C>A)=a+c+b+c

So C is the head of the winning chain C>A.

It's hard to think of another method that is half so simple and powerful.

-fws
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20230424/fee0815f/attachment.htm>