Tiebreakers, Subcycle Rules

[Norman Petry]

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
Schwartz.

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
choice.

***

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).


Norm Petry


-----Original Message-----
From: Markus Schulze <schulze at sol.physik.tu-berlin.de>
To: election-methods-list at eskimo.com <election-methods-list at eskimo.com>
Date: August 10, 1998 5:37 AM
Subject: Re: Tiebreakers, Subcycle Rules


>Dear participants,
>
>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
>winners.
>
>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
>indecisive.
>
>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:
>
>   A:B=5:4
>   A:C=5:4
>   A:D=3:6
>   B:C=7:2
>   B:D=5:4
>   C:D=5:4
>
>   As A > B > C > D > A, every candidate is in the
>   Smith set.
>
>   Via beat-paths, the matrix of defeats looks as
>   follows:
>
>   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.
>
>Markus Schulze
>
>
>