• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Chore division on a graph

Thumbnail
View/Open
chore_division.pdf (176.3Kb)
Date
2019
Notes
Le PDF est une version non publiée datant de 2018.
Dewey
Recherche opérationnelle
Sujet
Computational social choice; Resource allocation; Fair division; Indivisible chores
Journal issue
Autonomous Agents and Multi-Agent Systems
Volume
33
Number
5
Publication date
09-2019
Article pages
540-563
Publisher
Springer
DOI
http://dx.doi.org/10.1007/s10458-019-09415-z
URI
https://basepub.dauphine.fr/handle/123456789/19971
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Bouveret, Sylvain
24471 Laboratoire d'Informatique de Grenoble [LIG]
Cechlarova, Katarína
56239 Safarik University
Lesca, Julien
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Article accepté pour publication ou publié
Abstract (EN)
The 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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.