[EM] Sequential elimination method that turns out to be a generalization of fpA-fpC

[Filip Ejlak]

Thank you! But a little clarification - in the score definition I
meant "*pairwise
beaten by all candidates that pairwise beat X*" as in "*Y has to be beaten
by each and every candidate that beats X*", so it's just a covering
relation. Still, it does seem that the uncovered candidates should be the
last to be eliminated.


niedz., 23 kwi 2023 o 01:03 Forest Simmons <forest.simmons21 at gmail.com>
napisał(a):

> Very Good ... and nice explanation!
>
> On Sat, Apr 22, 2023, 11:11 AM Filip Ejlak <tersander at gmail.com> wrote:
>
>> Ok, after trying out a few things I found something that looks promising
>> in terms of passing all of ISDA, DMTCBR, Cloneproofness and, I hope,
>> Monotonicity. The scoring rule is similar to Friendly Cover (but without
>> subtracting fpC); the elimination rule is a bit atypical.
>>
>> The definition:
>>
>> "*Let X's score be the sum of 1st preferences of candidates that are
>> pairwise beaten by all candidates that pairwise beat X.*
>>
>
> In friendly parlance ... X's score is the sum of the first preference
> counts of all the friends of all of the enemies of X.
>
> Now suppose X' covers X.  Then enemies(X') is a subset of enemies(X), and
> so friends of enemies of X' is a subset of friends of enemies of X ...
> which gives X' a lower score than X.
>
> So argminScore(X) always contains an uncovered candidate ... which you
> probably already mentioned ... I haven't read all of the posts in this
> thread yet (sorry about that).
>
> -fws
>
> * In each round eliminate such a candidate that the sum of the eliminated
>> candidate's score and the greatest score growth caused by the elimination
>> is minimized*."
>>
>> The growth-minimizing part works for at least two reasons: 1) It
>> reinforces the behaviour we would expect in a situation with no cycles,
>> when an elimination shouldn't cause a positive score growth (if an
>> eliminated candidate was worse than X, then its 1st preferences were
>> already included in X's score). 2) In cycle situations it should benefit
>> candidates that already have a high score (because letting a low-score
>> candidate achieve some score level is less preferable to letting a
>> high-score candidate achieve such level).
>>
>> Also notice that the eliminated candidate's score is equal to the
>> greatest score decrease caused by the elimination, so there is a nice
>> symmetry between these two things we sum. It also means we can express the
>> elimination rule in a more elegant way ("*eliminate such a candidate
>> that the greatest score distance change between any two candidates is
>> minimized*"), but perhaps the former definition makes it more clear why
>> it works.
>>
>> It seems to me that the incentive to eliminate a non-Smith candidate
>> because of a low score should always outweigh the incentive to eliminate a
>> Smith candidate because of a low score growth, so all non-Smith candidates
>> should be eliminated first.
>>
>> Proof that the 3-candidate case is equivalent to fpA-fpC:
>>
>> If there is no cycle, it is trivial as both methods are Condorcet. If
>> there is an A>B>C>A cycle, then we look at the possible eliminations. Let
>> "a" be the number of A's 1st preferences, "b" of B, "c" of C.
>>
>> - if C is eliminated, A's score increases by b+c and A wins with B
>>
>> - if A is eliminated, B's score increases by a+c and B wins with C
>>
>> - if B is eliminated, C's score increases by a+b and C wins with A
>>
>> We add eliminated scores to score growths in order to find the optimal
>> elimination. If 2c+b is the lowest, A wins. If 2a+c is the lowest, B wins.
>> If 2b+a is the lowest, C wins.
>>
>> Notice that min(2c+b, 2a+c, 2b+a) = min(2c+b-(a+b+c), 2a+c-(a+b+c),
>> 2b+a-(a+b+c)) = min(c-a, a-b, b-c) = max(a-c, b-a, c-b). So we get the
>> fpA-fpC formula, QED.
>> ----
>> 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/20230423/77de1a9f/attachment-0001.htm>