[EM] Improved TACC (Total Approval Chain Climbing)

[Forest Simmons]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20211111/b495d702/attachment.html>