Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2604.11933 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908960544522240 |
|---|---|
| author | Cechlárová, Katarína Rothe, Jörg Schierreich, Šimon Schlotter, Ildikó |
| author_facet | Cechlárová, Katarína Rothe, Jörg Schierreich, Šimon Schlotter, Ildikó |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_11933 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Navigating the Complexity Landscape of Nominee Selection in Schulze Voting Cechlárová, Katarína Rothe, Jörg Schierreich, Šimon Schlotter, Ildikó Computer Science and Game Theory 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. |
| title | Navigating the Complexity Landscape of Nominee Selection in Schulze Voting |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2604.11933 |