[EM] Ernie: What started the discussion about BeatpathWinner algorithms
MIKE OSSIPOFF
nkklrp at hotmail.com
Sat Dec 20 03:18:01 PST 2003
Ernie wrote:
>I wrote:
>Can we chill?
Apparently the answer is "no". :-)
I reply:
Well, I said that I was going to quit replying to Markus, and that then he'd
stop his one-sided debate about something that he claims that I said several
postings back. I fully understand that that discussion has been a waste of
time, and that no one but Markus cares about his fictional claim about what
I allegedly said. I was saying that in my reply.
I agree, then, that the debate about what I said or didn't say several
postings back isn't important. I'm not trying to make it more important than
it was, but I just want to comment that you're talking about it as if was a
genuinely 2-sided problem. But it certainly was not. Markus wanted to keep
on repeating his claim that I claim that Steve's BeatpathWinner algorithm is
the Floyd algorithm, even though I was repeating in each reply that I'm now
making no such claim. Is that a stupid debate, or what? But it wasn't a
2-sided problem. It was a nuisance created and perpetuated by Markus, due to
some peculiar personality defect that he suffers from, which makes him feel
the need to behave in that manner.
You know, I haven't usually been posting here, or taking part in the
discussions. What got me to post was Markus's claim that Steve Eppley's
BeatpathWinner algorithm wouldn't work. Markus, you notice, forgot to tell
us what makes him think that it wouldn't work.
The algorithm looks at each 3-candidate permutation-- i,j, & k. Where
B(i,j) is the strength of the strongest beatpath so far found from i to j,
the program asks if the minimum of B(i,j) & B(j,k) is greater than B(i,k).
If so, then the beatpath made by concatenating the ij and jk beatpaths is
stronger than the ik beatpath, and therefore replaces it as the new value
of B(i,j).
With each pass through the permutations, this algorithm finds a new, longer
beatpath that is stronger than the previous beatpath between the same
endpoints. Eventually the B(i,j) values will be as strong as they can
get--there won't be a stronger beatpath from i to k than the current
B(i,k). When the most recent pass doesn't change any B(i,j) values, the
algorithm has completed its job and it stops.
There's no question about whether it works. It works.
Markus, when he said that it wouldn't work, forgot to tell us what makes him
think it wouldn't work. But that's typical for Markus. Statements that he
can't justify are Markus's stock-in-trade.
By saying on the mailing list that that algorithm wouldn't work, Markus was
misinforming list-members about a practical matter. Of course that's
irresponsible, but Markus doesn't care. It's as if Markus feels a need to
defend the honor of the Floyd algorithm by challenging this other algorithm
that finds strongest beatpaths.
Markus claims that the Floyd algorithm, which finds _shortest_ paths between
graph-nodes, can be modified so that it finds strongest beatpaths. He seems
to be implying that if the Floyd algorithm can do its job in one pass, when
its job is finding the shortest path, then it can also do its job in one
pass when its job is finding the strongest beatpaths between the ordered
pairs of candidates.
I haven't challenged that belief. Maybe it's true, maybe not. I don't care.
Markus says that that one-pass algorithm is faster than Steve's algorithm.
Fine, if true. I have no argument with that. But Steve's algorithm isn't
going to take problematically long counting any actual election, and so it's
reallly every bit as good as the one-pass algorithm, even if the one-pass
algorithm works for finding strongest beatpaths.
But the problem has been that Markus hasn't been content to recognize a
solution different from his favorite as being ok. Markus is just being
Markus again. Is it really necessary to fight about these 2 algorithms? Of
course not. I've answered Markus's mistaken claim, and I'm not interested in
fighting about it or debating it with Markus.
What if it's true that Markus's one-pass algorithm works for finding
strongest beatpaths, and does so faster than Steve's algorithm? Does Markus
believe that, therefore, Steve's algorithm shouldn't be used or proposed, or
sent to people who ask for an implementation algorithm? Steve's algorithm
obviously works. If Markus's one-pass algorithm works, it isn't as obvious.
I suppose that, when someone asks me for an implementation algorithm, I
could send them the one-pass algorithm, along with a proof that it works
(assuming that it does). But the validity of Steve's algorithm is more
obvious, and it woirks perfectly well. If it takes longer, that won't make
any difference, in actual elections, with today's fast computers. Will
Steve's program take 25 seconds instead of 5? Is that really a problem if it
does? I continue to send out Steve's algorithm when someone asks for one,
because it's obvious that it works. I don't even know if the one-pass
algorithm works for finding strongest beatpaths. And, if it does work, I'd
rather not have to prove that less obvious fact to people who request an
implementation algorilthm.
Mike Ossipoff
_________________________________________________________________
Check your PC for viruses with the FREE McAfee online computer scan.
http://clinic.mcafee.com/clinic/ibuy/campaign.asp?cid=3963
More information about the Election-Methods
mailing list