Re: Tiebreakers, Subcycle Rules
- Dear participants,
the Schulze method can be interpreted as a successive
elimination of pairwise defeats.
What is an elimination of a pairwise defeat?
It is obvious, what an elimination of a candidate is. "If a
candidate is eliminated, all ballots are treated as if that
candidate had never stood" (I.D. Hill, "Some Aspects of Elections
- to Fill One Seat or Many," Journal of the Royal Statistical
Society A, vol. 151, part 2, p. 243-275, 1988). To my opinion,
an elimination of a pairwise defeat should be considered, as
if this pairwise defeat is replaced by a pairwise tie. The
disadvantage of this interpretation of an elimination of a
pairwise defeat is the fact, that the Smith set will increase
and not decrease. But this problem can be avoided by using the
Schwartz set instead of the Smith set. Thus, the Schulze method
looks as follows:
Step1: Calculate the Schwartz set among the potential winners
and eliminate all those candidates, who are not in the
Schwartz set of the potential winners!
Step2: If there is still more than one potential winner, then
replace the weakest pairwise defeat (i.e. the pairwise
defeat with the smallest absolute number of votes for
the winner of that pairwise comparison) between two
potential winners with an equality! Pairwise defeats,
that have already been replaced by an equality, stay
replaced. Go to Step1!
Otherwise, if there is only one potential winner, then
this potential winner wins the election.
But, to my opinion, this interpretation of the Schulze method
as a successive elimination of pairwise defeats doesn't make
this method more simple.
- Dear Markus,
Thank-you for your reply.
The reason (in particular) that I am interested in your tiebreaker solution
is that the complexity of Schwartz set computation would make it desirable
to use a simpler tiebreaker, if possible (such as Condorcet(EM)) with the
beat-path method. The main (beat-path) portion of your method seems very
decisive in examples we've tried, so using a simpler tiebreaker for rare
cases would seem to be ok. Your example demonstrates at least a couple of
interesting things in this regard:
1) Your Schwartz set tiebreaker is more decisive than the tiebreaker I had
thought might be a reasonable substitute. If Condorcet(EM) (fewest
votes-against in largest defeat) is used to pick between B & D, the result
is _still_ indecisive (both have 5 votes against in their worst defeat). If
the example you provide is typical of the situations in which the beat-path
computation produces ties, Condorcet(EM) would be a poor substitute for
2) The other good method we've been looking at (Pairwise Dropping) is
equally indecisive in this example. Elimination of all the beat-paths of
strength 5 leaves a tie between D>A and B>C. This confirms my suspicion
that beat-path calculation is always _at least_ as decisive as Pairwise
Dropping. I think that Pairwise Dropping will only be indecisive in cases
like this, where dropping multiple defeats of equal strength reveals two or
more winners simultaneously. Therefore, Pairwise Dropping has the same need
for a good tiebreaker as Schulze's method.
3) Your recent re-wording of your method in terms of repeated application of
the Schwartz set followed by successive elimination of weak defeats, makes
it clear that Schwartz can be seen as an integral part of the method, rather
than just an "add-on" to eliminate ties. Therefore, the desirable
properties (i.e.: criteria compliance) that the method provides might only
be guaranteed in the case of ties if the same logic is extended to apply to
all cases, and not just those where there's a clear Schulze winner.
In conclusion: the use of the Schwartz set tiebreaker seems well justified,
despite the added complexity. Unless a simpler tiebreaker could be devised
that would always pick the same winners, Schwartz appears to be the best
A final thought:
It seems to me that the goal with the Schulze method is (or should be) to
produce the most perfect outcomes possible, despite complexity. Using a
complex tiebreaker with a (relatively) complex method is therefore less of a
problem than it would be to use such a tiebreaker with a method who's
advantage is simplicity (Sequential Dropping). Therefore, although Schwartz
seems to be a good tiebreaker for Schulze's method, Sequential Dropping will
need something easier to define (and Condorcet(EM) probably won't do, for
reasons given above).
From: Markus Schulze <schulze@...-berlin.de>
To: election-methods-list@... <election-methods-list@...>
Date: August 10, 1998 5:37 AM
Subject: Re: Tiebreakers, Subcycle Rules
>usually, if a tiebreaker doesn't lead to a unique
>winner but to a set of potential winners, the
>tiebreaker is restarted among the potential
>I have made the observation, that mostly the Schulze
>method is decisive. But in those cases, in which the
>Schulze method is not decisive, it is very often
>not possible to get a further reduction of the set
>of potential winners by restarting the tiebreaker
>among the potential winners. In those cases, which I
>had observed, a further reduction of the set of
>potential winners was possible only if the
>beat-path Schwartz set of the potential winners was
>used to restart the tiebreaker. The aim of this e-mail
>is to present an example where the Schulze method is
>Example (C.G. Hoag and G.H. Hallett, "Proportional
>Representation," page 502, 1926):
> 3 voters vote A > B > C > D.
> 2 voters vote D > A > B > C.
> 2 voters vote D > B > C > A.
> 2 voters vote C > B > D > A.
> The matrix of defeats looks as follows:
> As A > B > C > D > A, every candidate is in the
> Smith set.
> Via beat-paths, the matrix of defeats looks as
> A:B=5:5 via beat-paths
> A:C=5:5 via beat-paths
> A:D=5:6 via beat-paths
> B:C=7:5 via beat-paths
> B:D=5:5 via beat-paths
> C:D=5:5 via beat-paths
> There is no candidate, who wins against every other
> candidate via beat-paths. Thus, there is no Schulze
> winner. The beat-path Smith set (i.e. the smallest
> set of candidates, such that every candidate in this
> set wins against every candidate outside this set
> via beat-paths) consists of all four candidates,
> because A=B=D=C=A.
> Thus: It is not possible to get a further reduction
> of the set of potential winners simply by restarting
> the tie-breaker among the potential winners.
> The only way to get a further reduction of the
> set of potential winners (without violating clone
> criteria, monotonicity or other desired criteria),
> that I have found, is to calculate the beat-path
> Schwartz set of the potential winners. In the example
> above, the beat-path Schwartz set consists of the
> candidates B and D. If the tiebreaker is restarted
> among the candidates B and D, candidate B wins the
> election, because candidate B wins against
> candidate D 5:4.
- Sequential Dropping, admittedly, can return a tie when 2
candidates have the same vote-count in pairwise comparisons.
But there's no such thing as a method that will never return a
tie when 2 candidates have the same numbers, in terms of vote-counts.
So I'd say that the terms "decisive" vs "indecisive" have to be
used to distinguish between methods that can return a tie
only when 2 voters share a vote-count total, vs methods that
can return a tie without that happening.
In even a city-size public election, it's improbable that
a method that's decisive, as defined above, would return a tie.
Maybe, somewhere in the electoral laws, it says what to do when
Plurality (First Past The Post) returns a tie. If that isn't
currently in the electoral laws where we propose reform, then
it needn't be included in the reform--if it isn't considered needed
now, then it needn't be considered with the new decisive method.
If, on the other hand, such a tiebreaker _is_ included in
current electoral law (draw lots, let the mayor, governor or
President break the tie, or hold another election, etc.),
then that provision should be left as-is, and all that we'd
be proposing to add would be the new method, not the tiebreaker,
since we already have one on the books (by assumption).
So there's no need to complicate the rule of the methods that
are decisive, as defined in this letter, by addding a tiebreaker
to their rules.