Abstract (EN)

In a voting system, sometimes multiple new alternatives will jointhe election after the voters’ preferences over the initial alternativeshave been revealed. Computing whether a given alternative canbe a co-winner when multiple new alternatives join the election iscalled the possible co-winner with new alternatives (PcWNA) prob-lem and was introduced by Chevaleyre et al. [6]. In this paper, weshow that the PcWNA problems are NP-complete for the Buck-lin, Copeland0, and maximin (a.k.a. Simpson) rule, even when thenumber of new alternatives is no more than a constant. We alsoshow that the PcWNA problem can be solved in polynomial timefor plurality with runoff. For the approval rule, we examine threedifferent ways to extend a linear order with new alternatives, andcharacterize the computational complexity of the PcWNA problemfor each of them.