[EM] Condorcet-Kemeny clarifications
Forest Simmons
forest.simmons21 at gmail.com
Wed Nov 3 14:44:29 PDT 2021
Richard,
You have shown by your EM postings that you are not content to just
regurgitate the opinions and pronouncements of the "experts". You want
fundamental understanding so that you have the tools to form and defend
your own opinions with alacrity.. which you have done with admirable valor
based on above average curiosity and willingness to think carefully while
searching for truth.
That's why I want to dig a little more into Independence from Irrelevant
Alternatives... We have seen that no method based solely on ranked choice
ballots can satisfy the IIAC except by failing the Majority Criterion....
in fact, if a majority prefers A over B and another majority prefers B over
C, and another majority prefers C over A, then no matter which of these is
the method winner X the removal/withdrawal of the one majority beaten by X
will change the winner from X to the one that beats X by a majority.
So how do MJ and some versions of Cardinal Ratings satisfy IIAC? By going
outside Universal Domain .. i.e. by using ballot information beyond mere
ordinal information ... information that is supposed to be absolute, unlike
rankings which are fundamentally relative.
Does Approval satisfy IIAC? Technically yes ... sincere approval is not
supposed to be relative .. you either approve of X or you don't ...
according to your own standards, independent of your approval of other
people. Approval in a zero info environment would satisfy it ... as would
even FPTP if a candidate withdrew after the ballots were already submitted.
But not so with any ranked preference method ... re-counting the ballots
after the withdrawal can change the IRV winner, the Kemeny-Young winner,
etc ... but not the MJ winner, the FPTP winner, the Range winner, or the
Approval winner.
This is the best objective test fo IIAC compliance: if after all of the
ballots have been submitted and counted a losing candidate X withdraws ...
would a recount of the exact same ballots with X crossed out on all ballots
necessarily result in the same winner?
If so, then the method passes IIAC.
Now what about the Sorted Margins versions of IIAC compliant methods ... do
they satisfy the IIAC?
No, but like Kemeny-Young, they all satisfy "Local IIAC", which means that
if you transpose just one pair of candidates in the finish order, the
average Kemeny distance of that order from the ballot rankings will be
increased ... i.e. the finish order distance is a local minimum in the
Kemeny distance from the ballots.
Sorting the finish order pairwise as a last step confers local IIAC
compliance on any method that has both a finish order and a way of making
pairwise comparisons.
This kind of sorting of the finish order is sometimes referred to as
Kemenization, especially if the local minimum obtained therefrom is at
minimal distance from the original finish order.
In the case of ASM (or MJ) the original (base method) finish order already
satisfies the IIAC without necessarily being at a local or global minimal
average distance to the ballot rankings.
Ironically, since pairwise comparisons are generally based on relative
ordinal infornation only, this afterburner add-on can scuttle the absolute
IIAC compliance of the original finish order.
So as Ted Stern has pointed out, the sorting step is more of a guarantee
that the ballot CW cannot lose, like the necessary redundancy in an error
correcting code ... where the allowable code words (i.e. finish orders in
this context) are local minima of the Kemeny distance from the ballots.
This analogy is precise ... a non-code word "signal" W, when received and
detected is taken as contaminated by error/noise. The most likely intended
message word is the code word closest to W.
For example, if the cyclic pairwise beat order is ABCA, then the "code
words" (allowable rankings) are ABC, BCA, and CAB.
Suppose that the base method (say IRV) finish order is CBA. Then the
question becomes which code word is closest to the contaminated signal CBA
that was received after passing through IRV and the other elements of the
noisy, error fraught election system/environment?
Changing CBA to codeword BAC or to CAB involves one transposition in the
finish order, but on how many ballots?
That depends on the respective absolute margins of defeat of B>A and of
A>B, respectly.
Hence, Approval Sorted Margins, MJ Sorted Margins, etc.
Just one detail, in practice the "margins" in question can be pairwise
approval margins or pairwise range margins, etc ... whatever kind of
margins are most convenient ... as in Galerkin's method of error
minimization.
FWS
El mar., 2 de nov. de 2021 11:50 p. m., Forest Simmons <
forest.simmons21 at gmail.com> escribió:
> By the way, I'm referring to Ted Stern's most recent version of ASM that
> he calls PAIR-SM from his 27October EM message.
>
> As for MJ-SM, be sure to use a symmetric version of MJ for Reverse
> Symmetry Criterion compliance.
>
> By the way, what makes you think that the use of a couple of extra
> strength rank relations to fix K-Y's spoiler problem would impair IIAC
> compliance? It works great for PAIR-SM.
>
> You invoked Arrow, but Arrow never said that Clone Winner and IIAC were
> incompatible. He did say that IIAC and the Majority Criterion are
> incompatible, and it is easy to prove ...
>
> Consider for example ...
>
> 40 A>B>C
> 30 B>C>A
> 30 C>A>B
>
> If A wins, as in Kemeny-Young, River, Ranked Pairs, CSSD, Borda, Bucklin,
> IRV, etc. then B is an irrelevant alternative.
>
> But when B is removed, C becomes the Majority Winner 60 to 40.
>
> Perhaps in your simulations you threw out cycles like these ... but that
> would give all Condorcet Compliant methods perfect scores for IIAC. I am
> curious how you came up with the idea that K-Y trades in Clone Winner
> compliance for better IIAC compliance.
>
> FWS
>
> El mar., 2 de nov. de 2021 10:50 p. m., Forest Simmons <
> forest.simmons21 at gmail.com> escribió:
>
>> Richard,
>>
>> Clone winner failure is not about electing the wrong clone ... it's about
>> none of the clones of the erstwhile winner being elected. That is the
>> spoiler problem.
>>
>> If you want a method that is both clone winner compliant and IIAC
>> compliant, Approval Sorted Margins (ASM), or Majority Judgment Sorted
>> Margins (MJSM) is what you need.
>>
>> FWS
>>
>>
>>
>> El mar., 2 de nov. de 2021 9:02 p. m., Richard, the VoteFair guy <
>> electionmethods at votefair.org> escribió:
>>
>>> 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
>>> >
>>> ----
>>> 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/20211103/c322626b/attachment-0001.html>
More information about the Election-Methods
mailing list