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

[Warren Smith]

one very simple algorithm for Kemeny ranking
is the "quicksort" method.

That is, you pick a random candidate X.  You then
partition the others into two sets: above and below Xm,
by consulting random voters.
You then recursively sort the two resuitling subsets of candidates.

This method produces random ordering of the candidates selected from a
non-uniform distribution, which is biased in a good direction.  In
particular if the votes
all agree then it will get the best permutation immediately.
The point is that this bias means, that if you keep trying this over
and over, you will find the best permutation faster than if you just
tried uniform-random permutations over and over.

There are many other such heuristic hacks.
One of the better ones seems to be based on Copeland voting plus local search.




On Mon, Sep 12, 2011 at 10:32 AM, Warren Smith <warren.wds at gmail.com> wrote:
>> 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
>



-- 
Warren D. Smith
http://RangeVoting.org  <-- add your endorsement (by clicking
"endorse" as 1st step)
and
math.temple.edu/~wds/homepage/works.html