[EM] Head to Head Comparison of Election Methods

[Markus Schulze]

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