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 <[email protected]> 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 ---- Election-Methods mailing list - see http://electorama.com/em for list info
