[EM] Head to Head Comparison of Election Methods
Markus Schulze
schulze at sol.physik.tu-berlin.de
Thu Jun 10 10:01:21 PDT 1999
Dear Paul,
you wrote (8 Jun 1999):
> I would like to introduce other arguments against the use
> of path voting. Isn't it difficult to impliment? Given 100
> candidates, how long would it take you to find a winner
> (without a computer)?
Actually, the calculation of the _stongest_ path from
candidate A to candidate B is a _shortest_ path problem.
You only have to change the definition of the length
of a path accordingly.
To calculate the strongest path from a given candidate A
to every other candidate, you can use the Dijkstra Algorithm.
If N is the number of candidates, then the Dijkstra Algorithm
has a runtime of N^2. To calculate the strongest path from
every candidate to every other candidate, you can use
the Floyd Algorithm. This algorithm has a runtime of N^3.
******
Suppose that N is the number of candidates.
Suppose that d[X,Y] is the number of voters who strictly
prefer candidate X to candidate Y, then you can calculate
the stongest path p[X,Y] from every candidate X to every
other candidate Y as follows:
for i1:=1 to N
{
for i2:=1 to N
{
p[i1,i2]:=0;
marked[i1,i2]:=false;
}
}
for i1:=1 to N
{
for i2:=1 to N
{
if ((i2<>i1) and (d[i1,i2]>d[i2,i1]))
p[i1,i2]:=d[i1,i2]-d[i2,i1];
}
i3:=1;
while (i3<>0)
{
i3=0;
for i2:=1 to N
{
if (i2<>i1)
{
if ((marked[i1,i2]=false) and (p[i1,i2]>i3))
{
i3=p[i1,i2];
i4=i2;
}
}
}
if (i3>0)
{
p[i1,i4]=i3;
marked[i1,i4]=true;
for i2:=1 to N
{
if (i2<>i1)
{
if ((marked[i1,i2]=false)
and (MIN{p[i1,i4],d[i4,i2]-d[i2,i4]}>p[i1,i2]))
p[i1,i2]:=MIN{p[i1,i4],d[i4,i2]-d[i2,i4]};
}
}
}
}
}
******
To answer your question: The time you need to calculate the
paths from every candidate to every other candidate is
proportional to N^3. As the time you need to calculate the
matrix of pairwise defeats is already proportional to V*N^2,
the time you need to calculate the paths is neglectable
compared to the time you need to calculate the matrix
of pairwise defeats (whether you use a computer or not).
Markus Schulze
More information about the Election-Methods
mailing list