Possible Winners When New Alternatives Join: New Results Coming Up!
Xia, Lirong; Lang, Jérôme; Monnot, Jérôme (2011), Possible Winners When New Alternatives Join: New Results Coming Up!, in Yolum, Pınar, Proceedings of 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), IFAAMAS, p. 829-836
TypeCommunication / Conférence
Conference countryTAIWAN, PROVINCE OF CHINA
Book titleProceedings of 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011)
Book authorYolum, Pınar
MetadataShow full item record
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. . 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.
Subjects / Keywordsmulti-agent systems; possible co-winner with new alternatives; Computational social choice,
Showing items related by title and author.
Chevaleyre, Yann; Lang, Jérôme; Maudet, Nicolas; Monnot, Jérôme; Xia, Lirong (2012) Article accepté pour publication ou publié