[EM] Simple Method to Find the Smith Set

[John Karr]

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>