
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
Type
Communication / ConférenceDate
2014Conference title
ECAI 2014Conference date
2014-08Conference city
PragueConference country
Czech RepublicBook 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 : proceedingsBook author
Schaub, TorstenPublisher
IOS Press
Published in
Tokyo
ISBN
978-1-61499-418-3
Pages
393-398
Metadata
Show full item recordAuthor(s)
Gourvès, LaurentLaboratoire 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

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; matroidsRelated items
Showing items related by title and author.
-
Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2015) Article accepté pour publication ou publié
-
Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2013) Communication / Conférence
-
Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2013) Communication / Conférence
-
Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2012) Communication / Conférence
-
Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2015) Article accepté pour publication ou publié