[EM] A further improved (and more complex) Condorcet/Sainte-Lague hybrid

[Kristofer Munsterhjelm]

Some time ago, I wrote about a CPO variant of Sainte-Lague party list, 
and I  said that it would be better than the simple 
eliminate-zero-seat-parties variant, though also significantly more 
complex. In a later post I also wrote that while the CPO variant of 
Sainte-Lague would not fix all problems I noticed that ordinary 
Sainte-Lague had, and therefore I tried to find a better method.
I found something that kinda worked but had weird behavior with ties due 
to its Approval nature, but now I think I have found something that does 
better still, and is more manageable as well.

I found at least two problems remained even after fixing Sainte-Lague to 
use CPO logic. These were:
	- it remains house-monotone, even when that is not desirable
	- the "sliver" problem, which is a form of vote-splitting

I'll explain what these problems are, then I'll explain the new method 
and the reasoning behind it, and then how it solves those problems (with 
concrete examples). Finally, I'll mention how it could be altered to 
take thresholds into account.

-

The house monotonicity problem is most easily seen with the old LCR 
example (and I will be using that example elsewhere as well). Consider:
		11: L > C > R
		10: R > C > L
		 2: C > L > R

Now, for a one-seat election, Condorcet will pick C, and I would say 
that is the proper winner. Pretty much every voting system agrees; 
notably, IRV and Carey does not.

In the one-seat case, my CPO-ized variant of Sainte-Lague (which I'll 
call CPO-SL from now on) will pick C, since it then reduces to the base 
Condorcet method. It will also pick one L and one R in the two-seat 
case. But in the three-seat case, it will pick two L and one R. It does 
this because it has to pick L and R (to get one of each), and once L and 
R are in the running, they obscure the second (center) preference and so 
the method works like ordinary  Sainte-Lague.

So the problem here is that CPO-SL is too much like ordinary Sainte-Lague.

-

The sliver problem is a vote-splitting problem where different voters in 
support of different parties get slightly more than a seat's worth of 
support for their party. Each of the voting blocs get rounded down to an 
integer number of seats, and some monolithic opposition party gets the 
remaining seats. However, if the "excess" voters knew who they were and 
cooperated to vote for a single party, they would get an additional seat.

To be more concrete (with non-integer voting weights just to make it 
easier):
		1.33: L1 > LC
		1.33: L2 > LC
		1.34: L3 > LC
		   8: R

With 12 seats, ordinary Sainte-Lague will give 3 seats to the left-wing 
group and 9 seats to the R-group. But if the L-voters decided to be 
strategic and  group the excess "slivers" together, they could do this:
		1: L1 > LC
		1: L2 > LC
		1: L3 > LC
		1: LC
		8: R

so that each of the L-parties get one seat and the R-party gets 8, which 
is to the L-voters' benefit.

Nothing really changes here with CPO-SL. The set {L1, L2, L3, R} wins in 
the former case and {L1, L2, L3, LC, R} does in the latter, so CPO-SL 
also has this problem or incentive to strategy.

-

The common pattern here is that parties are either wholly in or wholly 
out. When they're wholly in, CPO-SL behaves just like Sainte-Lague, and 
when they're out, they're disregarded entirely.

So that led me to think about a way of fixing that particular problem in 
CPO-SL, and I think I have found something. If the problem is that 
parties are either wholly in or out, let's do something about it. But 
because these methods would be used on very large assemblies, it's not 
very tempting to go right to the sort of combinatorial methods that 
Schulze STV uses.

Thus, a hybrid. This hybrid goes as follows:
	1. Starting at n seats, perform an ordinary CPO-SL election.
	2. Eliminate all parties but those in the winning CPO-SL set
		from the ballots. Call the resulting ballots "the
		modified ballots".
	3. Doing an ordinary Sainte-Lague based on the modified
		ballots, determine what party should get the first seat.
	4. Give that seat to the party in question, then reweight the
		base ballots of every voter who, on the modified
		ballots, voted that party first.
	5. If n = 1, you're done, otherwise go back to 1 with an
		(n-1)-seat election using the reweighted ballots (but
		with no eliminated parties).

What's the complexity of this? If there are 10 parties and 128 seats, 
the number of party sets to consider is 2^10. Say we use an n^2 
Condorcet method. Then the Condorcet method has a runtime of a constant 
times 2^20, which is still manageable; and the method is called 128 
times, so the total is proportional to 2^27.

For an n^3 Condorcet method it gets a little tougher, but one can 
probably use tricks to quickly arrive at the set of parties that are in 
contention for the n-seat election (i.e. parties whose sets make up the 
Condorcet cycle if there is one).

Note that if x voters are reweighted once (by a division by three), and 
latter, another group including some of these x voters is reweighted, 
then the voters who got reweighted twice have a divisor of five, and 
those that were only reweighted once have a divisor of three.

-

The new iterated procedure seems to solve both of the problems I have 
mentioned, because it no longer considers parties to be either all in or 
all out. Let's look at the 3-seat LCR example above.

The first election goes:
	11: L > C > R
	10: R > C > L
	 2: C > L > R

so {LR} is the Condorcet winner. Thus all parties but L and R are 
removed and we get:
	11: L>R
	10: R>L
	 2: L>R

