A Protocol for Cutting Matroids Like Cakes
Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2013), A Protocol for Cutting Matroids Like Cakes, in Chen, Yiling; Immorlica, Nicole, Web and Internet Economics 9th International Conference, WINE 2013, Cambridge, MA, USA, December 11-14, 2013, Proceedings, Springer : Berlin, p. 216-229. 10.1007/978-3-642-45046-4_18
Type
Communication / ConférenceDate
2013Conference title
9th International Conference on Web and Internet Economics , WINE 2013Conference date
2013-12Conference city
Cambridge MAConference country
United StatesBook title
Web and Internet Economics 9th International Conference, WINE 2013, Cambridge, MA, USA, December 11-14, 2013, ProceedingsBook author
Chen, Yiling; Immorlica, NicolePublisher
Springer
Series title
Lecture Notes in Computer ScienceSeries number
8289Published in
Berlin
ISBN
978-3-642-45045-7
Number of pages
440Pages
216-229
Publication identifier
Metadata
Show full item recordAuthor(s)
Gourvès, LaurentLaboratoire 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]
Tlilane, Lydia
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
We study a problem that generalizes the fair allocation of indivisible goods. The input is a matroid and a set of agents. Each agent has his own utility for every element of the matroid. Our goal is to build a base of the matroid and provide worst case guarantees on the additive utilities of the agents. These utilities are private, an assumption that is commonly made for the fair division of divisible resources, Since the use of an algorithm is not appropriate in this context, we resort to protocols, like in cake cutting problems. Our contribution is a protocol where the agents can interact and build a base of the matroid. If there are up to 8 agents, we show how everyone can ensure that his worst case utility for the resulting base is the same as those given by Markakis and Psomas [18] for the fair allocation of indivisible goods, based on the guarantees of Demko and Hill [8].Subjects / Keywords
matroids; indivisible goods; fair allocationRelated items
Showing items related by title and author.
-
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 (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é