[EM] smith/schwartz/landau

[Curt]

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 <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.

Curt


> On Mar 9, 2018, at 7:41 AM, Kristofer Munsterhjelm <km_elmet at t-online.de> wrote:
> 
> On 03/09/2018 02:04 PM, Kevin Venzke wrote:
>> I think Schwartz members don't actually have to have beatpaths to each other though. Suppose there are five candidates. A>B>C>A cycle. E is the Condorcet loser. All of D's contests are ties except for D>E. Then the Schwartz set is {A,B,C,D}.
> 
> Ah, right, for the Schwartz set there may be disjoint smallest sets of candidates having beatpaths to everybody else inside that set. The smaller sets are called Schwartz set components, and the Schwartz set itself is the union of all those disjoint sets.
> 
> I think that strictly speaking holds for Smith, too, but the use of ties to bridge gaps means there won't be more than one such smallest set (unless you use a pairwise matrix setup that allows for, say, pairwise contests that are entirely unknown, so you neither have A beats B, A ties B, or B beats A).
> 
> You also gave the following description in a private reply:
> 
>> I like to define the Schwartz set as every candidate X who has a
>> beatpath to every other candidate Y who has a beatpath to X.
> 
> That works for both Schwartz and Smith with respectively the beats relation and the beats-or-ties relation. That is,
> 
> X is in the set if
> for every other Y where Y has a path to X using the relation,
> X also has a path to Y using the relation.
> 
> D above is in the Schwartz set because nobody has a path of pairwise defeats to D, and D trivially has a path of pairwise defeats to every candidate in the empty set.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20180323/5f83c2f8/attachment.html>