Qin et al. prove optimal bridge location with strategyproof mechanisms

This paper, submitted to arXiv on July 5, 2026, tackles the problem of where to place a bridge connecting two separate regions (e.g., across a river or highway) when each region already has a facility. Agents in each region have private locations and must travel to the nearest facility via the bridge, incurring cost equal to total distance traveled. The authors, Genjie Qin, Chenhao Wang, Jianan Lin, Qizhi Fang, and Wenjing Liu, design mechanisms that are strategyproof (SP), meaning agents cannot benefit by misreporting their locations.

Key results include characterizations and approximation guarantees. For minimizing maximum cost, the optimal solution is group-strategyproof (GSP). Under the stronger SGSP notion, they propose a deterministic 3-approximation and a randomized 2-approximation, with a lower bound of 2 for deterministic SGSP. For social cost minimization, they achieve deterministic 3-approx and randomized 2-approx under GSP, with lower bounds of 2 (deterministic) and 1.1 (randomized). Under SGSP, the deterministic lower bound rises to 1+min(m,n), and they provide a (1+2min(m,n))-approx mechanism. These results have direct implications for urban planning, traffic management, and facility location theory.