[EM] Condorcet-Kemeny clarifications

[Richard, the VoteFair guy]

On 10/31/2021 5:04 PM, Forest Simmons wrote:
 > So the intractability issue is mostly an inconvenience ...

I'm pleased that you, unlike many others, realize that the 
Condorcet-Kemeny method's long computation time for some possible cases 
is just an inconvenience, not a deal breaker.

 > but the clone dependence is a deal breaker ...

I disagree that a non-zero failure rate for clone independence is a 
deal-breaker.

The Beatpath (aka Schulze) method achieves a zero failure rate for clone 
independence, but I suspect that, as a result, it has a significantly 
higher failure rate for IIA -- Independence of Irrelevant Alternatives.

This characteristic would match what happens with IRV -- instant-runoff 
voting. It has a zero failure rate for clone independence, but it has a 
high failure rate for IIA.

The follow scatter plot shows this pattern:

   https://www.rankedchoiceoregon.org/img/clone_iia_success_rates.jpg

FYI, the upper right corner is where there are zero clone failures and 
zero IIA failures. Most of the plotted methods, with the notable 
exception of plurality, can correctly handle two-candidate cases.

If the Condorcet-Kemeny method were modified to reduce the failure rate 
for clone independence, that would increase its IIA failure rate.

I believe this obviously follows from the fact that Arrow's theorum and 
other proofs tell us that no method can have zero failure rates for all 
of a set of specific desirable fairness criteria. So it follows that 
decreasing the failure rate for one fairness criterion will increase the 
failure rate for at least one other fairness criterion.

This is why I've spent time calculating failure rates and plotting them 
on a scatter plot. I want to know the failure RATES, not just whether 
the failure rate is zero or non-zero.

In my opinion the scatter plot clearly shows that the Condorcet-Kemeny 
method has the best compromise for clone independence and IIA.

Specifically, look at the distance of the points from the upper right 
corner. The Condorcet-Kemeny points are closer than the other methods.

As a clarification about the data for the STAR method: These 
calculations simulate sincere voting -- with no tactical voting -- so 
the points for STAR voting are idealized compared to actual elections 
where tactical voting would be involved.

In contrast, the Kemeny, IPE (Instant Pairwise Elimination), and RCIPE 
(Ranked Choice Including Pairwise Elimination) method are more resistant 
to tactical voting compared to STAR voting, so tactical voting would not 
increase the failure rates for the same cases.

Since these calculations are based on randomly generated ballots, the 
failure rates in real elections would be lower than this data measures. 
That's because most real elections have clearer patterns regarding 
popularity of candidates. So these simulations are like stress tests 
that look at performance under challenging cases.

So, I disagree that "clone dependence is a deal breaker." Yes, clone 
independence is very important, but so is IIA.

In fact, the failure of IRV in Burlington is an IIA failure! I regard 
that IIA failure to be more important than the failure to elect the 
Condorcet winner. Of course in that case if the "Condorcet loser" 
(actually the "pairwise losing candidate") had been eliminated instead 
of eliminating the Condorcet winner, then the Condorcet winner would 
have won.

In other words, it was the presence of an irrelevant candidate (the 
pairwise losing candidate) in the top 3 that blocked the Condorcet 
winner from reaching the top 2.

The elimination of "pairwise losing candidates" is why the RCIPE method 
performs better than IRV.

And because the Condorcet-Kemeny method looks so deeply into ALL the 
ballot preferences on all the ballots, I suspect that it eliminates 
"irrelevant alternatives" better than a method that has a zero failure 
rate for clone independence.

Also consider that when an election has rock-paper-scissors (Condorcet) 
cycles (that involve the most popular candidates), ignoring irrelevant 
alternatives helps the method deal with near clones.

Admittedly I'm less concerned about the handling of *exact* clones 
because those are almost impossible in a real election.

Yet if an election did have almost exact clones, I'm willing to accept 
electing the wrong clone. That's better than if a method gets "confused" 
by an irrelevant alternative.

Richard Fobes
The VoteFair guy


