[EM] Methods, pair-ties, Schwartz, Smith
MIKE OSSIPOFF
nkklrp at hotmail.com
Sat Jan 10 23:59:02 PST 2004
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/
More information about the Election-Methods
mailing list