An official website of the United States government
Electoral control refers to attacking elections by adding, deleting, or partitioning voters or candidates [3]. Hemaspaandra et al. [16] discovered, for seven pairs (T , T ′ ) of seemingly distinct standard electoral control types, that T and T ′ are identical: For each input 𝐼 and each election system E, 𝐼 is a “yes” instance of both T and T ′ under E, or of neither. Surprisingly, this had gone undetected even as the field was score-carding how many standard control types election systems were resistant to; various “different” cells on such score cards were, unknowingly, duplicate effort on the same issue. This naturally raises the worry that other pairs of control types are also identical, and so work still is being needlessly duplicated. We determine, for all standard control types, which pairs are, for elections whose votes are linear orderings of the candidates, always identical. We show that no identical control pairs exist beyond the known seven. For three central election systems, we determine which control pairs are identical (“collapse”) with respect to those particular systems, and we explore containment/incomparability relationships between control pairs. For approval voting, which has a different “type” for its votes, Hemaspaandra et al.’s [16] seven collapses still hold. But we find 14 additional collapses that hold for approval voting but not for some election systems whose votes are linear orderings. We find one additional collapse for veto and none for plurality. We prove that each of the three election sys- tems mentioned have no collapses other than those inherited from Hemaspaandra et al. [16] or added here. But we show many new containment relationships that hold between some separating con- trol pairs, and for each separating pair of standard control types classify its separation in terms of containment (always, and strict on some inputs) or incomparability. Our work, for the general case and these three important election systems, clarifies the landscape of the 44 standard control types, for each pair collapsing or separating them, and also providing finer-grained information on the separations.
more »
« less
Separations and Collapses in Computational Social Choice and Complexity Theory
This thesis studies separations and collapses in new ways, in both computational social choice and computational complexity theory. Since the seminal work of Bartholdi et al. (1989a,b, 1992) and Bartholdi and Orlin (1991) in computational social choice, the tools and techniques of theoretical computer science have been used to discover the complexities of a range of attacks on different election systems. That line of work has broadly assumed that the seemingly different attacks were in fact different. A key contribution of this thesis will be to explore, in the widely-studied electoral attack domain known as electoral control, the extent to which that assumption is correct. In particular, Hemaspaandra et al. (2020) showed that there were several electoral control problems that, although they had been studied separately for years, are in fact one and the same (when viewed as decision problems). This showed that researchers had for years been doing redundant work. We continue this line of work and uncover additional surprising relationships among electoral control types, thus discovering additional cases where duplicate effort has occurred, and helping the field avoid further duplicate work. Building on this, for control types that collapse in the literature’s standard notion of collapse—equality of their decision problems—this thesis studies whether the search complexities of the collapsing types also collapse (i.e., coincide). We find they do for all known collapsing types, and for all new collapsing types discovered in this thesis. We indeed go beyond that by showing that one often can efficiently build search solutions for one type from the search solutions of the other type on the same input, and we provide a framework to study those search-complexity relationships. In computational complexity theory, we study which pairs of ambiguity-bounded versions of NP stand (collapse) or fall (separate) together: one collapses to P exactly if the other does too. Prior to our work, the only known family of such connections was due to Watanabe (1988), and we present here new collections of such families. Finally, in the area of the complexity of single-player games, we generalize a tool used to study reversible deterministic games to work for deterministic games with irreversible gravity. In some sense, this provides a “collapse” between the tools used to study two seemingly different categories of games. The particular too we study is the Nondeterministic Constraint Logic problem, which typically allows one to show PSPACE-hardness by constructing only two gadgets, but is unfortunately not directly applicable to the study of games with irreversible gravity. We devise a new method that when applied directly uses 32 gadgets, but we show that many of those gadgets are effectively equivalent (thus giving another type of “collapse”) and that we can simulate all 32 gadgets by using only three gadgets. We apply this method to the study of the Hanano Puzzle and find that only two gadgets are needed to show the PSPACE-hardness of that game. Looking at the bigger picture, this thesis looks in new ways at collapses and separations in computational social choice and computational complexity theory, making progress using a variety of tools ranging from proving theorems to providing new human and computer-discovered separations. Overall, we paint a clearer picture in computational social choice of what collapses and separations occur, and in computational complexity of what collapses stand or fall together.
more »
« less
- Award ID(s):
- 2006496
- PAR ID:
- 10644198
- Publisher / Repository:
- ProQuest
- Date Published:
- Subject(s) / Keyword(s):
- computational complexity computational social choice
- Format(s):
- Medium: X
- Institution:
- University of Rochester
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Electoral control refers to attacking elections by adding, deleting, or partitioning voters or candidates. Hemaspaandra, Hemaspaandra, and Menton recently discovered, for seven pairs (T, T′) of seemingly distinct standard electoral control types, that T and T′ are in practice identical: For each input I and each election system E, I is a “yes” instance of both T and T′ under E, or of neither. Surprisingly, this had previously gone undetected even as the field was score-carding how many standard control types various election systems were resistant to; various “different” cells on such score cards were, unknowingly, duplicate effort on the same issue. This naturally raises the worry that perhaps other pairs of control types are identical, and so work still is being needlessly duplicated.We completely determine, for all standard control types, which pairs are, for elections whose votes are linear orderings of the candidates, always identical. In particular, we prove that no identical control pairs exist beyond the known seven. We also for three central election systems completely determine which control pairs are identical (“collapse”) with respect to those particular election systems, and we also explore containment and incomparability relationships between control pairs. For approval voting, which has a different “type” for its votes, Hemaspaandra, Hemaspaandra, and Menton’s seven collapses still hold (since we observe that their argument applies to all election systems). However, we find 14 additional collapses that hold for approval voting but do not hold for some election systems whose votes are linear orderings of the candidates. We find one new collapse for veto elections and none for plurality. We prove that each of the three election systems mentioned have no collapses other than those inherited from Hemaspaandra, Hemaspaandra, and Menton or added in the present paper. We establish many new containment relationships between separating control pairs, and for each separating pair of standard control types classify its separation in terms of either containment (always, and strict on some inputs) or incomparability.Our work, for the general case and these three important election systems, clarifies the landscape of the 44 standard control types, for each pair collapsing or separating them, and also providing finer-grained information on the separations.more » « less
-
Hemaspaandra et al. [6] and Carleton et al. [3, 4] found that many pairs of electoral (decision) problems about the same election sys- tem coincide as sets (i.e., they are collapsing pairs), which had pre- viously gone undetected in the literature. While both members of a collapsing pair certainly have the same decision complexity, there is no guarantee that the associated search problems also have the same complexity. For practical purposes, search problems are more relevant than decision problems. Our work focuses on exploring the relationships between the search versions of collapsing pairs. We do so by giving a framework that relates the complexity of search problems via efficient reduc- tions that transform a solution from one problem to a solution of the other problem on the same input. We not only establish that the known decision collapses carry over to the search model, but also refine our results by determining for the concrete systems plurality, veto, and approval whether collapsing search-problem pairs are polynomial-time computable or NP-hard.more » « less
-
null (Ed.)A fundamental pursuit in complexity theory concerns reducing worst-case problems to average-case problems. There exist complexity classes such as PSPACE that admit worst-case to average-case reductions. However, for many other classes such as NP, the evidence so far is typically negative, in the sense that the existence of such reductions would cause collapses of the polynomial hierarchy(PH). Basing cryptographic primitives, e.g., the average-case hardness of inverting one-way permutations, on NP-completeness is a particularly intriguing instance. As there is evidence showing that classical reductions from NP-hard problems to breaking these primitives result in PH collapses, it seems unlikely to base cryptographic primitives on NP-hard problems. Nevertheless, these results do not rule out the possibilities of the existence of quantum reductions. In this work, we initiate a study of the quantum analogues of these questions. Aside from formalizing basic notions of quantum reductions and demonstrating powers of quantum reductions by examples of separations, our main result shows that if NP-complete problems reduce to inverting one-way permutations using certain types of quantum reductions, then coNP ⊆ QIP ( 2 ) .more » « less
-
Using the notion of visibility representations, our paper establishes a new property of in- stances of the Nondeterministic Constraint Logic (NCL) problem (a PSPACE-complete problem that is very convenient to prove the PSPACE-hardness of reversible games with pushing blocks). Direct use of this property introduces an explosion in the number of gadgets needed to show PSPACE-hardness, but we show how to bring that number from 32 down to only three in general, and down to two in a specific case! We propose it as a step towards a broader and more general framework for studying games with irreversible gravity, and use this connection to guide an indirect polynomial-time many-one reduction from the NCL problem to the Hanano Puzzle—which is NP-hard—to prove it is in fact PSPACE-complete.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Dissertation:
- The DOI is not currently available.
