[EM] Droop proportionality by unfortunates elimination: not so simple

[Kristofer Munsterhjelm]

I decided to find out what the unfortunates criteria for a four seat 
Droop election is. In this case, A is unfortunate if the Droop 
proportionality criteria force A to be excluded in a three-out-of-four 
multiwinner election.

The ways this can happen for four candidates, I think, are (up to 
candidate relabeling):
	- More than one Droop quota votes for each of the other three,
or	- More than two Droop quotas vote for {BC}, i.e. vote B and C before 
A and D; and more than one Droop quota votes for A
or	- More than three Droop quotas vote for {BCD}, i.e. A's last 
preferences is greater than 3/4 of the number of voters.

So writing this out in full (expanding the candidate relabeling 
symmetry), we have:
If the total sum of first preferences is 1, then A is unfortunate if:
	fpB > 1/4 and fpC > 1/4 and fpD > 1/4
	or
	BCAD + BCDA + CBAD + CBDA > 2/4 and fpD > 1/4
	or
	BDAC + BDCA + DBAC + DBCA > 2/4 and fpC > 1/4
	or
	CDAB + CDBA + DCAB + DCBA > 2/4 and fpB > 1/4
	or
	lpA > 3/4,

where fpX is X's first preferences and lpX is X's last preferences.

The four-seat analog of the Bucklin method I gave before would be: keep 
doing Bucklin until three candidates have more than 1/4 of the total 
preferences, then elect those three. I suspect that it will sometimes 
fail to eliminate an unfortunate candidate, and I think the failure mode 
is similar to something I a long time ago called "shadowing", where 
Bucklin gets confused between a solid coalition voting for {AB}, and a 
bunch of voters having A and B as their second preferences (say).

To prove that, I would have to set up a linear program to find a 
counterexample. It shouldn't be too difficult; it would just be rather 
much work to type out 24 preference orders and define first, first plus 
second, etc preferences in terms of them.

In any case, I think the following DP/recursive definition should 
provide unfortunates constraints for any number of candidates:

Let P be some ordered set, S be the ordered set of every candidate not 
including A, then

f(P, Droop quotas left):
	disjunction (or) over i = 1...Droop quotas left inclusive
		More than i Droop quotas vote for (form a solid coalition supporting) 
set Q, where Q contains the first i members of P
		and
			f(P \ Q, Droop quotas left - i)

f(P, 0): true

A is unfortunate iff f(S, n-1).

For three candidates, this evaluates to:
	S = {BC},
A is unfortunate if
	(i=1, Droop quotas=2)
		More than 1 Droop quota votes for B
		and
			(i=1)
			More than 1 Droop quota votes for A
	(i=2, Droop quotas=2)
		More than 2 Droop quotas vote for {BC}

which checks out.

The real question, of course, is whether there exists some unusually 
elegant simplification of all these constraints that could be used for a 
voting method, similar to how identifying the smallest mutual majority 
set is horrible but passing the mutual majority criterion is much easier.

In some sense there does (STV does it). But is there anything better, 
perhaps a combination of positional and pairwise logic?

-km