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