[EM] Algorithm to Calculate the Schwartz Set
Markus Schulze
markus.schulze at alumni.tu-berlin.de
Sun Jan 11 03:22:02 PST 2004
Hallo,
the Schwartz set can be calculated with the Floyd algorithm
in a runtime of O(N^3), where N is the number of candidates.
It cannot be said frequently enough that the order of the
indices in the triple-loop of the Floyd algorithm is _not_
irrelevant.
Input: d[i,j] with i <> j is the number of voters who strictly
prefer candidate i to candidate j.
Output: "Schwartz[i] : = true" means that candidate i is
a Schwartz winner.
"Schwartz[i] : = false" means that candidate i is not
a Schwartz winner.
for i : = 1 to N do
for j : = 1 to N do
if ( i <> j ) then
{
if ( d[i,j] > d[j,i] ) then
p[i,j] : = true ;
if ( d[i,j] <= d[j,i] ) then
p[i,j] : = false ;
}
for i : = 1 to N do
for j : = 1 to N do
if ( i <> j ) then
if ( p[j,i] = true ) then
for k : = 1 to N do
if ( i <> k ) then
if ( j <> k ) then
if ( p[i,k] = true ) then
p[j,k] : = true ;
for i : = 1 to N do
Schwartz[i] : = true ;
for i : = 1 to N do
for j : = 1 to N do
if ( i <> j ) then
if ( p[j,i] = true ) then
if ( p[i,j] = false ) then
Schwartz[i] : = false ;
Markus Schulze
More information about the Election-Methods
mailing list