Truthful Mechanisms for the Location of Different Facilities

In this paper we formalize and initiate the study of heterogeneous k-facility location without money, a problem akin to the classical k-facility location problem but encompassing a richer model and featuring multi-parameter agents. In particular, we consider truthful mechanisms without money for the problem in which heterogeneous (i.e. serving different purposes) facilities have to be located and agents are only interested in some of them. We study the approximation factor that can be achieved by truthful mechanisms in this setting and present some bounds which make a surprising parallel with our knowledge of truthfulness for the classical single-dimensional facility location problem.