[EM] A further improved (and more complex) Condorcet/SainteLague hybrid
Kristofer Munsterhjelm
km_elmet at tonline.de
Fri Jan 24 08:43:54 PST 2014
Some time ago, I wrote about a CPO variant of SainteLague party list,
and I said that it would be better than the simple
eliminatezeroseatparties variant, though also significantly more
complex. In a later post I also wrote that while the CPO variant of
SainteLague would not fix all problems I noticed that ordinary
SainteLague 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 SainteLague to
use CPO logic. These were:
 it remains housemonotone, even when that is not desirable
 the "sliver" problem, which is a form of votesplitting
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 oneseat 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 oneseat case, my CPOized variant of SainteLague (which I'll
call CPOSL 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 twoseat
case. But in the threeseat 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 SainteLague.
So the problem here is that CPOSL is too much like ordinary SainteLague.

The sliver problem is a votesplitting 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 noninteger 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 SainteLague will give 3 seats to the leftwing
group and 9 seats to the Rgroup. But if the Lvoters 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 Lparties get one seat and the Rparty gets 8, which
is to the Lvoters' benefit.
Nothing really changes here with CPOSL. The set {L1, L2, L3, R} wins in
the former case and {L1, L2, L3, LC, R} does in the latter, so CPOSL
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, CPOSL behaves just like SainteLague, and
when they're out, they're disregarded entirely.
So that led me to think about a way of fixing that particular problem in
CPOSL, 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 CPOSL election.
2. Eliminate all parties but those in the winning CPOSL set
from the ballots. Call the resulting ballots "the
modified ballots".
3. Doing an ordinary SainteLague 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
(n1)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 nseat 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 3seat 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 Lvoters 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 2seat 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 Rvoters 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 singlewinner 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
singlewinner 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 singlewinner 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 CPOSL 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 CPOSL 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 oneseat 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 CPOSL 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
CPOSL 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 firstplace 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 CPOSL 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 nonthreshold election, it gets none at all in the
withthreshold election"), but I can't see, short of adding another
timeconsuming 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.
More information about the ElectionMethods
mailing list