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

Very Good ... and nice explanation! On Sat, Apr 22, 2023, 11:11 AM Filip Ejlak <tersander@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 >

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@gmail.com> napisał(a): > Very Good ... and nice explanation! > > On Sat, Apr 22, 2023, 11:11 AM Filip Ejlak <tersander@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 >> >

I take that back - even if it always chooses an uncovered candidate, the method is not totally independent of covered alternatives. In this 4-candidate cycle example: 8: A>B>C>D 9: B>D>A>C 12: C>D>A>B Landau set is {A,B,D} as B covers C (and gets their 1st preferences added to the score), but C owns all their 1st preferences at the expense of D. Eliminating C in the first round doesn't happen because D would gain too much at the expense of B. A gets eliminated instead, and eventually B wins. If Landau//[This Method] was used instead, D would be the winner. niedz., 23 kwi 2023 o 14:43 Filip Ejlak <tersander@gmail.com> napisał(a): > 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@gmail.com> > napisał(a): > >> Very Good ... and nice explanation! >> >> On Sat, Apr 22, 2023, 11:11 AM Filip Ejlak <tersander@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 >>> >>

On 4/23/23 21:45, Filip Ejlak wrote: > I take that back - even if it always chooses an uncovered candidate, the > method is not totally independent of covered alternatives. > In this 4-candidate cycle example: > > 8: A>B>C>D > 9: B>D>A>C > 12: C>D>A>B > > Landau set is {A,B,D} as B covers C (and gets their 1st preferences > added to the score), but C owns all their 1st preferences at the expense > of D. Eliminating C in the first round doesn't happen because D would > gain too much at the expense of B. A gets eliminated instead, and > eventually B wins. > > If Landau//[This Method] was used instead, D would be the winner. That's not surprising -- under mild assumptions, you can't have monotonicity and independence of covered candidates. I haven't quite gathered how the elimination process works. Could you give an example election, e.g. the 4-candidate cycle example above? -km

(disclaimer: unfortunately there exists a 5-candidate cycle example that breaks monotonicity and my day is ruined, I show the example later) > 8: A>B>C>D > 9: B>D>A>C > 12: C>D>A>B So, in the first round we got B covering C, so B score includes C's 1st preferences: A score: 8 B score: 9+12=21 C score: 12 D score: 0 If A got eliminated, we would have: A score: 0 (*-8*) B score: 29 (*+8*) - receives votes from A, now a Condorcet winner C score: 12 (+0) D score: 0 (+0) With B eliminated, we would have: A score: 8 (+0) B score: 0 (*-21*) C score: 12 (no change) D score: 9 (*+9*) - receives B's votes With C eliminated, we would have: A score: 8 (+0) B score: 9 (*-12*) - loses C's votes, as they go to D which isn't covered by B C score: 0 (-12) D score: 12 (*+12*) - receives C's votes With D eliminated, we would have: A score: 29 (*+21*) - now a Condorcet winner, covers everyone B score: 21 (+0) C score: 12 (+0) D score: 0 (*+0*) The greatest increases and decreases are bolded. We calculate the penalties for each elimination: - A: 8+8=16 - B: 9+21=30 - C: 12+12=24 - D: 21+0=21 Eliminating A would create the smallest distortion of the scores, so A gets eliminated. Now we are left with B, C and D; B is the Condorcet winner. What happened was that B had a good starting position thanks to covering C, so the method preferred a choice that maintained this position. Now, the monotonicity counterexample: 17 ABCDE 16 BCDEA 15 CDEAB 14 DEABC 13 EABCD Here E gets eliminated first, and eventually D wins. However, if we change ABCDE to ABDCE and EABCD to EABDC, then C stops pairwise-beating D, which means that A will cover C if E gets eliminated. That discourages the method from eliminating E first (as A's score growth would be too big) and D gets eliminated instead. So even though I think I do like it a bit more than the Condorcet-IRV hybrids... unfortunately it doesn't fully do what I intended it to do. I guess the elimination approach actually *is* unsuitable for the monotonicity goal here. niedz., 23 kwi 2023 o 22:38 Kristofer Munsterhjelm <km_elmet@t-online.de> napisał(a): > On 4/23/23 21:45, Filip Ejlak wrote: > > I take that back - even if it always chooses an uncovered candidate, the > > method is not totally independent of covered alternatives. > > In this 4-candidate cycle example: > > > > 8: A>B>C>D > > 9: B>D>A>C > > 12: C>D>A>B > > > > Landau set is {A,B,D} as B covers C (and gets their 1st preferences > > added to the score), but C owns all their 1st preferences at the expense > > of D. Eliminating C in the first round doesn't happen because D would > > gain too much at the expense of B. A gets eliminated instead, and > > eventually B wins. > > > > If Landau//[This Method] was used instead, D would be the winner. > > That's not surprising -- under mild assumptions, you can't have > monotonicity and independence of covered candidates. > > I haven't quite gathered how the elimination process works. Could you > give an example election, e.g. the 4-candidate cycle example above? > > -km > >

