Mechanism Design for Reducing Agent Distances to Prelocated Facilities

We consider a variant of facility location problems where the facility is prelocated at a specific position to serve the agents who are located on a real line. Because the facility cannot be relocated due to various constraints (e.g., construction costs and requirements), the social planner considers the structural modification problem of adding short-cut edges to the real line (e.g., shuttles between pairs of locations) for improving the accessibility or reducing costs of the agents to the facility, where the cost of an agent is measured by their shortest distance to the facility possibly using the short-cut edges. We focus on the mechanism design aspects of the problems where the agents' locations are private. We propose several strategy-proof mechanisms that elicit true agent locations and minimize the total or maximum cost of agents. We provide approximation ratios for these mechanisms and lower bounds on the approximation ratios for total or maximum cost. © 2024 International Foundation for Autonomous Agents and Multiagent Systems.