[EM] Fast Condorcet-Kemeny calculations -- in polynomial time

[Richard Fobes]

On 12/21/2011 2:24 PM, Warren Smith wrote:
 > I have earlier cited published proofs this problem is NP-complete.  If
 > Fobes has a polynomial time algorithm he has proven P=NP ...


P does _not_ equal NP -- as far as I know.

Instead, Condorcet-Kemeny calculations are not really NP-hard.

If someone claims to have proved that the calculations are NP-hard, they 
are standing on thin ice.

NP-hard problems require that every possibility be tested in order to 
know the characteristics of each -- and every -- possibility.

In contrast, Condorcet-Kemeny calculations do not require that every 
possibility be checked in order to find the largest sequence score.

Consider the analogy of finding the highest mountain peak in a region. 
It is not necessary to go to every location (in the region) and measure 
the elevation in order to verify that the highest elevation has been found.

Yes, a _proof_ that the highest sequence score has been found may be 
NP-hard.  Yet, as the calculation descriptions point out, that becomes 
an issue only in situations that are like finding the highest sand dune 
in a desert.  In such cases different experts will argue about which 
candidate really should have won.  More specifically, there will be 
arguments about whether Condorcet-Kemeny method results are better than 
results from using approval voting or range voting.  In such cases one 
meaningful alternative is to declare a tie, and then use whatever 
tie-breaking rule (such as a runoff election) is mandated.

To respond to yet other comments (below) from Warren Smith:

As for why I have not measured the exact calculation times, they vary. 
They depend on the data.

For example, when a case has a Condorcet winner and each other choice 
pairwise beats all the lower-ranked choices, the calculation time is 
less.  For such cases the choice-specific pairwise-score estimation, 
followed by the insertion-sort algorithm, immediately reaches a stable 
state.

In contrast, resolving sequence-score ties takes time.  Note that this 
occurs _after_ the highest sequence score has been found.  Remember that 
resolving sequence-score ties is part of VoteFair popularity ranking, 
and not part of Condorcet-Kemeny calculations -- which do not specify 
how to resolve sequence-score ties.

To test this algorithm I have used data collected at the VoteFair.org 
site, so admittedly my testing has been biased toward real-life data 
rather than simulations.

Also I tested the VoteFair representation ranking calculations, and this 
algorithm repeatedly does VoteFair popularity ranking with different 
ballot adjustments, and that significantly increases the number of tests 
and, therefore, the calculation time.

Even when I run thousands of real-data cases through the VoteFair 
popularity ranking algorithm, the calculation time is less than about 
five minutes.  (Currently it takes longer to split and join the text and 
data.)

As I've said before, I accepted Warren Smith's challenge of calculating 
results for a case of 50 (or maybe it was 100) choices -- if he will 
supply ballot data instead of just pairwise counts (which may not 
correlate with an actual possible voting scenario).  I too will be 
interested in more carefully measuring that calculation time.  The exact 
number of seconds won't matter, but the fact that it can be done in less 
than an hour (or in less than a day if this estimate is mistaken) is 
enough to prove that it doesn't take a lifetime -- as Warren claims.

BTW, my reason for copyrighting is to protect the text from being used 
out of context or being "copied" with inaccurate modifications.

Warren implies that I think that "[t]hings like "pseudocode" and 
"proofs" evidently are unnecessary".  Quite the contrary.  Even better 
than pseudocode is real code, and that's what I am sharing on an 
open-source basis.  Anyone can run the code (unlike psuedocode).

As for proofs, the field of election methods is still in it's infancy. 
If it were better developed, then proofs of the unfairness of using 
single-mark ballots would have been written and taught in schools, and 
as a consequence single-mark ballots would have been banned long ago.

Also note that voting methods are still being crudely categorized using 
a checklist instead of quantitatively estimating _how_ _often_ each 
fairness criteria is violated for each method.  I think that this 
advancement would be a great graduate-student thesis.  And if this is 
done, I suggest that some of the strengths of the Condorcet-Kemeny -- 
such as reinforcement -- be taken into account (by measuring how often 
other methods fail this test -- which the Condorcet-Kemeny method always 
satisfies).

Warren, I thank you for complimenting my writing style with the words 
"English prose poetry-like descriptions".  One of my past professions 
involved lots of technical writing (specializing in documenting 
especially complex technology).  It's a useful skill.  But I don't use 
it to obfuscate descriptions.  In fact, clear explanations are easier to 
find fault with -- if there is fault -- than obscure and ambiguous wordings.

As for Warren's wager, no one would (or should) take it.  When I was 
told about the Clay prize I looked into what the prize was about, I 
learned more about NP-hard problems, and I recognized that 
Condorcet-Kemeny calculations are _not_ NP-hard.  The problems that are 
NP-hard really do require checking every possibility in order to find 
the optimum solution.

Richard Fobes


On 12/21/2011 2:24 PM, Warren Smith wrote:
> I have earlier cited published proofs this problem is NP-complete.  If
> Fobes has a
> polynomial time algorithm he has proven P=NP and
> should immediately collect his million dollar Clay Institute prize
> for the greatest mathematical achievement so far this century.
>
> However, I doubt it. I think it far more likely that Fobes is a fraud --
> as has been every other person who has claimed to have invented a
> polytime algorithm for an NP-hard problem
> (and there have been dozens -- they generally serve as a source of amusement for
> computer scientists who enjoy laughing at them).
>
>> Calculating a "complex" case with 12 choices is so fast that
>> I haven't bothered to time the calculations.
>
> --how touching.  Actual computer scientists time their calculations
> versus problem size, however.
>
>> The estimated time for calculating results for 50 choices (!) is less
>> than a minute -- which is far less than a "lifetime".
>
> --quite odd that Fobes had to "estimate" this, why not actually
> spend those few minutes to actually time it?
>
> --Looking at Fobes' so-called descriptions of his so-called algorithms,
> it is rapidly apparent that Fobes blatantly disregards
> and holds in contempt, every computer science paper that has ever presented
> an algorithm before.  Things like "pseudocode" and "proofs"
> evidently are unnecessary for
> a great and revolutionary thinker like Fobes, who instead resorts to
> "English prose poetry-like descriptions" reminiscent of an illustrated
> edition of
> Charles Dickens.
>
> And it all is carefully "copyrighted."
>
> But: might anybody be interested in a little wager?
> If Fobes successfully collects the million dollar Clay Prize by the end of 2012
> for his successful proof P=NP, I
> offer to pay whoever wagers versus me, $10000.
> If not, though, I get the $10000.
>
> Any takers?
>