[EM] A Decisive, Landau Efficient, Generalized Median, Single Winner Method

[Forest Simmons]

A slight correction is needed: the simple version, is Smith Efficient, but
not quite Landau efficient. For that we need a tweak to the cost of a
beatpath that is a concave down increasing function of k:

 c(k,epsilon)=(1-epsilon^k)/(1-epsilon),

in other symbols ...

Sum over j from zero to k of epsilon^j,

where epsilon is some fixed, positive infinitesimal.



On Sun, Oct 9, 2022, 3:45 PM Forest Simmons <forest.simmons21 at gmail.com>
wrote:

> It is now obvious to me that the simplest, adequate measure of beatpath
> cost, and the one that completes the "friendliness" measure in our
> longstanding foA-fpC thread, is simply the number of steps in the
> beatpath.  The fewer the number of steps in the beatpath from X to Y, the
> friendlier Y is to X.
>
> Time to summarize the method that has culminated in this thread. I'm
> tempted to call it the Munsterhjelm Venzke Heitzig or MVH method after the
> principal contributors of the key ideas. Many other EM List members from
> (Demorep to Lung) have contributed in ways too numerous to enumerate.  I
> can truly say that anybody who made regular contributions to the EM List in
> the form of questions, criticisms, or clarifications over any period of a
> year or more has contributed to my understanding of voting methods ... for
> which I am very grateful. Special mention to Benham, Ossipoff, Rob LeGrand,
> Andrew Jennings, Joe Weinstein, Bart Ingles, etc. for tolerating my newbie
> efforts.
>
> HVM: Elect the candidate X with the smallest total of beatpath costs from
> X to the ballot favorites.
>
> In other words, for each ballot B, and each candidate X, let Cost(X,fpB)
> be the minimum number of steps in a beatpath from X to fpB, the first place
> favorite of ballot B. Note that if X=fpB, then the beatpath from X to F(B
> has zero steps, so the cost is zero.
> Let SumfpB(X) be the sum over all ballots B of Cost(X,fpB).
> Elect argmin SumfpB(X)
>
> It is not hard to show that this simple, decisive, Universal Domain
> election method is clone independent, Landau efficient, and monotone.
>
> If these claims hold up to close scrutiny, and MVH truly does generalize
> fpA-fpC, then why not propose it for public elections?
>
> -Forest
>
> On Fri, Oct 7, 2022, 6:54 PM Forest Simmons <forest.simmons21 at gmail.com>
> wrote:
>
>> The median X of a finite set of distinct points arranged along a straight
>> line segment will always minimize the sum of distances from it to the other
>> points. [If the points are not distinct, a weighted sum does the job.]
>>
>> Consequently one way to generalize the concept of "median" in a general
>> metric space is by minimization of (weighted) sums of distances.
>>
>> Thus, the Kemeny-Young method chooses the "finish order" that minimizes
>> its sum of distances to the ballots, i.e to their respective rank orders.
>>
>> In this context, the distance from a ballot order to a potential finish
>> order is their Kendall-tau distance, the total number of basic order
>> reversals necessary to convert one order into the other.
>>
>> There are two unnecessary difficulties associated with Kemeny-Young:
>>  (1) The number of finish orders that need to be checked grows
>> exponentially with the number of candidates,  even when all we need is the
>> winner of a single winner election.
>> (2) The method is clone dependent ... a fatal flaw in the context of
>> electoral politics. The basic spoiler problem that sparked election method
>> reform in the first place was a failure of clone independence. Even IRV
>> with all of its other problems, is clone independent.
>>
>> The method we propose is both clone independent and computationally
>> efficient.
>>
>> The key innovation is that we gauge the distance from ballot B to a
>> potential winner X by the cost of the least expensive beatpath from X to
>> the candidate f(B) that is favored above all others on ballot B.
>>
>> I'm going to break here to let this idea sink in a little before filling
>> in the few remaining details.
>>
>> To be continued...
>>
>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20221009/6e7e3a58/attachment.htm>