We study the mechanism design of facility location problems.The problem is to design mechanisms to select a set of locations on which to build a set of facilities,aiming to optimize some system objective and achieve d...We study the mechanism design of facility location problems.The problem is to design mechanisms to select a set of locations on which to build a set of facilities,aiming to optimize some system objective and achieve desirable properties based on the strategic agents'locations.The agents might have incentives to misreport their private locations,in order to minimize the costs(i.e.,the distance from the closest facility).We study the setting with limited locations,that is,the facilities can only be built on a given finite set of candidate locations,rather than the whole space.For locating a single facility and two facilities on a real line,we propose strategyproof mechanisms with tight approximation ratios,under the objectives of minimizing the total cost and the maximum cost.Further,we consider the problem of locating an obnoxious facility from which the agents want to stay as far away as possible,and derive tight bounds on the approximation ratio of strategyproof mechanisms.展开更多
基金the National Natural Science Foundation of China(No.12101069)Innovation Foundation of BUPT for Youth(No.500421358)Ying-Chao Zhao was partially supported by the Research Grants Council of the HKSAR,China(No.UGC/FDS11/E03/21).
文摘We study the mechanism design of facility location problems.The problem is to design mechanisms to select a set of locations on which to build a set of facilities,aiming to optimize some system objective and achieve desirable properties based on the strategic agents'locations.The agents might have incentives to misreport their private locations,in order to minimize the costs(i.e.,the distance from the closest facility).We study the setting with limited locations,that is,the facilities can only be built on a given finite set of candidate locations,rather than the whole space.For locating a single facility and two facilities on a real line,we propose strategyproof mechanisms with tight approximation ratios,under the objectives of minimizing the total cost and the maximum cost.Further,we consider the problem of locating an obnoxious facility from which the agents want to stay as far away as possible,and derive tight bounds on the approximation ratio of strategyproof mechanisms.
