We study the problem of locating a new homogeneous facility under a prelocated facility. Here, a set of n agents is located on a real line or a circle, each of whom has her location as private information, and her cost is the (expected) distance from her location to the nearest facility. Our goal is to design mechanisms which can approximately minimize the maximum cost or the social cost while eliciting agents’ private information truthfully (i.e., strategy-proof). Based on real-life scenarios, we consider the problem in two settings: the general setting where each agent can be located at both sides of the prelocated facility, and the special setting where all agents are located at the same side of the prelocated facility. For agents on a line, in the general setting, we design the best possible deterministic strategy-proof mechanism with 2-approximation and provide a lower bound of \(1.5-\epsilon (\epsilon >0)\) for any randomized strategy-proof mechanism under the maximum cost objective. For the social cost, we obtain an upper bound of n for deterministic strategy-proof mechanisms and lower bounds of 1.5 and 1.0425 for any deterministic strategy-proof mechanism and any randomized strategy-proof mechanism, respectively. In the special setting, we further provide a randomized strategy-proof 5/3-approximation mechanism for the maximum cost and a deterministic strategy-proof \((n-1)\) -approximation mechanism for the social cost. For agents on a circle, we provide a deterministic strategy-proof 2-approximation mechanism under the maximum cost objective. We further introduce a performance measure for mechanisms in facility location problems with prelocated facilities, called the improvement ratio, which is defined as the worst ratio between the improvement achieved by a mechanism and the best possible improvement after adding a new facility. For the maximum cost, we derive tight bounds of 1.5 for deterministic mechanisms in the general setting, and an upper bound of \(\frac{15}{13}\) for randomized mechanisms in the special setting. For the social cost, we provide an upper bound of \(\frac{n}{2}\) in the special setting.
