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