Strategyproof ways to connect regions separated by obstacles on a line
Strategyproof Mechanisms for Connecting Impassable Regions
Computer Science and Game Theory
Summary
This paper looks at how to build a pathway connecting two parts of a line separated by a block, where each person involved starts in a private spot. The authors want ways to build this path that prevent people from lying about their locations to get a better route. They find exact mathematical limits on how well such fair and truthful methods can do when minimizing the longest travel time or the total travel time. They also explore random approaches that give some flexibility and improve those limits. Finally, they improve previous results from similar problems on a line.
strategyproofnessgroup-strategyproofnessapproximation ratiomechanism designsocial costmaximum costrandomized mechanismsfacility locationprivate information
Authors
Hau Chan, Jianan Lin, Chenhao Wang
Abstract
We study strategyproof mechanisms for building a pathway between two regions of a line segment separated by an obstacle. Each of the $n$ agents has a private location within its region and may use either its original route to a facility or the new pathway, whose traversal cost is a fraction $k\in[0,1)$ of its length. We seek strategyproof (SP) and group-strategyproof (GSP) mechanisms that approximately minimize maximum cost or social cost. After characterizing optimal pathways for both objectives, we establish a tight deterministic maximum-cost approximation ratio of $\frac{2}{1+k}$ and a deterministic social-cost upper bound of $\frac{n}{1+k(n-1)}$, together with complementary lower bounds. Both upper bounds are achieved by GSP mechanisms. We then study randomized mechanisms under strategyproofness in expectation. A power-proportional mechanism achieves a social-cost approximation ratio at most $5$, independent of $n$ and $k$, with a tight guarantee of $3$ for this mechanism when $k=0$. We prove randomized lower bounds of $\frac{3+2k}{2+3k}$ for maximum cost and $\max\big\{1,\frac{285}{263+385k}\big\}$ for social cost, the latter for $n\ge7$. Finally, we improve several bounds for the real-line pathway model of [Chan and Wang, AAMAS 2023]. Our deterministic maximum-cost lower bound of $2$ matches the upper bound obtainable from [Qin, Fang, and Liu, COCOA 2024]. We strengthen the deterministic social-cost lower bound from $\frac32$ to $2$ under SP and to $\max\{2,n-1\}$ under GSP. For randomized social cost, we sharpen the guarantee of Chan and Wang's proportional mechanism from $6$ to $3$ and raise their lower bound from $1.02$ to $\frac{285}{263}\approx1.08365$ for $n\ge7$.