[EM] Simple Method to Find the Smith Set

[Forest Simmons]

Good!

Here's a method that can take advantage of your procedure:

For each ballot B, let f(B) be B's highest ranked Smith member, unless B
ranks no Smith member, in which case ffB) is simply B's top choice.

Then for each candidate X, let p(X) be the percentage of the ballots B for
which X is f(B).

Finally, for each Z, let H(Z) be the sum given by the expression

Sum{p(X)|X defeats Z pairwise}

Elect argmin H(Z).

This is a decisive version of "friendly voting" so called because of
electing the candidate Z with minimal hostility H(Z) directed towards it.
Note H(Z) is the total percentage of the ballots B on which f(B) is hostile
to Z, i.e. "beats Z" pairwise.

A slight disadvantage of the method is that it requires two passes through
the ballots ... the first to get the pairwise matrix, and the second to get
p(X) for each X.

-Forest

On Thu, Nov 17, 2022, 11:02 AM John Karr <brainbuz at brainbuz.org> wrote:

> For the Vote::Count library I use the following method to find the Smith
> Set. It is simpler than any of the methods currently on
> https://electowiki.org/wiki/Smith_set#Algorithms as it only requires a
> complete matrix and does not require using another method to find a member
> of the Smith Set.
>
> Step 0 (Optional). Reduce the set by removing Condorcet Losers.
>
> Step 1. Each Choice proposes that they and every other choice which
> defeats or ties them is the Smith Set.
>
> Step 2. Find the smallest proposal and use it as the Active Proposal.
>
> Step 2A. If there is a tie for smallest combine the members to create the
> Active Proposal.
>
> Step 3. Check the proposal of each member of the Active Proposal and add
> any new members.
>
> Step 4. Repeat step 3 until no new members are added to the Active
> Proposal.
> This method will work because:
>
> Choices outside the Smith Set will always have a minimum number of losses
> at least equal to the size of the Smith Set.
>
> Choices within the Smith Set will always have a number of losses less than
> the size of the Smith Set because they will not be paired to themselves and
> there must always be at least one other member which does not defeat them.
>
> Therefore the choice or choices with the fewest defeats will always be
> members of the Smith Set, and any further choice that defeats (or ties)
> them must also be in the Smith Set.
> --
>
> Minds gets scrambled like eggs
> Get bruised and erased
> When you live in a brainstorm
>
> — Alice Cooper: Hard Hearted Alice
> ----
> Election-Methods mailing list - see https://electorama.com/em for list
> info
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20221117/da268640/attachment.htm>