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

[Jameson Quinn]

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.

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.

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.

JQ
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20110610/303aaf57/attachment-0003.htm>