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

[Jameson Quinn]

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 <fsimmons at pcc.edu>

> 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/7d8e23b0/attachment-0004.htm>