[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.

[Toby Pereira]

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  <-- 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/7c2b3740/attachment-0004.htm>