[EM] Semiproportional Bucklin method

[Kristofer Munsterhjelm]

Raph Frank wrote:
> On Sun, Apr 26, 2009 at 10:09 AM, Kristofer Munsterhjelm
> <km-elmet at broadpark.no> wrote:
>>  Round 1:
>>  {A}: 25       to be elected: 1, already elected: 0
>> but
>>  {A B}: 14     to be elected: 0, already elected: 0
> 
> I think the problem is that you need to be able to work out the total
> number of voters who support a given set.
> 
> {A} is supported by 25 votes, so is entiled to 1 seat
> 
> In round 3, {B,C,D} is supported by 24 voters, but they have already
> voted for A, so really they should have their voting weight reduced.
> 
> If {B,C,D} was actually 3 party X candidates (and they had 21 votes),
> then they would be entitled to a seat.
> 
> You need some way to indicate that B,C and D are using later choices
> from a candidate who was elected.

Yes, that's what IRV etc does. By reweighting the group who "got what 
they wanted", they keep that group from getting more than their share.

Using a DAC/DSC type set structure lets one do what you propose, 
directly. For instance, for something like:

4: B > C > A > E > D
5: A > B > D > E > A
5: A > C > E > B > D
5: D > E > C > A > B
5: E > D > B > C > A

you get (with a Droop quota of 8, two to elect)

  #  subset       DPC mandates how many
24: {A B C D E}  2
  9: {A B C E}    1
  5: {A B D E}    n/a
  5: {A C D E}    n/a
  5: {B C D E}    n/a
  4: {A B C}      n/a
  5: {A B D}      n/a
  5: {A C E}      n/a
  5: {B D E}      n/a
  5: {C D E}      n/a
  5: {A B}        n/a
  5: {A C}        n/a
  4: {B C}        n/a
10: {D E}        1
  4: {B}          n/a
10: {A}          1
  5: {D}          n/a
  5: {E}          n/a

which contains the proper Droop sets (the permitted outcomes are {A D}, 
{A E}). The problem with this is that in the worst case, there are 2^n 
possible subsets, and you have to keep track of all of them when summing 
up votes, because any of them might become a Droop set later on.

I think this can be used to make a proof that a summable multiwinner 
method can't let you actually discover all the Droop sets. The idea 
would be something like this: say that the method does, and it's 
summable. Then you can, by a combination of padding with irrelevant 
votes (for candidates that appear nowhere else), and altering the number 
of seats, determine the solid coalition set for any number of voters. If 
you can use the method to determine all the Droop sets, then this in 
effect lets you reconstruct the DAC/DSC information. But that 
information takes superpolynomial space, so by pigeonhole, you can't get 
it from a method that only relies on a polynomial amount of data.

If that proof is true, then the Bucklin method must be semiproportional, 
because you use it to construct sets, then check if they pass some rule. 
If that rule only caught Droop sets, you could derive the Droop sets, 
and thus reconstruct the DAC/DSC information, etc.

Note that this proof (if it works) doesn't apply to mutual majority, or 
to methods that are summable when the number of seats is held fixed. 
There can be only one smallest mutual majority set (since there's only 
one majority), and thus (at worst) n mutual majority sets for n 
candidates, which is polynomial in the number of candidates.
As for methods that are summable when the number of seats is held fixed, 
you can't increase the number to be elected to lower the Droop quota. 
For a practical example, Schulze STV is summable in this manner - the 
space required to hold the pairwise matrix is less than C^(M+1) where C 
is the number of candidates and M the number of seats. That's 
exponential if you let M change, but polynomial with M fixed.

-

So, if the above is right, the method can't let us determine the Droop 
sets. What about the output? Consider the worst case, where each winner 
is in the outcome because slightly more than a Droop quota voted for a 
set that included that winner. If there were no constraints, the winner 
set would simply be a subset of the union of all the Droop sets (which 
one might have if everybody unanimously voted in a certain order). 
However, there are constraints, e.g.

Droop quota + 1: {A B C} (pick only one)
Droop quota + 1: {B C D} (pick only one)

which permits {A D} but not {A C}, {B C} or {B D}.

That muddies the picture. Can one devise a method that is both summable 
(with varying numbers of seats) and that passes the DPC? I don't know, 
but it would seem that if we can, it can't work by the "here are all the 
Droop sets, pick as you wish" principle.

Perhaps a good place to start would be to try to find an algorithm that, 
given a bunch of sets and "elect exactly n" data for each, finds the 
output that is consistent with all those limits, if such an output 
exists. Another option would be to find other methods that pass mutual 
majority (but not Smith), and to see if they could be generalized, like 
I tried to do with Bucklin.

-

Also, if anyone here finds a problem with my proof idea, go ahead and 
say so. If I'm wrong, and a summable method can use all the Droop sets 
directly, all the better!