[EM] A more Condorcet-like party list PR method

[Kristofer Munsterhjelm]

Among other things, in Wahlberg's thread, there was a discussion about 
ways of making Sainte-Laguë party list PR accommodate ranked ballots.

The simplest method found was:

1. Allocate seats according to Sainte-Laguë or Webster with respect to 
first preference votes.
2. If any party got zero seats:
2.1. Remove the party with the least votes from all ballots.
2.2. Go to 1.

This will work most of the time, but it has two potential problems.

The first is that when there are only a few seats, it will reduce to 
Plurality (i.e. it doesn't take compromise parties into account).

The second is that the order of elimination may matter. If you have an 
L-C-R situation among parties, and none of them can get a seat by first 
preferences alone, then the compromise C (which may get a seat were L 
and R eliminated) may be eliminated early and so make the outcome worse 
for the L-C-R voters.


After some thinking, I think I've found a hack that should fix the 
second problem. I'm unsure how much it fixes the first, but it reduces 
to Condorcet in the single-seat case.

It's also probably too complex to be used, but that's another matter :-)


So, the method. It works like CPO-STV or Schulze STV: you define a 
function f({x}, {y}) for subsets {x} and {y}. This function produces a 
score of a virtual contest between the two subsets, and then these 
contests become the entries in a pairwise matrix that is run through a 
Condorcet method.

For this method, the subsets are sets of parties. To determine the score 
for f({x}, {y}), do this:

1. Eliminate all parties not in either {x} or {y}.
2. Do a restricted Sainte-Laguë allocation for {x}. A restricted 
allocation goes like Sainte-Laguë, but no party not in {x} can get any 
seats, and every party in {x} must get at least one seat. Implement 
thresholds as needed here.
2.1. If the allocation is contradictory (e.g. more parties than seats, 
or there is a threshold and a party below it has been given seats), then 
treat the allocation as one where no seats were given to any party.
3. Once done, for each party, add the number of voters that voted for 
that party, minus that party's quotient, to a common sum. Call this sum 
{x}'s proportionality score.
4. Do a restricted Sainte-Laguë allocation for {y} and similarly 
calculate {y}'s proportionality score.
5. f({x}, {y}) is equal to {x}'s proportionality score in this contest. 
f({y}, {x}) is equal to {y}'s proportionality score in this contest.

And here's a last-seat compromise example, adapted from the LCR example 
I gave earlier:
	100: X
	100: Y
	 46: L > C > R
	 44: R > C > L
	 10: C > R > L

3 seats.
Let's determine f({XYR}, {XYC}):
	The union of these subsets is {XYRC}, so L is eliminated. We now have:
	100: X
	100: Y
	44: R
	56: C

	Restricted Sainte-Laguë allocation for {XYR}:
		By the one-seat rule, we give one seat to each.
		This gives a quotient of 100/3 for X and Y, and
		44/3 for R.

	The proportionality score is thus:
		  100 - 100/3		(X-voters)
		+ 100 - 100/3		(Y-voters)
		+ 44 - 44/3		(R-voters)
		+ 0			(C-voters)
		= 488/3

	Now, do {XYC}.
	Restricted Sainte-Laguë allocation for {XYC}:
		By the one-seat rule, we give one seat to each.
		This gives a quotient of 100/3 for X and Y, and
		56/3 for C.

	The proportionality score is thus:
		  100 - 100/3		(X-voters)
		+ 100 - 100/3		(Y-voters)
		+ 0			(R-voters)
		+ 56 - 56/3		(C-voters)
		= 512/3

	So {XYC} wins, as it should.

And an example where the seats aren't all forced by the one-seat rule,
f({XL}, {XC}), again 3 seats:
	The union of these subsets is {XLC}, so we have
	100: X
	 46: L
	 54: C

	Restricted Sainte-Laguë allocation for {XL}:
		By the one-seat rule, one seat has to go to X and one
		has to go to L. Now the quotients are 100/3 for X,
		46/3 for L, and 54 for C. Since the allocation is
		restricted to {XL}, C can't get any seats. Of the
		remaining parties, X has the greatest quotient
		and gets the second seat.

		The final quotients are 100/5 for X, 46/3 for L, and
		54 for C.

	The proportionality score is thus:
		  100 - 100/5		(X-voters)
		+  46 - 46/3		(L-voters)
		+   0			(C-voters)
		= 332/3

	By the same reasoning, for {XC}, X gets two seats and C gets
	one. This gives a proportionality score of 116, which is
	348/3 and thus {XC} wins this contest.

Finally, in a 3-seat election, f({XYLC}, {XYRC}) would return 0 on both 
sides. The one-seat rule implies that all four parties must get a seat, 
but that is impossible as there are only three seats. Therefore the 
allocation aborts without allocating any seats, and so the 
proportionality score is 0 for every party, giving a total of 0.


To actually get the assembly, just find the party subset that wins 
according to the underlying Condorcet method, then do a restricted 
Sainte-Laguë allocation based on that subset.

This should work because all possible ways of eliminating subsets of 
parties are considered. Thus, in an "L-C-R among minor parties" 
scenario, {..., C} will beat either {..., L} or {..., R} pairwise: it 
beats {..., L} because both the C-first and R-first voters will be 
supported by C; and it beats {..., R} because both the C-first and 
L-first voters will be supported by C.


Yes, the method is basically CPO-STV applied to Sainte-Laguë.

A less hackish method might directly consider pairwise relations that 
hold true for Sainte-Laguë allocation, but I haven't got there yet. A 
better method might also redistribute voters that don't contribute to 
getting a seat allocated to the party. I'm not sure that would reduce 
the method to a quota-based one, now; perhaps we only need a "floating 
quota" for the method to be sufficiently divisor-like to satisfy 
population-pair monotonicity, reduce to ordinary party list with enough 
voters and seats, etc. On the other hand, I'm not sure that it wouldn't, 
either. In any event, in the current method, there's little reason for 
voters to vote beyond first rank if the party they vote for as favorite 
is guaranteed of getting at least one seat.

It may be possible to solve a variant of this method in less space than 
2^(num parties) by changing the proportionality score from sum to 
leximax and doing some kind of dynamic programming, because the 
allocation step seems to be quite suited to optimal substructure 
thinking. On the other hand, the elimination steps might make that 
impractical.

The method should be weakly summable (i.e. when the number of parties 
are kept constant). For each cell in the matrix, do the elimination 
first, then store the counts for each party. These counts can be summed 
up between districts, so if n is the number of parties, you have (2^n)^2 
cells, each of which stores n numbers in the worst case. And since n is 
a constant, so is 2^n.

It's also a relatively simple matter to switch out Sainte-Laguë for any 
other divisor method you might desire to use. A slight snag as it is 
currently set up: the initial divisor should be 1, so that parties that 
don't get any seats don't contribute to the proportionality count at 
all. Thus the modified Sainte-Laguë method would have to be adjusted, I 
think; unless the /1.4 reduces to a constant and so never changes the 
outcome.