[EM] Floyd-Warshall algorithm - variations

[Ernest Prabhakar]

Hi Markus,

On Dec 19, 2003, at 6:52 PM, Markus Schulze wrote:
> I consider the margins of defeats only when both defeats have the same
> absolute number of votes for the winner. The aim is to make the method
> more decisive without sacrificing any of the desired properties.

Ah, okay, that was hard for me to deduce from the original algorithm, 
where it seemed like you were primarily calculating margins. My 
implementation of this for object-oriented Dijkstra (using real Python 
code this time) is at the end.    The relevant section is here, where 
'rstrength', or relative strength, is used for the margin:

     # reset neighbor if unset or if new values would be better
     if next not in queue or\
        strength > self.strengthVS(next) or\
        strength == self.strengthVS(next) and rstrength > 
self.rstrengthVS(next):
       self.strengths[next.id] = strength
       self.rstrengths[next.id] = rstrength
       if next not in queue: queue.append(next)
       next.path[self.id] = current # remember beatpath predecessor
     #endif

That is, use the current calculated values for the strength of the path 
to this node if any of the following three conditions is true:
a) there are no other calculated values for this node ("next not in 
queue")
b) the strength (total votes) is better than the prior value ("strength 
 > self.strengthVS(next)")
c) the strength is equal, but the margin (rstrength) is better 
("rstrength > self.rstrengthVS(next)")

Does that look right to those who know what's going on? (apologies to 
people who don't do Python, but as you can see the code is vastly more 
compact, and I think far easier to follow).

I'm working on a well-formatted implementation of all this, which I 
hope will displace the other Condorcet implementations out there (and 
satisfy all the critics :-).

> You wrote (19 Dec 2003):
>> Also, is there a particular mathematical or anti-strategic reason for
>> randomizing the tie-breaking round, rather than just automatically
>> picking the candidate who would have the best chance of winning such
>> a random draw?
>
> Plurality as a tie-breaking strategy violates independence of clones.

Interesting.  Are you asserting that there is no deterministic 
tie-breaking algorithm that resists clones?  Does this mean that we 
really do need to keep track of all the actual ballots, and not just 
the Condorcet matrix?

-- Ernie P.

def findStrengths(self):
  "Find strongest paths to all candidates using Dijkstra, starting from 
self"
  self.initStrengths(max(self.votes)) # 'max_votes' is equivalent to 
'unset'
  current = self
  final = []
  queue = []

  while current:
   # declare this node's values as final
   final.append(current)

   # relax each of the neighbors (if not final)
   for next in current.beats:
     if next in final: continue

     # calculate (relative) strength, if this node were part of path
     strength = min(self.strengthVS(current), current.votesVS(next))
     rstrength = min(self.rstrengthVS(current), current.marginVS(next))

     # reset neighbor if unset or if new values would be better
     if next not in queue or\
        strength > self.strengthVS(next) or\
        strength == self.strengthVS(next) and rstrength > 
self.rstrengthVS(next):

	      self.strengths[next.id] = strength
	      self.rstrengths[next.id] = rstrength
	      if next not in queue: queue.append(next)
	      next.path[self.id] = current # remember beatpath predecessor
     #endif
   #end for

   # Remove and return weakest node from queue
   current = self.smallest(queue)
  #end while
#end findStrengths