[EM] Semiproportional Bucklin method
Kristofer Munsterhjelm
kmelmet at broadpark.no
Tue Apr 28 00:37:59 PDT 2009
Dan Bishop wrote:
> Kristofer Munsterhjelm wrote:
>> 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.
> I've long conjectured there is no multiwinner rankedballot method
> that is both proportional and summable.
>
> However, you haven't ruled out the possibility that there could exist
> a Droopproportional method that doesn't require explicitly finding
> all the Droop sets. Such methods DO exist in the singlewinner case,
> where Droop proportionality = Mutual Majority, which can be met by a
> quadratically summable method.
I may have been vague, but that was what I referred to when saying:
>> 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.
and
>> So, if the above is right, the method can't let us determine the
>> Droop sets.
I'm not saying that the proof (if it's right) proves that you can't have
a summable Droopproportional method, but that if such a method exists,
it can't be of the form "get the Droop sets, then pick someone inside by
another method", because if it explicitly gives you all the sets, then
you can get the DAC/DSC data.
The last paragraph (about constraints and such) considers whether there
can be a summable Droopproportional method that doesn't give you all
the sets, just the candidates that happen to fulfill the Droop
proportionality criterion. By only giving the candidates, you can't get
the DAC/DSC information directly, and so the above proof no longer applies.
The proof doesn't apply to singlewinner methods, either, because the
number of seats is held fixed (at one). Thus, it should be possible to
devise a method that explicitly finds the mutual majority set if there
is one  that is, unless there's another proof that prevents it.
I know it's possible to explicitly determine the Smith set with only
the Condorcet information, at least; and the Smith set is a subset of
the mutual majority set. Perhaps one can do a Bucklin type search using
my method for k=1, then determine beatpaths or Copeland score. If
there's a shadow set (false mutual majority set), it will have members
that are beaten by more people than those in the true mutual majority
set, because those are either not beaten by anyone (and thus in the
Smith set), or only beaten by other members of the mutual majority set.

So, in short, I haven't ruled out that possibility, but I have
(probably) ruled out another class of methods (the explicit
setfinders). That is useful in that we then know what *won't* work 
you may be able to make Smith,Plurality, for instance, but you can't
make Droop//Plurality  at least not if you want summability.
More information about the ElectionMethods
mailing list