On 6 Jan 2005 at 15:08 PST, Markus Schulze wrote: > Dear Ted, > > Jobst Heitzig wrote (5 Jan 2005): >> Although this means that it may in bad cases be complicated >> to find p, it is always easy to prove that the result is >> correct once it is found by just showing that it beats each >> of the n pure strategies. This can be done in O(n^2) time >> just as in case of Ranked Pairs or River. By the way, is it >> possible to prove a Beatpath winner in O(n^2) time also? > > I wrote (6 Jan 2005): >> Well, with the Dijkstra algorithm you can calculate >> in O(n^2) time the strengths of the strongest paths from >> candidate A to every other candidate and from every other >> candidate to candidate A. > > You wrote (6 Jan 2005): >> But that still leaves you with another order of n to >> calculate the winner out of n candidates, right? So the >> answer would be no, by all appearances. > > If I have understood Jobst Heitzig's question correctly, > he wants to know whether --when you guess that candidate A > is the winner of my beatpath method-- it is possible to > check in a O(n^2) time whether this guess is correct. > So the answer is yes. >
I guess it depends on what Jobst meant by "prove a Beatpath winner". I was assuming he meant determination of the actual Beatpath winner /ab initio/, not just testing whether or not A is the Beatpath winner. But I can see your interpretation as being equally valid. So the real problem is that his statement is a bit ambiguous. Ted -- Send real replies to ted stern at u dot washington dot edu Frango ut patefaciam -- I break that I may reveal ---- Election-methods mailing list - see http://electorama.com/em for list info