[EM] smith/schwartz/landau

Curt accounts at museworld.com
Mon Mar 26 12:20:52 PDT 2018

Hi Kristofer, 

Thank you for the test case, I’ve added it locally.

I had deja vu on this example because I came across it once before and it looked wrong to me at first. Here, I input the ballots and I got {E} as the single-member Smith and Schwartz set.

But then I realized the example has an alternate ballot style where 


is supposed to be interpreted as


My default ballot counter does not do that, it assumes no opinion over the rest. I now have a todo to supply a flag to support both ballot styles. :)

I adjusted the ballot input to manually specify the ties, and I got a Schwartz Set of {A, B, C, D, E}. (And then {F, G}, and then {H}, and then {I, J, K, L}).

It identifies the Smith Set as all candidates.

My Schwartz implementation is based off the Floyd-Warshall algorithm here: https://wiki.electorama.com/wiki/Maximal_elements_algorithms
My implementation:

It looks like that pseudocode doesn’t try to identify components within the Schwartz Set. But looking at the tally I see how E is the Weak Condorcet Winner. Is there pseudocode that identifies these minimal sets separately?

I will have to update my mental definition of Schwartz Set and update y docs; I would have thought E would be the Schwartz Set, although I see looking at the tally how that isn’t true. But I wish my code to identify the WCW(s) from the Schwartz Set, just like it identifies any CW from the Smith Set.


> On Mar 26, 2018, at 1:00 AM, Kristofer Munsterhjelm <km_elmet at t-online.de> wrote:
> On 03/23/2018 09:33 PM, Curt wrote:
>> Thanks to Kristofer for explaining my “beats” vs “beats or ties” confusion.
>> For anyone interested, here is the software package of me using scala to compute Smith and Schwartz sets. It’s not super-advanced, but it at least avoids mutable variables. In the future I may try to use more expressive FP concepts, and pull in one of the faster Schwartz algorithms. I don’t entirely understand the graph algorithms yet.
>> https://github.com/tunesmith/condorcet-counter
>> I opined a bit in the README but that’s not really the point of the project. I just wanted an easy way to identify Smith and Schwartz sets for myself.
> As Kevin pointed out, the Schwartz set is actually the union of all minimal such sets, because (unlike for Smith) that's not the same thing as just one such minimal set.
> At https://wiki.electorama.com/wiki/Beatpath_example_12 there is an example where the Schwartz set has two components ({A,B,C,D} and {E}). Could you test your software on it?
> -km

More information about the Election-Methods mailing list