[EM] New Smith, Schwartz Algorithms

[Norman Petry]

Dear list members,

There has been some off-list discussion of the algorithms that may be used
to compute the Schwartz Set.  Markus Schulze sent me (and others) an e-mail
which contains algorithms for both Smith and Schwartz that might be very
useful for anyone creating a software implementation of these methods.
Therefore, I obtained his permission to forward the message (below) to the
EM list so that it becomes part of the list archives.  I believe this is the
first Schwartz algorithm to ever be made available on EM.

I currently have working implementations of both Smith and Schwartz in my
voting methods simulator, but these ones supplied by Markus may be more
efficient than what I'm currently using.  Steve Eppley has also sent me a
copy of his software, which also contains a Schwartz algorithm.  I'll be
adapting both of these new versions to "VoteSim" (my simulator) in order to
compare their efficiency against what I'm currently using.

Norm Petry

p.s. I have distributed copies of VoteSim to many of the more active members
of this list, but if you have not received it and would like a copy, please
write to me directly and I will send it to you.

**********

Dear Norman,

you wrote (5 Apr 2000):
> After corresponding with Mike, I *did* develop my own Schwartz
> algorithm, but I'm still interested in seeing how our routines
> compare.  Computing Schwartz has always seemed like a real
> aggravation compared to what's needed for most other methods,
> so if you've found an elegant solution (like your Smith
> algorithm that you posted eons ago), it would interest me.

Let's say that A >= B is a Smith path from candidate A to
candidate B of length 1. Let's say that A >= C(1) >= ... >=
C(n) >= B is a Smith path from candidate A to candidate B of
length n+1.

Let's say that A > B is a Schwartz path from candidate A to
candidate B of length 1. Let's say that A > D(1) > ... >
D(m) > B is a Schwartz path from candidate A to candidate B of
length m+1.

Then the calculation of the Smith winners, the Schwartz winners
and the Landau winners is a "shortest path problem." To
calculate the shortest paths you can use the Floyd Algorithm.
The runtime of the Floyd Algorithm is O(NumberOfCandidates^3).

******

d[X,Y] with X <> Y is the number of voters who strictly prefer
candidate X to candidate Y.

"Smith[X] = true" means that candidate X is a Smith winner.
"Schwartz[X] = true" means that candidate X is a Schwartz winner.
"Landau[X] = true" means that candidate X is a Landau winner.

******

Floyd Algorithm to calculate the Smith winners and the
Landau winners:

for i := 1 to NumberOfCandidates do
   {
    Smith[i] := true;
    Landau[i] := true;
   }

for i := 1 to NumberOfCandidates do
for j := 1 to NumberOfCandidates do
if (i<>j)
   {
    if (d[i,j] >= d[j,i]) then
    dummy[i,j] = 1;
    else
    dummy[i,j] = infinity;
   }

for k := 1 to NumberOfCandidates do
for i := 1 to NumberOfCandidates do
for j := 1 to NumberOfCandidates do
if ((i<>j) and (i<>k) and (j<>k)) then
if (dummy[i,j] > dummy[i,k]+dummy[k,j]) then
dummy[i,j] := dummy[i,k]+dummy[k,j];

for i := 1 to NumberOfCandidates do
for j := 1 to NumberOfCandidates do
if (i<>j) then
   {
    if (dummy[i,j] = infinity) then
    Smith[i] := false;
    if (dummy[i,j] > 2) then
    Landau[i] := false;
   }

******

Floyd Algorithm to calculate the Schwartz winners:

for i := 1 to NumberOfCandidates do
Schwartz[i] := true;

for i := 1 to NumberOfCandidates do
for j := 1 to NumberOfCandidates do
if (i<>j)
   {
    if (d[i,j] > d[j,i]) then
    dummy[i,j] = 1;
    else
    dummy[i,j] = infinity;
   }

for k := 1 to NumberOfCandidates do
for i := 1 to NumberOfCandidates do
for j := 1 to NumberOfCandidates do
if ((i<>j) and (i<>k) and (j<>k)) then
if (dummy[i,j] > dummy[i,k]+dummy[k,j]) then
dummy[i,j] := dummy[i,k]+dummy[k,j];

for i := 1 to NumberOfCandidates do
for j := 1 to NumberOfCandidates do
if (i<>j) then
if ((dummy[i,j] = infinity) and (dummy[j,i] < infinity)) then
Schwartz[i] := false;

******

You can choose "infinity := NumberOfCandidates" because the
length of a Smith path or a Schwartz path can never be
NumberOfCandidates or larger than NumberOfCandidates.

Markus Schulze
schulze at sol.physik.tu-berlin.de
schulze at math.tu-berlin.de
markusschulze at planet-interkom.de