[EM] AP Chain Climbing 3.0

[Forest Simmons]

Here's a Banks efficient version that more closely mimics our proven Landau
efficient method.

First, for comparison a slight reformulation of Agenda Based Landau:

Definition: For each agenda item X, let thrall(X) be the set of agenda
items defeated by X.

Initialize X as the most favorable item on the agenda.

While some agenda item Y defeats both X and every member of thrall(X), let
the most favorable such Y be the new value of X.

Now for the analogous Banks efficient method:

Initialize X as the most favorable agenda item. Then while some agenda item
Y defeats both X and every member of chain(X), replace X with the most
favorable such Y.

To complete the definition, we need to define chain(X):

Chain(X) is the covering chain of thrall(X) constructed by the following
procedure ...

Initialize 'chain' as the empty set. Then ...
While some Z in thrall(X) defeats every member of 'chain', incorporate the
most favorable such Z into 'chain'. EndWhile.

As you can see, the difference between the two methods is that the rôle  of
thrall(X) in the first method is taken over in the second method by a set
chain(X) that covers thrall(X).



El mié., 27 de jul. de 2022 2:30 p. m., Forest Simmons <
forest.simmons21 at gmail.com> escribió:

> This procedure is composed of two sub-procedures ... one to construct an
> "advanced placement" chain headed by the most favorable agenda item ... and
> another to complete the chain by a process of chain climbing.
>
> First sub-procedure: initialize a chain 'c' as the empty set. Then while
> there exists (even vacuously) some agenda item that is defeated by every
> member of 'c', incorporate the most favorable such item into 'c'.
>
> Final sub-procedure: while any agenda item defeats every member of 'c',
> incorporate the most favorable such item into 'c'.
>
> After executing both sub-procedures, elect the head of the finished chain.
>
> This method is definitely Banks efficient. I'm pretty sure that it is also
> monotonic and (unlike ordinary chain climbing) Independent from Pareto
> Dominated Alternatives (IPDA).
>
> I'll send proof sketches soon (if it continues to hold up).
>
> -Forest
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20220728/1a265e2d/attachment.htm>