[EM] A monotonic proportional multiwinner method

[Warren Smith]

if you can find a polytime algorithm to find a violated constraint
whenever one exists, then I can find a polytime algorithm to solve the
linear program.  (Proof: known result about "ellipsoid method.")


On 3/12/10, Kristofer Munsterhjelm <km-elmet at broadpark.no> wrote:
> Warren Smith wrote:
>> Kristofer Munsterhjelm's "monotonic proportional multiwinner method"
>> -- a few comments
>>
>> (1) wow, very complicated.  Interesting, but I certainly do not feel
>> at present that I fully understand it.
>
> Alright. If you have any questions, feel free to ask.
>
>> (2) RRV obeys a monotonicity property and a proportionality property
>> http://rangevoting.org/RRV.html
>
> My experiments with multiwinner methods seem to indicate that you need
> proportionality not just of single candidates but also of groups of
> them, like satisfied by the DPC or by this.
>
>> (3) assuming we're willing to spend exponential(C) computer time to handle
>> elections with C candidates, then KM's constraints form a "linear program"
>> which
>> in fact would be an "01 integer program" if candidates get elected or
>> not (cannot be 37% elected).  Program has exponential(C) number of
>> constraints.
>
> So do methods like Schulze STV. In any case, I wonder if it's possible
> to make some sort of polytime algorithm for my method, but it would
> probably be quite difficult. One would have to understand the nature of
> the shifting of constraints as the divisor changes to find the
> best-margin council that doesn't contradict, implicitly.
>
> If it's possible, a comparison would be that a method like STV satisfies
> the Droop proportionality criterion even though this is also,
> mathematically speaking, an integer program ("every coalition supported
> by more than k Droop quotas should have at least k members in the
> outcome, unless the size of the coalition is less than that").
>


-- 
Warren D. Smith
http://RangeVoting.org  <-- add your endorsement (by clicking
"endorse" as 1st step)
and
math.temple.edu/~wds/homepage/works.html