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
---- Election-methods mailing list - see http://electorama.com/em for list info
