Fully proportional representation
The Monroe voting rule is a rule for multiwinner voting, published by Burt L. Monroe in 1995.[1] Its goal is to provide a fuller proportional representation than existing rules.
Background
Most existing electoral systems for proportional representation (PR) are based only on the voters' first preferences, for example: if 40% vote for party A as their first choice, then 40% of the parliament members should be of party A. This ignores the fact that voters may have different preferences below their first choice. Monroe's voting rule aims to provide fully proportional representation (FPR), based on the voters' preferences over all candidates.
Monroe's rule creates an explicit connection between the elected candidates and the voters; each voter knows his representatives, and each representative knows which voters he represents. It is one of the only rules that satisfies both proportionality and accountability.[2]
The rule
Let k be the number of committee members, m the number of candidates, and n the number of voters. Each voter submits a ranking of the candidates. Monroe's rule chooses k candidates and associates n/k voters with each candidate, such that each voter is associated with exactly one candidate.
The satisfaction of a voter from a given committee is determined by a fixed score function, usually the Borda count. For example, if a voter is represented by his best candidate, then his satisfaction is m-1; if a voter is represented by his worst candidate, then his satisfaction is 0.
Variants
Betzler, Slinko and Uhlmann[3] study a variation of Monroe's rule which, instead of minimizing the sum of misrepresentations, minimizes the maximal misrepresentation. These variants are still NP-hard. The results for the Chamberlin-Courant rule are similar.
Computation
Procaccia, Rosenschein and Zohar[4] proved that determining the winner of Monroe's voting rule is NP-hard, even with approval ballots. However, when the number of winners (k) is constant, the problem can be solved in polynomial time.
Betzler, Slinko and Uhlmann[3] investigate the parameterized complexity of winner determination: they prove fixed-parameter tractability for the parameter "number of candidates", but fixed-parameter intractability for "number of winners". For voters with single-peaked preferences, they classical Monroe rule is still NP-hard, but there is a polytime algorithm for its min-max variant.
Skowron, Faliszewski and Slinko[2] provide good approximation algorithms for the satisfaction-based utilitarian version of the Monroe's rule, and inapproximability results for the dissatisfaction-based utilitarian version and the egalitarian versions. The algorithms are applicable even with truncated ballots. Experiments on real-life preference-aggregation data shows that these fast algorithms in many cases find near-perfect solutions.
Generalizations
Lu and Boutilier[5] generalize the rule to budgeted social choice.
See also
- Chamberlin-Courant voting rule - another rule for fully-proportional representation. In that rule, there is no restriction that each candidate should represent exactly n/k voters.[6] By John R. Chamberlin and Paul N. Courant.
References
- ^ Monroe, Burt L. (1995-12-01). "Fully Proportional Representation". American Political Science Review. 89 (4): 925–940. doi:10.2307/2082518. ISSN 1537-5943.
- ^ a b Skowron, Piotr; Faliszewski, Piotr; Slinko, Arkadii (2015-05-01). "Achieving fully proportional representation: Approximability results". Artificial Intelligence. 222: 67–103. doi:10.1016/j.artint.2015.01.003. ISSN 0004-3702.
- ^ a b Betzler, N.; Slinko, A.; Uhlmann, J. (2013-07-22). "On the Computation of Fully Proportional Representation". Journal of Artificial Intelligence Research. 47: 475–519. doi:10.1613/jair.3896. ISSN 1076-9757.
- ^ Procaccia, Ariel D.; Rosenschein, Jeffrey S.; Zohar, Aviv (2008-04-01). "On the complexity of achieving proportional representation". Social Choice and Welfare. 30 (3): 353–362. doi:10.1007/s00355-007-0235-2. ISSN 1432-217X.
- ^ Lu, Tyler; Boutilier, Craig (2011-07-16). "Budgeted social choice: from consensus to personalized decision making". Proceedings of the Twenty-Second international joint conference on Artificial Intelligence - Volume Volume One. IJCAI'11. Barcelona, Catalonia, Spain: AAAI Press: 280–286. doi:10.5555/2283396.2283444. ISBN 978-1-57735-513-7.
{{cite journal}}: Check|doi=value (help) - ^ Chamberlin, John R.; Courant, Paul N. (1983-09). "Representative Deliberations and Representative Decisions: Proportional Representation and the Borda Rule". American Political Science Review. 77 (3): 718–733. doi:10.2307/1957270. ISSN 0003-0554.
{{cite journal}}: Check date values in:|date=(help)