Mechanism Design for Improving Accessibility to Public Facilities

We consider a variant of the facility location problems where agents are located on a real line and the facility is fixed at a designated location to serve the agents. As the facility cannot be relocated due to various constraints (e.g., construction costs and regulatory requirements), the social planner considers the structural modification problem of adding a shortcut edge to the real line for improving the accessibility or costs of the agents to the facility, where the cost of an agent is measured by their shortest distance to the facility. For a mechanism design version of the structural modification problem where the agents are assumed to have private locations, we propose several strategy-proof mechanisms to elicit truthful locations from the agents and add a shortcut edge to (approximately) minimize the total cost or maximum cost of agents. We derive the upper bounds of these mechanisms and provide lower bounds on the approximation ratios for both objectives.