@article{ 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} }