On the Complexity of the Two-Stage Majoritarian Rule
This work provides foundational complexity results for a new voting rule, which is incremental as it builds on prior theoretical proposals.
The paper investigates the computational complexity of 12 election control problems for the two-stage majoritarian rule, a sequential voting rule proposed to address failures in existing rules, finding that these problems are generally NP-hard or coNP-hard.
Sequential voting rules have played a crucial role in shaping decisions within parliamentary and legislative frameworks. After observing that the existing sequential rules fail several fundamental axioms, Horan and Sprumont [2022] proposed a sequential rule named two-stage majoritarian rule (TSMR). This paper examines this rule by investigating the complexity of {\sc{Agenda Control}}, {\sc{Coalition Manipulation}}, {\sc{Possible Winner}}, {\sc{Necessary Winner}}, and eight standard election control problems. Our study offers a comprehensive insight into the complexity landscape of these problems.