Date
2011
Dewey
Recherche opérationnelle
Sujet
multi-agent systems; possible co-winner with new alternatives; Computational social choice,
Conference country
TAIWAN, PROVINCE OF CHINA
Book title
Proceedings of 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011)
Author
Yolum, Pınar
Publisher
IFAAMAS
Year
2011
Author
Xia, Lirong
Lang, Jérôme
Monnot, Jérôme
Type
Communication / Conférence
Item number of pages
829-836
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.