Hi, In a couple of recent messages I mentioned my attempt to strengthen "independence from clones" to "independence from similar alternatives" (ISA). I defined similar alternatives in a message posted this morning. I haven't yet mentioned methods which comply with ISA or which "practically" comply in large public elections, and I haven't yet described a proposed tie- breaker. This message addresses those questions. Definition: A correspondence is a function which takes as its arguments a set of voters' rankings of the alternatives and a "feasible" set which is a non-empty subset of the alternatives, and chooses a non-empty subset of the feasible set, and chooses the same when alternatives not in the feasible set are deleted from the rankings. Definition: A correspondence is partially independent from similar alternatives if and only if for any set of voters' rankings, any set Y which is a similar set according to the rankings, and any set Ys which is a strict subset of Y, the following two conditions hold: 1. For all alternatives x not in Y, x is chosen when all alternatives are feasible if and only if x is chosen when all except those in Ys are feasible. 2. At least one alternative in Y is chosen when all alternatives are feasible if and only if at least one alternative in Y is chosen when all except those in Ys are feasible. I believe several of the voting procedures we've discussed here in EM are partially independent from similar alternatives, when suitably adjusted so they accept a feasible set as an argument: BCM, IBCM (a.k.a. DCD), probably Schulze, probably MTM (which is a "majoritarian", not a "margins", variation of Tideman). (Assuming this is true of Schulze, then it would also be true of Blake's "path voting" if the definition of similar set were modified to use margins instead of majorities.) If these beliefs are true, then all of those methods except BCM would be sufficiently decisive in large public elections that one could justifiably claim they are "practically" independent from similar alternatives in large public elections. While driving toward complete independence, I developed a tie- breaking procedure which I call Dissimilar(g). It's defined with respect to any g which is a correspondence. Here are the definitions associated with Dissimilar(g): Definition: For any set S, let #S denote the cardinality of S. Definition: For any sets S1 and S2, let S1\S2 denote the set of elements of S1 which are not in S2. Definition: Given a set S, random(S) denotes a function which randomly picks an element of S consistently with the lottery which gives an equal 1/#S chance to each element in S. (Note that when S is a singleton, random(S) picks the lone element of S with certainty.) Definition: A set Y of alternatives is a similar set with respect to a set Z of alternatives if and only if Y is a subset of Z and Y is a similar set when all alternatives not in Z are deleted from the rankings. Let A denote the set of alternatives. Let R denote the set of voters' rankings. Let Z denote the feasible set of alternatives (which may have been reduced before the Dissimilar tie-breaker is reached). Definition: Given any correspondence g, Dissimilar(g)(R,Z) elects according to the following procedure: Let D denote a variable set of alternatives. Let L denote a variable n-tuple of real numbers, with one component for each alternative. Let Represent denote a variable n-tuple of alternatives, with one component for each alternative. Step 1: (Initialization) 1.1 Let D = Z. 1.2 For all x in Z, let L(x)=1. 1.3 For all x in A\Z, let L(x)=0. 1.4 For all x in A, let Represent(x)=x. Step 2. Repeat while #D > 1: 2.1 Pick a set Y which is a similar set with respect to D such that #Y > 1 and no strict subset of Y having cardinality > 1 is a similar set with respect to D. 2.2 Let G = g(R,D). Let x' = random(G). 2.3 For all x in Z such that Represent(x) is in Y\G, let L(x)=0. 2.4 For all x in Z such that Represent(x) is in G, let L(x)=L(x)/#G and let Represent(x)=x'. 2.5 Let D = (D\Y) U {x}. Step 3. Randomly elect one alternative consistently with the lottery L, interpreting each component of L as the probability that its corresponding alternative will be elected. Remarks: 1. In step 2.1, while #D>1 there must be at least one such set Y since D is trivially a similar set with respect to D. 2. I haven't hammered out an algorithm for finding Y in step 2.1 and in the worst case, where #Z is large, it could take a long time to compute. This suggests that Dissimilar is useful only as a tie-breaker. 3. Assume that g (used in step 2.2) is partially independent from similar alternatives, and that g is "2-candidate majoritarian." (Definition of 2-candidate majoritarian: Given exactly 2 feasible candidates {x,y}, {x} is chosen whenever x beats y pairwise and {x,y} is chosen whenever x ties y pairwise. Note that most prominent single-winner methods are 2-candidate majoritarian.) 4. Step 2.5 eliminates from D all of Y except one "g-best" alternative of Y. Since Y is not a singleton, this must reduce the cardinality of D by at least 1 for each repetition of step 2. Here's an example showing the operation of Dissimilar: 3 alternatives {x, y1, y2} 100 voters rank the alternatives as follows: 1: y1 > x > y2 24: x > y1 > y2 25: x > y2 > y1 25: y1 > y2 > x 24: y2 > y1 > x 1: y2 > x > y1 The three pairings are all 50/50 ties so a tie-breaker is needed if a pairwise method is employed. Note that by changing 2 votes to produce the 25/25/25/25 scenario, y1 and y2 would be clones, and x would have a 1/2 chance of being elected, given Random Dictator or Random Hierarchy, if at least one of the y's competes. As is, y1 and y2 are similar alternatives but not clones, and Random Dictator and Random Hierarchy would give x only a 49/100 chance if both of the y's compete, but a 1/2 chance if exactly one of the y's compete. In step 1, Dissimilar initializes D={x,y1,y2}, L=(1,1,1), and Represent=(x,y1,y2). In step 2.1, Dissimilar finds Y={y1,y2}. In step 2.2, G=g(R,Y) must be {y1} or {y2} or {y1,y2}. Since the "y1 vs. y2" pairing is a tie, assume G={y1,y2}. Then x' is either y1 or y2, randomly picked. Assume x'=y1. In step 2.3, nothing happens since Y\G is empty. In step 2.4, Dissimilar sets L=(1,.5,.5) since #G=2, and sets Represent=(x,y1,y1). (Now y2 is represented by y1.) In step 2.5, Dissimilar eliminates y2 from D, so D=(x,y1}. Since #D is still greater than 1, step 2 repeats: In step 2.1, Y={x,y1}. In step 2.2, since the "x vs. y1" pairing is a tie, assume G=g(R,Y)={x,y1}. Then x' is either x or y1, randomly picked. Let's consider both cases: Case 1: x' = x. In step 2.3, nothing happens since Y\G is empty. In step 2.4, Dissimilar sets L=(.5,.25,.25) and sets Represent=(x,x,x). In step 2.5, Dissimilar sets D={x}. Then step 2 no longer repeats, and Dissimilar elects using the lottery (.5,.25,.25). Case 2: x' = y1. In step 2.3, nothing happens since Y\G is empty. In step 2.4, Dissimilar sets L=(.5,.25,.25) and sets Represent=(y1,y1,y1). In step 2.5, Dissimilar sets D={y1}. Then step 2 no longer repeats, and Dissimilar elects using the lottery (.5,.25,.25). One can easily verify that if g is a pairwise method, so that in the example g(R,Y) will always choose all of Y in step 2.2, then the lottery will be (.5,.25,.25) in all cases, and the probability that x will be elected is 1/2 if at least one of the y's competes. So in this example Dissimilar works as desired, providing independence from a similar set which is not a clone set. The only problem I'm aware of so far (apart from the slowness of calculating step 2.1 when #Z is large), which may be what loses complete compliance with ISA, is related to the ambiguity in step 2.1: there may be more than one similar set which could be picked for Y. This won't matter if the pickable sets are disjoint, since in this case the order they're picked won't matter ultimately. But what if two (or more) have a non-empty intersection? For instance, suppose that {y1,y2} and {y2,y3} are both similar sets with respect to D. I'm not yet sure if this can cost compliance with ISA, but my intuition is that there's a problem. There's a possible patch for the definition of similar set which is analogous to the patch for the clone definition which Markus reposted a couple of days ago. It would prevent {y1,y2} and {y2,y3} from being similar sets when {y1,y2,y3} is a similar set. But I don't think this would be as innocuous as the clone patch, since would-be manipulators could have a strong preference for two of the three over the third. Take the case where the would-be manipulators strongly prefer y1&y2 over y3, and assume the three are technically similar and all reach the tie-breaker. By nominating both y1 and y2, they reduce y3's chance of election, assuming the patch where {y1,y2} and {y2,y3} are not similar but {y1,y2,y3} is similar. Can we do better? ---Steve (Steve Eppley [EMAIL PROTECTED])