[EM] smith/schwartz/landau

[Kevin Venzke]

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

      De : Kristofer Munsterhjelm <km_elmet at t-online.de>
 À : Curt <accounts at museworld.com>; election-methods at lists.electorama.com 
 Envoyé le : Vendredi 9 mars 2018 6h22
 Objet : Re: [EM] smith/schwartz/landau
   
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.
----
Election-Methods mailing list - see http://electorama.com/em for list info


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