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

[Forest Simmons]

We now finish our description of the method introduced previously, by
defining the cost of a beatpath from candidate X to candidate Y as the
number of steps in the path plus epsilon times the losing vote total along
the path.

Any positive infinitesimal will do for epsilon, because all sufficiently
small standard positive values will give the same result as determining
cost primarily by the number of steps, and secondarily by the losing vote
sum.

Note that if X is in the Landau set, there will always be a a beatpath of
two or fewer steps to Y.

On the other hand, if X is not in Landau, then for some Y, no beatpath from
X to Y will have fewer than three steps.

It follows that this method is Landau efficient.

Questions?

Thanks!

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/20221007/dc6036a0/attachment.htm>