Fully proportional representation

Last updated April 18, 2024

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^[3] 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^[3] 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^[6] presented a polytime 0.63-factor approximation greedy algorithm for the optimal satisfaction of the CC rule.

Skowron, Faliszewski and Slinko^[7] 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.^[3]

Generalizations

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

Related Research Articles

Proportional representation (PR) refers to any type of electoral system under which subgroups of an electorate are reflected proportionately in the elected body. The concept applies mainly to political divisions among voters. The essence of such systems is that all votes cast – or almost all votes cast – contribute to the result and are effectively used to help elect someone – not just a bare plurality or (exclusively) the majority – and that the system produces mixed, balanced representation reflecting how votes are cast.

Score voting or range voting is an electoral system for single-seat elections, in which voters give each candidate a score, the scores are added, and the candidate with the highest total is elected. It has been described by various other names including evaluative voting, utilitarian voting, interval measure voting, point-sum voting, ratings summation, 0-99 voting, and average voting. It is a type of cardinal voting electoral system that aims to approximate the utilitarian social choice rule.

The single transferable vote (STV), sometimes known as proportional ranked choice voting (P-RCV), is a multi-winner electoral system in which each voter casts a single vote in the form of a ranked-choice ballot. Voters have the option to rank candidates, and their vote may be transferred according to alternate preferences if their preferred candidate is eliminated or elected with surplus votes, so that their vote is used to elect someone they prefer over others in the running. STV aims to approach proportional representation based on votes cast in the district where it is used, so that each vote is worth about the same as another. Formally, STV satisfies a fairness criterion known as proportionality for solid coalitions.

Bucklin voting is a class of voting methods that can be used for single-member and multi-member districts. As in highest median rules like the majority judgment, the Bucklin winner will be one of the candidates with the highest median ranking or rating. It is named after its original promoter, the Georgist politician James W. Bucklin of Grand Junction, Colorado, and is also known as the Grand Junction system.

The Borda count electoral system can be combined with an instant-runoff procedure to create hybrid election methods that are called Nanson method and Baldwin method. Both methods are designed to satisfy the Condorcet criterion, and allow for incomplete ballots and equal rankings.

An electoral system or voting system is a set of rules that determine how elections and referendums are conducted and how their results are determined. Electoral systems are used in politics to elect governments, while non-political elections may take place in business, non-profit organisations and informal organisations. These rules govern all aspects of the voting process: when elections occur, who is allowed to vote, who can stand as a candidate, how ballots are marked and cast, how the ballots are counted, how votes translate into the election outcome, limits on campaign spending, and other factors that can affect the result. Political electoral systems are defined by constitutions and electoral laws, are typically conducted by election commissions, and can use multiple types of elections for different offices.

<span class="mw-page-title-main">Ranked voting</span> Family of electoral systems

The term ranked voting, also known as preferential voting or ranked-choice voting, pertains to any voting system where voters indicate a rank to order candidates or options—in a sequence from first, second, third, and onwards—on their ballots. Ranked voting systems vary based on the ballot marking process, how preferences are tabulated and counted, the number of seats available for election, and whether voters are allowed to rank candidates equally.

Proportional approval voting (PAV) is a proportional electoral system for multiwinner elections. It is a multiwinner approval method that extends the highest averages method of apportionment commonly used to calculate apportionments for party-list proportional representation. However, PAV allows voters to support only the candidates they approve of, rather than being forced to approve or reject all candidates on a given party list.

Sequential proportional approval voting (SPAV) or reweighted approval voting (RAV) is an electoral system that extends the concept of approval voting to a multiple winner election. It is a simplified version of proportional approval voting. It is a special case of Thiele's voting rules, proposed by Danish statistician Thorvald N. Thiele in the early 1900s. It was used in Sweden for a short period from 1909-1921, and was replaced by a cruder "party-list" style system as it was easier to calculate.

Computational social choice is a field at the intersection of social choice theory, theoretical computer science, and the analysis of multi-agent systems. It consists of the analysis of problems arising from the aggregation of preferences of a group of agents from a computational perspective. In particular, computational social choice is concerned with the efficient computation of outcomes of voting rules, with the computational complexity of various forms of manipulation, and issues arising from the problem of representing and eliciting preferences in combinatorial settings.

A major branch of social choice theory is devoted to the comparison of electoral systems, otherwise known as social choice functions. Viewed from the perspective of political science, electoral systems are rules for conducting elections and determining winners from the ballots cast. From the perspective of economics, mathematics, and philosophy, a social choice function is a mathematical function that determines how a society should make choices, given a collection of individual preferences.

Combinatorial participatory budgeting,also called indivisible participatory budgeting or budgeted social choice, is a problem in social choice. There are several candidate projects, each of which has a fixed costs. There is a fixed budget, that cannot cover all these projects. Each voter has different preferences regarding these projects. The goal is to find a budget-allocation - a subset of the projects, with total cost at most the budget, that will be funded. Combinatorial participatory budgeting is the most common form of participatory budgeting.

Justified representation (JR) is a criterion of fairness in multiwinner approval voting. It can be seen as an adaptation of the proportional representation criterion to approval voting.

