[EM] UD Landau

[Forest Simmons]

Kristofer,

[For the record I am cc-ing this to the EM list.]

While pondering the geometry of our agenda deas for Landau efficient
methods, the following idea for a  Universal Domain Landau Efficient method
came into focus:

For each alternative X let D(X) be the set of alternatives that defeat X
pairwise, and let D'(X) be its complement. Note that X is in D'(X).

Our idea is that the closer D(X) is to being engulfed by D'X), the closer X
is to being undefeated.

So how do we measure how much D'(X) would have to be enlarged in order to
swallow up D(X)?

By the distance from the member of D(X) that is furthest from the unswollen
D'(X).

The distance of an alternative Y to the set D'(X) is defined as
dist(Y, D'(X))=Min over Z in D'(X) of dist(Y,Z), i.e. the distance from Y
to its nearest neighbor Z in D'(X).

So to engulf D(X) the frontier of D'(X) has to be extended outward a
distance of Extend(X)=Max over Y in D(X) of dist(Y,D'(X)).

The less extension needed, the better, so we want to elect argmin(Extend(X))

The only thing left is to pick an appropriate distance metric.

If we want to remain in the Universal Domain category, it seems to me that
the best gauge of dist(Y, Z) is the disappointment incurred by moving from
alternative Y to Z, in other words, the number of ballots that prefer Y
over Z.

Note that if A covers B, then it is (in general) easier for D(A) to engulf
D'(A) than for D(B) to engulf D'(B), so this method naturally elects
uncovered candidates.

There is a natural way to break ties that makes this Landau property snug
... by expanding/extending the engulfing frontier gradually, while keeping
track of how much expansion is needed to swallow up the respective
candidates one by one ... but for now we won't worry about the details.

Does this make sense?

Any obvious defects?

The basic idea that came from pondering our agenda covering Landau  method
(in connection with its Banks efficient mimic) is that it minimizes the max
distance to D'(X) or "theall(X) union {X}" instead of minimizing the max
distance to X itself as per standard MinMax. Similarly, the Banks version
minimizes the max distance to a dense subset of D'(X) [a chain that covers
D'(X].

["dense" because every member of D'(X) is just one small step away from the
chain]

So the topology of digraphs guides our intuition as always!

-Forest
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20220729/792cfd34/attachment.htm>