Mechanism Design for Building Optimal Bridges Between Regions

We study the bridge-building problem from the mechanism design perspective. In this problem, a social planner is tasked with building a bridge to connect two regions separated by an obstacle (e.g., a river or valley). Each agent in a region has a private location and is interested in traveling to a facility (e.g., a transportation hub) in the other region. The cost of an agent with respect to a bridge is the distance from their location to the facility of interest via the bridge. Our goal is to design strategy-proof mechanisms that elicit truthful locations from the agents and approximately optimize an objective by determining a location for building a bridge. We consider the social cost and maximum cost objectives, which are the total cost and maximum cost of agents, respectively. For the social cost objective, we characterize an optimal solution and show that it is strategy-proof. For the maximum cost objective, any optimal solution is no longer strategy-proof. We present deterministic \(\frac{5}{3}\)-approximation and randomized \(\frac{3}{2}\)-approximation strategy-proof mechanisms. We complement the results by providing tight lower bounds.