Kernelization complexity of possible winner and coalitional manipulation problems in voting

DOI10.1016/J.TCS.2015.12.023MaRDI QIDQ906403zbMATH OpenOpenAlexFDO

Authors Palash Dey, Neeldhara Misra, Y. Narahari

Publication date 21 January 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.3865

zbMATH Keywords

votingparameterized complexitykernelizationcomputational social choicepossible winner

Mathematics Subject Classification ID

Social choice (91B14) Analysis of algorithms and problem complexity (68Q25) Voting theory (91B12)

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.

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

• A parameterized complexity analysis of combinatorial feature selection problems
• Fixed-parameter algorithms for Kemeny rankings
• Incompressibility through Colors and IDs
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• Kernelization -- preprocessing with a guarantee
• Kernelization complexity of possible winner and coalitional manipulation problems in voting
• Multivariate complexity analysis of Swap Bribery
• On problem kernels for possible winner determination under the \(k\)-approval protocol
• Parametrized complexity theory.
• Partial kernelization for rank aggregation: theory and experiments
• Prices matter for the parameterized complexity of shift bribery
• Studies in Computational Aspects of Voting
• The computational difficulty of manipulating an election
• Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules

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?
• scientific article; zbMATH DE number 6928629 (Why is no real title available?)
• 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)