fsimmons | 3 Dec 02:36 2010

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

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
(Continue reading)

Jameson Quinn | 3 Dec 02:59 2010
Picon

Re: A Comparison of the Two Known Monotone, Clone Free Methods for Electing Uncovered Alternatives

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

----
Election-Methods mailing list - see http://electorama.com/em for list info
fsimmons | 3 Dec 03:46 2010

Re: A Comparison of the Two Known Monotone, Clone Free Methods for Electing Uncovered Alternatives

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
> >
> 
----
Election-Methods mailing list - see http://electorama.com/em for list info

Jameson Quinn | 3 Dec 05:13 2010
Picon

Re: A Comparison of the Two Known Monotone, Clone Free Methods for Electing Uncovered Alternatives

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

----
Election-Methods mailing list - see http://electorama.com/em for list info
Kristofer Munsterhjelm | 3 Dec 10:39 2010
Picon

Re: A Comparison of the Two Known Monotone, Clone Free Methods for Electing Uncovered Alternatives

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

I think Short Ranked Pairs also passes all these. To my knowledge, Short 
Ranked Pairs is like Ranked Pairs, except that you can only admit X>Y if 
that will retain the property that every pair of affirmed candidates 
have a beatpath of at most two steps between them.

See

http://lists.electorama.com/pipermail/election-methods-electorama.com/2004-November/014255.html 
. The definition of a short acyclic set of defeats was later changed, 
and the new definition is at 
http://lists.electorama.com/pipermail/election-methods-electorama.com/2004-November/014258.html

I also guess you could make methods with properties like the above by 
constraining monotone cloneproof methods to the Landau set (whether by 
making something like Landau,Schulze or Landau/Schulze). I'm not sure of 
that, however, particularly not in the X/Y case since the elimination 
could lead to unwanted effects.

Is one of the two methods you mention UncAAO generalized?
----
Election-Methods mailing list - see http://electorama.com/em for list info

fsimmons | 3 Dec 20:53 2010

Re: A Comparison of the Two Known Monotone, Clone Free Methods for Electing Uncovered Alternatives

Yes, that's DMC, just bubble sort the approval order. So the DMC winner is the
lowest approval candidate that pairwise beats every candidate with more approval.

----- Original Message -----
From: 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?

That's the idea.

>
> 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
>
> > 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!
> >
----
Election-Methods mailing list - see http://electorama.com/em for list info

fsimmons | 3 Dec 21:01 2010

Re: A Comparison of the Two Known Monotone, Clone Free Methods for Electing Uncovered Alternatives

Thanks for bringing these other ideas to my attention.

Where's a good place to find out more about the Landau set?  Is it really
possible to have a monotone, clone free method that is independent of non-Landau
alternatives?

And yes, the chain covering method is an adaptation of UncAAO to any monotone,
clone free list.

----- Original Message -----
From: Kristofer Munsterhjelm
> fsimmons <at> pcc.edu wrote:
> > 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.
>
> I think Short Ranked Pairs also passes all these. To my
> knowledge, Short
> Ranked Pairs is like Ranked Pairs, except that you can only
> admit X>Y if
> that will retain the property that every pair of affirmed
> candidates
> have a beatpath of at most two steps between them.
>
> See
> http://lists.electorama.com/pipermail/election-methods-
> electorama.com/2004-November/014255.html
> . The definition of a short acyclic set of defeats was later
> changed,
> and the new definition is at
> http://lists.electorama.com/pipermail/election-methods-
> electorama.com/2004-November/014258.html
>
> I also guess you could make methods with properties like the
> above by
> constraining monotone cloneproof methods to the Landau set
> (whether by
> making something like Landau,Schulze or Landau/Schulze). I'm not
> sure of
> that, however, particularly not in the X/Y case since the
> elimination
> could lead to unwanted effects.
>
> Is one of the two methods you mention UncAAO generalized?
> 
----
Election-Methods mailing list - see http://electorama.com/em for list info

fsimmons | 3 Dec 21:57 2010

Re: A Comparison of the Two Known Monotone, Clone Free Methods for Electing Uncovered Alternatives

