[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
More information about the Election-Methods
mailing list