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