[EM] Kemeny update

[Warren Smith]

To reiterate and/or answer some questions:

1. there is no way to find the Kemeny winner that is much faster than
finding the full Kemeny ordering. More precisely, both are NP-complete tasks
so there is no poly-time algorithm for either unless P=NP.

2. Even if some benificent God helpfully informs you of the name of
the Kemeny winner,
or the full Kemeny ordering, then there is no easy way for you
to confirm or deny that claim.   No matter how much supporting information
God provides to you (if it is only a polynomially-bounded number of
bits) -- such
as a proof -- there remains no way to confirm or deny either claim that runs in
polynomial time, unless NP=coNP.  In other words, no short proofs exist.

3. It IS possible to find both the Kemeny
ordering and Kemeny winner, in any election, if you are willing to
devote enough compute time to it.  But the amount of time needed will
exceed any polynomial in the #candidates.  Every currently known
algorithm in the papers I cited fails for easy-to-generate and fairly natural
40-candidate elections, no matter how much time they devote to it
within the limits of their finances.

4. The hardest elections have got Smith set = the full set of candidates.
This is asymptotically not a great restriction since random elections have
Smith set = full set, with probability -->1 in the limit as
#candidates --> infinity.

5. I posed as a challenge, a certain randomized class of 27-candidate elections
which I designed to be hard.
It seemed plausible to me that these 27-candidate elections might be too hard
for current algorithms to reliably provably find the Kemeny winner.
I of course do not know the winners of my challenge elections, since if I did,
then a short proof would exist, which it cannot in maximally hard elections.
So far, nobody has convinced me they are able to answer the Kemeny challenge,
but Kristofer Munsterhjelm has preliminarily claimed in email that
he's been able to solve
one election sampled from my class -- which causes
him to be optimistic that he can answer the challenge.
We'll see -- if that is true, I don't see why K.M. hasn't completed
the job, since
it seems like if he's done what he thinks he has, then he's
done 99% of the programming work
and the remaining 1% is for some reason holding him up.
In the event KM or somebody else successfully
answers the challenge, then I'll be reasonably impressed,
but then I probably can create harder challenges
with greater numbers of candidates -- the goal is to
try to identify the borderline between "hard" and "easy."

6. Richard Fobes has told me and the election methods group in emails
that he's got various
wonderful answers to all these issues, which he sadly has never found
the time to
explain, including in his privately published book on the subject.  I
  (a) just don't believe him.
  (b) some of his "great solutions" seem to be now to recommend a
hybrid of about 3 different
election methods -- which he has nowhere fully defined.   This hybrid
method no longer can
claim either simplicity or any attractive package of nice logical
properties, but it should at least
make it always feasible to compute the winner..

-- 
Warren D. Smith
http://RangeVoting.org  <-- add your endorsement (by clicking
"endorse" as 1st step)