Simple Method to Find the Smith Set
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
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@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