Fully proportional representation explained

Fully proportional representation (FPR) is a property of multiwinner voting systems. It extends the property of proportional representation (PR) by requiring that the representation be based on the entire preferences of the voters, rather than on their first choice. Moreover, the requirement combines PR with the requirement of accountability - each voter knows exactly which elected candidate represents him, and each candidate knows exactly which voters he represents.

The term was coined in 1995 by Burt L. Monroe,^[1] but a similar idea appeared already in 1983 in a paper by John R. Chamberlin and Paul N. Courant.^[2] The two voting rules known to satisfy this property are known - respectively - as Monroe's voting rule and the Chamberlin-Courant (CC) voting rule.

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.

Another shortcoming with existing systems for PR, e.g. party-list systems, is the lack of accountability:^[3] there is no direct connection between voters to elected candidates, as the candidates are elected via their party. Rules such as Single transferable vote and Expanding approvals rule aim to mitigate this problem by allowing people to rank candidates directly; however, it is still hard to tell which candidate exactly represents which voter.

FPR rules aim to amend both these shortcomings simultaneously: they are based on the voters' preferences over all candidates; and they create an explicit connection between the elected candidates and the voters: each voter knows his representatives, and each representative knows which voters he represents.

The rules

Let k be the required number of representatives (committee members), m the number of candidates, and n the number of voters. Each voter submits a ranking of the candidates. Both Monroe's rule and CC rule choose k representatives, and associates each voter to a unique representative (in other words, they compute a partition of the voters among the representatives). The main difference is as follows:

• Monroe's rule requires that each candidate is associated with exactly n/k voters (rounded up or down if it is not an integer).
• CC rule has no such requirement - each candidate can represent a different number of voters (but this should be taken into account later, during the committee operation, e.g. by applying weighted voting).

Both rules aim to maximize a global measure of satisfaction, which is based on individual preferences. The satisfaction of a voter from a given committee is determined by a fixed score function. Two common score functions are:

• Borda count: 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.
• Approval ballots: if a voter is represented by a candidate he approves, then his satisfaction is 1; otherwise, his satisfaction is 0.

Alternative variants of these rules use a dissatisfaction function instead of a satisfaction function. Based on these scoring functions, both rules have several variants:

• The Utilitarian rule aims to find a committee that maximizes the sum of satisfaction-levels of all voters (e.g. with approval ballots: maximize the number of voters represented by a candidate they approve); an alternative variant aims to minimize the sum of dissatisfaction-levels of all voters.
• Egalitarian rules aim to find a committee that maximizes the smallest satisfaction-level of a voter (e.g. with Borda count: find the optimal rank r such that all voters have a representative they rank r or better); an alternative variant aims to minimize the largest of dissatisfaction-levels of all voters.

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 investigate the parameterized complexity of winner determination of the dissatisfaction-based variants: they prove fixed-parameter tractability for the parameter "number of candidates", but fixed-parameter intractability for "number of winners". They study approval, Borda, and unrestricted scoring functions.

Some problems become easier for restricted preference domains:

• For single-peaked preferences, Betzler, Slinko and Uhlmann prove that the classical Monroe rule is still NP-hard, but there is a polytime algorithm for egalitarian Monroe. The CC variants are both polynomial.
• For single-crossing preferences, Skowron, Yu, Failszewski and Elkind^[5] prove that CC rule is polytime, but Monroe remains NP-hard. For single-crossing narcissistic preferences (each candidate is ranked first by at least one voter), there is an efficient algorithm for the egalitarian Monroe rule.

Lu and Boutilier presented a polytime 0.63-factor approximation greedy algorithm for the optimal satisfaction of the CC rule.

Skowron, Faliszewski and Slinko^[6] provide Approximation algorithms and Inapproximability results:

• For utilitarian satisfaction Monroe with Borda scoring, a (0.715-epsilon)-approximation;
• For utilitarian satisfaction Monroe with arbitrary positional scoring, a 0.63-approximation;
• For utilitarian satisfaction CC with Borda scoring, a PTAS.
• No constant-factor approximation exists for dissatisfaction-based utilitarian and egalitarian versions of both Monroe and CC, and for the satisfaction-based egalitarian versions.

The approximation 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.

Note that, once the k representatives are elected, finding the actual representation (which voter is represented by which candidate) can be done in polytime using network flow algorithms.

Generalizations

Lu and Boutilier^[7] generalized the CC rule to budgeted social choice.

References

1. Monroe . Burt L. . 1995-12-01 . Fully Proportional Representation . American Political Science Review . en . 89 . 4 . 925–940 . 10.2307/2082518 . 2082518 . 121059560 . 1537-5943.
2. Chamberlin . John R. . Courant . Paul N. . 1983-09-01 . Representative Deliberations and Representative Decisions: Proportional Representation and the Borda Rule . American Political Science Review . en . 77 . 3 . 718–733 . 10.2307/1957270 . 1957270 . 147162169 . 0003-0554.
3. Betzler . N. . Slinko . A. . Uhlmann . J. . 2013-07-22 . On the Computation of Fully Proportional Representation . Journal of Artificial Intelligence Research . en . 47 . 475–519 . 10.1613/jair.3896 . 1076-9757. free . 1402.0580 .
4. Procaccia . Ariel D. . Rosenschein . Jeffrey S. . Zohar . Aviv . 2008-04-01 . On the complexity of achieving proportional representation . Social Choice and Welfare . en . 30 . 3 . 353–362 . 10.1007/s00355-007-0235-2 . 18126521 . 1432-217X.
5. Book: Skowron . Piotr . Yu . Lan . Faliszewski . Piotr . Elkind . Edith . Algorithmic Game Theory . The Complexity of Fully Proportional Representation for Single-Crossing Electorates . 2013 . Vöcking . Berthold . Lecture Notes in Computer Science . 8146 . en . Berlin, Heidelberg . Springer . 1–12 . 10.1007/978-3-642-41392-6_1 . 1307.1252 . 978-3-642-41392-6.
6. Skowron . Piotr . Faliszewski . Piotr . Slinko . Arkadii . 2015-05-01 . Achieving fully proportional representation: Approximability results . Artificial Intelligence . 222 . 67–103 . 10.1016/j.artint.2015.01.003 . 467056 . 0004-3702. free . 1312.4026 .
7. 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 . 978-1-57735-513-7.