Show simple item record

dc.contributor.authorBouveret, Sylvain
dc.contributor.authorLang, Jérôme
dc.date.accessioned2011-10-01T12:20:03Z
dc.date.available2011-10-01T12:20:03Z
dc.date.issued2008
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/7068
dc.language.isoenen
dc.subjectallocation of resourcesen
dc.subjectComplexityen
dc.subjectnonmonotonic reasoningen
dc.subject.ddc006.3en
dc.titleEfficiency and envy-freeness in fair division of indivisible goods: logical representation and complexityen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe consider the problem of allocating fairly a set of indivisible goods among agents from the point of view of compact representation and computational complexity. We start by assuming that agents have dichotomous preferences expressed by propositional formulae. We express efficiency and envy-freeness in a logical setting, which reveals unexpected connections to nonmonotonic reasoning. Then we identify the complexity of determining whether there exists an efficient and envy-free allocation, for several notions of efficiency, when preferences are represented in a succinct way (as well as restrictions of this problem). We first study the problem under the assumption that preferences are dichotomous, and then in the general case.en
dc.relation.isversionofjnlnameThe Journal of Artificial Intelligence Research
dc.relation.isversionofjnlvol32en
dc.relation.isversionofjnldate2008
dc.relation.isversionofjnlpages525-564en
dc.relation.isversionofdoihttp://dx.doi.org/10.1613/jair.2467en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherAI Access Foundationen
dc.subject.ddclabelIntelligence artificielleen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record