[EM] smith/schwartz/landau

[Curt]

The wiki page https://wiki.electorama.com/wiki/Maximal_elements_algorithms <https://wiki.electorama.com/wiki/Maximal_elements_algorithms> confused me because it says (as you paraphrased) “X beats Y pairwise for the Schwartz set, X beat or ties Y pairwise for the Smith Set”.

Isn’t that backwards? I thought the Smith set was the smallest set of candidates who all *defeat* candidates outside of the set (as wikipedia says), while Schwartz set was the one that allowed ties.

> On Mar 8, 2018, at 11:28 AM, Kristofer Munsterhjelm <km_elmet at t-online.de> wrote:
> 
> On 03/07/2018 04:48 AM, Curt wrote:
> 
> Sets like Schwartz and Smith are usually maximal elements of a partially ordered set. https://wiki.electorama.com/wiki/Maximal_elements_algorithms gives more information about this, as well as how to use Floyd-Warshall or Kosaraju's algorithms to find maximal elements.
> 
> In graph theory terms, we're interested in the smallest set so that there's a cycle from any candidate in that set to any other candidate in that set, according to a relation (X beats Y pairwise for the Schwartz set, X beats or ties Y pairwise for the Smith set). Any strongly connected components algorithm should work, if given a directed graph where there's an edge from X to Y iff X is ranked ahead of Y according to the relation being used.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20180308/058db047/attachment.html>