[EM] Multiwinner Condorcet generalization on 1D politics

[Dave Ketchum]

On Thu, 12 Feb 2009 20:31:56 +0100 Kristofer Munsterhjelm wrote:
> 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.

Let me try a different picture:
      Candidates scattered across a 2-dimension space, unevenly.  There 
could be bunches near Party 1 position, near Party 2 position, etc.
      Voters scattered likewise.

Each voter would give top rank to the candidate they see as nearest, etc., 
not bothering to rank those too distant.

Looking for CW in the N*N matrix:  Pick any candidate as A and see if A was 
ranked higher than x for all A vs x:
      More A>x than x>A for each x - if so, A is CW.
      Has the x in x>A been an A in this search - if so, have a cycle.
      Try again with this x becoming A.

Note that this does not require looking at every entry in the matrix - move 
on as soon as disqualifying an A.

Seems to me 2-dimensional works better for such as three parties pulling in 
different directions.
      With a CW, extra winners should have looked good when looked at via 
the matrix.

Note that for multiwinner a 3-member cycle would almost certainly  fit for 
3 winners.

DWK
> 
> 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?
-- 
  davek at clarityconnect.com    people.clarityconnect.com/webpages3/davek
  Dave Ketchum   108 Halstead Ave, Owego, NY  13827-1708   607-687-5026
            Do to no one what you would not want done to you.
                  If you want peace, work for justice.