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

Andy Jennings elections at jenningsstory.com
Mon Sep 12 11:04:33 PDT 2011


Kemeny has a couple things going for it:

1. Peyton Young argues here (
http://www.econ.ucsb.edu/~tedb/Courses/UCSBpf/readings/PeytonYoungCondorcet.pdf)
that it is probably the rule that Condorcet himself had in mind.

2. It is mathematically simple and elegant, so it is easier to prove things
about it than the other Condorcet methods.  Hence, it appears in lots of
theoretical papers.

In my opinion, these are the reasons that it is one of the "frontrunners"
among the Condorcet methods.  It is interesting that neither of these
reasons relates to its performance (either in terms of worst-case runtime or
criterion compliance), so I am fine that we question it here.  However, I
don't know that we can ever dethrone it as one of the "frontrunners", so
maybe it's worth leaving in the declaration on those grounds alone...

I, personally, feel that Warren's points are well-made and that NP-complete
worst case behavior is of some concern, but it's not a deal-killer for me.
 Also, Kemeny is not cloneproof, but I think the fault is sufficiently
difficult to exploit that it will be very rare.  Famous last words, right?
 So my mind can be changed on these opinions.  I'm just saying at this point
that I, personally, feel that Kemeny is good enough.

But I'm interested to hear from others...

Andy





On Mon, Sep 12, 2011 at 10:07 AM, Toby Pereira <tdp201b at yahoo.co.uk> wrote:

> How much support does the Kemeny method actually have? I know Richard Fobes
> supports it obviously. But as far as I understand, is problems run deeper
> than runtime. Like not being cloneproof.
>
> When I first found out about Condorcet methods, I thought it looked like
> the most "natural" one and seemed the best to me. It has a "maximum
> likelihood estimator" property, but that doesn't apply to real life. It
> assumes that there is "an objectively 'correct', but unknown preference
> order over the alternatives, and voters receive noisy signals of this true
> preference order" (from Wikipedia). In real life, people aren't all working
> towards trying to find the "objectively best" candidate in this way.
>
> It may be the best (ignoring runtime) at finding a winner when voters are
> "neutral" and not all with their own opinions, and also I've heard that it's
> good at producing a full order. But in single-winner elections those don't
> apply. Other Condorcet systems can find a full order anyway, even if they
> aren't as "good" at it. And you wouldn't want to decrease the quality of the
> winner in a single-winner method just to improve the rest of the order.
>
> Also, I wonder where Kemeny and others (such as Schulze) differ in the
> winner, why they differ. Is it in most cases because Kemeny-Young is not
> cloneproof? If so, that's a point against Kemeny-Young. Is it to do with
> margins/winning votes? That's probably not an important factor anyway,
> because methods can generally be converted from winning votes to margins or
> vice versa.
>   *From:* Jameson Quinn <jameson.quinn at gmail.com>
> *To:* electionscience at googlegroups.com
> *Cc:* Kristofer Munsterhjelm <km_elmet at lavabit.com>; election-methods <
> election-methods at electorama.com>
> *Sent:* Monday, 12 September 2011, 16:00
> *Subject:* Re: [CES #3605] Re: [EM] Kemeny Condorcet method. Apparently
> not a good choice for those of us who want to know who won in our lifetimes.
>
> 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 <http://rangevoting.org/>  <-- add your
> endorsement (by clicking
> > "endorse" as 1st step)age/works.html
> >
>
>
>
> --
> Warren D. Smith
> http://RangeVoting.org <http://rangevoting.org/>  <-- add your endorsement
> (by clicking
> "endorse" as 1st step)
>  and
> math.temple.edu/~wds/homepage/works.html
>
>
>
>
>
> ----
> Election-Methods mailing list - see http://electorama.com/em for list info
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20110912/1aaf1b6b/attachment-0004.htm>


More information about the Election-Methods mailing list