Show simple item record

dc.contributor.authorLang, Jérôme
dc.contributor.authorPini, Maria Silvia
dc.contributor.authorRossi, Francesca
dc.contributor.authorSalvagnin, Domenico
dc.contributor.authorVenable, Kristen Brent
dc.contributor.authorWalsh, Toby
dc.date.accessioned2017-03-20T15:30:00Z
dc.date.available2017-03-20T15:30:00Z
dc.date.issued2012
dc.identifier.issn1387-2532
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16412
dc.language.isoenen
dc.subjectSocial choiceen
dc.subjectVoting treesen
dc.subjectIncompletenessen
dc.subjectWinner determinationen
dc.subject.ddc003en
dc.subject.classificationjelC44en
dc.titleWinner determination in voting trees with incomplete preferences and weighted votesen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn multiagent settings where agents have different preferences, preference aggregation can be an important issue. Voting is a general method to aggregate preferences. We consider the use of voting tree rules to aggregate agents’ preferences. In a voting tree, decisions are taken by performing a sequence of pairwise comparisons in a binary tree where each comparison is a majority vote among the agents. Incompleteness in the agents’ preferences is common in many real-life settings due to privacy issues or an ongoing elicitation process. We study how to determine the winners when preferences may be incomplete, not only for voting tree rules (where the tree is assumed to be fixed), but also for the Schwartz rule (in which the winners are the candidates winning for at least one voting tree). In addition, we study how to determine the winners when only balanced trees are allowed. In each setting, we address the complexity of computing necessary (respectively, possible) winners, which are those candidates winning for all completions (respectively, at least one completion) of the incomplete profile. We show that many such winner determination problems are computationally intractable when the votes are weighted. However, in some cases, the exact complexity remains unknown. Since it is generally computationally difficult to find the exact set of winners for voting trees and the Schwartz rule, we propose several heuristics that find in polynomial time a superset of the possible winners and a subset of the necessary winners which are based on the completions of the (incomplete) majority graph built from the incomplete profiles.en
dc.relation.isversionofjnlnameAutonomous Agents and Multi-Agent Systems
dc.relation.isversionofjnlvol25en
dc.relation.isversionofjnlissue1en
dc.relation.isversionofjnldate2012-07
dc.relation.isversionofjnlpages130-157en
dc.relation.isversionofdoi10.1007/s10458-011-9171-8en
dc.relation.isversionofjnlpublisherKluwer Academic Publishersen
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2017-03-20T14:59:26Z
hal.person.labIds989
hal.person.labIds39512
hal.person.labIds39512
hal.person.labIds39512
hal.person.labIds39512
hal.person.labIds57492
hal.identifierhal-01492911*


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