[EM] smith/schwartz/landau

Kristofer Munsterhjelm km_elmet at t-online.de
Fri Mar 9 04:22:33 PST 2018

On 03/09/2018 05:35 AM, Curt wrote:
> The wiki page 
> 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.

Suppose the relation is beats-or-ties. Then that implies that for all 
pairs of candidates X, Y inside the Smith set, there's a path from X to 
Y where X beats or ties A who beats or ties B who beats or ties... who 
beats or ties Y.

Then all candidates in the Smith set must beat every candidate outside. 
Suppose that this were not true; that X is in the Smith set and Z is 
not, but X doesn't beat Z. Then there are two possibilities. Either X 
ties Z, or Z beats X.

If X ties Z, then Z is in the Smith set because there's a path from Z 
(through X) to everyone else in the Smith set. If Z beats X, then 
there's similarly also a path from Z to everyone else in the Smith set. 
Thus Z must be in the Smith set as well.

For the Schwartz set, there's a beat (no tie) path from any X to any Y 
in the Schwartz set. Because you can no longer bridge a gap using ties, 
the Schwartz set is a subset of the Smith set. So the Schwartz set is 
never larger than the Smith set.

Since there's a path from any X in the Schwartz set to any Y also in it 
using only the beats relation, every member in the Schwartz set must 
beat or tie everyone outside.

So the confusion is, I think, about whether you're on the outside 
looking in or on the inside looking at others on the inside. Every Smith 
set member beats everyone outside, but the Smith set consists of 
candidates with beat-or-tie paths to each other. Every Schwartz set 
member beats or ties everyone outside, but the Schwartz set consists of 
candidates with beat-relation paths to each other.

More information about the Election-Methods mailing list