
Chore division on a graph
Bouveret, Sylvain; Cechlarova, Katarína; Lesca, Julien (2019), Chore division on a graph, Autonomous Agents and Multi-Agent Systems, 33, 5, p. 540-563. 10.1007/s10458-019-09415-z
View/ Open
Type
Article accepté pour publication ou publiéDate
2019Journal name
Autonomous Agents and Multi-Agent SystemsVolume
33Number
5Publisher
Springer
Pages
540-563
Publication identifier
Metadata
Show full item recordAuthor(s)
Bouveret, Sylvain
Laboratoire d'Informatique de Grenoble [LIG]
Cechlarova, Katarína
Lesca, Julien
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
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.Subjects / Keywords
Computational social choice; Resource allocation; Fair division; Indivisible choresRelated items
Showing items related by title and author.
-
Bouveret, Sylvain; Lang, Jérôme (2005) Communication / Conférence
-
Bouveret, Sylvain; Lang, Jérôme (2008) Article accepté pour publication ou publié
-
Bouveret, Sylvain; Endriss, Ulle; Lang, Jérôme (2010) Communication / Conférence
-
Baumeister, Dorothea; Bouveret, Sylvain; Lang, Jérôme; Nguyen, Nhan-Tam; Nguyen, Trung Thanh; Rothe, Jörg (2014) Communication / Conférence
-
Aziz, Haris; Bouveret, Sylvain; Caragiannis, Ioannis; Giagkousi, Ira; Lang, Jérôme (2018) Communication / Conférence