We've all had ruined days from monotonicity fails, but these are steps that ultimately pay off ... amazing how that works out! Don't get discouraged. Remember, if the method is Condorcet efficient, the Yee diagrams that show so much monotonicity dysphoria in IRV ... these diagrams cannot detect any defect whatsoever in your method! On Mon, Apr 24, 2023, 1:50 PM Filip Ejlak <tersander@gmail.com> wrote: > (disclaimer: unfortunately there exists a 5-candidate cycle example that > breaks monotonicity and my day is ruined, I show the example later) > > > 8: A>B>C>D > > 9: B>D>A>C > > 12: C>D>A>B > > So, in the first round we got B covering C, so B score includes C's 1st > preferences: > A score: 8 > B score: 9+12=21 > C score: 12 > D score: 0 > > If A got eliminated, we would have: > A score: 0 (*-8*) > B score: 29 (*+8*) - receives votes from A, now a Condorcet winner > C score: 12 (+0) > D score: 0 (+0) > > With B eliminated, we would have: > A score: 8 (+0) > B score: 0 (*-21*) > C score: 12 (no change) > D score: 9 (*+9*) - receives B's votes > > With C eliminated, we would have: > A score: 8 (+0) > B score: 9 (*-12*) - loses C's votes, as they go to D which isn't covered > by B > C score: 0 (-12) > D score: 12 (*+12*) - receives C's votes > > With D eliminated, we would have: > A score: 29 (*+21*) - now a Condorcet winner, covers everyone > B score: 21 (+0) > C score: 12 (+0) > D score: 0 (*+0*) > > The greatest increases and decreases are bolded. We calculate the > penalties for each elimination: > - A: 8+8=16 > - B: 9+21=30 > - C: 12+12=24 > - D: 21+0=21 > > Eliminating A would create the smallest distortion of the scores, so A > gets eliminated. > Now we are left with B, C and D; B is the Condorcet winner. > What happened was that B had a good starting position thanks to covering > C, so the method preferred a choice that maintained this position. > > Now, the monotonicity counterexample: > > 17 ABCDE > 16 BCDEA > 15 CDEAB > 14 DEABC > 13 EABCD > > Here E gets eliminated first, and eventually D wins. However, if we change > ABCDE to ABDCE and EABCD to EABDC, then C stops pairwise-beating D, which > means that A will cover C if E gets eliminated. That discourages the method > from eliminating E first (as A's score growth would be too big) and D gets > eliminated instead. > > So even though I think I do like it a bit more than the Condorcet-IRV > hybrids... unfortunately it doesn't fully do what I intended it to do. > I guess the elimination approach actually *is* unsuitable for the > monotonicity goal here. > > > > niedz., 23 kwi 2023 o 22:38 Kristofer Munsterhjelm <km_elmet@t-online.de> > napisał(a): > >> On 4/23/23 21:45, Filip Ejlak wrote: >> > I take that back - even if it always chooses an uncovered >> candidate, the >> > method is not totally independent of covered alternatives. >> > In this 4-candidate cycle example: >> > >> > 8: A>B>C>D >> > 9: B>D>A>C >> > 12: C>D>A>B >> > >> > Landau set is {A,B,D} as B covers C (and gets their 1st preferences >> > added to the score), but C owns all their 1st preferences at the >> expense >> > of D. Eliminating C in the first round doesn't happen because D would >> > gain too much at the expense of B. A gets eliminated instead, and >> > eventually B wins. >> > >> > If Landau//[This Method] was used instead, D would be the winner. >> >> That's not surprising -- under mild assumptions, you can't have >> monotonicity and independence of covered candidates. >> >> I haven't quite gathered how the elimination process works. Could you >> give an example election, e.g. the 4-candidate cycle example above? >> >> -km >> >> ---- > Election-Methods mailing list - see https://electorama.com/em for list > info >