[EM] Kemeny Condorcet method. Apparently not a good choice for those of us who want to know who won in our lifetimes.

[Warren Smith]

> Well, I can only speak from experience, but I've implemented the
> Kemeny-Young method in quadelect as an integer program, and the vast
> majority of the time (more than 90%), the LP linearization gives an optimal
> result.
>
> NP-complete problems usually have phase transitions, i.e. there are some
> regions of the problem that are easy and some that are very hard. It seems
> that at least for the ballots generated by my opinion-space model, the
> Kemeny instances tend to end up on the easy side.
>
> I could be wrong, of course, so any independent verification would be
> welcome.

--can you give more details?
For example, if you make N candidates, what percentage of time do you
succeed, as a function of N?
[make a graph or table for N=3..100, say]

If you have in mind the idea that this is an integer program, but the
fact it is an INTEGER rather than LINEAR program happens not to matter
in 90% of your
cases (I think that is what you are saying) that's nice,
but you lose for 10% of your cases.

The Conitzer et al paper (a local copy is now at
   http://rangevoting.org/AAAI06-099.pdf )
had a randomized method for generating Kemeny elections which involved
a parameter called the "consensus probability."

Vaguely speaking, votes tended to be more-alike when this parameter
was near 1, but tended to differ a lot when it was near 0.   They
found (page 624, footnote 2)
that Kemeny problems became harder for their algorithms when the
parameter small.  There may indeed be a phase transition, and roughly
the threshhold appears to be about 0.58 for this parameter,
below that and the problems get hard.

The other paper, now available at
  http://rangevoting.org/ColemanWirthKemeny.html
also has its own parameter of this ilk and also finds as
it is moved the problems tend to get harder for their
(different) algorithms, but this was not explored much
and the paper is written very badly.

I also just now found still another paper,
  Frans Schalekamp, Anke Van Zuylen:
Rank aggregation, together we're strong,
Proceedings of the Eleventh Workshop on Algorithm Engineering and
Experiments (ALENEX 2009)
paper #38, available here:
   http://rangevoting.org/alx09_004_schalekampf.pdf

it is much better written Coleman+Wirth
but it is similarly trying to review and tests lots of different
algorithms for Kemeny.   Unfortunately it tests on less kinds of data
and with poorer description of it, so I'm pretty unsatisfied with both
papers.

Anyhow, this paper agrees with K.Munsterhjelm that they too find that
"almost all the time" (on their datasets)
the linear program yielded optimal integer solutions.
So it would appear that their data lies on the easy side of the phase
transition.

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