Re: [EM] How close can we get to the IIAC
Marcus, you seem to think that the method is to elect the highest approval member of the uncovered set. That is not the case. Instead, first we check to see if the highest approval candidate C is uncovered. It is not, so then we check to see if the highest approval candidate B that covers C is uncovered. It is, so B is the winner. The method is monotone: Sketch of Proof: Suppose that the method winner is W. If W moves up in the approval list, then W obviously still wins. So we consider the interesting case where W now defeats some candidate C pairwise that beat W before. Suppose that the new method winner is W' . Then W' must be some candidate that now covers C but didn't before when C covered W. Why? Because W beats W'.So W' does not beat W. That means that W' gets into the act before W. But there was nothing to keep W' from getting into the act before W before. Therefore W covers W', and still wins. Forest > From: Markus Schulze > To: election-meth...@electorama.com > Subject: Re: [EM] How close can we get to the IIAC > Message-ID: <7.0.1.0.1.20100417234339.01100...@alumni.tu-berlin.de> > Content-Type: text/plain; charset="us-ascii" > > Hallo, > > > Here's a method I proposed a while back that is monotone, > > clone free, always elects a candidate from the uncovered > > set, and is independent from candidates that beat the > > winner, i.e. if a candidate that pairwise beats the > > winner is removed, the winner still wins: > > > > 1. List the candidates in order of decreasing approval. > > > > 2. If the approval winner A is uncovered, then A wins. > > > > 3. Otherwise, let C1 be the first candidate is the list > > that covers A. If C1 is uncovered, then C1 wins. > > > > 4. Else let C2 be the first candidate in the list that > > covers C1. If C2 is uncovered, then C2 wins. > > > > etc. > > Situation 1: > > Suppose the order of decreasing approval is CDAB. > > A beats B > B beats C > C beats D > D beats A > A beats C > B beats D > > uncovered set: A, B, D. > > The winner is D. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] How close can we get to the IIAC (=> "in the absence of cyclic preferences")
P.S. One way to use the concept of IAC would be to e.g. set a strict requirement of LNH-IAC to a method but only wish for reasonably good performance with full LNH. Juho On Apr 19, 2010, at 11:31 AM, Juho wrote: On Apr 19, 2010, at 11:11 AM, Kristofer Munsterhjelm wrote: Juho wrote: On Apr 19, 2010, at 10:46 AM, Kristofer Munsterhjelm wrote: The same is true of, for instance, LNHarm. If X is the CW, then if a subset of the voters add Y to the end of their ballots, that won't make X a non-CW. However, it's also possible to show that no matter how the Condorcet method behaves in the case of a cycle, one can construct an example where the method fails LNHarm. Your last sentence contains word "cycle". Were you thinking about IAC in the sincere opinions only or also in the actual votes? (If needed one can handle separately cases where IAC applies to sincere opinions only vs. both sincere opinions and actual votes.) No, that was a brief departure from IAC. The point was to show that even though Condorcet methods pass LNHarm in the "non-cycle" case, the Condorcet compliance itself introduces a discontinuity of sorts, which means that the method as a whole (with ballots that may be cyclic or not) cannot pass LNHarm. In other words, I was answering, in advance, a possible reply of "but if a Condorcet method can pass LNHarm inside the acyclical domain, then all we have to do is to align the cyclical domain propely, and we'll have a LNHarm Condorcet method, no?". Right. As you can guess from my comments I tend to see the cyclic opinions as forming a new kind of opinion space when compared to the simple models of individual voters and transitive preferences. It is reasonable to assume that the sincere opinions of individual voters are transitive. But we know that the opinions of groups don't follow the same laws. In the same way I want to reconsider whether or not those rules that apply in the simper models should apply also in the world of cyclic preferences. For example I don't like very much terms like "cycle breaking" because that seems to indicate that we want to change the rules of the cyclic opinion space to rules of the transitive opinion space, and I consider that to be more like a violent act that may distort the true laws of nature of the cyclic space. We should thus not break cycles but just identify the best winner despite of the (natural) existence of cycles. Juho Election-Methods mailing list - see http://electorama.com/em for list info Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] How close can we get to the IIAC (=> "in the absence of cyclic preferences")
On Apr 19, 2010, at 11:11 AM, Kristofer Munsterhjelm wrote: Juho wrote: On Apr 19, 2010, at 10:46 AM, Kristofer Munsterhjelm wrote: The same is true of, for instance, LNHarm. If X is the CW, then if a subset of the voters add Y to the end of their ballots, that won't make X a non-CW. However, it's also possible to show that no matter how the Condorcet method behaves in the case of a cycle, one can construct an example where the method fails LNHarm. Your last sentence contains word "cycle". Were you thinking about IAC in the sincere opinions only or also in the actual votes? (If needed one can handle separately cases where IAC applies to sincere opinions only vs. both sincere opinions and actual votes.) No, that was a brief departure from IAC. The point was to show that even though Condorcet methods pass LNHarm in the "non-cycle" case, the Condorcet compliance itself introduces a discontinuity of sorts, which means that the method as a whole (with ballots that may be cyclic or not) cannot pass LNHarm. In other words, I was answering, in advance, a possible reply of "but if a Condorcet method can pass LNHarm inside the acyclical domain, then all we have to do is to align the cyclical domain propely, and we'll have a LNHarm Condorcet method, no?". Right. As you can guess from my comments I tend to see the cyclic opinions as forming a new kind of opinion space when compared to the simple models of individual voters and transitive preferences. It is reasonable to assume that the sincere opinions of individual voters are transitive. But we know that the opinions of groups don't follow the same laws. In the same way I want to reconsider whether or not those rules that apply in the simper models should apply also in the world of cyclic preferences. For example I don't like very much terms like "cycle breaking" because that seems to indicate that we want to change the rules of the cyclic opinion space to rules of the transitive opinion space, and I consider that to be more like a violent act that may distort the true laws of nature of the cyclic space. We should thus not break cycles but just identify the best winner despite of the (natural) existence of cycles. Juho Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] How close can we get to the IIAC (=> "in the absence of cyclic preferences")
Juho wrote: On Apr 19, 2010, at 10:46 AM, Kristofer Munsterhjelm wrote: The same is true of, for instance, LNHarm. If X is the CW, then if a subset of the voters add Y to the end of their ballots, that won't make X a non-CW. However, it's also possible to show that no matter how the Condorcet method behaves in the case of a cycle, one can construct an example where the method fails LNHarm. Your last sentence contains word "cycle". Were you thinking about IAC in the sincere opinions only or also in the actual votes? (If needed one can handle separately cases where IAC applies to sincere opinions only vs. both sincere opinions and actual votes.) No, that was a brief departure from IAC. The point was to show that even though Condorcet methods pass LNHarm in the "non-cycle" case, the Condorcet compliance itself introduces a discontinuity of sorts, which means that the method as a whole (with ballots that may be cyclic or not) cannot pass LNHarm. In other words, I was answering, in advance, a possible reply of "but if a Condorcet method can pass LNHarm inside the acyclical domain, then all we have to do is to align the cyclical domain propely, and we'll have a LNHarm Condorcet method, no?". Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] How close can we get to the IIAC (=> "in the absence of cyclic preferences")
On Apr 19, 2010, at 10:46 AM, Kristofer Munsterhjelm wrote: Juho wrote: On Apr 16, 2010, at 1:23 AM, fsimm...@pcc.edu wrote: Since the IIAC is out of the question, how close can we get to the IIAC? Independence from Pareto Dominated Alternatives (IPDA) is one tiny step in that direction. Another step might be independence from alternatives that are not in the Smith set. There is one well known and useful borderline, "in the absence of cyclic preferences". This condition is not really an answer to the question "how close can we get" but it is often a natural rough estimate, and applies to many common criteria. One could answer to a question "does method m meet criterion c" either YES, NO or IAC. For many Condorcet methods and criteria answer IAC would much more informative than plain NO. In absence of cyclic preferences, any and all Condorcet methods pass IIAC. Say X is the CW. Then eliminating a candidate other than X won't turn X from CW to not-CW. The same is true of, for instance, LNHarm. If X is the CW, then if a subset of the voters add Y to the end of their ballots, that won't make X a non-CW. However, it's also possible to show that no matter how the Condorcet method behaves in the case of a cycle, one can construct an example where the method fails LNHarm. Your last sentence contains word "cycle". Were you thinking about IAC in the sincere opinions only or also in the actual votes? (If needed one can handle separately cases where IAC applies to sincere opinions only vs. both sincere opinions and actual votes.) Juho Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] How close can we get to the IIAC (=> "in the absence of cyclic preferences")
Juho wrote: On Apr 16, 2010, at 1:23 AM, fsimm...@pcc.edu wrote: Since the IIAC is out of the question, how close can we get to the IIAC? Independence from Pareto Dominated Alternatives (IPDA) is one tiny step in that direction. Another step might be independence from alternatives that are not in the Smith set. There is one well known and useful borderline, "in the absence of cyclic preferences". This condition is not really an answer to the question "how close can we get" but it is often a natural rough estimate, and applies to many common criteria. One could answer to a question "does method m meet criterion c" either YES, NO or IAC. For many Condorcet methods and criteria answer IAC would much more informative than plain NO. In absence of cyclic preferences, any and all Condorcet methods pass IIAC. Say X is the CW. Then eliminating a candidate other than X won't turn X from CW to not-CW. The same is true of, for instance, LNHarm. If X is the CW, then if a subset of the voters add Y to the end of their ballots, that won't make X a non-CW. However, it's also possible to show that no matter how the Condorcet method behaves in the case of a cycle, one can construct an example where the method fails LNHarm. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] How close can we get to the IIAC (=> "in the absence of cyclic preferences")
On Apr 16, 2010, at 1:23 AM, fsimm...@pcc.edu wrote: Since the IIAC is out of the question, how close can we get to the IIAC? Independence from Pareto Dominated Alternatives (IPDA) is one tiny step in that direction. Another step might be independence from alternatives that are not in the Smith set. There is one well known and useful borderline, "in the absence of cyclic preferences". This condition is not really an answer to the question "how close can we get" but it is often a natural rough estimate, and applies to many common criteria. One could answer to a question "does method m meet criterion c" either YES, NO or IAC. For many Condorcet methods and criteria answer IAC would much more informative than plain NO. In Condorcet methods it is typical that one can not meet all the criteria that one would like to meet, and therefore one must do some trading between different criteria. Often it is a good thing to fail numerous criteria slightly than to meet some of them fully and fail badly in some. (For example strategic voting often resembles security in the sense that the weakest link of the chain determines the strength of the whole system.) I also note that sometimes one may even prefer answer IAC to YES. Some criteria that are very natural requirements when there are no cycles may not be what we want when there are cycles. (One should not rely too much on the logic of the "Newtonian" transitive model when the world is no more transitive. The rules may well be different in the new cyclic space.) Textually term "IAC" gets very close to "IIAC" :-). Juho Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] How close can we get to the IIAC
Hallo, > Here's a method I proposed a while back that is monotone, > clone free, always elects a candidate from the uncovered > set, and is independent from candidates that beat the > winner, i.e. if a candidate that pairwise beats the > winner is removed, the winner still wins: > > 1. List the candidates in order of decreasing approval. > > 2. If the approval winner A is uncovered, then A wins. > > 3. Otherwise, let C1 be the first candidate is the list > that covers A. If C1 is uncovered, then C1 wins. > > 4. Else let C2 be the first candidate in the list that > covers C1. If C2 is uncovered, then C2 wins. > > etc. Situation 1: Suppose the order of decreasing approval is CDAB. A beats B B beats C C beats D D beats A A beats C B beats D uncovered set: A, B, D. The winner is D. Situation 3: B beats D. If B is removed, then the uncovered set is: A, C, D. So, if B is removed, then C wins. So, the proposed method doesn't satisfy this property: "If a candidate that pairwise beats the winner is removed, the winner still wins." Markus Schulze Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] How close can we get to the IIAC
Hallo, > Here's a method I proposed a while back that is monotone, > clone free, always elects a candidate from the uncovered > set, and is independent from candidates that beat the > winner, i.e. if a candidate that pairwise beats the > winner is removed, the winner still wins: > > 1. List the candidates in order of decreasing approval. > > 2. If the approval winner A is uncovered, then A wins. > > 3. Otherwise, let C1 be the first candidate is the list > that covers A. If C1 is uncovered, then C1 wins. > > 4. Else let C2 be the first candidate in the list that > covers C1. If C2 is uncovered, then C2 wins. > > etc. Situation 1: Suppose the order of decreasing approval is CDAB. A beats B B beats C C beats D D beats A A beats C B beats D uncovered set: A, B, D. The winner is D. * Situation 2: Suppose some voters rank D higher so that D beats B. Suppose the order of decreasing approval is still CDAB. A beats B B beats C C beats D D beats A A beats C D beats B uncovered set: A, C, D. Now, the winner is C. So, monotonicity is violated. Markus Schulze Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] How close can we get to the IIAC
- Original Message - From: Kristofer Munsterhjelm Date: Friday, April 16, 2010 10:14 am Subject: Re: [EM] How close can we get to the IIAC To: fsimm...@pcc.edu Cc: election-methods@lists.electorama.com > fsimm...@pcc.edu wrote: > > > Schulze's CSSD (Beatpath) method does not satisfy the IIAC, > but it does satisfy > > all of Arrow's other criteria, that is to say all of the > reasonable ones plus > > some others like Clone Independence, Independence from Pareto > Dominated> Alternatives, etc. We cannot hold the IIAC against > Schulze, because no > > reasonable method satisfies the IIAC. > > A nitpick: Schulze doesn't satisfy Independence from Pareto- > dominated > Alternatives. Steve Eppley gives an example on his site: > > 1: A>D>E>C>B > 5: A>D>E>B>C > 3: A>B>D>E>C > 2: B>A>D>E>C > 2: B>D>E>C>A > 6: C>B>A>D>E > 4: C>A>B>D>E > 5: D>E>C>A>B > 2: D>B>E>C>A > > D Pareto-dominates E. If E is removed, Schulze elects A, but if > not, > Schulze elects B. Thanks for the correction. > > A couple of years ago someone proposed that if adding a > candidate changed the > > winner, the new winner should be either the new candidate or > someone that beats > > the new candidate pairwise. > > I think Woodall has stated a weak version of IIA, as well. Ah > yes, here > it is: > > Weak-IIA. If x is elected, and one adds a new candidate y ahead > of x on > some of the ballots on which x was first preference (and nowhere > else), > then either x or y should be elected. Here's a method I proposed a while back that is monotone, clone free, always elects a candidate from the uncovered set, and is independent from candidates that beat the winner, i.e. if a candidate that pairwise beats the winner is removed, the winner still wins: 1. List the candidates in order of decreasing approval. 2. If the approval winner A is uncovered, then A wins. 3. Otherwise, let C1 be the first candidate is the list that covers A. If C1 is uncovered, then C1 wins. 4. Else let C2 be the first candidate in the list that covers C1. If C2 is uncovered, then C2 wins. etc. There are variations on this method that preserve all of the mentioned properties, including methods that do not require approval information, but I think it is nicer to take into account approval information. If this is done via an approval cutoff on ranked ballots, the approval cutoff, AC, itself can be considered a candidate with 50% approval. No candidate with less than 50% approval can cover the AC, and the AC beats pairwise every candidate with less than 50% approval, so no candidate at all can cover the AC unless it pairwise beats all of the candidates with less than 50% approval. What do we do if AC wins the election? If we want a deterministic answer, I suggest that we elect the candidate C that has the least pairwise opposition from the AC. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] How close can we get to the IIAC
fsimm...@pcc.edu wrote: Schulze's CSSD (Beatpath) method does not satisfy the IIAC, but it does satisfy all of Arrow's other criteria, that is to say all of the reasonable ones plus some others like Clone Independence, Independence from Pareto Dominated Alternatives, etc. We cannot hold the IIAC against Schulze, because no reasonable method satisfies the IIAC. A nitpick: Schulze doesn't satisfy Independence from Pareto-dominated Alternatives. Steve Eppley gives an example on his site: 1: A>D>E>C>B 5: A>D>E>B>C 3: A>B>D>E>C 2: B>A>D>E>C 2: B>D>E>C>A 6: C>B>A>D>E 4: C>A>B>D>E 5: D>E>C>A>B 2: D>B>E>C>A D Pareto-dominates E. If E is removed, Schulze elects A, but if not, Schulze elects B. If Schulze satisfied IPDA, the method would be even better than it is, but the difference may amount to nothing in the context of large public elections. Schulze does satisfy local IIA, i.e. independence from alternatives not in the Smith set, by virtue of always electing from the Smith set. In short it is possible to satisfy all of Arrow's criteria simultaneously except the IIAC. So you cannot use Arrow's Theorem to excuse the lack of any of his criteria, except the IIAC. If you could trade in a couple of the other criteria for the IIAC, it might be worth it, but you cannot make this trade, unless you are willing to sacrifice either decisiveness or two candidate majority (not to mention Condorcet and Monotonicity which both separately imply the two candidate majority condition). So IRV supporters cannot rationally blame Arrow for IRV's lack of compliances, since its compliances are not maximal within Arrow's set of criteria. They must resort to Benham or Woodall to explain that IRV has maximal compliance within some other set of criteria, not Arrow's. That's an interesting way to counter the IRV supporters; I hadn't thought of it, probably because I've considered the later proof of Arrow's (the one with unanimity) rather than the earlier one with monotonicity. It is kind of like saying that the three real algebraic equations x+y+z=5, x-y+2z=7, and z+12=z are incompatible. It is true that they are incompatible, but only because z+12 cannot equal z in the field of real numbers. The third equation is definitely to blame for the trouble, though it does make sense in mod twelve clock arithmetic. Since the IIAC is out of the question, how close can we get to the IIAC? Independence from Pareto Dominated Alternatives (IPDA) is one tiny step in that direction. Another step might be independence from alternatives that are not in the Smith set. If our only objective is to grow "independence from *" to as large a space as possible (Independence from Smith-dominated alternatives, IPDA, ...), then we may have to let go of other objectives on the way. The very statement that "IIAC is out of the question" is really just a variant of that, where we say that IIAC demands too much. Therefore, there has to be some limit to when we'll no longer permit the tradeoff. Where is that limit? The question depends on the relative value of criteria. For instance, say independence of non-Dutta candidates implies nonmonotonicity - I don't know if it does, but for the sake of the argument... then a Condorcet method that satisfies INDC would be neat, but I wouldn't be willing to give up monotonicity for it. Pressed to reason why, I would likely say something that in public voting settings, the additional protection conferred by INDC over say independence of non-Smith or Pareto-dominated alternatives is slight, but the loss of monotonicity is great, for the latter means that the way the method determines whether a candidate is "good" is itself suspect. A couple of years ago someone proposed that if adding a candidate changed the winner, the new winner should be either the new candidate or someone that beats the new candidate pairwise. I think Woodall has stated a weak version of IIA, as well. Ah yes, here it is: Weak-IIA. If x is elected, and one adds a new candidate y ahead of x on some of the ballots on which x was first preference (and nowhere else), then either x or y should be elected. ( http://www.mcdougall.org.uk/VM/ISSUE3/P5.HTM ) Election-Methods mailing list - see http://electorama.com/em for list info
[EM] How close can we get to the IIAC
Arrow's Theorem is grossly misunderstood, because people have the mistaken impression that the Independence from Irrelevant Alternatives Criterion (IIAC) is on a par with the other criteria he mentions in his theorem. To clear this up, let's consider the following theorem which is the essence of Arrow's Theorem: The Independence from Irrelevant Alternatives Criterion is incompatible with any decisive method that satisfies the Majority Criterion in the two candidate case: Proof: Suppose by way of contradiction that we have a decisive method that satisfies both the IIAC and (in the two candidate case) the Majority Criterion. Consider a three candidate pairwise majority beat cycle in which A beats B beats C beats A, which is not a perfect three way tie, i.e. which lacks the symmetry that would demand a three way tie even from a decisive method. Since the method is decisive there must be a winner. Without loss in generality suppose this winner to be A. Since we assume the IIAC is satisfied, removing a loser (B for example) cannot change the winner. So between A and the remaining loser C, candidate A must still win. But this contradicts the step "C beats A" in the majority pairwise beat cycle. This contradiction shows that the given conditions are incompatible. Note that "two candidate majority win" is extremely weak. All reasonable deterministic methods satisfy it, even Borda. Any deterministic method that is monotone in the two candidate case satisfies it. So no reasonable, decisive, deterministic method can satisfy the IIAC. Therefore contrary to naive expectations, the IIAC is not a reasonable requirement after all. This is the real way to interpret Arrow's theorem, contrary to the popular paraphrase "no voting method can satisfy all of the reasonable requirements of a voting method." The statement in quotes may be true, but it is does not accurately paraphrase Arrow's Theorem. Schulze's CSSD (Beatpath) method does not satisfy the IIAC, but it does satisfy all of Arrow's other criteria, that is to say all of the reasonable ones plus some others like Clone Independence, Independence from Pareto Dominated Alternatives, etc. We cannot hold the IIAC against Schulze, because no reasonable method satisfies the IIAC. In short it is possible to satisfy all of Arrow's criteria simultaneously except the IIAC. So you cannot use Arrow's Theorem to excuse the lack of any of his criteria, except the IIAC. If you could trade in a couple of the other criteria for the IIAC, it might be worth it, but you cannot make this trade, unless you are willing to sacrifice either decisiveness or two candidate majority (not to mention Condorcet and Monotonicity which both separately imply the two candidate majority condition). So IRV supporters cannot rationally blame Arrow for IRV's lack of compliances, since its compliances are not maximal within Arrow's set of criteria. They must resort to Benham or Woodall to explain that IRV has maximal compliance within some other set of criteria, not Arrow's. It is kind of like saying that the three real algebraic equations x+y+z=5, x-y+2z=7, and z+12=z are incompatible. It is true that they are incompatible, but only because z+12 cannot equal z in the field of real numbers. The third equation is definitely to blame for the trouble, though it does make sense in mod twelve clock arithmetic. Since the IIAC is out of the question, how close can we get to the IIAC? Independence from Pareto Dominated Alternatives (IPDA) is one tiny step in that direction. Another step might be independence from alternatives that are not in the Smith set. A couple of years ago someone proposed that if adding a candidate changed the winner, the new winner should be either the new candidate or someone that beats the new candidate pairwise. In my next message I will consider the IIAC approximation problem from another point of view. Election-Methods mailing list - see http://electorama.com/em for list info
