Show simple item record

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
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorTlilane, Lydia
dc.date.accessioned2017-01-04T16:29:51Z
dc.date.available2017-01-04T16:29:51Z
dc.date.issued2015
dc.identifier.issn0304-3975
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16121
dc.language.isoenen
dc.subjectMatroidsen
dc.subjectAllocation of indivisible goodsen
dc.subjectWorst case guaranteesen
dc.subject.ddc003en
dc.subject.classificationjelC.C4.C44en
dc.titleWorst case compromises in matroids with applications to the allocation of indivisible goodsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe consider the problem of equitably allocating a set of indivisible goods to n agents with additive utilities so as to provide worst case guarantees on agents' utilities. Demko and Hill [6] showed the existence of an allocation where every agent values his share at least Vn(α)Vn(α), which is a family of nonincreasing functions of α, defined as the maximum value assigned by an agent to a single good. A deterministic algorithm returning such an allocation in polynomial time was proposed in [15]. Interestingly, Vn(α)Vn(α) is tight for some values of α, i.e. it matches the highest possible utility of the least happy agent. However, this is not true for all values of α . We propose a family of functions WnWn such that Wn(x)≥Vn(x)Wn(x)≥Vn(x) for all x , and Wn(x)>Vn(x)Wn(x)>Vn(x) for values of x where Vn(x)Vn(x) is not tight. The functions WnWn apply on a problem that generalizes the allocation of indivisible goods. It is to find a base in a matroid which is common to n agents. Our results are constructive, they are achieved by analyzing an extension of the algorithm of Markakis and Psomas. We also present an upper bound on the utility of the least happy agent.en
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol589en
dc.relation.isversionofjnldate2015-07
dc.relation.isversionofjnlpages121-140en
dc.relation.isversionofdoi10.1016/j.tcs.2015.04.029en
dc.relation.isversionofjnlpublisherElsevieren
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.updated2017-01-03T13:55:15Z
hal.identifierhal-01426651*
hal.version1*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record