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
Is this (the objection) definitely correct? I might be being stupid or might have misunderstood the method, but the chain starts:
-
c1 (most approvals)2. c23. 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.
TobyFrom: Forest Simmons fsimmons@pcc.edu
To: EM election-methods@lists.electorama.com
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
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
This email has been checked for viruses by AVG.
https://www.avg.com
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
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 fsimmons@pcc.edu 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
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 fsimmons@pcc.edu 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
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 <fsimmons@pcc.edu
mailto:fsimmons@pcc.edu> 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
This email has been checked for viruses by AVG.
https://www.avg.com
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 <fsimmons@pcc.edu
mailto:fsimmons@pcc.edu> 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