The complexity of controlling candidate-sequential elections

DOI10.1016/J.TCS.2017.03.037MaRDI QIDQ526900zbMATH OpenOpenAlexFDO

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

Publication date 15 May 2017

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

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

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)

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.

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

Cites work

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

Cited in

(12)

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

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)