• 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

Truthful Many-to-Many Assignment with Private Weights

Escoffier, Bruno; Monnot, Jérôme; Pascual, Fanny; Spanjaard, Olivier (2013), Truthful Many-to-Many Assignment with Private Weights, in Serna, Maria; Spirakis, Paul G., Algorithms and Complexity 8th International Conference, CIAC 2013, Barcelona, Spain, May 22-24, 2013. Proceedings, Springer : Berlin, p. 209-220. 10.1007/978-3-642-38233-8_18

View/Open
bejmfposCIAC2013.pdf (181.0Kb)
Type
Communication / Conférence
Date
2013
Conference title
8th International Conference on Algorithms and Complexity, CIAC 2013
Conference date
2013-05
Conference city
Barcelone
Conference country
Spain
Book title
Algorithms and Complexity 8th International Conference, CIAC 2013, Barcelona, Spain, May 22-24, 2013. Proceedings
Book author
Serna, Maria; Spirakis, Paul G.
Publisher
Springer
Published in
Berlin
ISBN
978-3-642-38232-1
Pages
209-220
Publication identifier
10.1007/978-3-642-38233-8_18
Metadata
Show full item record
Author(s)
Escoffier, Bruno

Monnot, Jérôme cc

Pascual, Fanny

Spanjaard, Olivier
Abstract (EN)
This paper is devoted to the study of truthful mechanisms without payment for the many-to-many assignment problem. Given n agents and m tasks, a mechanism is truthful if no agent has an incentive to misreport her values on the tasks (agent a i reports a score w ij for each task t j ). The one-to-one version of this problem has already been studied by Dughmi and Ghosh [4] in a setting where the weights w ij are public knowledge, and the agents only report the tasks they are able to perform. We study here the case where the weights are private data. We are interested in the best approximation ratios that can be achieved by a truthful mechanism. In particular, we investigate the problem under various assumptions on the way the agents can misreport the weights.
Subjects / Keywords
Algorithmic game theory; truthful mechanism without payment; approximation algorithm; many-to-many assignment problem

Related items

Showing items related by title and author.

  • Thumbnail
    Strategy-Proof Mechanisms for Facility Location Games with Many Facilities 
    Spanjaard, Olivier; Pascual, Fanny; Thang, Nguyen Kim; Gourvès, Laurent; Escoffier, Bruno (2011) Communication / Conférence
  • Thumbnail
    Algorithmes à véracité garantie pour des problèmes de b‐couplage dans un graphe biparti 
    Escoffier, Bruno; Monnot, Jérôme; Pascual, Fanny; Spanjaard, Olivier (2013) Communication / Conférence
  • Thumbnail
    Algorithmes à véracité garantie pour le placement d'installations sur une ligne 
    Spanjaard, Olivier; Pascual, Fanny; Nguyen Kim, Thang; Gourvès, Laurent; Escoffier, Bruno (2011) Communication / Conférence
  • Thumbnail
    Solutions équitables approchées pour divers problèmes d’optimisation combinatoire 
    Bazgan, Cristina; Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme; Pascual, Fanny; Vanderpooten, Daniel (2012) Communication / Conférence
  • Thumbnail
    Some tractable instances of interval data minmax regret problems: bounded distance from triviality 
    Escoffier, Bruno; Monnot, Jérôme; Spanjaard, Olivier (2008) Communication / Conférence
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