Thank you to Kristofer and Andy for the references. As they and I'm sure many others have realized, my example was wrong. <div><br><div>I'm still interested in how strategy would work when combining SODA with a multiwinner approval-balloted method.</div>

<div><br></div><div>JQ</div><div><br></div><div><div><br><div class="gmail_quote">2011/6/10 Kristofer Munsterhjelm <span dir="ltr"><<a href="mailto:km_elmet@lavabit.com">km_elmet@lavabit.com</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

<div class="im">Jameson Quinn wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
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.<br>


<br>
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).<br>


<br>
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.<br>


<br>
Remember, the RAV procedure is: 0. While there are still open seats, repeat the following two steps:<br>
1. Elect the highest-approval candidate<br>
2. Reweight all ballots to 1/(n+1), where n is the number of elected candidates they approve<br>
<br>
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.<br>


</blockquote>
<br></div>
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.<br>


<br>
In sequential PAV, you pick the approval winner, reweight, pick the new winner, reweight, and so on.<div class="im"><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Here's a simple example of when it comes out different from RAV:<br>
11: AB<br>
10: AC<br>
6:D<br>
<br>
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. <br>


</blockquote>
<br></div>
Ordinary PAV also elects {A,D} - it's a very narrow margin under D'Hondt, not so under Sainte-Laguė.<div class="im"><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
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.<br>
<br>
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.<br>


</blockquote>
<br></div>
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.<br>
<br>
</blockquote></div><br></div></div></div>