Show simple item record

dc.contributor.authorXia, Lirong
dc.contributor.authorLang, Jérôme
dc.contributor.authorMonnot, Jérôme
dc.date.accessioned2011-08-31T10:51:57Z
dc.date.available2011-08-31T10:51:57Z
dc.date.issued2011
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/6905
dc.language.isoenen
dc.subjectmulti-agent systems
dc.subjectpossible co-winner with new alternatives
dc.subjectComputational social choice,
dc.subject.ddc003en
dc.titlePossible Winners When New Alternatives Join: New Results Coming Up!
dc.typeCommunication / Conférence
dc.contributor.editoruniversityotherDept. of Computer Science Duke University;États-Unis
dc.description.abstractenIn 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.
dc.identifier.citationpages829-836
dc.relation.ispartoftitleProceedings of 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011)
dc.relation.ispartofeditorYolum, Pınar
dc.relation.ispartofpublnameIFAAMAS
dc.relation.ispartofdate2011
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.confcountryTAIWAN, PROVINCE OF CHINA
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.date.updated2017-01-06T18:05:15Z


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record