Loading ...
Sorry, an error occurred while loading the content.

Re: Tiebreakers, Subcycle Rules

Expand Messages
  • Markus Schulze
    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
    Message 1 of 9 , Aug 10, 1998
    • 0 Attachment
      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.

      Markus Schulze
    • 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
      Message 2 of 9 , Aug 10, 1998
      • 0 Attachment
        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@...-berlin.de>
        To: election-methods-list@... <election-methods-list@...>
        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
        >
        >
        >
      • Mike Ositoff
        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
        Message 3 of 9 , Aug 10, 1998
        • 0 Attachment
          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.

          Mike Ossipoff
        Your message has been successfully submitted and would be delivered to recipients shortly.