[EM] Election-Methods Digest, Vol 78, Issue 12

[fsimmons at pcc.edu]

Chris,

Thanks for reminding me of Approval-Sorted Margins.  The covering chain method applied to the list obtained 
by approval sorted margins certainly has a maximal set of nice properties, in that any additional nice 
property would entail the loss of some highly desireable property.

Do you think it is better, in this context, to base approval on ranked-above-last, or by use of an explicit 
approval cutoff marker?

> From: "C.Benham" 
> To: em , Forest Simmons
> 
> Subject: [EM] A Comparison of the Two Known Monotone, Clone Free
> Methods for Electing Uncovered Alternatives
> Message-ID: <4D0A495C.7050608 at yahoo.com.au>
> Content-Type: text/plain; charset="iso-8859-1"; Format="flowed"
> 
> 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 
> climbingwinner. 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 
> climbingsequence 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 
> automaticallyelecting 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: > electorama.com/attachments/20101217/e2b5fe5c/attachment.htm>
> ------------------------------
> 
> _______________________________________________
> Election-Methods mailing list
> Election-Methods at lists.electorama.com
> http://lists.electorama.com/listinfo.cgi/election-methods-
> electorama.com
> 
> End of Election-Methods Digest, Vol 78, Issue 12
> ************************************************
>