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

[Jameson Quinn]

I wonder if there aren't also Kemeny optimizations similar to IRV's
multiple-elimination, which would work well for real data.

That is to say, that in real life, with enough candidates to make the
problem hard, there are even more likely to be Condorcet losers (also-rans)
than Condorcet winners. By successively peeling off the Condorcet loser, you
could quickly reduce the problem. This much is a clear, easy optimization,
and could easily bring an untractable 60 candidates down to a tractable 20.

The analogy with the IRV case is that if you had a Smith set of condorcet
losers, but they all (by some measure similar to IRV's summing) were "far
enough behind" all other candidates, then it might be safe to treat them as
a bloc, enabling a divide and conquer of the Kemeny problem. Or even if it
weren't 100% safe, it would certainly be a good first guess. This part is
just an intuition of mine, and it would certainly take further thought
before you could use this idea.

Jameson Quinn



2011/9/12 Warren Smith <warren.wds at gmail.com>

> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20110912/991c9c32/attachment-0004.htm>