I've been writing a library to tabulate results of ranked choice ballots by multiple methods. For Condorcet Methods I would like to quickly reach the smallest possible Dominant (Smith) Set.
The steps should be easy to code in any programming language, and not depend on math libraries. It should also be easy to explain the algorithm to people with only basic math skills.
I've written some code that I think will do this, but would like feedback from people more confident of the math.
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
and use that result as the base 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 proposal.
If I consider a preference-loop with this method, each loop member will have a proposal of 2 members. When combined the proposal will be the three members of the loop, and no new members will be added in step 3. This method is also valid for a 4 member knot (my term for a Smith Set which isn't a preference-loop).
Logically it appears that this algorithm should always work. I'm using it in Vote::Count, and would like to confirm that its right.
Logical Proof of my Method
The simple algorithm to find the Smith Set is to start by finding one member, a simple Smith Compliant Method such as BTR IRV can be used for this; then add any choice which defeats them and so on.
A choice outside the Smith Set must have a number of defeats at least equal to the number of members of the Smith Set, a choice within the Smith Set must have a number of defeats smaller than the size of the Smith Set. Therefore the choice or choices with the fewest defeats must be members of the Smith Set.