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

[Jameson Quinn]

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 <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
> > >
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20101202/4911b880/attachment-0004.htm>