[EM] Kemeny update

[Kristofer Munsterhjelm]

Warren Smith wrote:
> 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.

Is Kemeny independent of Smith-dominated alternatives? Toby said he 
thought he was. If it is, then Kemeny is feasible for practical 
elections because you can just restrict it to the Smith set (and the 
Smith set won't be very large in practice). That is, of course, unless 
the existence of advanced voting methods will make the public vote in 
ways that will lead to a greater Smith set (e.g. candidates who 
otherwise didn't want to split the vote now feel bold enough to show 
up). Still, even so, I can't imagine there would be a 27-member Smith set.

> 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.

The thing holding me up is called employment. As you may have noticed, 
I've been less active on the list as of late -- same reason: work is 
taking up my time and effort.

> 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."

I think I solved a few instances of Warren's 27x27 matrix on [0...1 
billion], but I can't be sure since I can't confirm that my Kemeny cost 
is indeed the least possible. I am, however, assuming that it is, and so 
I'm looking at larger sizes. Since these will be harder, I've thought of 
adding an initialization step where the program tells the IP solver of a 
reasonably low-cost guess. This could speed up the process, thus letting 
me solve greater size matrices in about the same time I currently solve 
27x27. However, I have not actually implemented this initialization yet 
(see above re what's holding me up).

> 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..

Kemeny would probably be best described as an optimization problem - 
that is, something like "the winning sequence is a transitive ordering 
for which the sum of voters who rank each candidate above the candidate 
just below it in the ordering is maximized". Then the actual process of 
optimization is an implementation detail, and may be as simple or 
complex as needed.