Show simple item record

hal.structure.identifier
dc.contributor.authorFerraioli, Diodato*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorGourvès, Laurent*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
*
dc.date.accessioned2016-02-22T11:07:26Z
dc.date.available2016-02-22T11:07:26Z
dc.date.issued2014
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/15393
dc.language.isoenen
dc.subjectComputational social choice
dc.subjectfairness
dc.subjectapproximation
dc.titleOn regular and approximately fair allocations of indivisible goods
dc.typeCommunication / Conférence
dc.contributor.editoruniversityotherSapienza Università di Roma
dc.description.abstractenAn active stream of research is devoted to the design of polynomial approximation algorithms for the fair allocation of indivisible goods. Central to this field is the MaxMin Allocation problem, for which there is a significant gap between known approximation and inapproximability results. Closing this gap is a stimulating challenge.To this end, we consider a regular version of MaxMin Allocation where each agent must receive exactly k goods, for a given integer k. We call this problem k-division. The analysis of this problem allows us to highlight two interesting features of the classical MaxMin Allocation problem. First, we show a close connection of the problem with matroid theory. This connection provides us an exact algorithm for a special case of k-division and a 1/k-approximation algorithm for general inputs. Moreover, we show that the difficulty of the MaxMin Allocation may be caught by an apparently simpler problem, namely the k-division problem in which an agent's utility for a single good can only take one value out of three.
dc.identifier.citationpages997-1004
dc.relation.ispartoftitleAAMAS '14 Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems
dc.relation.ispartofpublnameInternational Foundation for Autonomous Agents and Multiagent Systems
dc.relation.ispartofpublcityRichland
dc.relation.ispartofdate2014
dc.relation.ispartofpages997-1004
dc.relation.ispartofisbn978-1-4503-2738-1
dc.relation.conftitle2014 international conference on Autonomous agents and multi-agent systems (AAMAS '14 )
dc.relation.confdate2014-05
dc.relation.confcityParis
dc.relation.confcountryFrance
dc.relation.forthcomingnonen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewednon
dc.date.updated2016-02-22T11:54:03Z
hal.identifierhal-01288967*
hal.version1*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record