Show simple item record

A matroid approach to the worst case allocation of indivisible goods

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.accessioned2015-04-14T17:20:33Z
dc.date.available2015-04-14T17:20:33Z
dc.date.issued2013
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/14935
dc.language.isoenen
dc.subjectmatroidsen
dc.subjectindivisible goodsen
dc.subject.ddc006.3en
dc.titleA matroid approach to the worst case allocation of indivisible goodsen
dc.typeCommunication / Conférence
dc.description.abstractenWe consider the problem of equitably allocating a set of indivisible goods to n agents so as to maximize the utility of the least happy agent. [Demko and Hill, 1988] showed the existence of an allocation where every agent values his share at least Vn(α), which is a family of nonincreasing functions in a parameter α, 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 [Markakis and Psomas, 2011]. Interestingly, Vn(α) is tight for some values of α, i.e. it is the best lower bound on the valuation of the least happy agent. However, it is not true for all values of α. We propose a family of functions Wn such that Wn(x) ≥ Vn(x) for all x, and Wn(x) > Vn(x) for values of x where Vn(x) is not tight. The new functions Wn apply on a problem which generalizes the allocation of indivisible goods. It is to find a solution (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.en
dc.identifier.citationpages136-142en
dc.relation.ispartoftitleIJCAI '13 Proceedings of the Twenty-Third international joint conference on Artificial Intelligenceen
dc.relation.ispartofeditorRossi, Francesca
dc.relation.ispartofpublnameAAAI Pressen
dc.relation.ispartofdate2013
dc.subject.ddclabelIntelligence artificielleen
dc.relation.ispartofisbn978-1-57735-633-2en
dc.relation.conftitle23rd international joint conference on Artificial Intelligence (IJCAI 2013)en
dc.relation.confdate2013-08
dc.relation.confcityBeijingen
dc.relation.confcountryChinaen
dc.relation.forthcomingnonen
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.identifierhal-01508755*
hal.version1*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
IJCAI13-030.pdf
Size:
560.0Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record