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

Afficher

Cette collectionPar Date de CréationAuteursTitresSujetsNoms de revueToute la baseCentres de recherche & CollectionsPar Date de CréationAuteursTitresSujetsNoms de revue

Mon compte

Connexion

Statistiques

Afficher les statistiques d'usage

Chore division on a graph

Thumbnail
Ouvrir
chore_division.pdf (176.3Kb)
Date
2019
Description
Le PDF est une version non publiée datant de 2018.
Indexation documentaire
Recherche opérationnelle
Subject
Computational social choice; Resource allocation; Fair division; Indivisible chores
Nom de la revue
Autonomous Agents and Multi-Agent Systems
Volume
33
Numéro
5
Date de publication
09-2019
Pages article
540-563
Nom de l'éditeur
Springer
DOI
http://dx.doi.org/10.1007/s10458-019-09415-z
URI
https://basepub.dauphine.fr/handle/123456789/19971
Collections
  • LAMSADE : Publications
Métadonnées
Afficher la notice complète
Auteur
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é
Résumé en anglais
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

 Cette création est mise à disposition sous un contrat Creative Commons.