[EM] Multiwinner Condorcet generalization on 1D politics

[Kristofer Munsterhjelm]

I think that one problem with devising a multiwinner method is that we 
don't quite know what it should do. PAV type optimization methods try to 
fix this, but my simulations don't give them very favorable scores.

If we are to construct a multiwinner method that degrades gracefully, we 
probably need to have an idea of what, exactly, it should do, beyond 
just satisfying Droop proportionality (for instance). The problem with 
building a method primarily to satisfy a certain criterion is that if 
the criterion is broken slightly, then the criterion does not tell us 
how the method should work; and therefore, we might get "discontinuous" 
methods where the method elects a certain set if a Droop quota supports 
it, but a completely different group if the Droop quota less one 
supports that set.

So let's consider a case one may use to justify Condorcet, or to 
classify Condorcetian methods: if politics is one dimensional, and
people prefer candidates closer to them on the line, then there will be 
a Condorcet winner, and the CW is the candidate closest to the median 
voter, and (if we think electing the CW is a good idea), we should elect 
the candidate closest to the median voter.

This case, or general heuristic, seems to be simple to generalize, and 
one may do so in this manner: call a position the nth k-ile position if 
n/k of the voters are closer to 0. Then, a multiwinner method that 
elects k winners should, if politics is one-dimensional, pick the 
candidate closest to the first (k+1)-ile position, then closest to the 
second (k+1)-ile position (first candidate notwithstanding as he's 
already elected), etc, up to k.

To be more concrete, in a 2-candidate election, the first candidate 
should be the one closest to the point where 33% of the voters are below 
(closer to zero than) this candidate, and the second candidate should be 
the one closest to the point where 67% of the voters are below this 
candidate, the first candidate notwithstanding.

This heuristic covers only the one-dimensional case, but it is at least 
continuous if the comparison of a particular election *is* 
one-dimensional, and thus should reduce discontinuity problems.

Plurality party list methods can be modeled as instances where each 
voter is located at the position of the party they voted for, since that 
is all a Plurality vote lets us infer. Say that 52% are located at party 
A, and 48% at party B, and that WLOG, A's location on the line is closer 
to 0 than is B's. Then the count starts at A, and proceeds as such, 
electing candidates from A's list until A has its share, at which point 
it jumps closer to B. In essence, party list becomes a equal-rank 
plurality version where everybody either votes A1 = ... = An or B1 = ... 
= Bn.

The problem of synthesizing the distribution on the political line still 
remains, though. If people vote rationally (that is, that there is no 
noise), one can get some extent of the way by observing

	eee A fff ggg B hhh iii C jjj
       0|-----------------------------|1

The e faction would vote A > B > C. So would the f faction, while the g 
faction would vote B > A > C and the h faction, B > C > A. The i and j 
faction votes C > B > A. Noise votes are A > C > B and C > A > B.

However, while this gives us some information as to the relative sizes 
of the factions, it does not tell us whether (say) the e faction is 
large because there's a peak of support there, or because the others are 
more extreme, like this:

	eeeeeeee A ff gg B hh ii C jj
       0|-----------------------------|1

In the case of Condorcet, it doesn't matter, since Black's 
single-peakedness theorem says that in the one-dimensional case with 
voters preferring candidates closer to them, there'll always be a CW and 
that CW is the candidate closest to the median voter.

Can we use this to make "multiwinner Condorcet" where the k-ile property 
holds? To do so, I would have to understand the aforementioned 
single-peakedness theorem to know how it works, which I don't.

If I were to make a guess, I think it's because Condorcet removes the 
other candidates from each pairwise check. Assume A is the median 
candidate. Then on A vs B, A is closer to more voters than B is. If that 
is all that's needed, then we could imagine a Condorcet analog where if 
a voter is closer to A or B than to C or D, it counts as a win for {A, 
B}. If a council {X,Y} is a CW in this way, and X is closer to 0 than is 
Y, is then X closest to the 33% position, and is Y closest to the 67% 
position? I don't know.

In any case, even if I'm right about the above, we have to figure out 
what "{A, B} is closer than {C, D}" means. If a voter ranks A > B > C > 
D or B > A > C > D, it's pretty obvious that {A, B} is closer. But what 
of A > C > B > D or C > A > D > B ? And is it possible to make a system 
that picks the (k+1)-ile closest candidates without having to go through 
all possible combinations of the council in the worst case?

-

This may have been a bit meandering, but I wrote it as I went on. My 
general idea is this: multiwinner election is not as well defined as 
single-winner election, so I tried to find a way of defining it better 
by referring to issue space, and in a way so that it reduces to 
Condorcet in the single-winner case. Then I wrote a bit about the 
limitations of this (that we can't infer the shape of the curve in issue 
space from ranking alone), and that perhaps we don't need the shape of 
that curve - but on that, I'm uncertain, since I don't know Black's 
theorem.

There's also the problem of noise and multiple dimensions to consider, 
but let's keep this simple :-)

Any ideas, replies?