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

[Kristofer Munsterhjelm]

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.