• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

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

Thumbnail
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
URI
https://basepub.dauphine.fr/handle/123456789/6905
Collections
  • LAMSADE : Publications
Metadata
Show full item record
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.