Heterogeneous facility location without money

摘要: The study of the facility location problem in presence self-interested agents has recently emerged as benchmark research on mechanism design without money. In setting studied literature so far, are single-parameter that their type is a single number encoding position real line. We here initiate more realistic model for several real-life scenarios. Specifically, we propose and analyze heterogeneous money, novel wherein: (i) have multiple (i.e., serving different purposes) facilities, (ii) agents' locations disclosed to (iii) bid set facilities they interested (as opposed bidding network).We under two objective functions, namely: social cost sum all costs) maximum cost. For either function, approximation ratio both deterministic randomized truthful algorithms simplifying assumption underlying network topology devise an ( n - 1 ) -approximate prove constant lower bound. Furthermore, optimal (in expectation) algorithm. As regards 3-approximate strategyproof algorithm, 3/2 bound mechanisms. 3/2-approximate algorithm 4/3 algorithms.