[EM] UD Landau

[Forest Simmons]

I want to clean it up and name it MinMaxMinPO or MMMPO, in comparison (and
contrast) with MMPO (MinMaxPairwiseOpposition).

MMPO elects the candidate X whose maximum pairwise opposition (from Y, say)
is minimal.

In other words, MMPO elects the candidate X whose most reluctant holdout Y
resists the least against surrendering.

MinMaxMinPO also elects the candidate X whose most reluctant holdout Y is
least resistant... the only difference is the degree of "surrender" in the
two cases.

In the MMPO case, we're talking complete surrender ... Y resists moving
from its original position all of the way to X itself.

In the partial surrender MinMaxMinPO case Y only resists moving from its
original position to the frontier of a neighborhood ND of X;

In this case Y is not required to go all of the way to X ... but is allowed
to stop as soon as it reaches the border of the "thrall of X", defined as
the set of alternatives defeated by X.

Let ND(X) be the closed neighborhood of X defined as the set of
alternatives not defeating X, which is the same as the closure of the
thrall of X. This closure is the set of candidates defeated or tied by X,
including X itself.

The resistance of Y against entering the thrall of X is defined as Min(over
Z in ND(X)) of #[Y>Z].

In other words, the smaller the number of ballots on which Y outranks Z,
i.e. the smaller #[Y>Z], i.e. the smaller the pairwise opposition of Y to
Z, the less difficulty getting Y to surrender to Z.

In summary, we elect the candidate X whose max opposition to ND(X) is
minimal, where the opposition of Y to ND(X) is defined as its least
pairwise opposition to any member Z of ND(X).

The alteration of min's and max's is logically the same as a corresponding
alteration of Existential and Universal quantifiers, a measure of logical
complexity ... which is why people get confused by MinMax ... "Do you mean
Min or Max? ...make up your mind!"

All the more with MinMaxMin!

But the picture makes it easy ... a blob ND(X) centered on X, with a few
scattered points surrounding the blob, one of which (Y) is furthest from
the blob. The more remote Y, the more opposition Y has to surrendering to
the blob. That's the opposition we're trying to minimize by electing the
right X.

What's the advantage over ordinary MinMax?

The advantage is a subtle one... the conquering emperor doesn't have to
drag all of her new vassals into the Capitol of her empire ... but only to
the frontier of her control.

In terms of our method ... it turns out to yield Landau efficiency, and
softens the inevitable compromise that happens in all non-FBC Universal
Domain methods, including all UD Condorcet Compliant methods.

MMPO is about as close as you can get to being Condorcet Compliant for an
FBC method.

MinMaxMin is about as close as you can get to FBC for a UD Landau efficient
method, or so it seems to me.

If C covers X, then the blob for C  expands, generically shrinking the
distance from Y (or the new Y) to the blob. So the max opposition against C
is less than the max opposition against X.

Similarly, if X gets increased pairwise support, the opposition of Y
against any member Z of ND(X) does not increase, and in the case of Z=X it
decreases.

ETC. The method seems to be monotone.

Help me find its Achilles heel!

-Forest




El sáb., 30 de jul. de 2022 5:17 a. m., Forest Simmons <
forest.simmons21 at gmail.com> escribió:

> It must be the 40 degree Celsius heat wave frying my brain: D(X) is
> supposed to be the candidates defeating X, not defeated by X. And so D'(X)
> should be the set of candidates that do not defeat X.
>
> I apologize... right mental picture ... wrong verbal description!
>
> I have made this same error before ... in the context of Decloned Copeland.
>
> So let me run this past you ...
>
> Let FX) be the First place preference total of all candidates that do not
> defeat X. If no candidate defeated X, then F(X) would just be the total
> number of ballots ... which suggests electing the candidate X that
> maximizes F(X).
>
> Anything wrong with that?
>
> If not, then it is (arguably) the best UD Landau efficient method we could
> offer for public proposal (un my not overly humble opinion).
>
> Two more days of high temperatures!
>
> -Forest
>
>
>
> El vie., 29 de jul. de 2022 8:30 p. m., Forest Simmons <
> forest.simmons21 at gmail.com> escribió:
>
>> 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/20220801/9bb7db15/attachment.htm>