[EM] Ernie: What started the discussion about BeatpathWinner algorithms

[MIKE OSSIPOFF]

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