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

[Ted Stern]

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