[EM] smith/schwartz/landau
Kristofer Munsterhjelm
km_elmet at t-online.de
Thu Mar 8 11:28:08 PST 2018
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.
More information about the Election-Methods
mailing list