[EM] Improvement on Jobst's Chain climbing method

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

[EM] Improvement on Jobst's Chain climbing method

Forest Simmons
A few years back Jobst suggested "chain climbing" as a seamless, Condorcet compliant way of selecting an alternative from a given ordered list.

For example electing a winner from a list of candidates c1, c2, ... given in decreasing order of approval.

Chain Climbing initializes a chain of candidates with the last (least approved in this case) candidate in the list.  Then moving up the list each successive candidate "climbs the chain" as far it can before being bumped off by a chain member that defeats it. If it makes it all of the way to the top, it is added to the top of the chain.

The candidate who ends up at the top of the chain is elected.

Since a beats all candidate will never be defeated, the method is Condorcet compliant. It also turns out to be clone resistant and monotonic. 

Another nice property is that it always selects from the Banks set, a nice game theoretic subset set of the set of uncovered candidates. 

The biggest objection to this method is that when applied to a list a list where c1 beats c2 beats c3, and c3 beats c1, it elects c2.

Here's my proposed improvement:

Initialize the chain with c1.  Move down the list instead of up.  For each successive candidate x (as we move down the list) if possible, insert that candidate into the chain at a point where it is beaten by every candidate above it and is not defeated by any candidate below it.  If not possible, discard it.

After going through the entire list (top to bottom) inserting new candidates where possible into the totally ordered chain, we end up with a maximal totally ordered chain of candidates (ordered by pairwise defeat) The candidate at the top fo the completed chain (the one who is not defeated by any of the others) is elected.

It is easy to show that this method has all of the nice properties of chain climbing, but retains more of the spirit of the original list..

For example in the A>B>C example above it elects A.

What do you think?

Forest




----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Improvement on Jobst's Chain climbing method

Toby Pereira
Is this (the objection) definitely correct? I might be being stupid or might have misunderstood the method, but the chain starts:

1. c1 (most approvals)
2. c2
3. c3 (least approvals)

c3 then attempts to climb the chain, but is bumped of by their first opponent, c2, because c2 beats c3 in the head to head. Then c2 attempts to climb the chain but is bumped off by c1 who beats c2 in the head to head. c1 is then elected.

Toby



From: Forest Simmons <[hidden email]>
To: EM <[hidden email]>
Sent: Saturday, 2 March 2019, 21:20
Subject: [EM] Improvement on Jobst's Chain climbing method

A few years back Jobst suggested "chain climbing" as a seamless, Condorcet compliant way of selecting an alternative from a given ordered list.

For example electing a winner from a list of candidates c1, c2, ... given in decreasing order of approval.

Chain Climbing initializes a chain of candidates with the last (least approved in this case) candidate in the list.  Then moving up the list each successive candidate "climbs the chain" as far it can before being bumped off by a chain member that defeats it. If it makes it all of the way to the top, it is added to the top of the chain.

The candidate who ends up at the top of the chain is elected.

Since a beats all candidate will never be defeated, the method is Condorcet compliant. It also turns out to be clone resistant and monotonic. 

Another nice property is that it always selects from the Banks set, a nice game theoretic subset set of the set of uncovered candidates. 

The biggest objection to this method is that when applied to a list a list where c1 beats c2 beats c3, and c3 beats c1, it elects c2.

Here's my proposed improvement:

Initialize the chain with c1.  Move down the list instead of up.  For each successive candidate x (as we move down the list) if possible, insert that candidate into the chain at a point where it is beaten by every candidate above it and is not defeated by any candidate below it.  If not possible, discard it.

After going through the entire list (top to bottom) inserting new candidates where possible into the totally ordered chain, we end up with a maximal totally ordered chain of candidates (ordered by pairwise defeat) The candidate at the top fo the completed chain (the one who is not defeated by any of the others) is elected.

It is easy to show that this method has all of the nice properties of chain climbing, but retains more of the spirit of the original list..

For example in the A>B>C example above it elects A.

What do you think?

Forest



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



----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Improvement on Jobst's Chain climbing method

Chris Benham-2
In reply to this post by Forest Simmons

Forest,

I was impressed by your  "Max Covered Approval" method idea, which seems to be similar to this.

