[EM] A distance based method

[Kristofer Munsterhjelm]

fsimmons at pcc.edu 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.