[EM] Kemeny-Young Thoughts

[Forest Simmons]

Suppose you had a nice metric on a candidate space for measuring the
disparity between members of the electorate, and you wanted to use the
metric to find the most representative member of the electorate. How would
you use that metric?

There are many possibilities, but let's consider three of them that are
fairly natural and easy to understand:

Let V be the set of voters, and let K be the subset of V consisting of the
candidates who managed to get their names on the ballot.

1. Elect the candidate k that minimizes the total distance to the  other
voters, i.e. elect argmin{TotDist(k,V)|k in K} where TotDist(k,V) is the
total distance from k to the other members of V.

2. Elect the candidate k closest to the most representative voter,
namely argmin{TotDist(v,V)|v
in V}. This is analogous to the Condorcet dictum, "elect the candidate
closest to the voter median."

3. Find the point p in the space of possible ballots that minimizes the
total distance to the actual ballots. Then elect the most preferred
candidate on that idealized ballot.

Number 3 strongly depends on the Universal Domain requirement that the only
admissible information for determining the winner of the election is the
ordinal information contained in the ballots of the voters,. So if our
method depends on a distance metric between voters, that metric must be
completely determined by the voters' ordinal ballots.

In the case of Kemeny-Young, method three is the method used. The metric in
question is the Kendall-tau distance between rankings. The idealized ballot
ranking that determines the winner may or may not be one of the actual
ballot rankings.

The computational complexity of K-Y is not inherent in the Kendall-tau
distance calculations. Rather it stems from the sheer number of possible
idealized ballots. So methods one and two have available (low degree)
polynomial time counting procedures, despite their fundamental use of the
Kendall-tau metric. [The same goes for my de-cloned version of K-Y based on
a clone free version of the Kendall-tau metric.]

The winning idealized ballot not only decides the election winner, it also
suggests an entire "social order" or "finish order" of the candidates.

That's nice, and some applications may require it, but when the number of
candidates is large, the computational burden has to be forestalled one way
or another.

More to the point ...the idealized finish order is not needed in single
winner elections. Either of the first two methods above works great. In the
extremely rare case where they do not agree, you can elect the pairwise
winner of the two methods.

What got me thinking about this was Colin Champion's question about a
metric characterization of multi-winner/PR methods.

¿How would you make use of a decent metric on candidate/voter/ballot space
to compose (like a musician) a good multi-winner method? ... or for
starters, to choose between two or more proposed posible winning "slates"
....?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20220215/acf82c0c/attachment.html>