[EM] Condorcet-Kemeny clarifications

[Forest Simmons]

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> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20211031/274d9084/attachment.html>