[EM] MRSODA (Mr. Soda), a SODA-inspired PR method (NP-complete???)

[Jameson Quinn]

Thank you to Kristofer and Andy for the references. As they and I'm sure
many others have realized, my example was wrong.

I'm still interested in how strategy would work when combining SODA with a
multiwinner approval-balloted method.

JQ


2011/6/10 Kristofer Munsterhjelm <km_elmet at lavabit.com>

> Jameson Quinn wrote:
>
>> SODA is essentially a procedure for turning a mixture of inter-candidate
>> rankings, bullet votes, and approval ballots, into a set of approval
>> ballots. So any PR system which accepts a set of approval ballots can then
>> be applied, to turn it into a PR system.
>>
>> I'm not aware of many approval-based PR systems, though. Perhaps it's my
>> own ignorance, but the only ones I know of are RAV and the two-ranked case
>> of a complicated, unpublished Bucklin-based system I've come up with, based
>> on the concept of assigning individual votes and electing candidates one at
>> a time. Since I don't really even understand my own system (I've decided
>> it's too complex to be worth publishing until I've at least explored its
>> properties computationally) that leaves just RAV (reweighted approval
>> voting, the approval simplification of RRV).
>>
>> But the problem with systems like RAV is that they seem to be begging
>> voters to attempt free-rider strategy, and thus encouraging candidates to
>> downplay their own (polling) status. Any system with such a strong incentive
>> for candidate dishonesty is not transparent; and any system with inherent
>> negative feedback between voter strategies is not stable. So, I tried to
>> think of a system which would be better in that sense.
>>
>> Remember, the RAV procedure is: 0. While there are still open seats,
>> repeat the following two steps:
>> 1. Elect the highest-approval candidate
>> 2. Reweight all ballots to 1/(n+1), where n is the number of elected
>> candidates they approve
>>
>> I would propose a variant of this, Minimum Remainder RAV. The slate
>> elected is the one which leaves the lowest average final weight over all
>> ballots. This is an optimizing, not a procedural system, and so I do not
>> know how hard it is in practice to calculate the result; as far as I know
>> right now, it could be NP-complete. In that case, to make it decidable, the
>> rule could be to allow anybody to submit a slate for some period after the
>> election, and the winning slate is the optimum out of those submitted. With
>> modern computers, it would be possible to submit all possible slates for up
>> to a few dozen serious candidates; past that, it may be impossible to find a
>> provably-optimum solution, but you could be certain to come close.
>>
>
> What you call RAV is actually sequential PAV. There's a global-search
> variant of it, and that's simply called PAV, whose logic goes as follows:
> find the council so that satisfaction is maximized, where each voter gets
> satisfaction f(x) where x is the number of candidates both on the council
> and his approval ballot. Usually f(x) is cumulative D'Hondt (1, 1 + 1/2, 1 +
> 1/2 + 1/3...) or Sainte-Laguė (1, 1 + 1/3, 1 + 1/3 + 1/5, ...). I seem to
> recall someone saying it's NP-hard (and thus the decision problem is
> NP-complete), but I don't know any proof of this.
>
> In sequential PAV, you pick the approval winner, reweight, pick the new
> winner, reweight, and so on.
>
>
>
>> Here's a simple example of when it comes out different from RAV:
>> 11: AB
>> 10: AC
>> 6:D
>>
>> RAV elects A,D. MRRAV elects B,C. As this example shows, MRRAV decreases
>> the free-rider incentive; under RAV, it could be in the anti-D voters'
>> interest to not approve A, even in some cases if A were their honest
>> favorite.
>>
>
> Ordinary PAV also elects {A,D} - it's a very narrow margin under D'Hondt,
> not so under Sainte-Laguė.
>
>
>  The MR- tweak, then, can be applied to other RAV-like systems, including
>> RRV (MRRRV, aka Pirate Voting, arrr arrr arrr) and SODA. Thus the title of
>> this post: Mr. Soda.
>>
>> I would be interested to hear if anyone has any insight into whether
>> there's a polynomial-time algorithm for computing the MRRAV winner. Also, if
>> this system has been proposed before, I'd love to know about it.
>>
>
> I don't think that particular system has been proposed before, but the
> general concept of optimization over councils has been. Look at Warren's
> LPV0+ and birational voting methods, for instance.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20110610/5a1f2b76/attachment-0004.htm>