It differs by requiring any new addition to the chain to cover (not just pairwise beat) the last one.

So if the most approved candidate was uncovered it won, otherwise the most most approved candidate
that covered it if that candidate is uncovered, otherwise the most approved candidate that covered it,
and so on.

This is one of my two or three favourite (distinctly different from each other) Condorcet methods.

Chris Benham

On 3/03/2019 7:50 am, Forest Simmons wrote:
A few years back Jobst suggested "chain climbing" as a seamless, Condorcet compliant way of selecting an alternative from a given ordered list.

For example electing a winner from a list of candidates c1, c2, ... given in decreasing order of approval.

Chain Climbing initializes a chain of candidates with the last (least approved in this case) candidate in the list.  Then moving up the list each successive candidate "climbs the chain" as far it can before being bumped off by a chain member that defeats it. If it makes it all of the way to the top, it is added to the top of the chain.

The candidate who ends up at the top of the chain is elected.

Since a beats all candidate will never be defeated, the method is Condorcet compliant. It also turns out to be clone resistant and monotonic. 

Another nice property is that it always selects from the Banks set, a nice game theoretic subset set of the set of uncovered candidates. 

The biggest objection to this method is that when applied to a list a list where c1 beats c2 beats c3, and c3 beats c1, it elects c2.

Here's my proposed improvement:

Initialize the chain with c1.  Move down the list instead of up.  For each successive candidate x (as we move down the list) if possible, insert that candidate into the chain at a point where it is beaten by every candidate above it and is not defeated by any candidate below it.  If not possible, discard it.

After going through the entire list (top to bottom) inserting new candidates where possible into the totally ordered chain, we end up with a maximal totally ordered chain of candidates (ordered by pairwise defeat) The candidate at the top fo the completed chain (the one who is not defeated by any of the others) is elected.

It is easy to show that this method has all of the nice properties of chain climbing, but retains more of the spirit of the original list..

For example in the A>B>C example above it elects A.

What do you think?

Forest




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

Virus-free. www.avg.com

----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Improvement on Jobst's Chain climbing method

Richard Lung
In reply to this post by Forest Simmons

The American context of voting theory, in a country where single-winner elections predominate, is minimally democratic (maiorocracy, the tyranny of the majority: JS Mill) so unlikely to provide general conclusions.
And Condorcet is not an actual method, but a cross-checking of the result for any given method. Anyway, I suspect that this approach has turned into a search for the best way to eliminate candidates.
From my point of view, it is an unnecessary task, because the exclusion  of unprefered candidates can be conducted in a same accurate, rational manner (using Meek keep values) as the election of prefered candidates: Binomial STV, actually FAB STV. This does away with discarding the votes of candidates before the whole count has been completed. And thereby does away with non-monotonicity (preferential illogic in the count).

from Richard Lung.



On 02/03/2019 21:20, Forest Simmons wrote:
A few years back Jobst suggested "chain climbing" as a seamless, Condorcet compliant way of selecting an alternative from a given ordered list.

For example electing a winner from a list of candidates c1, c2, ... given in decreasing order of approval.

Chain Climbing initializes a chain of candidates with the last (least approved in this case) candidate in the list.  Then moving up the list each successive candidate "climbs the chain" as far it can before being bumped off by a chain member that defeats it. If it makes it all of the way to the top, it is added to the top of the chain.

The candidate who ends up at the top of the chain is elected.

Since a beats all candidate will never be defeated, the method is Condorcet compliant. It also turns out to be clone resistant and monotonic. 

Another nice property is that it always selects from the Banks set, a nice game theoretic subset set of the set of uncovered candidates. 

The biggest objection to this method is that when applied to a list a list where c1 beats c2 beats c3, and c3 beats c1, it elects c2.

Here's my proposed improvement:

Initialize the chain with c1.  Move down the list instead of up.  For each successive candidate x (as we move down the list) if possible, insert that candidate into the chain at a point where it is beaten by every candidate above it and is not defeated by any candidate below it.  If not possible, discard it.

After going through the entire list (top to bottom) inserting new candidates where possible into the totally ordered chain, we end up with a maximal totally ordered chain of candidates (ordered by pairwise defeat) The candidate at the top fo the completed chain (the one who is not defeated by any of the others) is elected.

