Kernelization complexity of possible winner and coalitional manipulation problems in voting
From MaRDI portal
Publication:906403
DOI10.1016/J.TCS.2015.12.023zbMATH Open1334.91035arXiv1405.3865OpenAlexW2951543204MaRDI QIDQ906403FDOQ906403
Authors: Palash Dey, Neeldhara Misra, Y. Narahari 
Publication date: 21 January 2016
Published in: Theoretical Computer Science (Search for Journal in Brave)
Abstract: In the Possible Winner problem in computational social choice theory, we are given a set of partial preferences and the question is whether a distinguished candidate could be made winner by extending the partial preferences to linear preferences. Previous work has provided, for many common voting rules, fixed parameter tractable algorithms for the Possible Winner problem, with number of candidates as the parameter. However, the corresponding kernelization question is still open and in fact, has been mentioned as a key research challenge. In this paper, we settle this open question for many common voting rules. We show that the Possible Winner problem for maximin, Copeland, Bucklin, ranked pairs, and a class of scoring rules that include the Borda voting rule do not admit a polynomial kernel with the number of candidates as the parameter. We show however that the Coalitional Manipulation problem which is an important special case of the Possible Winner problem does admit a polynomial kernel for maximin, Copeland, ranked pairs, and a class of scoring rules that includes the Borda voting rule, when the number of manipulators is polynomial in the number of candidates. A significant conclusion of our work is that the Possible Winner problem is harder than the Coalitional Manipulation problem since the Coalitional Manipulation problem admits a polynomial kernel whereas the Possible Winner problem does not admit a polynomial kernel.
Full work available at URL: https://arxiv.org/abs/1405.3865
Recommendations
- On problem kernels for possible winner determination under the \(k\)-approval protocol
- Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules
- Towards a dichotomy for the possible winner problem in elections based on scoring rules
- Determining possible and necessary winners given partial orders
- Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules
Cites Work
- Parametrized complexity theory.
- Kernelization -- preprocessing with a guarantee
- Partial kernelization for rank aggregation: theory and experiments
- Incompressibility through Colors and IDs
- Fixed-parameter algorithms for Kemeny rankings
- Multivariate complexity analysis of Swap Bribery
- The computational difficulty of manipulating an election
- Studies in Computational Aspects of Voting
- Prices matter for the parameterized complexity of shift bribery
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules
- Kernelization complexity of possible winner and coalitional manipulation problems in voting
- A parameterized complexity analysis of combinatorial feature selection problems
- On problem kernels for possible winner determination under the \(k\)-approval protocol
Cited In (16)
- On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard
- Kernelization complexity of possible winner and coalitional manipulation problems in voting
- The control complexity of \(r\)-Approval: from the single-peaked case to the general case
- Manipulative elicitation -- a new attack on elections with incomplete preferences
- Complexity of manipulation with partial information in voting
- Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers
- Resolute control: forbidding candidates from winning an election is hard
- How hard is safe bribery?
- Title not available (Why is that?)
- A parameterized perspective on protecting elections
- Possible winner problems on partial tournaments: a parameterized study
- Possible winner problems on partial tournaments: a parameterized study
- On problem kernels for possible winner determination under the \(k\)-approval protocol
- Predicting winner and estimating margin of victory in elections using sampling
- On the exact amount of missing information that makes finding possible winners hard
- Frugal bribery in voting
This page was built for publication: Kernelization complexity of possible winner and coalitional manipulation problems in voting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q906403)
