[EM] Floyd-Warshall algorithm - variations
Ernest Prabhakar
drernie at mac.com
Sat Dec 20 19:58:08 PST 2003
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
More information about the Election-Methods
mailing list