The complexity of controlling candidate-sequential elections

DOI10.1016/J.TCS.2017.03.037zbMATH Open1371.91053arXiv1202.6649OpenAlexW2964125475MaRDI QIDQ526900FDOQ526900

Authors: Edith Hemaspaandra, Jörg Rothe, Lane A. Hemaspaandra 

Publication date: 15 May 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Candidate control of elections is the study of how adding or removing candidates can affect the outcome. However, the traditional study of the complexity of candidate control is in the model in which all candidates and votes are known up front. This paper develops a model for studying online control for elections where the structure is sequential with respect to the candidates, and in which the decision regarding adding and deleting must be irrevocably made at the moment the candidate is presented. We show that great complexity---PSPACE-completeness---can occur in this setting, but we also provide within this setting polynomial-time algorithms for the most important of election systems, plurality.

Full work available at URL: https://arxiv.org/abs/1202.6649

Recommendations

• Online voter control in sequential elections
• Elections with few voters: candidate control can be easy
• Control complexity in Borda elections: solving all open cases of offline control and some cases of online control
• The complexity of online manipulation of sequential elections
• The complexity of online bribery in sequential elections

zbMATH Keywords

computational complexityonline algorithmsonline controlcomputational social choicecandidate control of electionssequential voting

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Social choice (91B14) Analysis of algorithms and problem complexity (68Q25) Voting theory (91B12)

Cites Work

• Title not available (Why is that?)
• Alternation
• When are elections with few candidates hard to manipulate?
• Anyone but him: the complexity of precluding an alternative
• How hard is it to control an election?
• New candidates welcome! Possible winners with respect to the addition of new candidates
• The complexity of manipulative attacks in nearly single-peaked electorates
• Control and bribery in voting
• The theory of voting and equilibria in noncooperative games
• The complexity of online manipulation of sequential elections
• Online voter control in sequential elections

Cited In (12)

• Complexity of control by partitioning veto elections and of control by adding candidates to plurality elections
• The complexity of online bribery in sequential elections
• Online voter control in sequential elections
• Control complexity in Borda elections: solving all open cases of offline control and some cases of online control
• Sequential elections with limited information. A formal analysis
• The Last Voting Rule Is Home: Complexity of Control by Partition of Candidates or Voters in Maximin Elections
• Optimal defense against election control by deleting voter groups
• The complexity of priced control in elections
• The complexity of online manipulation of sequential elections
• Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
• SEQUENTIAL OR SIMULTANEOUS ELECTIONS? A WELFARE ANALYSIS
• Title not available (Why is that?)

This page was built for publication: The complexity of controlling candidate-sequential elections

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q526900)