Based on a suggestion from a user on Reddit, I have revised the
definition of the Instant Pairwise Elimination method that previously I published at Democracy Chronicles and then discussed here. The method still successively eliminates pairwise (Condorcet) losers. Now, instead of resolving Condorcet (rock-paper-scissors) cycles using an "upside-down" version of instant-runoff voting (IRV), it uses pairwise counts as described here: "If an elimination round has no pairwise-losing candidate, then the method eliminates the candidate with the largest pairwise opposition count, which is determined by counting on each ballot the number of not-yet-eliminated candidates who are ranked above that candidate, and adding those numbers across all the ballots. If there is a tie for the largest pairwise opposition count, the method eliminates the candidate with the smallest pairwise support count, which similarly counts support rather than opposition. If there is also a tie for the smallest pairwise support count, then those candidates are tied and all those tied candidates are eliminated in the same elimination round." Below are my guesses for which fairness criteria it fails and passes. Please tell me which guesses are not correct. Condorcet: fail Condorcet loser: pass Ranks equal: pass Ranks greater than 2: pass Polytime: pass Resolvable: pass Majority: fail Majority loser: fail Mutual majority: fail Smith/ISDA: fail LIIA: fail IIA: fail Cloneproof: fail Monotone: fail Consistency: fail Reversal symmetry: fail Later no harm: fail Later no help: fail Burying: fail Participation: fail ? No favorite betrayal: fail ? Summable: O(N!) ? As I've said many times, it's the frequency with which the failures occur that is much, much more important than simply counting how many criteria it fails. I suspect that its frequencies of failure will be quite low compared to most other single-winner methods, and may approach the low frequencies that I believe characterize the Condorcet-Kemeny method. I've created a page for this method on Electowiki. You are welcome to edit that page with any corrections. BTW, I realize that it's possible that the alternate elimination method always identifies the pairwise/Condorcet loser (if there is one). If so, this would mean that the description could be "simplified" to a single step (actually two steps in case there is a tie). However, for the benefit of most voters who are not comfortable with mathematics it's important to explicitly state that the first priority is to eliminate the pairwise loser. Of course software that implements the method would do the calculations using a much faster method than the counting method described above. The description above is written to be understandable to people who are not already familiar with pairwise counting. In advance, thank you for any feedback. Richard Fobes ---- Election-Methods mailing list - see https://electorama.com/em for list info |
I missed the earlier discussion on this. On 13/01/2020 12:14 pm, VoteFair wrote:
Based on a suggestion from a user on Reddit, I have revised the definition of the Instant Pairwise Elimination method that previously I published at Democracy Chronicles and then discussed here. ---- Election-Methods mailing list - see https://electorama.com/em for list info |
On 1/13/2020 7:56 AM, C.Benham wrote:
> I missed the earlier discussion on this. > ... > And what exactly is a "pairwise-losing candidate"? My apologies. For brevity I omitted the first paragraph of the description, which is here: "Instant Pairwise Elimination (IPE) eliminates one candidate at a time. During each elimination round the candidate who loses every pairwise contest against every other not-yet-eliminated candidate is eliminated. The last remaining candidate wins." Hopefully now the second paragraph will make sense: "If an elimination round has no pairwise-losing candidate, then the method eliminates the candidate with the largest pairwise opposition count, which is determined by counting on each ballot the number of not-yet-eliminated candidates who are ranked above that candidate, and adding those numbers across all the ballots. If there is a tie for the largest pairwise opposition count, the method eliminates the candidate with the smallest pairwise support count, which similarly counts support rather than opposition. If there is also a tie for the smallest pairwise support count, then those candidates are tied and all those tied candidates are eliminated in the same elimination round." > Just curious. Curiosity is what led me to election-method reform. Thanks for asking. Richard Fobes On 1/13/2020 7:56 AM, C.Benham wrote: > I missed the earlier discussion on this. > > So what if an elimination round /does /have a "pairwise-losing > candidate", what then? > > And what exactly is a "pairwise-losing candidate"? > > Just curious. > > Chris Benham > > On 13/01/2020 12:14 pm, VoteFair wrote: >> Based on a suggestion from a user on Reddit, I have revised the >> definition of the Instant Pairwise Elimination method that previously >> I published at Democracy Chronicles and then discussed here. >> >> The method still successively eliminates pairwise (Condorcet) losers. >> >> Now, instead of resolving Condorcet (rock-paper-scissors) cycles using >> an "upside-down" version of instant-runoff voting (IRV), it uses >> pairwise counts as described here: >> >> "If an elimination round has no pairwise-losing candidate, then the >> method eliminates the candidate with the largest pairwise opposition >> count, which is determined by counting on each ballot the number of >> not-yet-eliminated candidates who are ranked above that candidate, and >> adding those numbers across all the ballots. If there is a tie for the >> largest pairwise opposition count, the method eliminates the candidate >> with the smallest pairwise support count, which similarly counts >> support rather than opposition. If there is also a tie for the >> smallest pairwise support count, then those candidates are tied and >> all those tied candidates are eliminated in the same elimination round." >> >> Below are my guesses for which fairness criteria it fails and passes. >> Please tell me which guesses are not correct. >> >> Condorcet: fail >> Condorcet loser: pass >> Ranks equal: pass >> Ranks greater than 2: pass >> Polytime: pass >> Resolvable: pass >> Majority: fail >> Majority loser: fail >> Mutual majority: fail >> Smith/ISDA: fail >> LIIA: fail >> IIA: fail >> Cloneproof: fail >> Monotone: fail >> Consistency: fail >> Reversal symmetry: fail >> Later no harm: fail >> Later no help: fail >> Burying: fail >> Participation: fail ? >> No favorite betrayal: fail ? >> Summable: O(N!) ? >> >> As I've said many times, it's the frequency with which the failures >> occur that is much, much more important than simply counting how many >> criteria it fails. I suspect that its frequencies of failure will be >> quite low compared to most other single-winner methods, and may >> approach the low frequencies that I believe characterize the >> Condorcet-Kemeny method. >> >> I've created a page for this method on Electowiki. You are welcome to >> edit that page with any corrections. >> >> BTW, I realize that it's possible that the alternate elimination >> method always identifies the pairwise/Condorcet loser (if there is >> one). If so, this would mean that the description could be >> "simplified" to a single step (actually two steps in case there is a >> tie). However, for the benefit of most voters who are not comfortable >> with mathematics it's important to explicitly state that the first >> priority is to eliminate the pairwise loser. >> >> Of course software that implements the method would do the >> calculations using a much faster method than the counting method >> described above. The description above is written to be understandable >> to people who are not already familiar with pairwise counting. >> >> In advance, thank you for any feedback. >> >> Richard Fobes >> ---- >> Election-Methods mailing list - see https://electorama.com/em for list >> info > > > ---- > Election-Methods mailing list - see https://electorama.com/em for list info > Election-Methods mailing list - see https://electorama.com/em for list info |
On 14/01/2020 01.03, VoteFair wrote:
> On 1/13/2020 7:56 AM, C.Benham wrote: >> I missed the earlier discussion on this. >> ... >> And what exactly is a "pairwise-losing candidate"? > > My apologies. For brevity I omitted the first paragraph of the > description, which is here: > > "Instant Pairwise Elimination (IPE) eliminates one candidate at a time. > During each elimination round the candidate who loses every pairwise > contest against every other not-yet-eliminated candidate is eliminated. > The last remaining candidate wins." > > Hopefully now the second paragraph will make sense: > > "If an elimination round has no pairwise-losing candidate, then the > method eliminates the candidate with the largest pairwise opposition > count, which is determined by counting on each ballot the number of > not-yet-eliminated candidates who are ranked above that candidate, and > adding those numbers across all the ballots. If there is a tie for the > largest pairwise opposition count, the method eliminates the candidate > with the smallest pairwise support count, which similarly counts support > rather than opposition. If there is also a tie for the smallest pairwise > support count, then those candidates are tied and all those tied > candidates are eliminated in the same elimination round." > >> Just curious. > > Curiosity is what led me to election-method reform. Thanks for asking. The fallback sounds a lot like Raynaud(PO). If I'm right, then it should always pick the same winner as Raynaud(PO) does. Proof sketch: call the Smith set according to pairwise opposition the "PO Smith set". Since Raynaud(wv or margins) passes Smith, Raynaud(PO) passes PO Smith. Eliminating the Condorcet loser whenever it exists can't make a method that passes PO Smith fail it. Now suppose that every candidate not in the PO Smith set has been eliminated. By definition of the PO Smith set, it has no Condorcet losers, so IPE will then use the fallback to eliminate all but one member of that set. Since the fallback uses the same elimination as Raynaud, the winner must be the Raynaud winner. Or to put it differently, both Raynaud(PO) and IPE will eliminate every candidate outside of the PO Smith set. And once that's done, both methods will use the IPE fallback, which clearly eliminates candidates in the same order, ending up with the same winner. As a consequence, if you were to change "pairwise opposition" to "margins" or "winning votes" in the definition, the IPE variant -- call it IPE(margins) or IPE(wv) -- would pass Condorcet, Smith, and ISDA. If I'm right about that reduction, then it automatically follows for IPE itself: Summable: O(n^2) (You can find the Condorcet loser using the Condorcet matrix, and eliminating someone doesn't change the pairwise counts for other pairs) Majority: pass (Suppose X is ranked first by a majority. X has a stronger pairwise victory over everybody else than anyone else has over him, and X is not a Condorcet loser. So X will never be eliminated.) Majority loser: pass (The majority loser is not in the PO Smith set) And since pairwise opposition, margins, and wv all agree when nobody truncates or equal-ranks, and it's possible to make Raynaud fail certain criteria without using either truncation or equal-rank: IIA: fail Monotonicity: fail Consistency: fail Burying: fail Participation: fail ---- Election-Methods mailing list - see https://electorama.com/em for list info |
On 1/14/2020 2:34 PM, Kristofer Munsterhjelm wrote:
> The fallback sounds a lot like Raynaud(PO). If I'm right, then it should > always pick the same winner as Raynaud(PO) does. Highlight from below: The fact that the Raynaud method passes the Condorcet criterion suggested to me that the two methods could not be the same. Apparently my description of the "fallback" method was not clear. So, I added an example to the Electowiki article: https://electowiki.org/wiki/Instant_Pairwise_Elimination#Example Notice that it looks at columns in the pairwise matrix and sums the pairwise counts in each column -- and looks for the highest sum. If there is a tie, then it looks at rows in the pairwise matrix (and sums each row and looks for the smallest sum). I believe -- but I could be wrong -- that Instant Pairwise Elimination (IPE) fails the Condorcet criterion. (This would only happen when there is a Condorcet cycle.) By design IPE does pass the Condorcet loser criterion. The fact that the Raynaud method passes the Condorcet criterion suggested to me that the two methods could not be the same. I have not seen any other (non-IPE) methods that use pairwise counts and yet fail the Condorcet criterion. Is that right? As a reminder I created IPE to appeal to non-math voters. They don't care about the Condorcet criterion. Apparently they do care that the method eliminates just one candidate at a time, the way IRV does. And based on some feedback they like the idea of eliminating a candidate who is strongly disliked by a group of voters. For us math geeks, what I like about IPE is that when pass/fail frequencies/rates are finally calculated, IPE should perform better than some methods that are carefully designed to pass specific criteria -- without concern that they might often (rather than rarely) fail other criteria (which they are known to fail). Once again I greatly appreciate your sharp mind analyzing the IPE method. Thank you Kristofer! Richard Fobes On 1/14/2020 2:34 PM, Kristofer Munsterhjelm wrote: > On 14/01/2020 01.03, VoteFair wrote: >> On 1/13/2020 7:56 AM, C.Benham wrote: >>> I missed the earlier discussion on this. >>> ... >>> And what exactly is a "pairwise-losing candidate"? >> >> My apologies. For brevity I omitted the first paragraph of the >> description, which is here: >> >> "Instant Pairwise Elimination (IPE) eliminates one candidate at a time. >> During each elimination round the candidate who loses every pairwise >> contest against every other not-yet-eliminated candidate is eliminated. >> The last remaining candidate wins." >> >> Hopefully now the second paragraph will make sense: >> >> "If an elimination round has no pairwise-losing candidate, then the >> method eliminates the candidate with the largest pairwise opposition >> count, which is determined by counting on each ballot the number of >> not-yet-eliminated candidates who are ranked above that candidate, and >> adding those numbers across all the ballots. If there is a tie for the >> largest pairwise opposition count, the method eliminates the candidate >> with the smallest pairwise support count, which similarly counts support >> rather than opposition. If there is also a tie for the smallest pairwise >> support count, then those candidates are tied and all those tied >> candidates are eliminated in the same elimination round." >> >>> Just curious. >> >> Curiosity is what led me to election-method reform. Thanks for asking. > > The fallback sounds a lot like Raynaud(PO). If I'm right, then it should > always pick the same winner as Raynaud(PO) does. > > Proof sketch: call the Smith set according to pairwise opposition the > "PO Smith set". Since Raynaud(wv or margins) passes Smith, Raynaud(PO) > passes PO Smith. Eliminating the Condorcet loser whenever it exists > can't make a method that passes PO Smith fail it. > > Now suppose that every candidate not in the PO Smith set has been > eliminated. By definition of the PO Smith set, it has no Condorcet > losers, so IPE will then use the fallback to eliminate all but one > member of that set. Since the fallback uses the same elimination as > Raynaud, the winner must be the Raynaud winner. > > Or to put it differently, both Raynaud(PO) and IPE will eliminate every > candidate outside of the PO Smith set. And once that's done, both > methods will use the IPE fallback, which clearly eliminates candidates > in the same order, ending up with the same winner. > > As a consequence, if you were to change "pairwise opposition" to > "margins" or "winning votes" in the definition, the IPE variant -- call > it IPE(margins) or IPE(wv) -- would pass Condorcet, Smith, and ISDA. > > If I'm right about that reduction, then it automatically follows for IPE > itself: > > Summable: O(n^2) > (You can find the Condorcet loser using the Condorcet matrix, and > eliminating someone doesn't change the pairwise counts for other pairs) > > Majority: pass > (Suppose X is ranked first by a majority. X has a stronger pairwise > victory over everybody else than anyone else has over him, and X is not > a Condorcet loser. So X will never be eliminated.) > > Majority loser: pass > (The majority loser is not in the PO Smith set) > > And since pairwise opposition, margins, and wv all agree when nobody > truncates or equal-ranks, and it's possible to make Raynaud fail certain > criteria without using either truncation or equal-rank: > > IIA: fail > Monotonicity: fail > Consistency: fail > Burying: fail > Participation: fail > Election-Methods mailing list - see https://electorama.com/em for list info |
On 16/01/2020 01.36, VoteFair wrote:
> On 1/14/2020 2:34 PM, Kristofer Munsterhjelm wrote: >> The fallback sounds a lot like Raynaud(PO). If I'm right, then it should >> always pick the same winner as Raynaud(PO) does. > > Highlight from below: The fact that the Raynaud method passes the > Condorcet criterion suggested to me that the two methods could not be > the same. > > Apparently my description of the "fallback" method was not clear. So, I > added an example to the Electowiki article: > > https://electowiki.org/wiki/Instant_Pairwise_Elimination#Example > > Notice that it looks at columns in the pairwise matrix and sums the > pairwise counts in each column -- and looks for the highest sum. > > If there is a tie, then it looks at rows in the pairwise matrix (and > sums each row and looks for the smallest sum). > > I believe -- but I could be wrong -- that Instant Pairwise Elimination > (IPE) fails the Condorcet criterion. (This would only happen when there > is a Condorcet cycle.) I see; I thought your fallback was to eliminate the candidate who's on the losing end of the strongest pairwise victory (by anyone over anyone else). The fallback as I thought it would have reduced IPE to Raynaud(PO), but the fallback you've given here does not. So you should probably disregard what I've said about criterion compliances. Or you could change the fallback to eliminate the candidate on the losing end of the strongest pairwise victory :-) It wouldn't take much to get you all the way to Condorcet. Though I would make one qualification to my previous sentence. IPE as you've defined it here is still O(n^2) summable. Consider what happens when you eliminate a candidate X: - Every pairwise contest between candidates not involving X stay the same. - Every pairwise contest including X is removed from the pairwise matrix. So you can modify a pairwise matrix to the effect of eliminating a candidate without needing more information than the pairwise matrix itself -- as long as your criterion of who to eliminate only needs to use the pairwise matrix. For instance, Schulze can be stated like this: 1. Find the smallest group of candidates who collectively beat or tie everybody else. 2. Eliminate every candidate not in that group. If only one candidate remains, he's the winner. 3. Replace the weakest pairwise defeat (between uneliminated candidates) with a tie. 4. Go to 1. And this can be done with only the pairwise matrix. ---- Election-Methods mailing list - see https://electorama.com/em for list info |
On 1/22/2020 4:13 PM, Kristofer Munsterhjelm wrote:
> So you should probably disregard what I've said about criterion > compliances. OK. I removed (at https://electowiki.org/wiki/Instant_Pairwise_Elimination) these two criteria (which I have not found definitions for) because I don't know if IPE passes or fails them: * Ranks equal * Ranks greater than 2 Now the only criteria that Instant Pairwise Elimination (IPE) is indicated as passing are: * Condorcet loser * Resolvable * Polytime All other criteria are listed as "fail". And I specified order N squared for summability (if that's a word). > So you can modify a pairwise matrix to the effect of eliminating a > candidate without needing more information than the pairwise matrix > itself -- as long as your criterion of who to eliminate only needs to > use the pairwise matrix. The recent modification I made enables it to be calculated with just the pairwise matrix. Interestingly IPE can be calculated "by hand" on paper just using the printed pairwise matrix and a calculator. Each time a candidate is eliminated, the sums for each row and each column are updated by subtracting just one pairwise count in each row and each column. Kristofer, thank you for your feedback! As a reminder for anyone who is following this discussion, IPE is intended to have very low failure rates for the "fairness" criteria, even though there are some cases that cause it to fail almost all the criteria. Its advantages will become clearer when failure rates are used instead of checklists. Also keep in mind that the method is designed to be easy to understand for non-math folks. And admittedly I named it in a way to help clarify that IRV is not the only "instant" runoff/elimination method. :) Richard Fobes On 1/22/2020 4:13 PM, Kristofer Munsterhjelm wrote: > On 16/01/2020 01.36, VoteFair wrote: >> On 1/14/2020 2:34 PM, Kristofer Munsterhjelm wrote: >>> The fallback sounds a lot like Raynaud(PO). If I'm right, then it should >>> always pick the same winner as Raynaud(PO) does. >> >> Highlight from below: The fact that the Raynaud method passes the >> Condorcet criterion suggested to me that the two methods could not be >> the same. >> >> Apparently my description of the "fallback" method was not clear. So, I >> added an example to the Electowiki article: >> >> https://electowiki.org/wiki/Instant_Pairwise_Elimination#Example >> >> Notice that it looks at columns in the pairwise matrix and sums the >> pairwise counts in each column -- and looks for the highest sum. >> >> If there is a tie, then it looks at rows in the pairwise matrix (and >> sums each row and looks for the smallest sum). >> >> I believe -- but I could be wrong -- that Instant Pairwise Elimination >> (IPE) fails the Condorcet criterion. (This would only happen when there >> is a Condorcet cycle.) > > I see; I thought your fallback was to eliminate the candidate who's on > the losing end of the strongest pairwise victory (by anyone over anyone > else). The fallback as I thought it would have reduced IPE to > Raynaud(PO), but the fallback you've given here does not. > > So you should probably disregard what I've said about criterion > compliances. Or you could change the fallback to eliminate the candidate > on the losing end of the strongest pairwise victory :-) It wouldn't take > much to get you all the way to Condorcet. > > Though I would make one qualification to my previous sentence. IPE as > you've defined it here is still O(n^2) summable. Consider what happens > when you eliminate a candidate X: > > - Every pairwise contest between candidates not involving X stay the same. > - Every pairwise contest including X is removed from the pairwise matrix. > > So you can modify a pairwise matrix to the effect of eliminating a > candidate without needing more information than the pairwise matrix > itself -- as long as your criterion of who to eliminate only needs to > use the pairwise matrix. > > For instance, Schulze can be stated like this: > > 1. Find the smallest group of candidates who collectively beat or tie > everybody else. > 2. Eliminate every candidate not in that group. If only one candidate > remains, he's the winner. > 3. Replace the weakest pairwise defeat (between uneliminated candidates) > with a tie. > 4. Go to 1. > > And this can be done with only the pairwise matrix. > Election-Methods mailing list - see https://electorama.com/em for list info |
Free forum by Nabble | Edit this page |