[EM] multiwinner election space plots

[Kristofer Munsterhjelm]

Brian Olson wrote:
> 
> On Aug 13, 2009, at 9:18 AM, Kristofer Munsterhjelm wrote:
> 
>> Brian Olson wrote:
>>> http://bolson.org/voting/sim_one_seat/20090810/
>>> I think a few of these plots show Single Transferrable Vote behaving 
>>> badly in the same ways IRV does, with discontinuities and irregular 
>>> solution spaces.
>>> I also ran Condorcet and IRNR using combinatoric expansion. 
>>> Combinatoric variants of single winner election methods adapt to 
>>> multiwinner situations by enumerating all possible winning sets of 
>>> the available choices and using a simulated voter's preferences on 
>>> the choices in each set to determine a preference for each 
>>> winner-set. Voting on the n-choose-k preferences for winner-sets then 
>>> procedes as for a single-winner election.
>>
>> How does the combinatorial expansion work? The way you describe it, it 
>> seems like it's general purpose - that you could combine it with any 
>> single-winner method.
> 
> It's pretty general purpose but works well when there are ratings 
> backing each voter. It's easy to derive a rating for a winner-set by 
> just adding up the individual ratings. There would be more ties if there 
> was an initial conversion from rankings to ratings, as 1st + 4th would 
> be equal to 2nd + 3rd.

So, basically, if you have a vote of the type A: 100, B: 50, C: 20, and 
there are two seats, you get:

AB: 150, AC: 120, BC: 70

and hence

AB > AC > BC ?

Wouldn't that be majoritarian? Say 50%+1 prefer A > B > C, and the rest 
prefers C > B > A (C: 100, B: 50, A: 20). Then a majority plus one will 
prefer AB to the rest. However, Droop proportionality would mean that 
each bloc should get one candidate (hence one should elect AC).

The Condorcet Internet Voting Service has their own combinatorial 
method, see here: 
http://www.cs.cornell.edu/w8/~andru/civs/proportional.html . It may be 
more proportional - I haven't tried it.

One could also try adding Schulze STV to the list of methods, since it 
reduces to Condorcet in the single-winner case. It is combinatorial, but 
maybe it'll help us know what we "ought to see" without discontinuities 
and such.

>>> I think based on this I'm going to have to think more about making 
>>> native multiwinner methods. Combinatoric expansion gets pretty 
>>> expensive for large numbers of choices or seats to elect. I had been 
>>> kinda resigned to STV being the state of the art in multiwinner 
>>> methods, but we seriously ought to be able to do better.
>>
>> You could try implementing my DAC/DSC-based method (see 
>> http://www.mail-archive.com/election-methods@lists.electorama.com/msg04001.html ) 
>> or Quota-Preferential by Quotient (QPQ, 
>> seehttp://www.votingmatters.org.uk/ISSUE17/I17P1.PDF ), even if the 
>> latter is nonmonotonic (to my knowledge).
> 
> Thanks for the links. Those both seem to be party-based proportional 
> systems and I have so far been going (for partly ideological and partly 
> technical reasons) for party-agnostic candidate-based systems. But 
> perhaps I have misunderstood 'setwise highest'. I must have missed these 
> the first times around and am now reading up and thinking about them more.

They aren't. They're both based on party systems, but they aren't party 
systems themselves. QPQ could be considered an IRV-type method that uses 
quotients (like the divisor methods do with respect to parties) instead 
of straight score propagation.
Setwise Highest Average is Sainte-Laguë applied to DAC/DSC type 
coalitions instead of parties. Looking at the example, it uses 
acquiescing coalitions derived from the (candidate-only) ballots. Like 
highest average party-based methods, it reweights the groups according 
to which include candidates that have already been elected, but those 
groups are determined based on voters' ballots alone.

>> It may also be that the construction of the voter preference profiles 
>> (Gaussian centered on a particular point) means that the ideal maps 
>> will look like Condorcet majoritarian elections. If so, they won't 
>> help distinguish proportional methods from disproportional ones, only 
>> show errors like clone problems.
> 
> Proportionality might show itself somewhat like the distortions Borda 
> counts show in single winner elections:
> http://bolson.org/voting/sim_one_seat/zoomout/4a_Condorcet.png
> http://bolson.org/voting/sim_one_seat/zoomout/4a_Borda.png
> 
> http://bolson.org/voting/sim_one_seat/zoomout/4c_Condorcet.png
> http://bolson.org/voting/sim_one_seat/zoomout/4c_Borda.png
> 
> (above from this page http://bolson.org/voting/sim_one_seat/zoomout/ )
> 
> The lines shift a bit and twist in weird ways, but have basically the 
> same shape and none of the IRV discontinuities.

The IRV discontinuities in single-winner Yee diagrams are visual proof 
of IRV's nonmonotonicity. Consider it like this: if you draw a line from 
the center of a candidate's support (the circle or point) outwards, then 
if that line goes from "candidate wins" to "candidate doesn't win", and 
then back to "candidate wins", then the "doesn't win -> wins" transition 
can only have happened because of nonmonotonicity.

As for multiwinner, I'm not sure what the diagrams would be like. I 
wrote an argument that they would be like Condorcet majoritarian 
elections, but now I'm not so sure. If we're to reason to find the 
optimum, we'd probably do better if we knew why the optimum is a Voronoi 
diagram in the single winner case.

A rangevoting.org page (http://rangevoting.org/BlackSingle.html) says this:

"MORAL: For L² distance, Condorcet voting methods always yield the L² 
Voronoi diagram for voters centrosymmetrically distributed about each 
pixel (by part b of theorem). Also (as you can prove using facts about 
convolutions) this always is the same as the socially-best-winner 
picture. Thus, with utilities based on L² distance, for honest voters 
distributed centrosymmetrically, Condorcet voting methods are always 
optimum and in particular are superior to range voting."

A problem here is that we don't have any equation that describes 
"socially best" in the multiwinner case (the issue being the tradeoff 
between proportionality and getting "your" best). Methods like LPV0+ and 
PAV try to construct such equations, but they don't seem to be very 
proportional.