[EM] Condorcet-Kemeny clarifications (was: Condorcet-Kemeny calculations are not NP-hard)

[Richard Fobes]

On 9/29/2011 11:06 AM, Toby Pereira wrote:
 > Richard Fobes <ElectionMethods at VoteFair.org> wrote:
 > > Some people have questioned why it is worth doing Condorcet-Kemeny
 > > calculations when there are faster Condorcet methods. The answer is
 > > that Condorcet-Kemeny results offer lots of advantages, including
 > > one named advantage that is currently underappreciated and a
 > > significant advantage that has not yet been named or widely
 > > recognized.

 > This is very cryptic. What is this named advantage and why haven't
 > > you named it here? Is the unnamed advantage also indescribable?

The named criteria is "reinforcement".  It requires that if all the 
ballots are divided into separate races and the overall ranking for the 
separate races are the same, then the same ranking occurs when all the 
ballots are combined.

As far as I know, the Condorcet-Kemeny method is the only voting method 
that meets this criteria.

Markus Schulze claims that this criteria is not important, yet recently 
he removed from the discussion page of "his" Wikipedia "Schulze Method" 
article the fact that "his" Condorcet-Schulze method does not meet the 
reinforcement criteria:

http://en.wikipedia.org/w/index.php?title=Talk%3ASchulze_method&action=historysubmit&diff=454246530&oldid=439262253

One of the reasons I regard the reinforcement criteria as 
underappreciated is that, unlike the other voting-method "fairness" 
criteria, there is no Wikipedia article describing the reinforcement 
criteria.

Of course many (most?) single-winner voting methods do not produce a 
full ranking (or are not designed to do so), and only identify a single 
winner, so it can be claimed that the reinforcement criteria is not 
relevant to single-winner methods.  In contrast, my claim is that one of 
the strengths of the Condorcet-Kemeny method is that it not only 
"correctly" (see below) identifies the most popular candidate/choice, 
but it also "correctly" identifies the second-most popular 
candidate/choice, and so on down to the least-popular candidate/choice.

Note that correctly identifying the _least_-popular choice is very 
relevant in TV's American Idol contest because each week the "least 
popular" singer is eliminated.  To educate people that the contestant 
with the fewest plurality ("first-choice") votes is not necessarily the 
least popular, I conduct an unofficial weekly VoteFair American Idol 
poll, which attracts about one thousand (unique) voters each week.

As a reminder, here are the voting criteria that the Condorcet-Kemeny 
method meet:

* Condorcet criterion
* Majority criterion
* Non-imposition
* Non-dictatorship
* Unrestricted domain
* Pareto efficiency
* Monotonicity
* Smith criterion
* Independence of Smith-dominated alternatives
* Reinforcement
* Reversal symmetry

The other item, the "unnamed" criteria, relates to the simplicity of the 
Condorcet-Kemeny method.  Of course Approval voting and Range voting are 
much simpler, yet Majority Judgment and the Condorcet-Schulze method are 
more complex, and I am working on a way to quantify this "simplicity" 
dimension, but I have not yet fully developed this idea.

The reason I didn't explain these points in the earlier message is that, 
as you can see, they require lots of explanation, which would have 
distracted from the main topic of that message, which was calculation time.

 > > The only valid disadvantage is that in very rare cases it fails the
 > >"independence of clones" criteria, yet this perceived disadvantage
 > > does not yield unfair results if all aspects of VoteFair Ranking
 > > are used.

 > I'm not sure how rare it would be myself (an exact clone isn't
 > required for a non-cloneproof method to have problems).

Keep in mind that the Condorcet-Kemeny method can only fail the 
independence of clones criteria when there is circular ambiguity (i.e. 
no Condorcet winner).  In such cases I contend that it is debatable as 
to who the winner really should be.

To clarify this point, imagine a group of people around a large table 
being asked to elect a president.  Imagine that in response to being 
asked "who is your first choice?" each person points to the person on 
the right.  Then imagine that in response to being asked "who is your 
second choice?" each person points to the person on the left.  Finally 
imagine that in response to being asked "who is your third choice?" each 
person points to the person at the head of the table.  In this situation 
IRV advocates would claim that the person at the head of the table does 
not deserve to win because he or she was the first choice of only one 
voter.  This kind of circular ambiguity, which is easily handled by the 
Condorcet-Kemeny method, may involve electing the "wrong" candidate 
according to the independence of clones criteria, but in such cases does 
the "correct" clone deserve to win?  This is debatable.

My point is that the conditions under which the Condorcet-Kemeny method 
fails the independence of clones criteria involve circular ambiguity, 
which in turn can involve lots of head scratching about who really 
deserves to win.

 > So VoteFair doesn't use the Kemeny method then?

VoteFair popularity ranking is mathematically equivalent to the 
Condorcet-Kemeny method.  VoteFair popularity ranking, which I created 
without knowing about the Condorcet-Kemeny method, calculates a sequence 
score that is the sum of all the pairwise counts that _support_ that 
sequence, and the sequence with the _highest_ score indicates the 
overall ranking.  The original method described by Kemeny calculates a 
sequence score that is the sum of all the pairwise counts that _oppose_ 
that sequence, and the sequence with the _lowest_ score indicates the 
overall ranking.

I apologize for the long delay in replying to this message.  Jameson 
Quinn and I have been attempting to refine a couple of controversial 
sentences in the Declaration of Election-Method Reform Advocates (which 
I think we are close to achieving, and that edit will be posted here) 
and, as I've said before, I don't earn income from anything related to 
election-method reform.

Richard Fobes