My Bad. I meant DMC (democratic majority choice) not MCA. That's what I get for making up names for the sole purpose of making a method sound attractive!
----- Original Message ----- From: Jameson Quinn Date: Thursday, December 2, 2010 6:00 pm Subject: Re: [EM] A Comparison of the Two Known Monotone, Clone Free Methods for Electing Uncovered Alternatives To: [email protected] Cc: [email protected] > I understand all of this except your definition for MCA. As I > understand it, > MCA has more rating categories than approval, yet is not ranked, > so the MCA > order cannot be inferred from either approval or pairwise wins > or both. It > seems you have a different definition. > > JQ > > 2010/12/2 > > > To my knowledge, so far only two monotone, clone free, > uncovered methods > > have > > been discovered. Both of them are ways of processing given > monotone, clone > > free > > lists, such as a complete ordinal ballot or a list of > alternatives in order > > of > > approval. > > > > The first method, "chain climbing," starts at the bottom of > the list and > > works > > upward. It initializes a "chain" with the lowest alternative > of the list > > and > > while there is any alternative that pairwise beats all the > current members > > of > > the chain, the lowest such member of the list is added to the > chain. The > > last > > alternative added to the chain is the chain climbing winner. > > > > The second method, the "covering chain" method, starts at the > top of the > > list > > and works downward. A variable X is initialized as the > alternative highest > > on > > the list. While some alternative covers X, the highest such > alternative on > > the > > list becomes the new value of X. The final value of X is the > covering chain > > winner. > > > > Both methods pick from the uncovered set, so they are both Condorcet > > efficient. > > > > Suppose, for example, that the alternatives A, B, C, D, and E > are arranged > > along > > a line in alphabetical order with C at the voter median > position. The > > sincere, > > rational ordinal ballot of a voter near alternative A would > likely list the > > alternatives in alphabetical order. If this ballot were taken > as the list > > L, > > and the two methods were applied to L, the first method (chain > climbing)> would > > build up the chain in the order E,D, C, so C would be the > chain climbing > > winner. If the second method were used, the successive values > of X would > > be A, > > B, and C, so C would also be the covering chain winner. > > > > The two methods approach the voter median alternative from > opposite sides. > > > > If C were replaced with the cycle C1 beats C2 beats C3 beats > C1, and the > > list > > order became > > > > A, B, C1, C2, C3, D, E, > > > > then the chain climbing chain would build up in the order E, > D, C3, C2, > > with C2 > > winning, while the successive covering chain values of X would > be A, B, C1, > > respectively, with C1 becoming the covering chain winner. > > > > This illustrates the general principle that when the Smith set > is a cycle > > of > > three alternatives, chain climbing is more penetrating than > the covering > > chain > > method. In this context the covering chain method will always > stop at the > > first > > member of the top cycle that it encounters, thus pleasing > those voters who > > favor > > the list order, while the chain climbing method always > penetrates beyond > > the > > first member of the top cycle that it encounters, but it may > or may not > > make it > > to the highest member of the top cycle on the list. > > > > In the above example, the A supporter who supplied the list > would prefer > > the > > covering chain winner, but C2 might be better for the > electorate as a > > whole. > > > > Chain climbing has more penetrating power in another sense, > too. It never > > stops > > short of the Banks set, a special subset of the uncovered set. > When the > > top > > cycle has only three members, the Banks set contains all of > the uncovered > > set, > > so this Banks set penetration is something beyond that shown > in the above > > example. > > > > The covering chain method is not guaranteed to pick from > Banks, but it has > > a > > nice property that chain climbing lacks, namely it satisfies > independence> from > > pareto dominated alternatives (IPDA). > > > > So we cannot say that one of these methods is uniformly better > than the > > other. > > > > Here's another instructive example. Suppose that the list of > alternatives> is > > > > L = [A, D, B, C] in that order, and that the pairwise "beats" > relation is > > > > C beats B beats D beats A coupled with D beats C beats A beats B. > > > > Then, all of the alternatives are in the Smith set, but A is > covered only > > by C, > > so C is the covering chain winner. On the other hand the > chain climbing > > sequence is C followed by D, so D is the chain climbing > winner. This is > > the > > first example we have seen where the chain climbing winner > comes out higher > > on > > the list than the covering chain winner. That can never > happen when the > > top > > cycle (Smith set) has fewer than four members. > > > > Now suppose that we bubble sort the list L to get the list > > > > L' = [D, C, A, B] > > > > If the original list L were the approval order, then this list > would be the > > Majority Choice Approval order after the bubble sort, and we > would discover > > alternative D to be the MCA winner. > > > > The list L' is fair game for our two methods, since bubble sorting > > preserves > > monotonicity and clone independence, so let's see how they > compare with MCA > > in > > this example: > > > > Chain climbing builds up its chain in the order B, A, C, and > stops with C, > > since > > D does not beat B. So C is the chain climbing winner for the > list L'. On > > the > > other hand, C at the top of list L' is uncovered, so C is the > covering> chain > > winner for list L'. So in this example, our two methods > switch winners as > > we go > > from the unsorted list L to the bubble sorted list L'. > > > > So (under the assumption that L is the approval order) the MCA > winner D is > > the > > chain climbing winner for the unsorted list L, as well as the > covering> chain > > winner for the sorted list L', while the MCA runner-up C is > the covering > > chain > > winner for the unsorted list L and the chain climbing winner > for the sorted > > list > > L' . > > > > Since MCA is not guaranteed to pick from the uncovered set, I > am not > > suggesting > > that we consider it in the same class as our two uncovered > methods. But > > the > > above comparison at least makes a connection with something > more familiar > > to > > most of us. > > > > I do suggest the following: > > > > In any context where being as faithful as possible to the > original list > > order is > > considered important, perhaps because the only reason for not > automatically> electing the top of the list is a desire to > satisfy Condorcet efficiency, > > then > > in this case I suggest computing both the chain climbing > winner and the > > covering > > chain winner for the list L, and then going with which ever of > the two > > comes out > > higher on L. > > > > On the other hand, when the list L is just considered a > convenient starting > > place, with no other special importance, then I suggest bubble > sorting L to > > get > > L', and then flip a coin to decide which of the two methods to > use for > > processing this sorted list. > > > > This coin flip (after the ballots have been voted) will > largely foil > > attempts at > > manipulation. But it can also be thought of in the following > way: the two > > different methods tend to approach the "center" of the voter > distribution> from > > opposite sides, so they can be thought of as bracketing the > "center." The > > coin > > flip is an averaging mechanism that takes us closer (on > average) to the > > "center." > > > > If the coin flip is unpalatable, then apply only chain > climbing to L', > > since > > chain climbing is more apt to penetrate to the Banks set in general. > > > > Thought and comments? > > > > Thanks, > > > > Forest > > ---- > > Election-Methods mailing list - see http://electorama.com/em > for list info > > > ---- Election-Methods mailing list - see http://electorama.com/em for list info
