[EM] Droop-proportional expansion methods

[Kristofer Munsterhjelm]

[ 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 Hare-Condorcet method. It's 
simple because a Hare quota reduces to unanimity in the single-winner 
case, so we can just extract Hare blocs from the ballots and run the 
single-winner method internally on them. However, that won't work for 
Droop quotas because a Droop quota is a majority in the single-winner 
case, not unanimity.

But then I thought that we do have something that corresponds to a 
majority in a single-winner 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)+x-1)/(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/(v-p) * (1-f_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)+0-1)/(2*s) = (s-1)/(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 low-tech method is a pile-counting 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 non-coalition 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 population-pair monotone. 
It'd be good to have a similar method that reduces to Sainte-Laguë 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 mono-add-top 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 mono-add-top 
failure, this makes A lose? Perhaps, but then again, perhaps not. For 
the low-tech method in particular, the expansion pile is always the same 
size. The increased probability of an A-first ballot existing in the 
balance pile might still invoke mono-add-top 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.