Re: RFD: Reviving Constitutional amendment: Smith/Condorcet vote tallying

[Markus Schulze <markus.schulze@alumni.tu-berlin.de>]

Dear Manoj, dear Raul, dear Anthony,

I have added the original description (1997) of this method.
I hope that it will make the idea behind this method clearer.

***********************************************************************

Axiomatic Definition:

   Suppose, that d(Ci,Cj) is the number of voters who strictly prefer
   candidate Ci to candidate Cj. A "beat path from candidate A to
   candidate B" is an ordered set of candidates C1,...,Cn such that
   candidate A is identical to candidate C1, such that candidate B
   is identical to candidate Cn, and such that
   d(Ci,C(i+1)) - d(C(i+1),Ci) >= 0 for all i = 1,...,(n-1).

   S1(C1,...,Cn) : = min{ d(Ci,C(i+1))                | i = 1,...,(n-1)}.
   S2(C1,...,Cn) : = min{ d(Ci,C(i+1)) - d(C(i+1),Ci) | i = 1,...,(n-1)}.

   P1(A,B) : = max { S1(C1,...,Cn) | C1,...,Cn is a beat path from A to B}.
   P2(A,B) : = max { S2(C1,...,Cn) | C1,...,Cn is a beat path from A to B;
                                     S1(C1,...,Cn) = P1(A,B)}.

   When there is no beat path from candidate A to candidate B, then
   P1(A,B) := -1. [P2(A,B) can be defined arbitrarily when there is
   no beat path from candidate A to candidate B.]

   When C1,...,Cn is a beat path, then S1(C1,...,Cn) is called the
   "absolute strength of the beat path C1,...,Cn" and S2(C1,...,Cn)
   is called the "margin of the beat path C1,...,Cn".

   A "Schulze winner" is a candidate A such that
   (P1(A,B) > P1(B,A)) or ((P1(A,B) = P1(B,A)) and (P2(A,B) >= P2(B,A)))
   for every other candidate B.

   The "Schulze set" is the set of all Schulze winners. [It can be proven
   that there is always at least one Schulze winner.] If there is more
   than one Schulze winner, the elector with the casting vote picks the
   winner from the Schulze set.

***********************************************************************

Algorithmic Definition with the Floyd Algorithm:

   Input: d(i,j) is the number of voters who strictly
   prefer candidate i to candidate j

   for (i : = 1; i <= NumberOfCandidates; i++)
   for (j : = 1; j <= NumberOfCandidates; j++)
   if (i <> j) then
      {
       if (d(i,j) >= d(j,i)) then
       P1(i,j) : = d(i,j);
       else
       P1(i,j) : = -1;

       P2(i,j) : = d(i,j) - d(j,i);
      }

   for (i : = 1; i <= NumberOfCandidates; i++)
   for (j : = 1; j <= NumberOfCandidates; j++)
   if (i <> j) then
   for (k : = 1; k <= NumberOfCandidates; k++)
   if ((i <> k) and (j <> k)) then
      {
       s : = min(P1(j,i),P1(i,k));
       t : = min(P2(j,i),P2(i,k));
       
       if ((P1(j,k) < s) or
          ((P1(j,k) = s) and (P2(j,k) < t))) then
          {
           P1(j,k) : = s;
           P2(j,k) : = t;
          }
      }

   for (i : = 1; i <= NumberOfCandidates; i++)
      {
       winner(i) : = true;
       for (j : = 1; j <= NumberOfCandidates; j++)
       if (i <> j) then
       if ((P1(i,j) < P1(j,i)) or
          ((P1(i,j) = P1(j,i)) and (P2(i,j) < P2(j,i)))) then
       winner(i) : = false;
      }

   If there is more than one candidate with "winner(i) = true",
   the elector with the casting vote picks the winner from all
   the candidates with "winner(i) = true".

Markus Schulze