Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers
From MaRDI portal
(Redirected from Publication:2317862)
Abstract: We study the computational complexity of committee selection problem for several approval-based voting rules in the presence of outliers. Our first result shows that outlier consideration makes committee selection problem intractable for approval, net approval, and minisum approval voting rules. We then study parameterized complexity of this problem with five natural parameters, namely the target score, the size of the committee (and its dual parameter, the number of candidates outside the committee), the number of outliers (and its dual parameter, the number of non-outliers). For net approval and minisum approval voting rules, we provide a dichotomous result, resolving the parameterized complexity of this problem for all subsets of five natural parameters considered (by showing either FPT or W[1]-hardness for all subsets of parameters). For the approval voting rule, we resolve the parameterized complexity of this problem for all subsets of parameters except one. We also study approximation algorithms for this problem. We show that there does not exist any alpha(.) factor approximation algorithm for approval and net approval voting rules, for any computable function alpha(.), unless P=NP. For the minisum voting rule, we provide a pseudopolynomial (1+eps) factor approximation algorithm.
Recommendations
- Does choosing committees from approval balloting fulfill the electorate's will?
- Mathematical programming formulations for the efficient solution of the \(k\)-sum approval voting problem
- Robustness of approval-based multiwinner voting rules
- Multiwinner rules with variable number of winners
- Approximation and parameterized complexity of minimax approval voting
Cites work
- scientific article; zbMATH DE number 1288298 (Why is no real title available?)
- scientific article; zbMATH DE number 512804 (Why is no real title available?)
- scientific article; zbMATH DE number 1507224 (Why is no real title available?)
- scientific article; zbMATH DE number 5240213 (Why is no real title available?)
- A Consistent Extension of Condorcet’s Election Principle
- Approval balloting for multi-winner elections
- Approximation and parameterized complexity of minimax approval voting
- Axioms for approval voting: Direct proof
- Book review of: Jean-François Laslier and M. Remzi Sanver (eds.), Handbook on approval voting
- Complexity of manipulation with partial information in voting
- Complexity of strategic behavior in multi-winner elections
- Computational Aspects of Approval Voting
- Consistent approval-based multi-winner rules
- Dogson's rule and Yong's rule
- Elections with few voters: candidate control can be easy
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Fixed-parameter algorithms for CLOSEST STRING and related problems
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Frugal bribery in voting
- Fundamentals of parameterized complexity
- Handbook of Computational Social Choice
- How hard is it to control an election?
- Justified representation in approval-based committee voting
- Kernelization complexity of possible winner and coalitional manipulation problems in voting
- Local distance constrained bribery in voting
- Manipulative elicitation -- a new attack on elections with incomplete preferences
- On approximating string selection problems with outliers
- On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard
- On the complexity of \(k\)-SAT
- On the complexity of achieving proportional representation
- PTAS for minimax approval voting
- Parameterized algorithms
- Parameterized complexity dichotomy for \textsc{Steiner Multicut}
- Parameterized lower bounds and dichotomy results for the NP-completeness of \(H\)-free edge modification problems
- Parliamentary voting procedures: agenda control, manipulation, and uncertainty
- Prices matter for the parameterized complexity of shift bribery
- Rationalizations of Voting Rules
- Stable marriage with covering constraints -- a complete computational trichotomy
- Studies in Computational Aspects of Voting
- Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules
- Towards a dichotomy for the possible winner problem in elections based on scoring rules
Cited in
(4)
This page was built for publication: Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2317862)