It is easy to show that this method has all of the nice properties of chain climbing, but retains more of the spirit of the original list..

For example in the A>B>C example above it elects A.

What do you think?

Forest




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



----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Improvement on Jobst's Chain climbing method

Kevin Venzke
In reply to this post by Forest Simmons
Hi Forest, I agree your revision seems better. I also don't like the potential for C3 to change the outcome like that.

It seems like the revised method would usually elect C1, with the most common exception being when C2 pairwise defeats C1. As you proceed down the list it starts to become hard to imagine how the candidate could do well enough in pairwise contests (to be elected) while doing so poorly in approval.

So this seems to me like a clone-independent way of fixing an overly simple method like "elect the approval winner unless second place beats him pairwise."

Kevin


Le samedi 2 mars 2019 à 15:20:39 UTC−6, Forest Simmons <[hidden email]> a écrit :


A few years back Jobst suggested "chain climbing" as a seamless, Condorcet compliant way of selecting an alternative from a given ordered list.

For example electing a winner from a list of candidates c1, c2, ... given in decreasing order of approval.

Chain Climbing initializes a chain of candidates with the last (least approved in this case) candidate in the list.  Then moving up the list each successive candidate "climbs the chain" as far it can before being bumped off by a chain member that defeats it. If it makes it all of the way to the top, it is added to the top of the chain.

The candidate who ends up at the top of the chain is elected.

Since a beats all candidate will never be defeated, the method is Condorcet compliant. It also turns out to be clone resistant and monotonic. 

Another nice property is that it always selects from the Banks set, a nice game theoretic subset set of the set of uncovered candidates. 

The biggest objection to this method is that when applied to a list a list where c1 beats c2 beats c3, and c3 beats c1, it elects c2.

Here's my proposed improvement:

Initialize the chain with c1.  Move down the list instead of up.  For each successive candidate x (as we move down the list) if possible, insert that candidate into the chain at a point where it is beaten by every candidate above it and is not defeated by any candidate below it.  If not possible, discard it.

After going through the entire list (top to bottom) inserting new candidates where possible into the totally ordered chain, we end up with a maximal totally ordered chain of candidates (ordered by pairwise defeat) The candidate at the top fo the completed chain (the one who is not defeated by any of the others) is elected.

It is easy to show that this method has all of the nice properties of chain climbing, but retains more of the spirit of the original list..

For example in the A>B>C example above it elects A.

What do you think?

Forest




----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Improvement on Jobst's Chain climbing method

Forest Simmons
In reply to this post by Forest Simmons

Greetings again EM list friends:


I appreciate the response from Toby, P., Chris B., R. Lung, Kevin V. and Jobst H.


All of your observations are very close to my own thoughts, and I heartily agree with them all, except perhaps from Richard Lung who used some terminology with which I am unfamiliar. [I do not doubt its value, but I am not qualified to judge.]


Unfortunately, a rather subtle effect destroys mono-raise winner.  There is no problem if the only improvement in status of the winner is from increased approval.  But when the winner W adds another pairwise defeat (say candidate W over candidate X) this X may newly qualify for a position at the bottom of the chain, thus preventing some candidate Y lower down the approval list from occupying that bottom chain position any more, thus removing the only impassable obstacle from the rise of (even lower approval) candidate Z to the very top of the chain, thereby electing Z instead of W.


Right now I do not see any way around this, so  chain climbing (taught to us by Jobst) is the only monotone Banks method that I know of.

Sorry to get your hopes up in vain.  For me trying to improve on chain climbing is a kind of isometric exercise;  by straining against a hard, perhaps impossible problem, you get stronger (if it does not kill you).


And Chris is right; the idea for the covering chain method that starts at the top of the approval order and works its way down was inspired by my attempts at finding a monotone Banks method.  I do not have the time here to tell you about some of the other spinoff from these attempts.


Thanks Guys,


Forest


On Sat, Mar 2, 2019 at 1:20 PM Forest Simmons <[hidden email]> wrote:
A few years back Jobst suggested "chain climbing" as a seamless, Condorcet compliant way of selecting an alternative from a given ordered list.

