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
