Search versus Search for Collapsing Electoral Control Types

Hemaspaandra et al. [6] and Carleton et al. [3, 4] found that many pairs of electoral (decision) problems about the same election system coincide as sets (i.e., they are collapsing pairs), which had previously 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 reductions 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.