For example electing a winner from a list of candidates c1, c2, ... given in decreasing order of approval.

Chain Climbing initializes a chain of candidates with the last (least approved in this case) candidate in the list.  Then moving up the list each successive candidate "climbs the chain" as far it can before being bumped off by a chain member that defeats it. If it makes it all of the way to the top, it is added to the top of the chain.

The candidate who ends up at the top of the chain is elected.

Since a beats all candidate will never be defeated, the method is Condorcet compliant. It also turns out to be clone resistant and monotonic. 

Another nice property is that it always selects from the Banks set, a nice game theoretic subset set of the set of uncovered candidates. 

The biggest objection to this method is that when applied to a list a list where c1 beats c2 beats c3, and c3 beats c1, it elects c2.

Here's my proposed improvement:

Initialize the chain with c1.  Move down the list instead of up.  For each successive candidate x (as we move down the list) if possible, insert that candidate into the chain at a point where it is beaten by every candidate above it and is not defeated by any candidate below it.  If not possible, discard it.

After going through the entire list (top to bottom) inserting new candidates where possible into the totally ordered chain, we end up with a maximal totally ordered chain of candidates (ordered by pairwise defeat) The candidate at the top fo the completed chain (the one who is not defeated by any of the others) is elected.

It is easy to show that this method has all of the nice properties of chain climbing, but retains more of the spirit of the original list..

For example in the A>B>C example above it elects A.

What do you think?

Forest




----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Improvement on Jobst's Chain climbing method

Chris Benham-2

Forest,

In that case I dump my advocacy of  Max Covered Approval. 

I seem to recall there was also some problem with Uncovered//Approval, so I'll stick with
Smith//Approval and maybe also Smith//Top-Ratings (along with some quite different methods).

Chris Benham


On 5/03/2019 8:26 am, Forest Simmons wrote:

Greetings again EM list friends:


I appreciate the response from Toby, P., Chris B., R. Lung, Kevin V. and Jobst H.


All of your observations are very close to my own thoughts, and I heartily agree with them all, except perhaps from Richard Lung who used some terminology with which I am unfamiliar. [I do not doubt its value, but I am not qualified to judge.]


Unfortunately, a rather subtle effect destroys mono-raise winner.  There is no problem if the only improvement in status of the winner is from increased approval.  But when the winner W adds another pairwise defeat (say candidate W over candidate X) this X may newly qualify for a position at the bottom of the chain, thus preventing some candidate Y lower down the approval list from occupying that bottom chain position any more, thus removing the only impassable obstacle from the rise of (even lower approval) candidate Z to the very top of the chain, thereby electing Z instead of W.


Right now I do not see any way around this, so  chain climbing (taught to us by Jobst) is the only monotone Banks method that I know of.

Sorry to get your hopes up in vain.  For me trying to improve on chain climbing is a kind of isometric exercise;  by straining against a hard, perhaps impossible problem, you get stronger (if it does not kill you).


And Chris is right; the idea for the covering chain method that starts at the top of the approval order and works its way down was inspired by my attempts at finding a monotone Banks method.  I do not have the time here to tell you about some of the other spinoff from these attempts.


Thanks Guys,


Forest


On Sat, Mar 2, 2019 at 1:20 PM Forest Simmons <[hidden email]> wrote:
A few years back Jobst suggested "chain climbing" as a seamless, Condorcet compliant way of selecting an alternative from a given ordered list.

For example electing a winner from a list of candidates c1, c2, ... given in decreasing order of approval.

Chain Climbing initializes a chain of candidates with the last (least approved in this case) candidate in the list.  Then moving up the list each successive candidate "climbs the chain" as far it can before being bumped off by a chain member that defeats it. If it makes it all of the way to the top, it is added to the top of the chain.

The candidate who ends up at the top of the chain is elected.

Since a beats all candidate will never be defeated, the method is Condorcet compliant. It also turns out to be clone resistant and monotonic. 

Another nice property is that it always selects from the Banks set, a nice game theoretic subset set of the set of uncovered candidates. 

The biggest objection to this method is that when applied to a list a list where c1 beats c2 beats c3, and c3 beats c1, it elects c2.

