election-methods@mailman.electorama.com

Technical discussion of election methods

View all threads

Droop proportionality by unfortunates elimination: not so simple

KM
Kristofer Munsterhjelm
Mon, Feb 27, 2023 8:53 PM

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

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