Improved TACC (Total Approval Chain Climbing)
A few years ago we applied to the "total approval order" a "chain climbing"
idea of Jobst Heitzig for monotonically extracting a member of the Banks
set from an ordered list of alternatives ... monotonic in the sense that if
you move the winner W higher up the list while preserving the relative
order of the other alternatives, or if uniquely W acquires a new pairwise
victory, then the alternative W still wins the chain climbing competition.
In general, an alternative is a Banks alternative if it is the head of a
maximal totally ordered chain of alternatives ... where the order relation
in question is that of pairwise defeat... total order means that (1) each
member of the chain pairwise defeats every member of the chain that comes
after it and (2) is defeated by every member that precedes it. "Maximal"
means (3) there is no room to expand the chain while maintaining the total
order conditions (1) and (2).
In practice it is not necessary to find an entire maximal chain; it
suffices to reach the point where no alternative can be added to the front
end of the chain ... since it is only the winner, i.e. the head of the
chain, that we are interested in ... at least in our single winner context.
In the original version of TACC we initialize our chain with the least
total approval alternative .... then while there remains any un-tested
alternative, we test the lowest total approval previously untested
alternative X against the current members of the chain one-by-one as it (X)
"climbs" up the chain. If it makes it to the head of the chain without
being bumped off (pairwise defeated and discarded) along the way, it (X)
gets incorporated into the chain as the current head or champion. The last
alternative incorporated into the chain (as champion/winner) directly beats
every other member of the chain ... and each non-chain member was bumped by
a chain member, so the champion beats each alternative in a "short
beatpath" of two or fewer steps.
Now here is the new & improved version in succinct form:
While ...
any undiscarded alternative remains (i.e. "survives") ...
discard all (previous) survivors that do not pairwise beat the survivor X
that has the highest total approval among those survivors that are not
beaten pairwise by any survivor with lower total approval.
EndWhile
Elect the final survivor.
This method definition is not easy to digest in one or two cursory
readings, but it is all there.
Working through a few concrete examples will easily clear up any confusion
(and expose any potential bugs) ... which we will attempt tomorrow!
-FWS
-FWS
I need to simplify this definition so that incessant (& annoying)
references to forms of the word "survivor" are not needed... let's see if a
recursive definition might help:
The input to this method M consists of an agenda A of alternatives in
approval order along with a table T of their pairwise win/loss/tie
relationships. The output M(A,T) of the method will be some alternative Y
from the agenda A.
-
Identify the alternative X closest to the good (high approval) end of
the agenda that covers every worse (lower approval) alternative on the
agenda. -
Eradicate from both the agenda A and from the win/loss/tie table T ...
every alternative (including X) that does not beat X pairwise. -
IF this elimination step exhausts the agenda A, then set the output Y
equal to X. -
ELSE apply this method M recursively to elect Y= M(A, T).
Now (por favor) disregard the previous definition with all of its typos,
thinkos, y otros defectos!
Promised examples tomorrow!
-FWS
El jue., 11 de nov. de 2021 8:50 p. m., Forest Simmons <
forest.simmons21@gmail.com> escribió:
A few years ago we applied to the "total approval order" a "chain
climbing" idea of Jobst Heitzig for monotonically extracting a member of
the Banks set from an ordered list of alternatives ... monotonic in the
sense that if you move the winner W higher up the list while preserving the
relative order of the other alternatives, or if uniquely W acquires a new
pairwise victory, then the alternative W still wins the chain climbing
competition.
In general, an alternative is a Banks alternative if it is the head of a
maximal totally ordered chain of alternatives ... where the order relation
in question is that of pairwise defeat... total order means that (1) each
member of the chain pairwise defeats every member of the chain that comes
after it and (2) is defeated by every member that precedes it. "Maximal"
means (3) there is no room to expand the chain while maintaining the total
order conditions (1) and (2).
In practice it is not necessary to find an entire maximal chain; it
suffices to reach the point where no alternative can be added to the front
end of the chain ... since it is only the winner, i.e. the head of the
chain, that we are interested in ... at least in our single winner context.
In the original version of TACC we initialize our chain with the least
total approval alternative .... then while there remains any un-tested
alternative, we test the lowest total approval previously untested
alternative X against the current members of the chain one-by-one as it (X)
"climbs" up the chain. If it makes it to the head of the chain without
being bumped off (pairwise defeated and discarded) along the way, it (X)
gets incorporated into the chain as the current head or champion. The last
alternative incorporated into the chain (as champion/winner) directly beats
every other member of the chain ... and each non-chain member was bumped by
a chain member, so the champion beats each alternative in a "short
beatpath" of two or fewer steps.
Now here is the new & improved version in succinct form:
While ...
any undiscarded alternative remains (i.e. "survives") ...
discard all (previous) survivors that do not pairwise beat the survivor X
that has the highest total approval among those survivors that are not
beaten pairwise by any survivor with lower total approval.
EndWhile
Elect the final survivor.
This method definition is not easy to digest in one or two cursory
readings, but it is all there.
Working through a few concrete examples will easily clear up any confusion
(and expose any potential bugs) ... which we will attempt tomorrow!
-FWS
-FWS