Paper  Website  abstract   bibtex   

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