Candidate Nomination for Condorcet-consistent Voting Rules

Consider elections where the set of candidates is partitioned into parties, and each party must nominate exactly one candidate. The Possible President problem asks whether some candidate of a given party can become the winner of the election for some nominations from other parties. We perform a multivariate computational complexity analysis of Possible President for a range of Condorcet-consistent voting rules, namely for Copeland 𝛼 for 𝛼 ∈ [0, 1] and Maximin. The parameters we study are the number of voters, the number of parties, and the maximum size of a party. For all voting rules under consideration, we obtain dichotomies based on the number of voters, classifying NP-complete and polynomialtime solvable cases. Moreover, for each NP-complete variant, we determine the parameterized complexity of every possible parameterization with the studied parameters as either (a) fixed-parameter tractable, (b) W[1]-hard but in XP, or (c) para-NP-hard, outlining the limits of tractability for these problems.