[EM] Condorcet-Kemeny clarifications
km_elmet at t-online.de
Thu Nov 4 16:14:51 PDT 2021
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
> 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:
> 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
> 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
Because if it's the former, then Borda should have nonzero clone
independence failure, e.g. this example:
A wins. Now clone B:
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,
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.
 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.
More information about the Election-Methods