[EM] A Comparison of the Two Known Monotone, Clone Free Methods for Electing Uncovered Alternatives

[fsimmons at pcc.edu]

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: fsimmons at pcc.edu
Cc: election-methods at lists.electorama.com

> 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
> >
>