{"_id":"Li9GsEppXLLCZs39z","bibbaseid":"menon-larson-reinstatingcombinatorialprotectionsformanipulationandbriberyinsinglepeakedandnearlysinglepeakedelectorates-2015","downloads":0,"creationDate":"2016-07-09T17:03:16.684Z","title":"Reinstating Combinatorial Protections for Manipulation and Bribery in Single-Peaked and Nearly Single-Peaked Electorates","author_short":["Menon, V.","Larson, K."],"year":2015,"bibtype":"article","biburl":null,"bibdata":{"title":"Reinstating Combinatorial Protections for Manipulation and Bribery in Single-Peaked and Nearly Single-Peaked Electorates","type":"article","year":"2015","identifiers":"[object Object]","websites":"http://arxiv.org/abs/1511.08141","id":"85d2ce4f-a8b0-3b77-8c06-ecd8f4aa69a5","created":"2016-07-09T17:08:36.000Z","file_attached":"true","profile_id":"6835648d-fd3c-34d3-a1a2-9a7b291884eb","group_id":"c5a02f2e-65c1-39ec-ac2e-a720cb3dfc60","last_modified":"2016-07-09T17:08:36.000Z","read":false,"starred":false,"authored":false,"confirmed":"true","hidden":false,"abstract":"Understanding when and how computational complexity can be used to protect elections against different manipulative actions has been a highly active research area over the past two decades. A recent body of work, however, has shown that many of the NP-hardness shields, previously obtained, vanish when the electorate has single-peaked or nearly single-peaked preferences. In light of these results, we investigate whether it is possible to reimpose NP-hardness shields for such electorates by allowing the voters to specify partial preferences instead of insisting they cast complete ballots. In particular, we show that in single-peaked and nearly single-peaked electorates, if voters are allowed to submit top-truncated ballots, then the complexity of manipulation and bribery for many voting rules increases from being in P to being NP-complete.","bibtype":"article","author":"Menon, Vijay and Larson, Kate","bibtex":"@article{\n title = {Reinstating Combinatorial Protections for Manipulation and Bribery in Single-Peaked and Nearly Single-Peaked Electorates},\n type = {article},\n year = {2015},\n identifiers = {[object Object]},\n websites = {http://arxiv.org/abs/1511.08141},\n id = {85d2ce4f-a8b0-3b77-8c06-ecd8f4aa69a5},\n created = {2016-07-09T17:08:36.000Z},\n file_attached = {true},\n profile_id = {6835648d-fd3c-34d3-a1a2-9a7b291884eb},\n group_id = {c5a02f2e-65c1-39ec-ac2e-a720cb3dfc60},\n last_modified = {2016-07-09T17:08:36.000Z},\n read = {false},\n starred = {false},\n authored = {false},\n confirmed = {true},\n hidden = {false},\n abstract = {Understanding when and how computational complexity can be used to protect elections against different manipulative actions has been a highly active research area over the past two decades. A recent body of work, however, has shown that many of the NP-hardness shields, previously obtained, vanish when the electorate has single-peaked or nearly single-peaked preferences. In light of these results, we investigate whether it is possible to reimpose NP-hardness shields for such electorates by allowing the voters to specify partial preferences instead of insisting they cast complete ballots. In particular, we show that in single-peaked and nearly single-peaked electorates, if voters are allowed to submit top-truncated ballots, then the complexity of manipulation and bribery for many voting rules increases from being in P to being NP-complete.},\n bibtype = {article},\n author = {Menon, Vijay and Larson, Kate}\n}","author_short":["Menon, V.","Larson, K."],"urls":{"Paper":"http://bibbase.org/service/mendeley/6835648d-fd3c-34d3-a1a2-9a7b291884eb/file/1aaa2adf-c6fb-12c3-52c7-11578bfb98f6/2015-Reinstating_Combinatorial_Protections_for_Manipulation_and_Bribery_in_Single-Peaked_and_Nearly_Single-Peaked_Electo.pdf.pdf","Website":"http://arxiv.org/abs/1511.08141"},"bibbaseid":"menon-larson-reinstatingcombinatorialprotectionsformanipulationandbriberyinsinglepeakedandnearlysinglepeakedelectorates-2015","role":"author","downloads":0,"html":""},"search_terms":["reinstating","combinatorial","protections","manipulation","bribery","single","peaked","nearly","single","peaked","electorates","menon","larson"],"keywords":[],"authorIDs":[]}