[EM] Possibly making Sainte-Lague even more STV-like

[Kristofer Munsterhjelm]

On 09/05/2013 11:12 PM, Vidar Wahlberg wrote:
> On Thu, Sep 05, 2013 at 11:42:44AM +0200, Kristofer Munsterhjelm wrote:
>> So a Sainte-Laguë based on DAC or DSC is better than one based on
>> Plurality - and we know how to do the generalization - but there
>> isn't much else to be said about it. (It might also be weakly
>> monotone, which would be nice since STV isn't.)
>
> Will be a bit short as I've been busy lately.
>
> I looked briefly into DAC/DSC, I couldn't visualize how to expand that
> to a multi-seat system, though. May look more into it at a later time.

Okay, here's an example which will show the particular kind of 
vote-splitting problem that DAC/DSC itself fixes. Say A, B, C, X are 
parties, and the ballots are:

12: A>B>C>X
11: B>A>C>X
10: C>A>B>X
15: X>C>A>B

Three seats (because calculating these things manually does take some 
effort). The coalitions are:

{ABCX}: 48
{ABC}: 33
{AB}: 23
{ACX}: 15
{CX}: 15
{X}: 15
{A}: 12
{B}: 11
{AC}: 10
{C}: 10


For the first seat we first take ABCX, then intersect to ABC, then with 
AB, then XAC, which produces the initial winner of A. Okay. Now all sets 
that include A are deweighted by 2 * 1 + 1, giving:

{ABCX}: 48/3 = 16
{ABC}: 33/3 = 11
{AB}: 23/3 = 7.67
{ACX}: 15/3 = 3
{CX}: 15 (no A here, so no deweighting)
{X}: 15
{A}: 12/3 = 4
{B}: 11
{AC}: 10/3 = 3.33
{C}: 10

Resorting:

{ABCX}: 16
{X}: 15
{ABC}: 11

and so on. It's obvious X gets the second seat. After this, the 
weightings would be 3 for any seat that includes either X or A, and 5 
for any that includes both:

{ABCX}: 48 / 5 = 9.6
{ABC}: 33 / 3 = 11
{AB}: 23 / 3 = 7.67
{ACX}: 15 / 5 = 3
{CX}: 15 / 3 = 5
{X}: 15 / 3 = 5
{A}: 12 / 3 = 4
{B}: 11 = 11
{AC}: 10 / 3 = 3.33
{C}: 10 = 10

or

{ABC}: 11
{B}: 11
(and so on)

so the third seat goes to B. So this method is quite close to Plurality 
Sainte-Laguë, which is why I don't think it would make enough of a 
difference, and thus why I didn't bother to write the calculations in my 
previous post :-)

If it has any place, it would instead be in calculating the party seats 
for a single district. And even there, I don't think it solves the 
polarization problem well enough. In a sense, the coalition-type methods 
(DAC, DSC, HDSC) are "IRV without the chaos". The Yee diagrams also show 
this: IRV's can have odd disconnected areas, while the descending 
coalitions methods have polygonal connected regions, but the regions can 
be quite far from the optimal solution (Voronoi map) that Condorcet 
produces.

Its main difference from Plurality Sainte-Laguë is that if there's a 
group of uncoordinated voters, then they get a seat before the 
beneficiaries of the vote-splitting do. So it could make a difference 
with marginal seats. (E.g. imagine that the situation above happens 
after X has got a lot of seats and there's only one seat remaining; then 
it would give the final seat to the {ABC} group instead of to X}.

(Interesting side question: does D*C suffer from center squeeze in the 
single-winner case? In one respect it does: if C is everybody's second 
choice, it is retained until the single-seat sets, but then it is 
eliminated. In another, it does not: if the center gains greater 
popularity, the method doesn't decide to favor the opposing wing 
instead. Another interesting question would be whether the 
coalition-type methods are cloneproof as multiwinner methods as well, 
not just as single-winner methods.)

> However, I want to elaborate a bit more on the SL/RP system I mentioned
> earlier:
> There were two issues you pointed out. First was that in an election
> with 3 parties (L, C, R), strong support for L & R where all agreed on C
> being the preferred winner in a 1-seat election, but in a 2-seat
> election it would make more sense to let L & R to win.
> This criticism I share.
> On the other hand, when I implemented this idea I had a typical
> Norwegian parliament election in mind (for 169 seats), so my question to
> you would be; While this would not be a good system for few seats and
> parties with distinguished differences, won't that problem quickly
> diminish when you have significantly more seats and parties?

