Navigating the Complexity Landscape of Nominee Selection in Schulze Voting
For computational social choice theorists, this work provides a complete parameterized complexity landscape for nominee selection in Schulze voting, refining previous NP-completeness results.
The paper analyzes the parameterized complexity of the Possible President and Necessary President problems for Schulze voting, determining dichotomies based on the number of voters, maximum party size, and number of parties. It shows that both problems are fixed-parameter tractable when the number of voters is a parameter, but become intractable when it is unbounded.
We study the Possible President problem and the Necessary President problem for Schulze voting, a rule that, due to its many desirable axiomatic properties, is popular in practice. In both problems, we are given an election with the candidates partitioned into a set of parties, and we are interested in questions about a given distinguished party. In the Possible President problem, we ask whether it is possible for the parties to each nominate exactly one candidate such that the nominee of the distinguished party is a Schulze winner of the resulting election with only the nominees running. In the Necessary President problem, we ask whether the distinguished party's nominee is a Schulze winner of the resulting election, irrespective of the nomination from the other parties. Rothe and Woitaschik have shown that Possible President is NP-complete and Necessary President is coNP-complete for Schulze elections. We complement and improve their results by a more fine-grained analysis: we determine the parameterized complexity of both problems with respect to all possible parameterizations, where we consider each of three natural parameters -- the number of voters, the maximum party size, and the number of parties -- to be either a constant, a parameter, or unbounded. In particular, we obtain dichotomies regarding the number of voters for both problems.