[EM] Multiwinner Condorcet generalization on 1D politics

[Kristofer Munsterhjelm]

Raph Frank wrote:
> I read somewhere that for most legislators, their voting record can be
> defined using 2 dimensions.
> 
> (Found something that might be it:  http://saweis.net/svd/ )
> 
> Anyway, the basic point is that you can place each member of a
> legislature on a 2-d plane based solely on their voting records and
> then use that to predict future votes.  You don't need to actually
> know what the votes are about.
> 
> I wonder if a similar trick could be used with voters who submit a
> ranked ballot.
> 
> You could try each possible ordering of the candidates.  The result
> that gives the fewest contradictions could be the considered the
> actual ordering of the candidates.
> 
> You could then go through all the ballots and place them in a position
> that minimises the number of contradictions.  (Alternatively, you
> could just place them beside their favourite on the same side as their
> 2nd preference).
> 
> Finally, you could then pick the percentile candidates.
> 
> Ofc, there may be some serious strategy issues with people's rankings.

Let's first find out how to handle honest ballots, then we can harden 
the system later :)

I've been thinking along your lines before. At least with Range-style 
votes, it would be relatively simple to run an SVD on the voters and 
candidates. Say there are X candidates and Y voters, and all voters 
submit ranks for all the candidates. If you do a singular vector 
decomposition of d dimensions, then for some candidate or voter p, you 
get numbers p[0]...p[d], so that for a candidate X_c and voter Y_v,

X_c[0] * Y_v[0] + X_c[1] * Y_v[1] + ... + X_c[d-1] * Y_v[d-1] = r_cv

where r_cv is Y_v's rating of X_c (or close to it).

The problem I encountered when using SVD is that this is not a model 
that's based on difference. Even though it can provide very accurate 
guesses of r_cv for low dimensions, it's not obvious how to change this 
into a model of the form:

|mX_c[0] - mY_v[0]| + |mX_c[1] - mY_v[1]| + ... + |mX_c[d-1] - 
mY_v[d-1]| = max - r_cv

where m is for "modified", and which would be truly distance-based (in 
this particular case, based on the Manhattan distance). That looks 
suspiciously nonlinear, and nonlinear optimization is much more 
difficult than linear optimization.

Perhaps a spring model like Olson's could be used here. I know that 
similar spring models have been used to calculate virtual coordinates in 
peer-to-peer schemes, where latency measurements provide distance 
information. I think those spring models have local optima that are 
distinct from their global optima, though, which could encourage 
strategy aimed at moving the method to a certain local optimum.

It's not easy to use this for ranked vote mechanisms, though a simple 
way would be to Borda-ify by counting the first rank as score n, the 
second as score (n-1), etc.; but that could lead to Majority problems, 
since, as I showed, the only weighted positional methods that always 
obey Majority are equivalent to Plurality with a tiebreaker of some sort.

We're also left with the question of where the percentile mark is 
located in a multidimensional space. A straightforward generalization 
would put the median point in the "middle" as defined by weighted 
Euclidean distance, but even if the voters were uniformly distributed, 
this "middle" would provide a circle, not a point, for the percentile 
marks. One could also generalize it to the "percentile of all dimensions 
equally", so that in 2D, the 10th percentile is the point (x,y) where 
10% of the voters are inside a box given by the corner coordinates (0,0) 
and (x,y). This wouldn't be rotation invariant, though, because the 90th 
percentile from upper left would have a long strip at the bottom and the 
right, whereas the 10th percentile from lower right would have just the 
box there, and none of the strips.

Another generalization that might work, although I don't know how often 
it occurs, is of the DDH median. The DDH median is the point where if 
you draw a line, no matter its angle, that passes through this point and 
no other point, then that line puts half the voters in one half and the 
other half in the other. A DDH percentile would have the property that 
no matter how you draw the line (so that it doesn't collide with any 
voters), it divides the voters into k% in one part of the line, and 
100-k% in the other. There might be more than one DDH percentile point, 
however - for instance if the distribution is symmetric.