Geometrically speaking, you could consider a house-monotone method one 
that picks the median/consensus points for (n+1) seats by adding a point 
to the ones for n seats. As n increases, the worst case error (compared 
to a method that can pick all n points from scratch) should decrease 
because there are more points. If there are many dimensions to political 
opinion space, the error may decrease more slowly, but yes, in general 
you are right.

The geometrical interpretation also shows two ways in which problems 
could present themselves. First, in the LCR situation, the point for n=1 
is simply far away from the points for n=2, period. This kind of error 
could be amplified in kingmaker settings: e.g. imagine 49 seats to L, 50 
to R, but one of them should have been C. But apart from that, the error 
should diminish. There would also be a greater chance of imbalance if 
you increase the number of parties - e.g. consider parties on the 
vertices of a pentagon in 2D space with a compromise party at the center 
of this pentagon: then the house-monotone method will be biased until at 
least 5 seats have been given.

Second, a poorly constructed house-monotone method could perform 
insufficient lookahead and get into trouble later on, since the 
distribution for n depends on the distribution for n-1. So the demands 
are greater on such a method, though I don't know how to measure this.

Ultimately, though, Schneier's statement about crypto can be rephrased 
to apply to electoral methods too. 169 seats do solve a lot of ills. 
About the only thing needed is that the method properly converges - i.e. 
that it can reduce its bias however far one would like given enough seats.

> The second issue you raised was that an A>B>C>* preference, where A had
> won some seats while B had not would not weight down the B>C preference
> as it should. Again you're absolutely correct so I've changed the
> implementation. Currently I've set it to be that with the same
> preference, A having 2 seats and B having 3 seats and C having no seats
> the weight for A>(B>C>*) would be 1/(2 * 2 + 1), the weight for B>(C>*)
> would be 1/11 (2 * (2 + 3) + 1) and the weight for C>* would also be
> 1/11 (vote weight is the SL divisor for the accumulated amount of
> seats). It's a small task to change the deweighting if it should be
> more/less, or if the weight should be fixed (to 1/11 in this case) for
> all preferences in the vote. I've not pondered much on either of these
> aspects yet.
> I've done some quick tests, and I do see some peculiar artifacts, like
> not getting the exact same result when each vote only got one preference
> as when using plain Sainte-Laguë. There are smaller changes, such as
> some parties winning an extra seat while others losing one. I can only
> imagine that this is because I'm currently using floating points rather
> than rational number and thus get rounding errors, the algorithm is too
> slow for rational numbers with the data sets I'm using. I will fix this
> later.

Not getting the same result may indicate either that the subtleties of 
Condorcet need to be adjusted or that there's a bug. What we have when 
everybody bullet votes is in essence (for different favored parties A):

x: A > B = C = D

and this in turn means that the voter has a preference that says "I'd 
like to have A, but if I can't have A, it doesn't matter who I get". So 
the contest should weight A>(everybody else) by x.

Say that A and B are elected. Then the method should act as if the above 
ballot is in fact

x/3: A > B = C = D.

So there may be one of two problems here. Either there's a subtlety 
about the postprocessing (wv, margins, etc) interacting with how you 
reweight so that what is supposed to be a tie (the B = C = D part) ends 
up not looking like a tie (e.g. A>B is weighted at x/3 but B = C is 
weighted as B>C and C>B at x/5). I don't think that's likely, but I 
don't remember how the postprocessing is done, at the moment, so that 
might be what's throwing the method off. The other possibility is that 
there's a bug: that even after an A and B have been elected, your 
program is supposed to only change x/3 into x/5 for A>B, but it somehow 
alters the B vs C contest as well.

I would suggest setting up some test cases. Try an election with only 
two kinds of voters, something like:

x: A > B = C = ... = n
y: B > A = C = ... = n

and see if the results are as expected by ordinary Sainte-Laguë. If not, 
see why not. With only two blocs of voters, it should be easier to track 
down the quirk or bug.