[EM] There is always a Condorcet Winner! (among all lotteries of candidates :-)

[Markus Schulze]

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