Budget feasible mechanisms for facility location games with strategic facilities

摘要

This paper studies the facility location game with payments, in which customers and facilities are located at publicly known locations on a line segment, and the facilities are strategic players. Each facility has an opening-cost as her private information, and she may strategically report it. Upon receiving the reports, the government uses a mechanism to select some facilities to open and pay them. The cost/utility of each customer depends on the distance to the nearest opened facility. Under a given budget B, which constrains the total payment, we derive upper and lower bounds on the approximation ratios of truthful budget feasible mechanisms for four utilitarian and egalitarian objectives, and investigate the case when augmented budget is allowed.