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