In the following allocation, it's obvious that L gets the seat (because 
it has the most votes). As a consequence, all L-voters in the reduced 
ballot set above get deweighted, so that we get:

	11/3: L>R	(full ballot: L>C>R )
	10  : R>L	(full ballot: R>C>L )
	 2/3 :L>R	(full ballot: C>L>R )

So L is given a seat, and then we start on the 2-seat election with the
following ballots:
	11/3: L>C>R
	10  : R>C>L
	 2/3: C>L>R

And it's pretty obvious that again {LR} wins and R gets the first seat 
of the actual allocation. So seat #2 goes to R. The truncated ballots 
look like:
	11/3: L
	10  : R
	 2/3: L

so the R-voters are deweighted and we end up with
	11/3: L>C>R
	10/3: R>C>L
	 2/3: C>L>R

We finally end up with the single-winner situation where the system 
reduces to plain Condorcet. And because all the vote counts have simply 
been divided by 3, there's no in principle difference between this and 
the original ballot set, so C is still the Condorcet winner.

Hence, the apportionment gives one seat to L, one to R, and one to the 
compromise, C. (This might even help defuse kingmaker objections in 
favor of a threshold, because the last few seats will go to centrists.)

-

And then, the sliver problem:

                 1.33: L1 > LC
                 1.33: L2 > LC
                 1.34: L3 > LC
                    8: R

Since there are so many seats, I won't go manually through every single 
seat.
Define the first stage as the elections where {L1, L2, L3, R} is the CW:
	In the first stage, first R gets three seats. After the
	successive deweightings, we have:

		1.33/1   =     1.33: L1 > LC
		1.33/1   =     1.33: L2 > LC
		1.34/1   =     1.34: L3 > LC
		8.00/7   =     1.14: R

	so now L3, L1, and L2 get one seat each, and we have:

		1.33/3   =     0.443: L1 > LC
		1.33/3   =     0.443: L2 > LC
		1.34/3   =     0.447: L3 > LC
		8.00/7   =     1.143: R

In the second stage, {L3, R} wins and the seventh seat goes to R. Now we 
have:

	1.33/3   =     0.443: L1 > LC
	1.33/3   =     0.443: L2 > LC
	1.34/3   =     0.447: L3 > LC
	8.00/9   =     0.888: R

Finally, for the last seat, the election reduces to an ordinary 
single-winner Condorcet election, which LC wins.

Generally, the iterated procedure solves the sliver problem because, 
when all the "ordinary" seats have been allocated to the split faction, 
it no longer considers their minor parties in the running. To be more 
precise, sets that include the parties are beaten by sets that don't. 
This leaves it free to consider the election as if the split parties 
hadn't participated at all, and all the "slivers" add up to give the 
compromise party a seat.

The method will still tend towards giving seats to highly preferred 
parties rather than seeking a compromise, though. It just doesn't waste 
a seat when there is a compromise to be found; and the closer it gets to 
the final seat, the more willing it is to compromise (since the method 
approaches single-winner Condorcet).

-

What about thresholds? If thresholds are based on initial first 
preference counts, then the answer would seem to be easy: simply 
eliminate parties that are below the threshold, one at a time, until 
they're all gone. However, this is like eliminating parties that get no 
seats until they're all gone, and I constructed CPO-SL to get around the 
path dependence that leads to.

So I can think of two different ways of handling thresholds. They're 
both based on a modification of the scoring function. The threshold 
effectively means that any party that has support less than x% of the 
total vote will get zero seats no matter what. So simply include this 
into the scoring function for a CPO-SL contest: if the set of parties 
includes a party that's below the threshold (according to the ballots 
where irrelevant parties have been eliminated), then that's a violation 
of the one-seat constraint (i.e. the party will get no seats, but since 
it's included in the set, it should have at least one), and so the
side of the pairwise matchup that includes that party gets zero points.

The first way would run an initial CPO-SL election (for as many seats as 
there are in the assembly) with the modified scoring function mentioned 
above. Then you eliminate every party not in the winning set, and then 
you run the iterated procedure, with an unmodified scoring rule, on the 
ballots where all the other parties have been eliminated. If the initial 
CPO-SL set is a Condorcet winner, then that means that none of the 
parties who were eliminated can be sequentially
introduced without either falling below the threshold (if I'm not 
mistaken). This property could be used to explain what the threshold 
actually *means*.

However, the first way would eliminate compromise parties that don't get 
any first-place votes. While some people think this is a feature (err, 
"core support"), I disagree, and so there's the second way: use the 
modified scoring function for every seat of the iterated CPO-SL method, 
but count thresholds based on unweighted ballots. The ballots to use for 
the threshold calculation still have parties that are not part of the 
contest/matchup eliminated, but they're not reweighted as the method 
continues. That way, parties are eliminated if they go below the 
threshold, except if they're important centrists.

Perhaps one could make seat thresholds (e.g. "if a party would get fewer 
than x seats in a non-threshold election, it gets none at all in the 
with-threshold election"), but I can't see, short of adding another 
time-consuming level on top of the election (try every combination of 
parties and see if they do gain fewer than x seats), see how to 
implement that. Just running an iterated method once, then eliminating 
those that got fewer than x seats may risk path dependence of the sort 
that causes IRV's chaos / sensitivity to initial conditions.