Separations and Collapses in Computational Social Choice

Following the seminal work of Bartholdi et al. [2], there has been a slew of research on the complexity of constructive and destructive control for specific election systems (a.k.a. voting rules), which was driven by the field's desire to find a natural election system that is "resistant" to as many control attacks (types) as possible. While this race was happening, many proofs were devised for a variety of election systems, and yet unbeknownst to many, several control attacks were in fact exactly the same (when viewed as decision problems, which is the common framework). Hemaspaandra et al. [14] were the first to make this observation, demonstrating that there was a general lack of understanding of the standard control attacks. My work continues this line of research in three ways: (1) determining the relationships of electoral control types both in the "general" setting and in concrete settings, (2) finding axiomaticsufficient conditions to determine if a particular equality between control types (a.k.a. collapse) occurs, and (3) linking results in the more abstract decision model to the more explicit search model.