[EM] smith/schwartz/landau

[Kristofer Munsterhjelm]

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.