Show simple item record

dc.contributor.authorAziz, Haris*
dc.contributor.authorBrill, Markus*
dc.contributor.authorFischer, Felix*
dc.contributor.authorHarrenstein, Paul*
dc.contributor.authorLang, Jérôme*
dc.contributor.authorSeedig, Hans-Georg*
dc.date.accessioned2017-01-13T11:44:37Z
dc.date.available2017-01-13T11:44:37Z
dc.date.issued2015
dc.identifier.issn1076-9757
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16161
dc.language.isoenen
dc.subjectcomputational social choiceen
dc.subject.ddc003en
dc.titlePossible and Necessary Winners of Partial Tournamentsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe study the problem of computing possible and necessary winners for partially specified weighted and unweighted tournaments. This problem arises naturally in elections with incompletely specified votes, partially completed sports competitions, and more generally in any scenario where the outcome of some pairwise comparisons is not yet fully known. We specifically consider a number of well-known solution concepts---including the uncovered set, Borda, ranked pairs, and maximin---and show that for most of them, possible and necessary winners can be identified in polynomial time. These positive algorithmic results stand in sharp contrast to earlier results concerning possible and necessary winners given partially specified preference profiles.en
dc.relation.isversionofjnlnameThe Journal of Artificial Intelligence Research
dc.relation.isversionofjnlvol54en
dc.relation.isversionofjnldate2015-12
dc.relation.isversionofjnlpages493-534en
dc.relation.isversionofdoi10.1613/jair.4856en
dc.relation.isversionofjnlpublisherMorgan Kaufmann 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-01-13T11:22:43Z
hal.person.labIds134757*
hal.person.labIds105966*
hal.person.labIds*
hal.person.labIds98120*
hal.person.labIds989*
hal.person.labIds109286*
hal.identifierhal-01434599*
hal.faultCodeThe supplied format packaging is not supported by the server


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