# [EM] Algorithm to Calculate the Schwartz Set

Bart Ingles bartman at netgate.net
Sun Jan 11 11:27:01 PST 2004

```With only one level of indentation, the scope of the IF and FOR
statements weren't completely clear, although only one interpretation
appeared to make sense.  Is the following restatement accurate?

BEGIN
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 ;
{
else
{
p[i,j] : = false ;
}
}
}
}
for i : = 1 to N do
{
for j : = 1 to N do
{
if ( ( i <> j ) and
( p[j,i] = true ) ) then
{
for k : = 1 to N do
{
if ( ( i <> k ) and
( j <> k ) and
( 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 ) and
( p[j,i] = true ) and
( p[i,j] = false ) ) then
{
Schwartz[i] : = false ;
}
}
}
END

Bart

Markus Schulze wrote:
>
> 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
> ----
> Election-methods mailing list - see http://electorama.com/em for list info

```