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

[Andy Jennings]

Jameson,

On Fri, Jun 10, 2011 at 6:53 AM, Jameson Quinn <jameson.quinn at gmail.com>wrote:

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

You may want to Google "Brams Kilgour Approval Committee".  In early 2009, I
saw Marc Kilgour give a talk that surveyed MANY different methods of
resolving a multiwinner election from approval ballots.  He considered many
different permutations and parameters.    I think this is a similar "survey"
paper: http://www.springerlink.com/content/r173p72n6l1q6880/

But it's not free...  :(

It seems the method that Kilgour and Brams like best is called Satisfaction
Approval Voting.  There is some material about this in Brams' book
"Mathematics and Democracy".



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


Can you explain what it means that "the slate elected is the one which
leaves the lowest average final weight"?

I thought it meant to minimize SUM(1/(N_i + 1)) over all voters, i, where
N_i is the number of winning candidates approved by voter i.

But in your example, electing B and C would leave 21 voters with one
approved candidate and 6 voters with zero approved candidates, which gives
an average final weight of 0.6111.  Electing A and D would give all 27
voters exactly one approved candidate, for an average final weight of 0.5.
 So wouldn't A and D be the winner in MRRAV?

Andy
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20110610/51573a4e/attachment-0004.htm>