Multiwinner approval voting, also called approval-based committee (ABC) voting, is a multi-winner electoral system that uses approval ballots. Each voter may select ("approve") any number of candidates, and multiple candidates are elected. The number of elected candidates is usually fixed in advance. For example, it can be the number of seats in a country's parliament, or the required number of members in a committee.

Multiwinner voting, also called committee voting or committee elections, is an electoral system in which multiple candidates are elected. The number of elected candidates is usually fixed in advance. For example, it can be the number of seats in a country's parliament, or the required number of members in a committee.

Fractional approval voting is an electoral system using approval ballots, in which the outcome is fractional: for each alternative j there is a fraction p_j between 0 and 1, such that the sum of p_j is 1. It can be seen as a generalization of approval voting: in the latter, one candidate wins and the other candidates lose. The fractions p_j can be interpreted in various ways, depending on the setting. Examples are:

The Method of Equal Shares is a proportional method of counting ballots that applies to participatory budgeting, to committee elections, and to simultaneous public decisions. It can be used when the voters vote via approval ballots, ranked ballots or cardinal ballots. It works by dividing the available budget into equal parts that are assigned to each voter. The method is only allowed to use the budget share of a voter to implement projects that the voter voted for. It then repeatedly finds projects that can be afforded using the budget shares of the supporting voters. In contexts other than participatory budgeting, the method works by equally dividing an abstract budget of "voting power".

Multi-issue voting is a setting in which several issues have to be decided by voting. Multi-issue voting raises several considerations, that are not relevant in single-issue voting.

Participatory budgeting experiments are experiments done in the laboratory and in computerized simulations, in order to check various ethical and practical aspects of participatory budgeting. These experiments aim to decide on two main issues:

Front-end: which ballot type to use as an input? See Participatory budgeting ballot types for common types of ballots.
Back-end: Which rule to use for aggregating the voters' preferences? See combinatorial participatory budgeting for detailed descriptions of various aggregation rules.

Thiele's voting rules are rules for multiwinner voting. They allow voters to vote for individual candidates rather than parties, but still guarantee proportional representation. They were published by Thorvald Thiele in Danish in 1895, and translated to English by Svante Janson in 2016. They were used in Swedish parliamentary elections to distribute seats within parties, and are still used in city council elections.

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. JSTOR 2082518. S2CID 121059560.
↑ Chamberlin, John R.; Courant, Paul N. (1983-09-01). "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. JSTOR 1957270. S2CID 147162169.
1 2 3 4 Betzler, N.; Slinko, A.; Uhlmann, J. (2013-07-22). "On the Computation of Fully Proportional Representation". Journal of Artificial Intelligence Research. 47: 475–519. arXiv: 1402.0580 . 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. S2CID 18126521.
↑ Skowron, Piotr; Yu, Lan; Faliszewski, Piotr; Elkind, Edith (2013). "The Complexity of Fully Proportional Representation for Single-Crossing Electorates". In Vöcking, Berthold (ed.). Algorithmic Game Theory. Lecture Notes in Computer Science. Vol. 8146. Berlin, Heidelberg: Springer. pp. 1–12. arXiv: 1307.1252 . doi:10.1007/978-3-642-41392-6_1. ISBN 978-3-642-41392-6.
1 2 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. ISBN 978-1-57735-513-7.
↑ Skowron, Piotr; Faliszewski, Piotr; Slinko, Arkadii (2015-05-01). "Achieving fully proportional representation: Approximability results". Artificial Intelligence. 222: 67–103. arXiv: 1312.4026 . doi: 10.1016/j.artint.2015.01.003 . ISSN 0004-3702. S2CID 467056.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Monroe, Burt L. (1995-12-01). "Fully Proportional Representation". American Political Science Review. 89 (4): 925–940. doi:10.2307/2082518. ISSN 1537-5943. JSTOR 2082518. S2CID 121059560.

[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. 77 (3): 718–733. doi:10.2307/1957270. ISSN 0003-0554. JSTOR 1957270. S2CID 147162169.

[:0-3] 1 2 3 4 Betzler, N.; Slinko, A.; Uhlmann, J. (2013-07-22). "On the Computation of Fully Proportional Representation". Journal of Artificial Intelligence Research. 47: 475–519. arXiv: 1402.0580 . doi: 10.1613/jair.3896 . ISSN 1076-9757.

[4] 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. S2CID 18126521.

[5] Skowron, Piotr; Yu, Lan; Faliszewski, Piotr; Elkind, Edith (2013). "The Complexity of Fully Proportional Representation for Single-Crossing Electorates". In Vöcking, Berthold (ed.). Algorithmic Game Theory. Lecture Notes in Computer Science. Vol. 8146. Berlin, Heidelberg: Springer. pp. 1–12. arXiv: 1307.1252 . doi:10.1007/978-3-642-41392-6_1. ISBN 978-3-642-41392-6.

[:2-6] 1 2 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. ISBN 978-1-57735-513-7.

[:1-7] Skowron, Piotr; Faliszewski, Piotr; Slinko, Arkadii (2015-05-01). "Achieving fully proportional representation: Approximability results". Artificial Intelligence. 222: 67–103. arXiv: 1312.4026 . doi: 10.1016/j.artint.2015.01.003 . ISSN 0004-3702. S2CID 467056.

[1]

[2]

[3]

[4]

[5]

[6]

[7]