• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

Near Fairness in Matroids

Gourvès, Laurent; Tlilane, Lydia; Monnot, Jérôme (2014), Near Fairness in Matroids, in Schaub, Torsten, ECAI 2014 : 21st European Conference on Artificial Intelligence, 18-22 August 2014, Prague, Czech Republic : including Prestigious Applications of Artificial Intelligence (PAIS 2014), Systems : proceedings, IOS Press : Tokyo, p. 393-398

View/Open
FAIA263-0393.pdf (235.2Kb)
Type
Communication / Conférence
Date
2014
Conference title
ECAI 2014
Conference date
2014-08
Conference city
Prague
Conference country
Czech Republic
Book title
ECAI 2014 : 21st European Conference on Artificial Intelligence, 18-22 August 2014, Prague, Czech Republic : including Prestigious Applications of Artificial Intelligence (PAIS 2014), Systems : proceedings
Book author
Schaub, Torsten
Publisher
IOS Press
Published in
Tokyo
ISBN
978-1-61499-418-3
Pages
393-398
Metadata
Show full item record
Author(s)
Gourvès, Laurent

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Tlilane, Lydia
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]

Monnot, Jérôme cc

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
This article deals with the fair allocation of indivisible goods and its generalization to matroids. The notions of fairness under consideration are equitability, proportionality and envy-freeness. It is long known that some instances fail to admit a fair allocation. However, an almost fair solution may exist if an appropriate relaxation of the fairness condition is adopted. This article deals with a matroid problem which comprises the allocation of indivisible goods as a special case. It is to find a base of a matroid and to allocate it to a pool of agents. We first adapt the aforementioned fairness concepts to matroids. Next we propose a relaxed notion of fairness said to be near to fairness. Near fairness respects the fairness up to one element. We show that a nearly fair solution always exists and it can be constructed in polynomial time in the general context of matroids.
Subjects / Keywords
fair allocation; indivisible goods; matroids

Related items

Showing items related by title and author.

  • Thumbnail
    Worst case compromises in matroids with applications to the allocation of indivisible goods 
    Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2015) Article accepté pour publication ou publié
  • Thumbnail
    Approximation du point idéal dans des matroïdes: bornes et algorithmes 
    Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2013) Communication / Conférence
  • Thumbnail
    A matroid approach to the worst case allocation of indivisible goods 
    Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2013) Communication / Conférence
  • Thumbnail
    Approximate Tradeoffs on Matroids 
    Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2012) Communication / Conférence
  • Thumbnail
    Approximate tradeoffs on weighted labeled matroids 
    Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2015) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo