[EM] Algorithm to Calculate the Schwartz Set

[Markus Schulze]

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