Show simple item record

dc.contributor.authorBouveret, Sylvain
dc.contributor.authorCechlarova, Katarína
dc.contributor.authorLesca, Julien
dc.date.accessioned2019-10-02T14:10:02Z
dc.date.available2019-10-02T14:10:02Z
dc.date.issued2019
dc.identifier.issn1387-2532
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/19971
dc.descriptionLe PDF est une version non publiée datant de 2018.en
dc.language.isoenen
dc.subjectComputational social choiceen
dc.subjectResource allocationen
dc.subjectFair divisionen
dc.subjectIndivisible choresen
dc.subject.ddc003en
dc.titleChore division on a graphen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe paper considers fair allocation of indivisible nondisposable items that generate disutility (chores). We assume that these items are placed in the vertices of a graph and each agent’s share has to form a connected subgraph of this graph. Although a similar model has been investigated before for goods, we show that the goods and chores settings are inherently different. In particular, it is impossible to derive the solution of the chores instance from the solution of its naturally associated fair division instance. We consider three common fair division solution concepts, namely proportionality, envy-freeness and equitability, and two individual disutility aggregation functions: additive and maximum based. We show that deciding the existence of a fair allocation is hard even if the underlying graph is a path or a star. We also present some efficiently solvable special cases for these graph topologies.en
dc.relation.isversionofjnlnameAutonomous Agents and Multi-Agent Systems
dc.relation.isversionofjnlvol33en
dc.relation.isversionofjnlissue5en
dc.relation.isversionofjnldate2019-09
dc.relation.isversionofjnlpages540-563en
dc.relation.isversionofdoi10.1007/s10458-019-09415-zen
dc.contributor.countryeditoruniversityotherFRANCE
dc.contributor.countryeditoruniversityotherSLOVAKIA
dc.relation.isversionofjnlpublisherSpringeren
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.updated2019-10-02T14:07:14Z
hal.person.labIds24471
hal.person.labIds56239
hal.person.labIds989
hal.identifierhal-02303821*


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record