> Where's a good place to find out more about the Landau set? Is
> it really
> possible to have a monotone, clone free method that is
> independent of non-Landau
> alternatives?

It turns out that there are several versions of covering, depending on how ties
are treated.  All of them including the Landau set are the same when there are
no pairwise ties (except with self).

In July of this year I gave an example that shows that no decent deterministic
monotone method can be independent from covered alternatives.  The example
applies to the Landau version of uncovered.  So neither Ranked Pairs nor
Beatpath nor Range restricted to Landau can monotone.

Here's the example

Suppose that we have a method that satisfies independence from non-Landau
alternatives, and that gives 
greater winning probability to alternative B in this scenario

40 B>C>A
30 C>A>B
30 A>B>C

than in this scenario

40 D>B>C
30 B>C>D
30 C>D>B

as any decent method would.

Then consider the scenario

40 D>B>C>A
30 A>B>C>D
30 C>A>D>B

The Landau set is {A,B,C} and so by independence from non-Landau alternatives
the winner is chosen 
according to the first scenario above.

Now switch A and B in the second faction to get

40 D>B>C>A
30 B>A>C>D
30 C>A>D>B .

The Landau set becomes  {D,B,C}.and so by independence from non-Landau
alternatives the winner is 
chosen according to the second scenario above.

In summary, solely by raising B relative to A , the winning probability of B
decreased.

For a deterministic method the probability of B would go from one to zero.

----
Election-Methods mailing list - see http://electorama.com/em for list info

Jobst Heitzig | 4 Dec 01:27 2010
Picon

Re: A Comparison of the Two Known Monotone, Clone Free Methods for Electing Uncovered Alternatives

Hi Kristofer,

you wrote:
> I think Short Ranked Pairs also passes all these. To my knowledge, Short
> Ranked Pairs is like Ranked Pairs, except that you can only admit X>Y if
> that will retain the property that every pair of affirmed candidates
> have a beatpath of at most two steps between them.
> 
> See
> http://lists.electorama.com/pipermail/election-methods-electorama.com/2004-November/014255.html
> . The definition of a short acyclic set of defeats was later changed,
> and the new definition is at
> http://lists.electorama.com/pipermail/election-methods-electorama.com/2004-November/014258.html

Thanks for unearthing this old idea of mine -- I had forgotten them
completely already.

Unfortunately, I fear Short Ranked Pairs might not be monotonic. One
would habe to check. And I'm not sure your description of an algorithm
for Short Ranked Pairs is valid -- after all, I only defined it
abstractly by saying that one has to find the "lexicographically maximal
short acyclic set" without giving an algorithm to find it.

I propose to proceed as follows: Check how that lexicographically
maximal short acyclic set can be found in the simpler case in which we
define defeat strength as approval of defeating option. This will also
allow us to compare the method to DMC since DMC is the result of
applying ordinary Ranked Pairs with this definition of defeat strength,
so applying Short Ranked Pairs to them should not be too much different.

The resulting short acyclic set will contain all defeats from the
approval winner to other options, but I don't see immediately whether
one can somehow continue to lock in defeats similar to ordinary Ranked
Pairs, skipping certain defeats that would destroy the defining
properties of a short acyclic set. I somehow doubt that since that
defining property is not that some configurations must not exist but
than some configurations must exist. Anyway, in the case where defeat
strength is approval of defeating option, all might be somewhat simpler.

Jobst

> 
> 
> I also guess you could make methods with properties like the above by
> constraining monotone cloneproof methods to the Landau set (whether by
> making something like Landau,Schulze or Landau/Schulze). I'm not sure of
> that, however, particularly not in the X/Y case since the elimination
> could lead to unwanted effects.
> 
> Is one of the two methods you mention UncAAO generalized?
> ----
> Election-Methods mailing list - see http://electorama.com/em for list info
----
Election-Methods mailing list - see http://electorama.com/em for list info

Jobst Heitzig | 4 Dec 12:17 2010
Picon

Re: A Comparison of the Two Known Monotone, Clone Free Methods for Electing Uncovered Alternatives

