[email protected] wrote:
Here's a simpler version that is basically the same:
Make use of cardinal ratings so that the rating of candidate X on
ballot b is given by b(X).
Define the closeness of candidate X to candidate Y as the dot product
Sum b(X)*b(Y)
where the sum is taken over all b in the set beta of ballots.
While there remain two or more candidates, eliminate the pairwise
loser of the two that are least close to each other.
Since that distance definition would give actual numbers, one could use
an approximation algorithm (I tend to use Vivaldi:
https://secure.wikimedia.org/wikipedia/en/wiki/Vivaldi_coordinates ).
However, these algorithms are approximate - they don't guarantee that
you'll come within a certain factor of the true optimal result, and they
can get stuck in local optima. In the case of Vivaldi, the fitting
consists of, basically, a network of springs that is then relaxed.
I wonder if this problem has any provably good approximation algorithms
(or even exact optimization problems, which would probably involve
quadratic programming, and I don't know enough about Lagrange
multipliers to venture there). One might formally define it as:
Given distances d[a,b] for a,b = 1...n, and a dimensionality number k,
find n k-dimensional coordinates c[1]...c[n] so that
SUM p = 1...n
SUM q = 1...n
|d[p,q] - f(c[p], c[q])|
is minimized, where f(c[p],c[q]) is the Euclidean distance, in
k-dimensional space, between coordinates belonging to p and q.
We would also still be faced with the problem of actually picking k, and
if k is inferred from the ballot set itself (e.g. by trying different k
until finding the one with the best fit), it would be susceptible to
strategy.
----
Election-Methods mailing list - see http://electorama.com/em for list info
