[EM] Getting closer to the DPC while strongly summable.

[Kristofer Munsterhjelm]

As I wrote in a post I think I sent to this list, no method that uses a 
positional matrix can pass the Droop proportionality criterion when 
there are more than three candidates. I showed this by giving two ballot 
sets, each of which had the DPC mandate a different subset of the 
candidates should win, but that had the exact same positional matrix.

(If I didn't post that to the list, let me know, and I'll resubmit!)

By the "positional matrix", I here mean an n*n matrix where the (a,b)th 
entry gives how many times the ath candidate was placed in bth place.

A method that's limited to the positional matrix is, to use my terms, 
"strongly summable". A strongly summable method is one where you have an 
amount of data that grows as a polynomial of the number of candidates 
involved, and that this data can be used for every single- or 
multiwinner election of subsets of the number of candidates. That is, 
you can use the same data for a single-winner election out of three 
candidates as one where you elect two out of three. That is opposed to 
"weakly summable", where, if you set the number of seats to be constant, 
the method is summable, but it is not summable when you vary the number 
of seats. I think Schulze STV is weakly summable, but CPO-STV is not. 
Ordinary STV is neither strongly nor weakly summable.

Thus we can ask - how close can we get to the DPC while being strongly 
summable? I don't know how to answer that question. I only have a vague 
idea of how to find what polynomial subset to use for a strongly 
summable method that passes the DPC, if one exists*. However, I can try 
to get closer for methods limited to the positional matrix.

Some time ago, someone advocated SNTV (or a cumulative vote version of 
it) as a pretty good strongly summable multiwinner method - or rather, I 
think they said something to the effect of "if you're going to demand 
strong summability, you're pretty much limited to SNTV. It'll give you 
*some* proportionality, but not much". I think I have found something 
better, though.

Consider a version of Bucklin where the threshold is at (or 
infinitesimally greater than) a Droop quota rather than a majority. In 
the single-winner case, this method meets the single-winner version of 
the DPC, mutual majority. What of multiwinner cases?

Well, that's where I first found this solution. I was fiddling with 
geometric logic, kind of like Saari has been doing but on a much simpler 
level (using lots of trial and error and Redlog, the latter crashing 
often). The Bucklin method with a threshold of a Droop quota seems to 
meet the Droop proportionality criterion not just in the single-winner 
case but in the "elect two out of three" case, too.

To be more proper about it, it definitely meets the following weakened 
criteria:

Say the Droop quota is 1/(k+1) of the total.

- If a candidate gets more than k/(k+1) first place votes, he should be 
in the outcome.

- If a candidate gets more than k/(k+1) last place votes, he should 
*not* be in the outcome.

The first follows directly from the DPC: if a candidate gets more than 
k/(k+1) of the FPPs, then that means that a coalition that includes him 
also has got k/(k+1) support, so that coalition should get all the seats.

The second can be reasoned analogously. If a coalition that does not 
include a certain candidate got k/(k+1) of the other place votes, 
meaning the candidate should not be part of the outcome, then that 
candidate will have k/(k+1) of the last place votes.

Furthermore, in the two-out-of-three case, the Bucklin method does more. 
Consider the case where a solid coalition gets more than one Droop quota 
but not more than two. Then, if the coalition consists of a single 
candidate, that candidate obviously becomes part of the outcome (as it 
should).
On the other hand, if the coalition consists of two candidates, say A 
and B, then the DPC constraints say "at least one of A and B must be 
elected". The Bucklin method passes by electing A (if that's the 
candidate ranked first).

SNTV passes neither of the (much weaker) criteria above. Consider this 
ranked ballot situation:

100: A > B > C
   1: C > A > B

two to elect.

Here, the DPC says that A and B should be elected. SNTV elects A and C 
instead.

-

What can we do with this method, and what other things can be concluded 
from it? Well, first, if I'm right that it does pass the DPC in the 
2-of-3 case, it shows that you can pass it in that particular case and 
be monotone. That is, if there's a proof that you can't have both the 
Droop proportionality criterion and monotonicity, it must involve more 
than three candidates.

Second, it could be used as the final stage of an "elect and punish" 
type method based on Bucklin. It would be monotone not just for the 
final member of the assembly, but also for the final two if there are 
only three candidates left. Of course, it could also be used when there 
are more than three candidates left, but then the combined method 
wouldn't pass the DPC.

-

Can we get further? I don't know yet, but I may tinker more.

-

* I imagine this would take the form of a logic statement of the sort: 
"There exists an assignment of weighted sums of all possible orderings 
to a certain number of variables so that there is no example where the 
DPC constraints differ yet these variables are the same". But doing that 
by automated quantifier elimination would still only prove the thing for 
a finite number of candidates! It would take a very long time, too.