Hi again,

I wrote:
> Unfortunately, I fear Short Ranked Pairs might not be monotonic. One
> would habe to check. And I'm not sure your description of an algorithm
> for Short Ranked Pairs is valid -- after all, I only defined it
> abstractly by saying that one has to find the "lexicographically maximal
> short acyclic set" without giving an algorithm to find it.

Maybe my gut-feeling was incorrect. Short Ranked Pairs is probably
monotonic. As it is also clone-proof and uncovered, we really have a
third type of method with those three properties, just as Kristofer
remarked!

Now why should it be monotonic? Assume that...

s(x,y) is the strength of the defeat x>y,

s1>s2>s3... is the descending sequence of all defeat strengths,

x1>y1,x2>y2,x3>y3,... are the corresponding defeats,

D is the lexicographically maximal short acyclic set of defeats,

w is the top option of D

and I is the set of ranks i of defeats in the above numbering that
belong to D, so that

D = { xi>yi : i in I }.

Then no defeat x>w is in D, hence all defeats w>y are in D since
otherwise adding them won't construct a cycle.

Now assume some defeat w>a is reinforced, moving it up in the ordering
x1>y1,x2>y2,x3>y3,... by one place. Let j be the index of w>a in this
list before the reinforcing, so that w=xj, a=yj. Also introduce a new
numbering of the defeats corresponding to the new ranking of defeats:

x'1>y'1,x'2>y'2,x'3>y'3,...

Then x'i=xi and y'i=yi for all i different from j and j-1,
and x'j=x(j-1), y'j=y(j-1), x'(j-1)=xj=w, y'(j-1)=yj=a.
D consists of those defeats x'i>y'i with ranks i in the new set

J = I with j and j-1 exchanged.

We will prove that after the reinforcing, D is still lexicographically
maximal. Assume that it is not. Then there is another short acyclic set
of defeats D' that is lexicographically larger than D in the new ranking
of defeats. Hence there is some new rank k such that the defeat x'k>y'k
is in D' but not in D, and such that for all i<k, the defeat x'i>y'i is
either in both D' and D or in neither of the two.

If k were different from j-1, then D' would be already lexicographically
larger than D in the original ranking of defeats, which was not the case
as D was maximal there.

But k can't be j-1 since the defeat x'(j-1)>y'(j-1) is the defeat w>a
and thus belongs to D. Hence there is no such D' as assumed, D is still
lexicographically maximal, and w is still the winner after the
reinforcement of the defeat w>a. That is, Short Ranked Pairs is monotonic.

> I propose to proceed as follows: Check how that lexicographically
> maximal short acyclic set can be found in the simpler case in which we
> define defeat strength as approval of defeating option. 

This is still open and I don't see a simple algorithm coming to my mind...

> This will also
> allow us to compare the method to DMC since DMC is the result of
> applying ordinary Ranked Pairs with this definition of defeat strength,
> so applying Short Ranked Pairs to them should not be too much different.
> 
> The resulting short acyclic set will contain all defeats from the
> approval winner to other options, but I don't see immediately whether
> one can somehow continue to lock in defeats similar to ordinary Ranked
> Pairs, skipping certain defeats that would destroy the defining
> properties of a short acyclic set. I somehow doubt that since that
> defining property is not that some configurations must not exist but
> than some configurations must exist. Anyway, in the case where defeat
> strength is approval of defeating option, all might be somewhat simpler.
> 
> Jobst
> 
> 
> 
>>
>>
>> I also guess you could make methods with properties like the above by
>> constraining monotone cloneproof methods to the Landau set (whether by
>> making something like Landau,Schulze or Landau/Schulze). I'm not sure of
>> that, however, particularly not in the X/Y case since the elimination
>> could lead to unwanted effects.
>>
>> Is one of the two methods you mention UncAAO generalized?
>> ----
>> Election-Methods mailing list - see http://electorama.com/em for list info
> ----
> Election-Methods mailing list - see http://electorama.com/em for list info
----
Election-Methods mailing list - see http://electorama.com/em for list info


Gmane