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

[C.Benham]

After pasting below, I fixed up the  "MCA instead of DMC" mistake, in 
accordance with what Forest
has since wrote that he meant.

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

I vastly prefer the  covering chain method.  When the Smith set has 3 
members (more would be very uncommon),
it is the same as  Smith//Approval (which I like and endorse).

25: A>B
06: A>C
32: B>C
27: C>A
10: C

C>A 69-31,   A>B 58-32,   B>C 57-43

Approval (ranking) scores: C 75,  A 58,  B 57.

As I pointed out in an earlier thread, the climbing chain method elects A.
The complaint of the voters who prefer C would in my mind be unanswerable.

>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
>Definite Majority Choice order after the bubble sort, and we would discover
>alternative D to be the DMC winner.
>
>The list L'  is fair game for our two methods, since bubble sorting preserves
>monotonicity and clone independence,...
>

That would also be true of  Approval-Sorted Margins, which I prefer:

http://wiki.electorama.com/wiki/Approval_Sorted_Margins

> First "seed" the list in approval order. Then while any alternative X 
> pairwise defeats the alternative Y immediately
> above it in the list, find the X and Y of this type that have the 
> least difference D in approval, and modify the list by swapping X and Y.


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

I am happy with this, if the Approval-Sorted Margins order is used for 
L' . More simply just using the plain approval
order for L would also probably be fine.

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

But not with this. That would still give the dominated (by C) candidate 
A in my example a 50% chance of
winning.


Chris Benham




Forest Simmons wrote (2 Dec 2010):

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
Definite Majority Choice order after the bubble sort, and we would discover
alternative D to be the DMC 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 DMC 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 DMC 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 DMC runner-up C is the covering chain
winner for the unsorted list L and the chain climbing winner for the sorted list
L' .

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

------------------------------------------------------------------------

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20101217/e2b5fe5c/attachment-0004.htm>