Truthful Many-to-Many Assignment with Private Weights

摘要

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.