[EM] Condorcet-Kemeny clarifications

[Kristofer Munsterhjelm]

On 11/3/21 5:02 AM, Richard, the VoteFair guy wrote:
> 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.

I wouldn't trust IRV's clone independence all that much. James 
Green-Armytage showed that, although IRV strictly passes clone 
independence, it has serious candidate exit incentive, which means that 
some allied candidates have an incentive to drop out, similar to Plurality.

A much better comparison to Kemeny is Ranked Pairs; see below.

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

That only holds if you're on the Pareto front and the two criteria 
aren't aligned, which needs to be separately argued. Your graph shows 
that it's possible to considerably improve your IIA compliance by losing 
only a sliver of clone independence - that's what RCIPE does. So I 
wouldn't consider it impossible that what you're seeing is just IRV 
being bad, rather than clone independence and IIA inherently being 
subject to a trade-off.

One could even argue that IIA should benefit from clone independence, 
because clone independence is a form of IIA: Removing a clone who 
doesn't win changes who actually wins. So a clone failure *is* an IIA 
failure.[1]

> 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 your plot, does 2 candidates clone independence mean that you have 
two candidates and then you clone one of them and see if the winner 
changes, or that you start off with one candidate and then you clone 
that candidate?

Because if it's the former, then Borda should have nonzero clone 
independence failure, e.g. this example:

6: A>B
3: B>A

A wins. Now clone B:

6: A>B1>B2
3: B1>B2>A

B1 wins, clone failure.

And if it's the latter, then Plurality should also be cloneproof.

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

I'll take both, thanks :-)

I know: I can't have IIA with a ranked method. But I can have ISDA, or 
even River's IPDA and independence of strongly dominated alternatives.

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

Kemeny is a method that seeks to optimize a certain scoring function of 
the pairwise matchups that agree with the returned social outcome. (WLOG 
I'll phrase it as maximizing, not minimizing.) The Kemeny objective 
function is the sum of the strength of all the pairwise match-ups that 
agree with the output ranking.

Another method can be phrased this way: Ranked Pairs. Its objective 
function is just the strength of the strongest victory consistent with 
the outcome, with ties broken by second strongest, then third strongest, 
etc. Leximax.

Both these methods look deeply enough into all the ballots that they 
pass both LIIA and ISDA. The difference is that Ranked Pairs is 
computable in polynomial time... and happens to be cloneproof.

I don't see why should a method that is cloneproof necessarily look less 
deeply into all the ballots than one that fails clone independence, just 
because IRV happens to be that way.

-km

[1] I suspect that clone independence won't have much of a bearing on 
(other) IIA failures because two candidates just happening to be clones 
is vanishingly rare in the space of all possible elections. But by that 
reasoning, any constraint relating clone independence to (other) IIA 
failures should also be very weak unless the implications of passing the 
property propagate throughout most of election space.