2011/05/25 by Faliszewski, Piotr, Hemaspaandra, Edith, Hemaspaandra, Lane A. · 1 citation
#Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #F.1.3 #F.2.2 #FOS: Computer and information sciences #I.2.11 #Multiagent Systems (cs.MA)
paper · doi:10.48550/arxiv.1105.5032
Many electoral bribery, control, and manipulation problems (which we will refer to in general as "manipulative actions" problems) are NP-hard in the general case. It has recently been noted that many of these problems fall into polynomial time if the electorate is single-peaked (i.e., is polarized along some axis/issue). However, real-world electorates are not truly single-peaked. There are usually some mavericks, and so real-world electorates tend to merely be nearly single-peaked. This paper studies the complexity of manipulative-action algorithms for elections over nearly single-peaked electorates, for various notions of nearness and various election systems. We provide instances where even one maverick jumps the manipulative-action complexity up to \np-hardness, but we also provide many instances where a reasonable number of mavericks can be tolerated without increasing the manipulative-action complexity.