Maybe Schulze is decisive.

[Norman Petry]

Dear Markus,

Thank-you for providing a proof of the impossibility of 3-candidate cycles
in a beat-path matrix.

This result is interesting, because it suggests that if your proof could be
generalised to apply to cycles of any size, this would greatly simplify the
calculation of the Schwartz-set tiebreaker that is sometimes required by
your method.  I _have_ finally devised a general-purpose Schwartz algorithm
that I'm reasonably happy with which could be used.  However, it's
necessarily slower and more complex than would be needed for the special
case in which cyclic patterns are known to be absent.

Unless I'm mistaken, in the absence of cycles the beat-path Schwartz set
simply consists of all the unbeaten candidates, since any beaten candidate
(B) cannot indirectly beat the candidate it's beaten by (A), otherwise a
cycle would be present.  If A beats B but not vice-versa, then B cannot be
in the Schwartz set, by definition.  In the few examples I have seen in
which there is no "Schulze Winner" (by this I mean, one candidate who beats
all other candidates in the beat-path matrix), I have never encountered
cycles.

While testing your method, have you ever observed cycles in a beat-path
matrix?  If so, I'd be interested in seeing one, particularly to determine
how other methods which are being discussed (such as Goldfish 0.3, SD)
handle them.  If not, do you think that cycles of any size are impossible?


Norm Petry

-----Original Message-----
From: Markus Schulze <schulze at sol.physik.tu-berlin.de>
To: npetry at sk.sympatico.ca <npetry at sk.sympatico.ca>
Cc: ntk at netcom.com <ntk at netcom.com>
Date: August 12, 1998 3:14 AM
Subject: Re: Maybe Schulze is decisive.


>Dear Norman, dear Mike,
>
>the aim of this e-mail is to prove, that the
>following situation is _not_ possible:
>Candidate A defeats candidate B via beat-paths;
>candidate B defeats candidate C via beat-paths;
>candidate C defeats candidate A via beat-paths.
>
>*****
>
>Prove:
>
>First: Suppose, that candidate A defeats
>candidate B via beat-paths ab:ba. Suppose, that
>candidate B defeats candidate C via
>beat-paths bc:cb. Suppose, that candidate C
>defeats candidate A via beat-paths ca:ac.
>Then, I get the following equations:
>
>   ( 1) ab > ba
>   ( 2) bc > cb
>   ( 3) ca > ac
>
>Without loss of generality, I can assume, that
>candidate A is chosen in such a way, that
>his Schulze win against candidate B is larger
>or equal to the Schulze win of candidate B
>against candidate C and that the Schulze win of
>candidate A against candidate B is larger or equal
>to the Schulze win of candidate C against
>candidate A. Thus, I get the following equations:
>
>   ( 4) ab >= bc
>   ( 5) ab >= ca
>
>*****
>
>Second: I get the following equations:
>
>   ( 6) min{ab;bc} <= ac
>   ( 7) min{ac;cb} <= ab
>   ( 8) min{ba;ac} <= bc
>   ( 9) min{bc;ca} <= ba
>   (10) min{ca;ab} <= cb
>   (11) min{cb;ba} <= ca
>
>Example: If min{ab;bc} > ac, then I could find a
>stronger beat-path from candidate A to candidate C
>by going from candidate A to candidate B and then
>from candidate B to candidate C. This would be a
>contradiction to the assumption, that ac is already
>the strength of the strongest beat-path from
>candidate A to candidate C.
>
>*****
>
>Third: As I assumed without loss of generality, that
>(4) ab >= bc and as (2) bc > cb, I get ab > cb.
>If I insert ab > cb in equation (10) I get:
>
>   (12) ca <= cb
>
>As I assumed without loss of generality, that
>(5) ab >= ca and as (2) ca > ac, I get ab > ac.
>If I insert ab > ac in equation (6) I get:
>
>   (13) bc <= ac
>
>Thus I get:
>
>   (12) ca <= cb
>   ( 2) cb <  bc
>   (13) bc <= ac
>
>Thus I get:
>
>   ca < ac
>
>But this is a contradiction to (3). Thus it is not
>possible, that simultaneously candidate A has a
>Schulze win against candidate B, candidate B has a
>Schulze win against candidate C, and candidate C has
>a Schulze win against candidate A.
>
>Markus Schulze
>
>