[EM] Simple Method to Find the Smith Set
John Karr
brainbuz at brainbuz.org
Thu Nov 17 11:02:20 PST 2022
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20221117/35c0f688/attachment.htm>
More information about the Election-Methods
mailing list