Budgeted Facility Location Games with Strategic Facilities

Abstract

This paper studies the facility location games with payments, where facilities are strategic players. In the game, customers and facilities are located at publicly known locations on a line segment. Each selfish 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 to 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 study the case when augmented budget is allowed.