• 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

A Protocol for Cutting Matroids Like Cakes

Thumbnail
Date
2013
Collection title
Lecture Notes in Computer Science
Collection Id
8289
Dewey
Programmation, logiciels, organisation des données
Sujet
matroids; indivisible goods; fair allocation
DOI
http://dx.doi.org/10.1007/978-3-642-45046-4_18
Conference name
9th International Conference on Web and Internet Economics , WINE 2013
Conference date
12-2013
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
Author
Chen, Yiling; Immorlica, Nicole
Publisher
Springer
Publisher city
Berlin
Year
2013
Pages number
440
ISBN
978-3-642-45045-7
Book URL
http://dx.doi.org/10.1007/978-3-642-45046-4
URI
https://basepub.dauphine.fr/handle/123456789/14938
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
Communication / Conférence
Item number of pages
216-229
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].

  • 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.