Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers
From MaRDI portal
Publication:2317862
DOI10.1016/J.TCS.2019.03.022zbMATH Open1427.91119arXiv1511.04190OpenAlexW4255392577WikidataQ128140359 ScholiaQ128140359MaRDI QIDQ2317862FDOQ2317862
Authors: Palash Dey, Neeldhara Misra, Y. Narahari 
Publication date: 13 August 2019
Published in: Theoretical Computer Science (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1511.04190
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
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Voting theory (91B12)
Cites Work
- Fundamentals of parameterized complexity
- Fixed-parameter algorithms for CLOSEST STRING and related problems
- Computational Aspects of Approval Voting
- A Consistent Extension of Condorcet’s Election Principle
- Title not available (Why is that?)
- Title not available (Why is that?)
- Parameterized algorithms
- On the complexity of \(k\)-SAT
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Towards a dichotomy for the possible winner problem in elections based on scoring rules
- Parameterized complexity dichotomy for \textsc{Steiner Multicut}
- Title not available (Why is that?)
- How hard is it to control an election?
- Studies in Computational Aspects of Voting
- Prices matter for the parameterized complexity of shift bribery
- Complexity of strategic behavior in multi-winner elections
- Elections with few voters: candidate control can be easy
- Handbook of Computational Social Choice
- Justified representation in approval-based committee voting
- On the complexity of achieving proportional representation
- Approval balloting for multi-winner elections
- PTAS for minimax approval voting
- Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules
- Axioms for approval voting: Direct proof
- On approximating string selection problems with outliers
- Book review of: Jean-François Laslier and M. Remzi Sanver (eds.), Handbook on approval voting
- Title not available (Why is that?)
- Frugal bribery in voting
- Kernelization complexity of possible winner and coalitional manipulation problems in voting
- Rationalizations of Voting Rules
- Stable marriage with covering constraints -- a complete computational trichotomy
- Manipulative elicitation -- a new attack on elections with incomplete preferences
- Complexity of manipulation with partial information in voting
- Approximation and parameterized complexity of minimax approval voting
- Parameterized lower bounds and dichotomy results for the NP-completeness of \(H\)-free edge modification problems
- On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard
- Dogson's rule and Yong's rule
- Consistent approval-based multi-winner rules
- Local distance constrained bribery in voting
- Parliamentary voting procedures: agenda control, manipulation, and uncertainty
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)
