[EM] UD Landau

[Forest Simmons]

Well this new version fails mono-raise, so its equivalent MMMPO must also
fail monotonicity.

But let's not give up on the Min cost, short beatpath idea ... as long as
the primary cost is the number of steps in the beatpath the method will be
Landau efficient ... so that gives us some wiggle room.

Perhaps the secondary cost should be the cost of the most expensive step,
tertiary cost the greatest sum of any two steps,  etc. That way ties will
be rare, etc.

Let's try that for awhile!

-Forest

Remember, our cost for an isolated beatpath step is the number of losing
votes, i.e. the pairwise opposition against that step.

El lun., 1 de ago. de 2022 8:35 p. m., Forest Simmons <
forest.simmons21 at gmail.com> escribió:

> Here's a conceptually simpler formulation that also automatically resolves
> ties.
>
> Define the cost of a beatpath A>B>C>... as the polynomial C(N) whose k_th
> degree term (for k=0,1,2...) is N^k times the losing votes of step (k+1) in
> the beatpath.
>
> If N is sufficiently large, between two beatpaths the one with fewer steps
> will be cheaper.
>
> It follows that the method that minimizes the maximum beatpath cost from X
> to the other alternatives, will always elect an uncovered candidate.
>
> So that's the method we want: elect the candidate X that minimizes the
> maximum beatpath cost from X to the other candidates.
>
> Note that the last step dominates the cost, while the cost of any earlier
> steps still contributes enough to prevent ties.
>
> Thinking of the blob picture of MMMPO, the first step (in the winning
> beatpath) is from X to some other point Z in the blob ...while the other
> step (if needed) is from Z to Y.
>
> Isn't this a conceptually simpler way to formulate MMMPO?
>
> Simple enough for a public proposal?
>
> -Forest
>
>
>
>
>
> El lun., 1 de ago. de 2022 2:12 p. m., Forest Simmons <
> forest.simmons21 at gmail.com> escribió:
>
>> 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/f024b8b3/attachment.htm>