Kernelization complexity of possible winner and coalitional manipulation problems in voting

Show simple item record

dc.contributor.author Dey, Palash
dc.contributor.author Misra, Neeldhara
dc.contributor.author Narahari, Y.
dc.date.accessioned 2016-04-16T16:17:24Z
dc.date.available 2016-04-16T16:17:24Z
dc.date.issued 2016-02
dc.identifier.citation Dey, Palash; Misra, Neeldhara and Narahari, Y., "Kernelization complexity of possible winner and coalitional manipulation problems in voting", Theoretical Computer Science, DOI: 10.1016/j.tcs.2015.12.023, vol. 616, pp. 111-125, Feb. 2016. en_US
dc.identifier.issn 0304-3975
dc.identifier.uri http://dx.doi.org/10.1016/j.tcs.2015.12.023
dc.identifier.uri https://repository.iitgn.ac.in/handle/123456789/2200
dc.description.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 [10]. 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 includes the Borda voting rule does 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. en_US
dc.description.statementofresponsibility by Palash Dey, Neeldhara Misra and Y. Narahari
dc.format.extent Vol. 616, pp. 111-125
dc.language.iso en_US en_US
dc.publisher Elsevier en_US
dc.subject Computational social choice en_US
dc.subject Possible winner en_US
dc.subject Voting en_US
dc.subject Kernelization en_US
dc.subject Parameterized complexity en_US
dc.title Kernelization complexity of possible winner and coalitional manipulation problems in voting en_US
dc.type Article en_US
dc.relation.journal Theoretical Computer Science


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


Browse

My Account