[EM] Methods, pair-ties, Schwartz, Smith

[MIKE OSSIPOFF]

Ernie--

You wrote:

If there are no pairwise ties:
- The Schwartz & Smith sets are identical

I reply:

Yes.

You continued:

- PC, Smith PC, and Schwartz PC all give the same result

I reply;:

Smith PC & Schwartz PC are the same then, but PC is still different from 
both,  in public elections and in committees.

You continued:

[If there are no pairwise ties]:

- SD, SSD, CSSD (Beatpath) are identical to each othe

I reply:

With no pairwise ties, SSD & CSSD are identical, but SD can be different, 
because it repeatedly drops the weakest defeat that's in a cycle,  rather 
than the weakest defeat that's in the Schwartz set. Like SSD & MAM, SD meets 
all the majority defensive strategy criteria, but SD has been shown on EM to 
be able to be nonmonotonic. Its nonmonotonicity would be rare, and isn't an 
important problem.


 > , but may differ  from * PC

Yes.

- Tideman still differs from *SD and *PC [is that true?]

Certainly. Tideman (aka MAM or RP) can differ from SSD, SD, PC, & 
BeatpathWinner/CSSD whether or not there are pairwise ties.


>If there are pairwise ties: - The Smith set (beat all outside) is larger 
>than the Schwartz  (smallest unbeaten set)

Yes, if someone outside the Schwartz set ties one  or more of its members.

>- PC, Smith PC, and Schwartz PC can give different results

Yes. But PC can give different results from Smith PC & Schwartz PC even with 
no pairwise ties.

>That is, the Plain Condorcet winner - with the least greatest defeat -  may 
>NOT be in the            >  Schwartz or Smith set

Yes, that can happen in committees or in a public election.

>So, back to the algorithm I proposed earlier: - count the number of 
>pairwise contests each candidate wins  (Nwins[candidate]) - identify the 
>candidate(s) with the greatest number of wins - pick the candidate that 
>beats the other candidates with the same  number of wins (LB)  if cyclic 
>tie, pick one at random

>Is that in fact sure to pick a member of the Schwartz set?

A similar approach works for the Smith set, and probably something like 
could find the Schwartz set too, but I don't know exactly how it would be 
done, finding the Schwartz set in that way.

For finding someone in an innermost unbeaten set, woudn't one want to judge 
him by his number of defeats rather than victories? For the Smith set one 
would count his victories. I could be mistaken, of course, because I'm 
looking at this for the first time.  A Schwartz set member could tie most of 
the people outside the Schwartz set, as long as he isn't beaten by anyone 
outside it. He might not have many victories, but will have few defeats, 
only from members of his set. Of course maybe everyone outside the Schwartz 
set has no defeats except for one defeat from one member of the set. So I 
have to admit that I don't know, at this first glance, how to make that 
approach work for the Schwartz set.

Anyone who beats a member of the Schwartz set has got to be a member of the 
Schwartz set.

But if someone doesn't beat anyone in that sequence, he could still be in a 
_different_ innermost unbeaten set. With pairwise ties there can be more 
than 1 innermost unbeaten set. The Schwartz set is the set of candidates who 
are in innermost unbeaten sets.

With pairwise ties, there could be two innermost unbeaten sets such that all 
of the members of one pair-tie all the members of the other.

I'd felt that if I were going to program the Schwartz set, I'd say that if i 
beats j, then D(i,j) =1 and if i doesn't beat j, D(i,j) = 0. I'd copy those 
values into the strongest beatpaths array, B(i,j), and apply the strongest 
beatpaths algorithm to it. Then, with the resulting B(i,j) array, if B(j,i) 
 > B(i,j) then i isn't in the Schwartz set. Because j has a beatpath to i 
(B(j,i) =1), but i doesn't have a beatpath to j (B(i,j) = 0).

The way you suggest hadn't occurred to me, but surely something like it 
could work. I don't know exactly how to make it work though, due to the 
problems that I mentioned above.

>Similarly, if this algorithm gives the Schwartz set: - choose all the 
>candidates which beat LB, directly or indirectly

>Then, does this algorithm give the Smith set: - choose all the candidates 
>which beat OR TIE LB, directly or indirectly

Yes, that would work for the Smith set. It's the smallest set such that 
everyone in it beats everyone outside it. So start with the person with the 
most pairwise victories and anyone who beats or ties him, or beats or ties 
someone who beats or ties him, or is part of a longer such sequence, is a 
member of the Smith set.

Wilth the Smith set there isnt the problem of 2 or more sets. There's only 
one smallest set of candidates who beat everyone outside that set.

A member of the Smith set beats everyone outside it. No nonmember can beat 
as many people as that. So one can start with the person with the most 
pairwise victories. Anyone who beats or ties him must also be a member. 
Likewise anyone who beats or ties any member. So members can be found from a 
sequence of defeats/ties, as you described.

So I can say that the Smith set procedure you described works.

Mike Ossipoff

_________________________________________________________________
Learn how to choose, serve, and enjoy wine at Wine @ MSN. 
http://wine.msn.com/