[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