Source-linked AI summary
Computational Aspects of Multi-Winner Approval Voting
Haris Aziz, Serge Gaspers, Joachim Gudmundsson, Simon Mackenzie, Nicholas Mattei, Toby Walsh
TL;DR
The paper asks how computationally tractable multi-winner approval rules are, both for determining winners and for strategic voting. It studies SAV, PAV, and RAV, proving PAV winner determination NP-hard and finding widespread NP-hardness of best-response computation. These results distinguish RAV by combining easy winner determination with hard manipulation.
Problem
The paper addresses limited computational understanding of multi-winner approval rules, including winner determination and beneficial preference misreports.
Method
The paper analyzes winner determination and strategic voting for SAV, PAV, and RAV under approval ballots and dichotomous preferences.
Results
PAV winner determination is NP-hard, and computing a best response is NP-hard in many settings for SAV, PAV, and RAV.
Takeaways & Limitations
RAV is supported over PAV and SAV because it has computationally easy winner determination while manipulation remains hard.
Takeaways & Limitations
Some manipulation hardness proofs require both the number of agents and the winning-set size to grow, leaving bounded cases open.
Abstract
from arXiv · showhide
We study computational aspects of three prominent voting rules that use approval ballots to elect multiple winners. These rules are satisfaction approval voting, proportional approval voting, and reweighted approval voting. We first show that computing the winner for proportional approval voting is NP-hard, closing a long standing open problem. As none of the rules are strategyproof, even for dichotomous preferences, we study various strategic aspects of the rules. In particular, we examine the computational complexity of computing a best response for both a single agent and a group of agents. In many settings, we show that it is NP-hard for an agent or agents to compute how best to vote given a fixed set of approval ballots from the other agents.
Introduction
The paper motivates multi-winner approval rules as responses to fairness and proportionality concerns inadequately addressed by ordinary Approval Voting. It studies the computational complexity of SAV, PAV, and RAV, including winner determination and strategic manipulation.
- Introduction: Multi-winner approval voting is used for committees and other settings requiring a fixed number k of winners.Applications include parliamentary elections, faculty hiring, and movie recommendation systems.
- Introduction: Approval ballots let agents approve multiple candidates, but Approval Voting is less clearly suitable for multiple winners.The paper specifically notes that AV does not address egalitarian concerns such as proportional representation.
- Introduction: SAV, PAV, and RAV were developed to address fairness concerns and pursue more egalitarian outcomes than AV.PAV reduces an agent’s approval weight as approved candidates are elected, while RAV reweights agents over sequential rounds.
- Introduction: The paper provides a detailed computational study of SAV, PAV, and RAV, beginning with the complexity of computing winners.Winner determination is necessary if a voting rule is to be used in practice.
- Introduction: Winner determination for PAV is NP-hard, closing a longstanding open problem.The hardness result applies to approval-based multi-winner rules with diminishing scores as more approved candidates are elected.
- Introduction: For strategic voting, the paper shows that these rules are not strategyproof and that best-response computation is NP-hard in many settings.The results support RAV over PAV or SAV because RAV has easy winner determination but hard manipulation.
Related Work
Related work places multi-winner approval voting within computational social choice and proportional representation. Earlier studies considered several voting and manipulation problems, while related approval-based rules include minimax approval voting.
- Related Work: Computational social choice studies whether agents can benefit from misreporting preferences through the lens of computational complexity.The relevant question is whether finding a beneficial misreport is computationally hard.
- Related Work: Prior work on multi-winner elections has been limited, with exceptions covering approval voting, k-approval, cumulative voting, and proportional schemes.For approval voting, earlier results include polynomial-time manipulation with general utilities and candidate-control problems.
- Related Work: The Handbook of Approval Voting surveys SAV, PAV, RAV, and minimax approval voting among prominent multi-winner approval rules.Minimax approval voting selects k candidates minimizing the maximum Hamming distance from submitted ballots.
- Related Work: Winner computation for minimax approval voting is NP-hard, and its strategic and approximation questions are studied as the closest string problem.Each approval ballot and winning set can be represented as a binary vector.
- Related Work: Multi-winner approval voting is closely related to proportional representation and committee selection, including applications requiring diversity among selected objects.Committee-selection ideas have been used in computational social choice to ensure diversity.
Formal Background
The paper formalizes approval-based multi-winner rules over agents, candidates, approval ballots, and committees of fixed size. It then specifies AV, SAV, PAV, and RAV, together with the tie-breaking assumption used in complexity analysis.
- Formal Background: A social-choice instance consists of agents, candidates, approval ballots, and a committee size k, with a rule returning k winners.Each approval ballot represents the candidates an agent approves.
- Approval Voting (AV ): AV selects a size-k committee maximizing the total number of approvals received by its candidates.Its score sums each agent’s number of approved elected candidates.
- Satisfaction Approval Voting (SAV ): SAV maximizes the sum of agents’ satisfaction, where each agent’s satisfaction is the fraction of approved candidates elected.SAV was proposed to represent more diverse interests than AV.
- Proportional Approval Voting (PAV ): PAV assigns an agent the harmonic satisfaction score 1+1/2+1/3+...+1/j when j approved candidates are elected.This scoring captures diminishing returns as an individual agent becomes more satisfied.
- Proportional Approval Voting (PAV ): PAV chooses a size-k committee maximizing the total of these harmonic satisfaction scores.The rule aggregates each agent’s satisfaction across the elected committee.
- Reweighted Approval Voting (RAV ): RAV selects candidates sequentially across k rounds, reweighting each agent’s approvals according to previously elected approved candidates.It is also called sequential proportional AV and was used briefly in Sweden.
- Reweighted Approval Voting (RAV ): Complexity analyses use a linear candidate order as the worst-case tie-breaking rule, favoring the preferred candidate.Many proofs are independent of tie-breaking, so their hardness results transfer to arbitrary tie-breaking rules.
Winner Determination
Winner determination is polynomial-time for SAV, RAV, and AV but NP-complete for PAV, even when each agent approves only two candidates. The PAV hardness proof reduces Independent Set to committee selection and also establishes W[1]-hardness.
- Winner Determination: Winner Determination asks for the size-k winning committee produced from candidates, approval ballots, and an approval-based voting rule.The problem is defined for any rule R over an approval profile.
- Winner Determination: Winner determination is polynomial-time computable for SAV, RAV, and AV, while PAV winner determination is the unresolved case addressed here.The paper separately studies the computational difficulty of manipulating RAV.
- Winner Determination: WD for PAV is NP-complete even if each agent approves of two candidates.Membership in NP follows because a candidate committee with a specified PAV score can serve as a witness.
- Winner Determination: The hardness proof reduces Independent Set to PAV by making a winning committee of size t correspond to an independent set of size t.The construction uses vertex candidates, dummy candidates, edge agents, and vertex-associated agents.
- Winner Determination: A committee of size k=t reaches score deg(G)·t exactly when its selected vertex candidates form an independent set.Each added candidate contributes at most deg(G), and achieving that maximum excludes adjacent selected vertices.
- Winner Determination: WD for PAV is W[1]-hard, and unless FPT=W[1] it cannot run in time f(k)·m^O(1), even with two approvals per agent.Thus a running-time factor m^k appears unavoidable for relatively small committees.
Strategic Voting
SAV, PAV, and RAV are manipulable even with dichotomous preferences, and computing beneficial strategic votes is often computationally hard. The section establishes rule-specific complexity results for individual and coalition manipulation.
- SAV, PAV, and RAV are not strategyproof with dichotomous preferences.
- Winner Manipulation and Winning Set Manipulation formalize whether additional approval ballots can make a preferred candidate or set win.
- Satisfaction Approval Voting (SAV): SAV permits polynomial-time Winner Manipulation, but coalition votes may need to differ, and Winning Set Manipulation is NP-hard.
- Satisfaction Approval Voting (SAV): For SAV, computing a utility-maximizing vote is NP-hard, while two-agent Winning Set Manipulation is polynomial.
- Proportional Approval Voting (PAV): For PAV, Winner Manipulation and Winning Set Manipulation are coNP-hard even without manipulators, and utility-maximizing voting is NP-hard for one manipulator.
- Reweighted Approval Voting (RAV): Under RAV, a manipulator may need to approve extra candidates for one target, but never a superset when seeking an exact favored set; Winner Manipulation is NP-hard.
- Reweighted Approval Voting (RAV): The RAV hardness proof reduces 3SAT to deciding whether a preferred candidate can enter the winning set.
Conclusions
The paper closes PAV winner-determination complexity and analyzes best-response computation across approval-based multi-winner rules. It finds NP-hardness in many strategic-voting settings and identifies further axiomatic and empirical analysis as an open direction.
- The study closes the computational-complexity question for PAV winner determination and examines best-response computation for approval voting rules.
- In many settings, computing how one or more agents should vote given other approval ballots is NP-hard.
- Further axiomatic and empirical analyses of PAV, RAV, and SAV could clarify their relative merits.