[EM] Yet Another Simple Way to Find Smith Set

[Kristofer Munsterhjelm]

On 4/8/23 03:18, Gervase wrote:
> I've been perusing the Election Methods archive and noticed that more or
> less recently there was the need for simple legislative language to
> define Condorcet and/or Smith (Subjects: "Hay guys, look at this..." and
> "Another Simple Way to Find Smith").  Apologies if what I write
> following this paragraph has already been explored in the mailing list.
> 
> Looking at the Wikipedia page for "Smith Set", it seems to contain a
> simple algorithm for finding the Smith Set...
> 
> (1) Start with a set D (Dominating/Smith Set) with no candidates in it.
> (2) Add all candidate(s) who are in the Copeland (Winner) Set to D.
> (3) Add to D the candidate(s) who are NOT currently in D and who also
> pairwise beats any candidate currently in D.
> (4) Repeat step (3) until no candidate(s) are added by step (3).
> 
> RESULT: Set D is the Smith Set.
> 
> Copeland (Winner) Set are set of candidate(s) with the highest Copeland
> score.
> 
> That's it!  Read further if you want more details...

That's a good idea. If there's a problem with it, I'd say it's the 
complexity: I think you worst case could end up doing n passes through 
the list of candidates, and each of these take n time.

On the other hand, every Smith set candidate is in a three-cycle with 
some other Smith set candidate (absent ties), so perhaps I'm wrong about 
this.

-km