[EM] Droopproportional expansion methods
Kristofer Munsterhjelm
km_elmet at tonline.de
Mon Sep 14 14:30:29 PDT 2015
[ or: in which I consider electoral methods on election day here in
Norway in between watching coverage of the election :) ]
In my previous post, I mentioned a simple HareCondorcet method. It's
simple because a Hare quota reduces to unanimity in the singlewinner
case, so we can just extract Hare blocs from the ballots and run the
singlewinner method internally on them. However, that won't work for
Droop quotas because a Droop quota is a majority in the singlewinner
case, not unanimity.
But then I thought that we do have something that corresponds to a
majority in a singlewinner case, namely the mutual majority criterion.
It says that if a majority prefers a set of candidates to everybody
else, then someone from that set must be elected.
Thus the "expansion methods", whose idea is to expand (that's why I call
them that) a Droop quota into a majority, run an election on the altered
ballot set, and then reverse the expansion. After thinking for a bit, I
found three possible approaches: a low tech one, a linear one, and a
quadratic one.
The idea of the linear method is to fit a linear function so that a
Droop quota (1/(s+1)) gets mapped to a majority (50%) and unanimity
(100%) still gets mapped to unanimity (100%). That's two points, so a
linear function is good enough. The linear function turns out to be
(unless I'm mistaken)
f_linear(x) = (s(x+1)+x1)/(2*s)
where x is the share of the ballots (0 meaning 0% and 1 meaning 100%)
and s is the number of seats. Let's again disregard equal rank to make
matters easier. Then the method becomes, based on the Hare method of the
last post:
====
1. Count the strengths (support) of every solid coalition.
2. Among the coalitions with more than a Droop quota's worth of
support, let the one with least number of candidates be the "smallest
strong Droop coalition" (SSDC). Break ties in favor of the coalition
with most votes.
3. Say the SSDC is supported by p voters out of v. Then create a
temporary ballot set where each ballot that is in that coalition has its
weight multiplied by v/p * f_linear(p/v), and each ballot not in the
coalition has its weight multiplied by v/(vp) * (1f_linear(p/v)). This
expands the coalition to have f_linear(p/v) relative support.
4. Conduct an advanced Condorcet election (i.e. with a Condorcet method
that passes mutual majority) on the temporary ballot set. Call the
winner W. (Since the method passes mutual majority, the winner picked by
the method must be part of the coalition.)
5. Elect W, eliminate him from every ballot, and reweight and distribute
the surplus of the SSDC on the main ballot set. Discard the temporary
ballot set.
6. If all seats are filled, we're done.
7. Otherwise go to 1.
===
The quadratic method is just like the linear one, except it might be
more mathematically consistent. One might argue that a ballot set with
no support whatsoever should be scaled to zero. But f_linear(0) =
(s(0+1)+01)/(2*s) = (s1)/(2s) > 0. So if we desire mathematical
consistency of the function, even outside of the domain where it is to
be used, then we should fit three points instead:
f(0) = 0
f(1/(s+1)) = 0.5
f(1) = 1
and the simplest way of doing so is with a quadratic. It turns out that
the equation to use is (again, unless I miscalculated)
f_quadratic(x) = (x^2  x)/(2s)  (sx^2  sx)/2 + x.
The system is otherwise as above. The reason we might prefer something
that extrapolates smoothly is that it, in some sense, is a simpler model
(no discontinuity) and so might have better properties. But I don't know
if it actually would; mathematical elegance is only a heuristic.
===
The lowtech method is a pilecounting method that might be a variant of
the linear method. At first I thought it was indeed equivalent to the
linear method (in expectation), but now I'm not so sure.
It is somewhat of a paradoxical method because finding solid coalitions
by hand is very tedious and the most advanced systems (Ranked Pairs,
etc) are also impractical to count by hand.
The manual method works this way:
1. Count the strengths (support) of every solid coalition.
2. Find the smallest strong Droop coalition as in the other methods.
3. Pull a Droop quota's worth of ballots from that coalition and place
them in the expansion pile.
4. Randomly draw from the remainder (the surplus of the coalition as
well as the noncoalition ballots) to a balance pile until the balance
pile is as large as the expansion pile.
5. Conduct an advanced Condorcet election on the two piles (balance and
expansion), and elect and eliminate the winner.
6. If the council is full, we're done. Otherwise:
7. Discard the expansion pile and place the contents of the balance pile
back in the main pile.
8. Go to 1.
===
All the methods above are easy to modify into party list methods. If
each of the candidates represent parties, then just don't eliminate that
candidate before it has exhausted its list  e.g. if party X fields
three candidates, it is only eliminated after it has been elected three
times. Everything else proceeds as usual, and the Droop quota is defined
on the number of seats in the assembly in total.
In this respect, the candidate method is equivalent to a party list
method where each candidate is a "party" that fields a single candidate.
Unfortunately, being based on a set quota, the method would (most
likely) reduce to a largest remainder method when everybody plumps.
That, in turn, means that the method is not populationpair monotone.
It'd be good to have a similar method that reduces to SainteLaguë or
Webster (or even D'Hondt), but I don't know how to do so.

The methods seem to be safe from most of STV's nonmonotonicity. Suppose
that someone who voted B>A>... raises A to A>B>... . They can't make A
drop out of an SSDC by doing so; either the SSDC was a single candidate
(say B), in which case the disappearance of that SSDC doesn't harm A; or
the SSDC had and has both A and B in it, in which case that coalition
will still be the SSDC. Furthermore, if the Condorcet method used passes
monotonicity, raising A can't make A lose if the coalition remains the same.
Perhaps monoaddtop failure can make the system nonmonotone? Say
someone who voted B>C>A>... raises his vote to A>B>C>..., and is added
to the {AB} coalition. Is it then possible that, because of monoaddtop
failure, this makes A lose? Perhaps, but then again, perhaps not. For
the lowtech method in particular, the expansion pile is always the same
size. The increased probability of an Afirst ballot existing in the
balance pile might still invoke monoaddtop failure. In any case, what
the system fails and passes can be kind of hard to see by intuition alone.
It should also behave better as far as clones are concerned. Cloning A
can't make A disappear from the SSDC if it was in it, except when it's
displaced by a clone. Within a given SSDC, if the advanced method used
is cloneproof, the presence of a clone won't alter anything either.[1]
Another interesting aspect is that while mutual majority ensures that
the winners must come from the coalitions, which of them wins may be
influenced by votes outside of the coalition. So it both pays attention
to votes within the coalition and outside it.
The method is sort of clumsy (particularly with the need to find
coalitions manually), but perhaps the logic can be incorporated into an
advanced method more directly. That is, if there isn't some hidden flaw
that seriously compromises this approach.
[1] But perhaps it is still clone vulnerable, e.g. if before the cloning
you have something like
{A B} 100
{B C} 99
and AB is the SSDC with say, the Droop quota being 90, but afterwards:
{A1 A2 B} 100
{B C} 99
{A1 B} 49
{A2 B} 51
after which {B C} becomes the SSDC. Again, hard to tell.
More information about the ElectionMethods
mailing list