[EM] smith/schwartz/landau

[Kristofer Munsterhjelm]

On 03/07/2018 04:48 AM, Curt wrote:
> Hi, as a side project I’m writing a scala script that determines the smith set and schwartz set from ranked ballots. (I’m not currently interested in implementing any tiebreakers/completion algorithms. Just condorcet winner, smith set, schwartz set.)
> 
> I’m uncertain about my implementations for smith and schwartz. I followed some pseudocode algorithms I found online but I’m not sure they’re quite right. The schwartz algorithm I found looks more like how landau is described. Part of my challenge is also that I’m trying to do them functional-style without mutable variables like loops and counters.
> 
> Could someone post an example of a simple collection of ballots where the smith set, schwartz set, and landau sets are all different?
> 
> Also if we have a collection of ballot example somewhere that show odd examples of condorcet winner, smith set, schwartz set, etc, and what the count should yield, I’d love to collect them because they’d make a good test suite.

A partial answer: The Wikipedia article on the Schwartz set, 
https://en.wikipedia.org/wiki/Schwartz_set, gives an example where the 
Schwartz set is a single candidate but the Smith set consists of every 
candidate.

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.

https://stackoverflow.com/a/15905986 links to a paper detailing 
(somewhat complex) Haskell code for Kosaraju's algorithm, and the 
accepted answer has Scala code for Tarjan's algorithm (which also finds 
strongly connected components). I imagine that Floyd-Warshall could be 
implemented relatively simply in a functional style by just using the 
dynamic programming equation that drives it, and memoization.