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
TypeCommunication / Conférence
Conference title8th International Conference on Algorithms and Complexity, CIAC 2013
Book titleAlgorithms and Complexity 8th International Conference, CIAC 2013, Barcelona, Spain, May 22-24, 2013. Proceedings
Book authorSerna, Maria; Spirakis, Paul G.
MetadataShow full item record
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  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 / KeywordsAlgorithmic game theory; truthful mechanism without payment; approximation algorithm; many-to-many assignment problem
Showing items related by title and author.
Spanjaard, Olivier; Pascual, Fanny; Thang, Nguyen Kim; Gourvès, Laurent; Escoffier, Bruno (2011) Communication / Conférence
Spanjaard, Olivier; Pascual, Fanny; Nguyen Kim, Thang; Gourvès, Laurent; Escoffier, Bruno (2011) Communication / Conférence
Bazgan, Cristina; Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme; Pascual, Fanny; Vanderpooten, Daniel (2012) Communication / Conférence