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

Kristofer Munsterhjelm km_elmet at t-online.de
Fri Jan 24 08:43:54 PST 2014

```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

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.

```