Necessary President in Elections with Parties

Cechlárová, Katarína and Schlotter, Ildikó Anna (2026) Necessary President in Elections with Parties. In: AAMAS '26. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), Richland (SC), pp. 892-900. ISBN 9798400723179

Preview

Text RYRS8869.pdf - Published Version Available under License Creative Commons Attribution. Download (1MB) | Preview

Abstract

Consider an election where the set of candidates is partitioned into parties, and each party must choose exactly one candidate to nominate for the election held over all nominees. The Necessary President problem asks whether a candidate, if nominated, becomes the winner of the election for all possible nominations from other parties. We study the computational complexity of Necessary President for several voting rules. We show that while this problem is solvable in polynomial time for Borda, Maximin, and Copelandα for every α ∈ [0, 1], it is coNP-complete for general classes of positional scoring rules that include ℓ-Approval and ℓ-Veto, even when the maximum size of a party is two. For such positional scoring rules, we show that Necessary President is W[2]-hard when parameterized by the number of parties, but fixed-parameter tractable with respect to the number of voter types. Additionally, we prove that Necessary President for Ranked Pairs is coNP-complete even for maximum party size two, and W[1]-hard with respect to the number of parties; remarkably, both of these results hold even for constant number of voters. © 2026 International Foundation for Autonomous Agents and Multiagent Systems.

Actions (login required)

View Item