OK, so what's DMC? Feel free to link to an electowiki description or old post, you don't have to rewrite the description.
Or... well, I guess I can figure it out - it's approval bubble-sorted by pairwise. And it's apparently monotone and clone-free, but not uncovered. So if the approval order is A>B but B is the pairwise champion (CW), then a "caricature of B", B', who beats B but loses to A, can stop B from winning DMC, but will not stop them in DMC/Covering Chain. Am I right? Still, I think that DMC is "good enough" in practical terms; I don't think that the (debatable) benefits of the other methods are worth the extra complication. "The most-approved candidate who could beat all more-approved candidates" is actually pretty easy to understand. JQ 2010/12/2 <[email protected]> > 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
