View source for Proportional approval voting

{{Short description|Multiple-winner electoral system}}
{{About|2=an overview of proportional variants of approval voting|3=multiwinner approval voting}}{{Distinguish|sequential proportional approval voting|text=[[sequential proportional approval voting]], an approximation algorithm for proportional approval voting}}{{Electoral systems}}

'''Proportional approval voting''' ('''PAV''') is a [[proportional representation|proportional]] [[electoral system]] for [[multiwinner elections]]. It is a [[Multiwinner approval voting|multiwinner approval method]] that extends the [[D'Hondt method]] of [[Apportionment (politics)|apportionment]] commonly used to calculate apportionments for [[party-list proportional representation]].<ref name="dhondt">{{cite journal |last1=Brill |first1=Markus |last2=Laslier |first2=Jean-François |last3=Skowron |first3=Piotr |year=2018 |title=Multiwinner Approval Rules as Apportionment Methods |journal=Journal of Theoretical Politics |volume=30 |issue=3 |pages=358–382 |arxiv=1611.08691 |doi=10.1177/0951629818775518 |s2cid=10535322}}</ref> 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 [[Electoral list|party list]].<ref name="pavaxioms">{{cite journal |last1=Lackner |first1=Martin |last2=Skowron |first2=Piotr |year=2021 |title=Consistent approval-based multi-winner rules |url=https://www.sciencedirect.com/science/article/abs/pii/S0022053120301666 |journal=Journal of Economic Theory |volume=192 |page=105173 |arxiv=1704.02453 |doi=10.1016/j.jet.2020.105173 |s2cid=232116881}}</ref>

In PAV, voters cast [[approval ballot]]s marking all candidates they approve of; each voter's ballot is then treated as if all candidates on the ballot were on their own "party list." Seats are then [[Apportionment (politics)|apportioned]] between candidates in a way that ensures all coalitions are represented proportionally.

==History==
PAV is a special case of [[Thiele's voting rules|Thiele's voting rule]], proposed by [[Thorvald N. Thiele]].<ref>{{cite journal|last1=Thiele|first1=Thorvald N.|title=Om Flerfoldsvalg|journal=Oversigt over Det Kongelige Danske Videnskabernes Selskabs Forhandlinger|date=1895|pages=415–441}}</ref><ref name="jansonsurvey">{{cite arXiv|last1=Janson|first1=Svante|title=Phragmén's and Thiele's election methods|date=2016|eprint = 1611.08826| class = math.HO}}</ref> It was used in combination with [[ranked voting]] in the Swedish elections from 1909 to 1921 for distributing seats within parties and in local elections.<ref name="jansonsurvey"/> PAV was rediscovered by Forest Simmons in 2001,<ref name="Kilgour2010" /> who gave it the name "proportional approval voting."

==Method==
{{See also|Highest averages method}}
Like its close cousin, [[satisfaction approval voting]], PAV can be thought of as selecting a committee by testing all possible committees, then choosing the committee with the most votes. In satisfaction approval voting, each voter's ballot is split equally between all <math>r</math> candidates they approve of, giving each one <math>1/r</math> votes. If voters are perfectly strategic, and only support as many candidates as their party is entitled to, SAV creates a proportional result. 

PAV makes one modification to remove this need for strategy: it only splits a voter's ballot ''after'' they have elected a candidate. As a result, voters can freely approve of losing candidates without diluting their ballot. Voters contribute a whole vote to the first candidate they support who is elected; half a vote to the second candidate; and so on. 

Thus, of a ballot approves of <math>r</math> candidates who are elected, that ballot contributes the <math>r</math>-th [[harmonic number]] to that committee's vote total. In other words:<ref name="Kilgour2010">{{cite book |last=Kilgour |first=D. Marc |editor1=Jean-François Laslier |editor2=M. Remzi Sanver  |title=Handbook on Approval Voting |chapter-url=https://books.google.com/books?id=mQBEAAAAQBAJ&pg=PA114 |date=2010 |publisher=Springer  |isbn=978-3-642-02839-7 |pages=105–124 |chapter=Approval Balloting for Multi-winner Elections}}</ref><ref name="justified-representation" />
: <math>\mathrm{H}(r) = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{r}</math>
The score for a given committee is calculated as the sum of the scores garnered from all the voters. We then choose the committee with the highest score. 

Formally, assume we have a set of candidates <math>C = \{c_1, c_2, \ldots, c_m\}</math>, a set of voters <math>N = \{1, 2, \ldots, n\}</math>, and a committee size <math>k</math>. Let <math>A_i</math> denote the set of candidates approved by voter <math>i \in N</math>. The PAV score of a committee <math>W \subseteq C</math> with size <math>|W| = k</math> is defined as <math>\textstyle \mathrm{sc}_{\mathrm{PAV}}(W) = \sum_{i=1}^{n}\mathrm{H}(|A_i \cap W|)</math>. PAV selects the committee <math>W</math> with the maximal score.

=== Example 1 ===

Assume 2 seats to be filled, and there are four candidates: Andrea (A), Brad (B), Carter (C), and Delilah (D), and 30 voters. The ballots are:

* 5 voters voted for A and B
* 17 voters voted for A and C
* 8 voters voted for D

There are 6 possible results: AB, AC, AD, BC, BD, and CD.

{| class="wikitable"
!  !! AB !! AC !! AD !! BC !! BD !! CD
|-
| score from the 5 voters voting for AB  || <math> 5\cdot \left(1 + \tfrac{1}{2}\right) = 7.5 </math>|| <math> 5\cdot 1 = 5 </math> || <math> 5\cdot 1 = 5 </math> || <math> 5\cdot 1 = 5 </math> || <math> 5\cdot 1 = 5 </math> || <math> 5\cdot 0 = 0 </math>
|-
| score from the 17 voters voting for AC || <math> 17\cdot 1 = 17 </math> || <math> 17\cdot \left(1 + \tfrac{1}{2}\right) = 25.5 </math>|| <math> 17\cdot 1 = 17 </math> || <math> 17\cdot 1 = 17 </math> ||  <math> 17\cdot 0 = 0 </math> || <math> 17\cdot 1 = 17 </math>
|-
| score from the 8 voters voting for D   || <math> 8\cdot 0 = 0 </math> || <math> 8\cdot 0 = 0 </math>  || <math> 8\cdot 1 = 8 </math> ||  <math> 8\cdot 0 = 0 </math> || <math> 8\cdot 1 = 8 </math> || <math> 8\cdot 1 = 8 </math>
|-
| Total score                            || 24.5 || '''30.5'''  || 30 || 22 || 13 || 25
|}

Andrea and Carter are elected.

Note that Simple Approval shows that Andrea has 22 votes, Carter has 17 votes, Delilah has 8 votes and Brad has 5 votes.  In this case, the PAV selection of Andrea and Carter is coincident with the Simple Approval sequence.  However, if the above votes are changed slightly so that A and C receive 16 votes  and D receives 9 votes, then Andrea and Delilah are elected since the A and C score is now 29 while the A and D score remains at 30.  Also, the sequence created by using Simple Approval remains unchanged.  This shows that PAV can give results that are incompatible with the method which simply follows the  sequence implied by Simple Approval.

=== Example 2 ===

Assume there are 10 seats to be selected, and there are three groups of candidates: <span style="color:red">red</span>, <span style="color:blue">blue</span>, and <span style="color:#228B22">green</span> candidates. There are 100 voters:
* <span style="color:blue">60 voters</span> voted for all <span style="color:blue">blue</span> candidates,
* <span style="color:red">30 voters</span> voted for all <span style="color:red">red</span> candidates,
* <span style="color:#228B22">10 voters</span> voted for all <span style="color:#228B22">green</span> candidates.
In this case PAV would select <span style="color:blue">6 blue</span>, <span style="color:red">3 red</span>, and <span style="color:#228B22">1 green</span> candidate. The score of such a committee would be<math display="block"> 60 \cdot \mathrm{H}(6) + 30 \cdot \mathrm{H}(3) + 10 \cdot \mathrm{H}(1) = 60 \cdot \left(1 + \tfrac{1}{2} + \ldots + \tfrac{1}{6} \right) + 30 \cdot \left(1 + \tfrac{1}{2} + \tfrac{1}{3} \right) + 10 \cdot 1 = 147 + 55 + 10 = 212 \text{.} </math>All other committees receive a lower score. For example, the score of a committee that consists of only blue candidates would be 
: <math> 60 \cdot \mathrm{H}(10) + 30 \cdot \mathrm{H}(0) + 10 \cdot \mathrm{H}(0) = 60 \cdot \left(1 + \tfrac{1}{2} + \ldots + \tfrac{1}{10} \right) \approx 175.73  \text{.} </math>

In this example, the outcome of PAV is [[proportional representation|proportional]]: the number of candidates selected from each group is proportional to the number of voters voting for the group. This is not coincidence: If the candidates form disjoint groups, as in the above example (the groups can be viewed as political parties), and each voter votes exclusively for all of the candidates within a single group, then PAV will act in the same way as the [[D'Hondt method]] of [[party-list proportional representation]].<ref name="dhondt" />

== Properties ==

This section describes axiomatic properties of Proportional Approval Voting.

=== Committees of size one ===
In an election with only one winner, PAV operates in exactly the same way as [[approval voting]]. That is, it selects the committee consisting of the candidate who is approved by the most voters.

=== Proportionality ===
Most systems of [[proportional representation]] use [[Party-list system|party lists]]. PAV was designed to have both proportional representation and personal votes (voters vote for candidates, not for a party list). It deserves to be called a "proportional" system because if votes turn out to follow a partisan scheme (each voter votes for all candidates from a party and no other) then the system elects a number of candidates in each party that is proportional to the number of voters who chose this party (see [[#Example 2|Example 2]]).<ref name="dhondt"/> Further, under mild assumptions (symmetry, continuity and [[Pareto efficiency]]), PAV is the only extension of the [[D'Hondt method]] that allows personal votes and satisfies the [[consistency criterion]].<ref name="pavaxioms"/>

Even if the voters do not follow the partisan scheme, the rule provides proportionality guarantees. For example, PAV satisfies the strong fairness property called [[Extended Justified representation|extended justified representation]],<ref name="justified-representation">{{Cite journal|last1=Aziz|first1=Haris|last2=Brill|first2=Markus|last3=Conitzer|first3=Vincent|last4=Elkind|first4=Edith|last5=Freeman|first5=Rupert|last6=Walsh|first6=Toby|date=2017|title=Justified representation in approval-based committee voting|url=https://ideas.repec.org/a/spr/sochwe/v48y2017i2d10.1007_s00355-016-1019-3.html|journal=Social Choice and Welfare|language=en|volume=48|issue=2|pages=461–485|doi=10.1007/s00355-016-1019-3|s2cid=8564247|arxiv=1407.8269}}</ref> as well as the related property [[proportional justified representation]].<ref>{{Cite journal |last1=Sánchez-Fernández |first1=Luis |last2=Elkind |first2=Edith |last3=Lackner |first3=Martin |last4=Fernández |first4=Norberto |last5=Fisteus |first5=Jesús |last6=Val |first6=Pablo Basanta |last7=Skowron |first7=Piotr |title=Proportional Justified Representation |journal=Proceedings of the AAAI Conference on Artificial Intelligence |date=2017-02-10 |url=https://ojs.aaai.org/index.php/AAAI/article/view/10611 |language=en |volume=31 |issue=1 |doi=10.1609/aaai.v31i1.10611 |s2cid=17538641 |issn=2374-3468|doi-access=free |hdl=10016/26166 |hdl-access=free }}</ref> It also has optimal proportionality degree.<ref>{{Cite journal |last1=Aziz |first1=Haris |last2=Elkind |first2=Edith |last3=Huang |first3=Shenwei |last4=Lackner |first4=Martin |last5=Sánchez Fernández |first5=Luis |last6=Skowron |first6=Piotr |title=On the Complexity of Extended and Proportional Justified Representation |journal=Proceedings of the AAAI Conference on Artificial Intelligence |date=2018 |url=https://ojs.aaai.org/index.php/AAAI/article/view/11478 |volume=32 |issue=1 |language=en |pages=902–909|doi=10.1609/aaai.v32i1.11478 |s2cid=19124729 |doi-access=free }}</ref><ref>{{Cite book |last1=Skowron |first1=Piotr |title=Proceedings of the 22nd ACM Conference on Economics and Computation |chapter=Proportionality Degree of Multiwinner Rules |date=2021 |series=EC-21 |language=en |arxiv=1810.08799 |doi=10.1145/3465456.3467641 |pages=820–840|isbn=9781450385541 |s2cid=53046800 }}</ref> All these properties guarantee that any group of voters with cohesive (similar) preferences will be represented by a number of candidates that is at least proportional to the size of the group. PAV is the only method satisfying such properties among all PAV-like optimization methods (that may use numbers other than harmonic numbers in their definition).<ref name="justified-representation" />

The committees returned by PAV might not be in the [[Core (game theory)|core]].{{Technical inline|date=May 2024}}<ref name="justified-representation"/><ref name="welfarismLimits"/> However, it guarantees 2-approximation of the core,{{Technical inline|date=May 2024}} which is the optimal approximation ratio that can be achieved by a rule satisfying the [[Pigou–Dalton principle]] of transfers.<ref name="welfarismLimits" /> Furthermore, PAV satisfies the property of the core if there are sufficiently many similar candidates running in an election.<ref name="approval-apportionment">{{Cite journal|last1=Brill | first1= Markus | last2 =Gölz | first2 = Paul | last3 = Peters | first3 = Dominik | last4 = Schmidt-Kraepelin | first4 = Ulrike | last5 = Wilker | first5 = Kai | date= 2019 | title= Approval-Based Apportionment | journal= Proceedings of the AAAI Conference on Artificial Intelligence | volume= 34 | issue= 2 |pages=1854–1861|doi=10.1609/aaai.v34i02.5553 | arxiv=1911.08365| s2cid= 208158445 }}</ref>

PAV fails priceability (that is, the choice of PAV cannot be always explained via a process where the voters are endowed with a fixed amount of virtual money, and spend this spend money on buying candidates they like) and fails laminar proportionality.<ref name="welfarismLimits"/> Two alternative rules that satisfy priceability and laminar proportionality, and that have comparably good proportionality-related properties to PAV are the [[method of equal shares]] and [[Phragmen's voting rules|Phragmén's sequential rules]].<ref name="abcsurvey"/> These two alternative methods are also computable in [[polynomial time]], yet they fail [[Pareto efficiency]].

=== Other properties ===

Apart from properties pertaining to proportionality, PAV '''satisfies''' the following axioms:
* [[Pareto efficiency]]
* [[Consistency criterion|Consistency]]
* Support monotonicity (if the support of a winning candidate increases, i.e., more voters vote for this candidate, then this candidate remains winning)<ref>{{Cite journal|last1 = Sánchez Fernández | first1 = Luis | last2 = Fisteus | first2 = Jesús | title = Monotonicity axioms in approval-based multi-winner voting rules |date=2019 |arxiv=1710.04246 |language=en|pages=485–493|url=https://www.ifaamas.org/Proceedings/aamas2019/pdfs/p485.pdf}}</ref>
* [[Pigou–Dalton principle]]<ref name="welfarismLimits">{{Cite book|last1=Peters|first1=Dominik|last2=Skowron|first2=Piotr|title=Proceedings of the 21st ACM Conference on Economics and Computation |chapter=Proportionality and the Limits of Welfarism |series=EC'20|date=2020 |pages=793–794|doi=10.1145/3391403.3399465|arxiv=1911.11747|isbn=9781450379755|s2cid=208291203}}</ref>

PAV '''fails''' the following properties:
* [[House monotonicity]].<ref name="abcsurvey">{{cite book | arxiv = 2007.01795| last1 = Lackner| first1 = Martin| last2 = Skowron| first2 = Piotr| title = Multi-Winner Voting with Approval Preferences| chapter = | series = SpringerBriefs in Intelligent Systems| year = 2023| doi = 10.1007/978-3-031-09016-5| isbn = 978-3-031-09015-8| s2cid = 244921148}}</ref> Two alternative methods that satisfy house monotonicity and that have comparably good proportionality-related properties to PAV are [[Sequential proportional approval voting|Sequential Proportional Approval Voting]] and [[Phragmen's voting rules|Phragmén's Sequential Rules]].<ref name="abcsurvey"/> These two alternative methods are also computable in [[polynomial time]], but they fail [[Pareto efficiency]], [[Consistency criterion|Consistency]], and the [[Pigou–Dalton principle]].<ref name="abcsurvey"/>

== Computation ==
[[File:ILP-PAV.jpg|thumb|upright=1.8|An [[integer linear programming]] formulation for computing winning committees according to PAV. The variable <math>y_c</math> indicates whether candidate <math>c</math> is selected or not. The variable <math>x_{i, \ell}</math> indicates whether voter <math>i</math> approves at least <math>\ell</math> selected candidates.<ref name="abcsurvey"/><ref name=":0">{{cite journal |last1=Peters |first1=Dominik |year=2018 |title=Single-Peakedness and Total Unimodularity: New Polynomial-Time Algorithms for Multi-Winner Elections |pages=1169–1176 |arxiv=1609.03537}}</ref>]]
PAV solutions and their quality can be verified in [[polynomial-time]],<ref name="AzizGaspers2014">{{cite book|last1=Aziz|first1=Haris |first2=Serge| last2=Gaspers | first3 = Joachim | last3 = Gudmundsson | first4 = Simon | last4= Mackenzie | first5 = Nicholas | last5 = Mattei | first6= Toby | last6 = Walsh|title=Computational Aspects of Multi-Winner Approval Voting |isbn=978-1-4503-3413-6|pages=107–115 |year=2015|arxiv=1407.3247}}</ref><ref name="pav-approx"/> making transparency easy. However, the [[worst-case]] time complexity is [[NP-completeness|NP-complete]], meaning that for some elections it can be difficult or impossible to find an exact solution that guarantees all the theoretical properties of PAV. 

In practice, the outcome of PAV can be computed exactly for medium-sized committees (<50 candidates) using [[integer programming]] solvers (such as those provided in the [https://github.com/martinlackner/abcvoting ''abcvoting''] Python package). Finding an exact solution has time complexity <math>O(n m^k)</math> with {{Math|''k''}} seats and {{Math|''n''}} voters.

From the perspective of [[parameterized complexity]], the problem of computing PAV is theoretically difficult outside of a few exceptional easy cases.<ref name="AzizGaspers2014" /><ref>{{cite journal |last1=Bredereck |first1=Robert |last2=Faliszewski |first2=Piotr |last3=Kaczmarczyk |first3=Andrzej |last4=Knop |first4=Dusan |last5=Niedermeier |first5=Rolf |author5-link=Rolf Niedermeier |year=2020 |title=Parameterized Algorithms for Finding a Collective Set of Items |journal=Proceedings of the AAAI Conference on Artificial Intelligence |volume=34 |issue=2 |pages=1838–1845 |doi=10.1609/aaai.v34i02.5551 |s2cid=213963505 |doi-access=free}}</ref><ref>{{cite journal |last1=Godziszewski |first1=Michal |last2=Batko |first2=Pawel |last3=Skowron |first3=Piotr |last4=Faliszewski |first4=Piotr |year=2021 |title=An Analysis of Approval-Based Committee Rules for 2D-Euclidean Elections |url=https://ojs.aaai.org/index.php/AAAI/article/view/16686 |journal=Proceedings of the AAAI Conference on Artificial Intelligence |volume=35 |issue=6 |pages=5448–5455 |doi=10.1609/aaai.v35i6.16686 |s2cid=235306592 |doi-access=free}}</ref> Luckily, such cases are often good approximations of real elections, allowing them to be used as heuristics that dramatically reduce the computational effort of finding a correct solution. For example, exact election results can be solved in polynomial time in the case where voters and candidates lie along a single-dimensional political spectrum,<ref name=":0" /> and in linear time when voters are strong partisans (i.e. vote for party lists instead of candidates). 

=== Deterministic approximations ===
[[Sequential proportional approval voting]] is a greedy approximation for PAV with a worst-case approximation ratio of <math>1 - 1/e \approx 0.63</math>, so the PAV score of the resulting committee is at least 63% of the optimal.<ref name="pav-approx">{{cite journal|last1=Skowron | first1= Piotr| last2= Faliszewski |first2 = Piotr | last3 = Lang | first3 = Jérôme  |journal=Artificial Intelligence|volume=241|pages=191–216|title=Finding a collective set of items: From proportional multirepresentation to group recommendation|year=2016|arxiv=1402.3044|doi=10.1016/j.artint.2016.09.003| s2cid= 11313941}}</ref> This method can be computed in polynomial time, and the election outcome could potentially be determined by hand. A different approach including [[randomized rounding|derandomized rounding]] (with the [[method of conditional probabilities]]) gives a worst-case approximation ratio of 0.7965;<ref name="pav-approx2">{{cite book|last1=Dudycz |first1= Szymon | last2=Manurangsi | first2=Pasin | last3=Marcinkowski | first3=Jan |last4=Sornat |first4=Krzysztof |title= Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence |chapter= Tight Approximation for Proportional Approval Voting |series=IJCAI-20|pages=276–282|year=2020|doi=10.24963/ijcai.2020/39|isbn= 978-0-9992411-6-5 |s2cid= 220484671 |doi-access=free }}</ref> under standard assumptions in complexity theory, this is the best approximation ratio that can be achieved for PAV in polynomial time.<ref name="pav-approx2" /> The problem of approximating PAV can be also formulated as a minimization problem (instead of maximizing <math>\textstyle \mathrm{sc}_{\mathrm{PAV}}(W)</math> we want to minimize <math>\textstyle \sum_{i \in N }\mathrm{H}(k) - \mathrm{sc}_{\mathrm{PAV}}(W)</math>), in which case the best known approximation ratio is 2.36.<ref name="pav-approx3">{{cite book|last1=Byrka |first1=Jaroslaw |last2=Skowron | first2=Piotr | last3=Sornat |first3=Krzysztof |title=Proportional Approval Voting, Harmonic k-median, and Negative Association |date=2017 |volume=107 |pages=26:1–26:14 |doi=10.4230/LIPIcs.ICALP.2018.26|doi-access=free | arxiv=1704.02183|isbn=9783959770767 |s2cid=3839722 }}</ref>

== Further reading ==
* {{cite book | arxiv = 2007.01795| last1 = Lackner| first1 = Martin| last2 = Skowron| first2 = Piotr| title = Multi-Winner Voting with Approval Preferences| chapter = | series = SpringerBriefs in Intelligent Systems| year = 2023| doi = 10.1007/978-3-031-09016-5| isbn = 978-3-031-09015-8| s2cid = 244921148}}
* {{Cite book|last=Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, Nimrod Talmon|chapter-url=https://books.google.com/books?id=0qY8DwAAQBAJ&dq=multiwinner++voting+a+new+challenge&pg=PA27|title=Trends in Computational Social Choice|date=2017-10-26|publisher=AI Access|isbn=978-1-326-91209-3|editor-last=Endriss|editor-first=Ulle|language=en|chapter=Multiwinner Voting: A New Challenge for Social Choice Theory}}

== See also ==
* [[Method of equal shares]]
* [[D'Hondt method]]
* [[Sequential proportional approval voting]]
* [[Phragmen's voting rules]]

==References==
{{reflist}}

== External links ==

* [https://pref.tools/abcvoting/ Online tool for computing PAV and other approval-based multi-winner methods]
* [https://github.com/martinlackner/abcvoting Python package abcvoting containing an implementation of PAV] ([https://pypi.org/project/abcvoting/ pypi])
{{voting systems}}

[[Category:Multi-winner electoral systems]]
[[Category:Proportional representation electoral systems]]
[[Category:Approval voting]]