2015/06/15 by Zack Fitzsimmons, Edith Hemaspaandra, Fitzsimmons, Zack +1
Computer Science · Decision Sciences · Economics, Econometrics and Finance · Psychology · #Algorithm #Artificial intelligence #Auction Theory and Applications #Business #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #Computer science #Control (management) #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems #Interpersonal ties #Law #Multiagent Systems (cs.MA) #Order (exchange) #Political science #Politics #Psychology #Social psychology #State (computer science) #Strong ties #Voting #cs.CC #cs.GT #cs.MA
paper · pdf · doi:10.48550/arxiv.1506.04722
published in arXiv (Cornell University) (Cornell University) · A version of this paper will appear in ADT-2015
arxiv created 2015/06/15 · openalex publication_date 2015/06/15 · arxiv updated 2015/06/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
Most of the computational study of election problems has assumed that each voter's preferences are, or should be extended to, a total order. However in practice voters may have preferences with ties. We study the complexity of manipulative actions on elections where voters can have ties, extending the definitions of the election systems (when necessary) to handle voters with ties. We show that for natural election systems allowing ties can both increase and decrease the complexity of manipulation and bribery, and we state a general result on the effect of voters with ties on the complexity of control.