• 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 - Request a copy

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érence
Date
2013
Conference title
9th International Conference on Web and Internet Economics , WINE 2013
Conference date
2013-12
Conference city
Cambridge MA
Conference country
United States
Book title
Web and Internet Economics 9th International Conference, WINE 2013, Cambridge, MA, USA, December 11-14, 2013, Proceedings
Book author
Chen, Yiling; Immorlica, Nicole
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
8289
Published in
Berlin
ISBN
978-3-642-45045-7
Number of pages
440
Pages
216-229
Publication identifier
10.1007/978-3-642-45046-4_18
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]
Monnot, Jérôme cc
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 allocation

Related items

Showing items related by title and author.

  • Thumbnail
    A parameterized approximation for matroids with multiple objectives 
    Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia (2013) Communication / Conférence
  • 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