Here's my proposed improvement:

Initialize the chain with c1.  Move down the list instead of up.  For each successive candidate x (as we move down the list) if possible, insert that candidate into the chain at a point where it is beaten by every candidate above it and is not defeated by any candidate below it.  If not possible, discard it.

After going through the entire list (top to bottom) inserting new candidates where possible into the totally ordered chain, we end up with a maximal totally ordered chain of candidates (ordered by pairwise defeat) The candidate at the top fo the completed chain (the one who is not defeated by any of the others) is elected.

It is easy to show that this method has all of the nice properties of chain climbing, but retains more of the spirit of the original list..

For example in the A>B>C example above it elects A.

What do you think?

Forest




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

Virus-free. www.avg.com

----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Improvement on Jobst's Chain climbing method

Richard Lung
In reply to this post by Forest Simmons
More than anyone could possibly want to know about the terminology in question is found in my (Smashwords or Amazon kdp) book -- FAB STV: Four Averages Binomial Single Transferable Vote.

from Richard Lung.

On 04/03/2019 21:56, Forest Simmons wrote:

Greetings again EM list friends:


I appreciate the response from Toby, P., Chris B., R. Lung, Kevin V. and Jobst H.


All of your observations are very close to my own thoughts, and I heartily agree with them all, except perhaps from Richard Lung who used some terminology with which I am unfamiliar. [I do not doubt its value, but I am not qualified to judge.]


Unfortunately, a rather subtle effect destroys mono-raise winner.  There is no problem if the only improvement in status of the winner is from increased approval.  But when the winner W adds another pairwise defeat (say candidate W over candidate X) this X may newly qualify for a position at the bottom of the chain, thus preventing some candidate Y lower down the approval list from occupying that bottom chain position any more, thus removing the only impassable obstacle from the rise of (even lower approval) candidate Z to the very top of the chain, thereby electing Z instead of W.


Right now I do not see any way around this, so  chain climbing (taught to us by Jobst) is the only monotone Banks method that I know of.

Sorry to get your hopes up in vain.  For me trying to improve on chain climbing is a kind of isometric exercise;  by straining against a hard, perhaps impossible problem, you get stronger (if it does not kill you).


And Chris is right; the idea for the covering chain method that starts at the top of the approval order and works its way down was inspired by my attempts at finding a monotone Banks method.  I do not have the time here to tell you about some of the other spinoff from these attempts.


Thanks Guys,


Forest


On Sat, Mar 2, 2019 at 1:20 PM Forest Simmons <[hidden email]> wrote:
A few years back Jobst suggested "chain climbing" as a seamless, Condorcet compliant way of selecting an alternative from a given ordered list.

For example electing a winner from a list of candidates c1, c2, ... given in decreasing order of approval.

Chain Climbing initializes a chain of candidates with the last (least approved in this case) candidate in the list.  Then moving up the list each successive candidate "climbs the chain" as far it can before being bumped off by a chain member that defeats it. If it makes it all of the way to the top, it is added to the top of the chain.

The candidate who ends up at the top of the chain is elected.

Since a beats all candidate will never be defeated, the method is Condorcet compliant. It also turns out to be clone resistant and monotonic. 

Another nice property is that it always selects from the Banks set, a nice game theoretic subset set of the set of uncovered candidates. 

The biggest objection to this method is that when applied to a list a list where c1 beats c2 beats c3, and c3 beats c1, it elects c2.

Here's my proposed improvement:

Initialize the chain with c1.  Move down the list instead of up.  For each successive candidate x (as we move down the list) if possible, insert that candidate into the chain at a point where it is beaten by every candidate above it and is not defeated by any candidate below it.  If not possible, discard it.

After going through the entire list (top to bottom) inserting new candidates where possible into the totally ordered chain, we end up with a maximal totally ordered chain of candidates (ordered by pairwise defeat) The candidate at the top fo the completed chain (the one who is not defeated by any of the others) is elected.

It is easy to show that this method has all of the nice properties of chain climbing, but retains more of the spirit of the original list..

For example in the A>B>C example above it elects A.

What do you think?

Forest




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



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