Mechanism Design for Facility Location with Fractional Preferences and Minimum Distance

In this paper, we study the mechanism design for two-facility-location games with the fractional preferences of agents, in which each agent has private information including her location in an interval [0, 1] and her fractional preference to indicate how much she prefers the two facilities. The decision maker needs to locate the two facilities to serve the agents, who has a utility equal to the interval length 1 minus the sum of weighted distances to both facilities. The facility locations are required to satisfy a minimum distance constraint, i.e., the distance of the two facilities must exceed a given number d∈ [ 0, 1 ]. The goal is to design strategy-proof mechanisms to maximize the social/minimum utility among the agents. We propose a randomized strategy-proof mechanism, which is 2-approximation for both objectives of maximizing the social utility and minimum utility. We also propose a deterministic strategy-proof mechanism which has an approximation ratio of 42-d and 4 for the two objectives, respectively. Furthermore, we derive corresponding lower bounds on the approximation ratios of strategy-proof mechanisms.