On 10/31/2021 5:04 PM, Forest Simmons wrote:
> Richard,
>
> Twenty years ago I was excited to learn about K-Y because a topologist
> is always on the lookout for interesting metrics on multidimensional
> spaces. The NP complete intractability intrigued me without discouraging
> me because in practice with hundreds of ballots the one among them with
> the minimum average distance to the other ballots would be the actual
> global minimum or very close to it ... after all, billions of such
> averages can be calculated every second ... the problem is the sheer
> number of finish orders that need to be checked to be absolutely sure
> that you got the right one .... for 30 finalists it would be about 2.65
> times 10^32 different orders ... but that is just a messy inconvenience
> for picky people to worry about ... anybody who thinks they have found a
> better solution can easily check it ... and then (if it pans out) easily
> prove it by one additional average distance calculation ... a drop in
> the bucket compared with the millions of such calculations required for
> an exhaustive search for the winning order, even in an election with
> only ten candidates, for example.
>
> So the intractability issue is mostly an inconvenience ... but the clone
> dependence is a deal breaker ... the whole impetus for single winner
> election method reform is the spoiler problem ... an example of clone
> winner failure.
>
> K-Y fails clone winner because the Kemeny distance itself, the
> fundamental basis of the method, is distorted by cloning.
>
> There is a way to declone the Kemeny metric, but at a sacrifice of
> monotonicity and simplicity .... in fact, any Universal Domain metric
> will result in a monotonicity failure, a clone independence failure, or
> both. What is needed is a way of reducing the cost of shuffling clones
> around within their own clone set ... ranking clones equally would do
> that, but with a loss of ability to help decide which of them wins if
> the set had a chance of producing a winner. Also is needed a way for
> non-clones to pass through the clone set at a discount.
>
> However, going outside of Universal Domain by allowing one or more
> approval cutoff (or other virtual) candidates (as ASM does) makes
> decloning more or less automatic as long as clone sets more or less
> respect these cutoffs, and in the case of Kemeny distance, a
> transposition with a cutoff candidate is significantly more costly than
> a normal transposition....[The Kemeny Distance between two candidate
> rankings is the number of transpositions required to convert one into
> the other.]
>
> K-Y started out in the old Universal Domain ... strict rankings
> required... so I am happy to hear that it has been adapted to the
> relaxed UD rules allowing equal rankings and truncations ... but that is
> not far enough to solve the clone problem of K-Y or to distinguish
> between ballot sets resulting from burial attacks and chicken attacks
> ... even clone-free UD constrained methods like River, CSSD, and Ranked
> Pairs are incapable of making that distinction, as I have reminded
> readers of the EM list many times.
>
> The next step in UD rules relaxation should be either general allowance
> of virtual candidates or else Ranked Rankings ballots that allow
> expressions of relative strength of preference to be utilized.
>
> Then, for example, clone free metrics can be used, and Borda can be
> decloned without sacrificing monotonicity. Many of the excuses for the
> (purportedly psychologically stressful) requirement of cardinal ratings
> would vanish.
>
> So that you can judge for yourself rather than rely on what somebody
> else told you about the seriousness of K-Y's spoiler problem, here is an
> example ...
>
> 40 A>B>C
> 30 B>C>A
> 30 C>A>B
>
> A wins according to K-Y rules and any other method anybody has ever
> invented based on Universal Domain rules.
>
> So according to clone-winner, a member of A's clone set should win if A
> is cloned.
>
> Suppose the A faction ranks the clone members in the order a1>a2> ...
> a9, but the other factions rank this clone set in the opposite order
> a9>...>a1. This will be the Kemeny order among the clones ... in fact,
> to change from one clone order to the other takes a minimum of 36
> transpositions... so changing all 60 of the reverse orders would require
> 60*36 while changing the other 40 ballots would require only 40*36. The
> difference is 36*20 or 720, a great cost (i.e.distance) saving by
> rejecting the A faction order.
>
> This puts the A faction ballots at a significant disadvantage compared
> with the other two orders, so one of them will be the winning order
> after the dust clears.
>
> The A faction would claim that a2, a3, ...a9 spoiled the chances of
> their favorite a1.  That's why clone winner failure is referred to as
> the spoiler effect.
>
> That's not the only kind of clone dependence suffered under K-Y ... it
> also suffers from crowding, for example; If B were cloned, and the C and
> B faction ranked the clones in the same order and A in a significantly
> different order, that could cost A the election.
>
> On the other hand if we were not constrained by UD, the factions could vote
>
> 40 a1>a2> ...a9>>B>C
> 30 B>C>>a9>...>a1
> 30 C>>a9>...>a1>>B
>
> for example, and the extra cost of moving {A} around could save the
> first faction order.
>
> Does that help clarify the situation?
>
> Thanks!
>
>
>
> El vie., 29 de oct. de 2021 4:29 p. m., Kristofer Munsterhjelm
> <km_elmet at t-online.de <mailto:km_elmet at t-online.de>> escribió:
>
>     On 10/29/21 8:09 PM, Richard, the VoteFair guy wrote:
>
>     >  > (2) it fails clone independence,
>     >
>     > It has a nice balance between clone independence and independence of
>     > irrelevant alternatives.  "Fails" just means the failure rates are
>     not
>     > zero.
>
>     I'd rather pick a Condorcet method with Condorcet methods' IIA
>     resilience (when there is a CW) *and* full clone independence, than one
>     with the former but not the latter. :-)
>
>     Since that option is available, I mean.
>
>     -km
>     ----
>     Election-Methods mailing list - see https://electorama.com/em for
>     list info
>