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

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Worst case compromises in matroids with applications to the allocation of indivisible goods

Thumbnail
Date
2015
Dewey
Recherche opérationnelle
Sujet
Matroids; Allocation of indivisible goods; Worst case guarantees
JEL code
C.C4.C44
Journal issue
Theoretical Computer Science
Volume
589
Publication date
07-2015
Article pages
121-140
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.tcs.2015.04.029
URI
https://basepub.dauphine.fr/handle/123456789/16121
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Gourvès, Laurent
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Monnot, Jérôme
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Tlilane, Lydia
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Article accepté pour publication ou publié
Abstract (EN)
We 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.

  • 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

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.