Possible Winners When New Alternatives Join: New Results Coming Up!

摘要

In a voting system, sometimes multiple new alternatives will join the election after the voters' preferences over the initial alternatives have been revealed. Computing whether a given alternative can be a co-winner when multiple new alternatives join the election is called the possible co-winner with new alternatives (PcWNA) problem and was introduced by Chevaleyre et al. [6]. In this paper, we show that the PcWNA problems are NP-complete for the Buck-lin, Copelando, and maximin (a.k.a. Simpson) rule, even when the number of new alternatives is no more than a constant. We also show that the PcWNA problem can be solved in polynomial time for plurality with runoff. For the approval rule, we examine three different ways to extend a linear order with new alternatives, and characterize the computational complexity of the PcWNA problem for each of them.