Improved methods boost fairness in placing unpleasant facilities on a line
Improved Randomized Approximations for Strategic Obnoxious Facility Location
Computer Science and Game Theory
Summary
This work looks at how to fairly place a facility that everyone wants to be far away from, like a noisy plant, along a straight line. The authors improve ways to decide where to put it using random choices that keep people honest about their preferences. They find better ways to get close to the best overall happiness and ensure the least satisfied person isn't left too unhappy. They also show limits on how good any method can be when people might lie about where they are. Overall, their techniques give better guarantees than earlier ones.
obnoxious facility locationstrategyproof mechanismrandomized algorithmsapproximation ratiosocial utilityminimum utilitytruthfulness in mechanism designasymptotic boundsagent preferences
Authors
Hau Chan, Jianan Lin, Chenhao Wang
Abstract
We study randomized strategyproof mechanisms for strategic obnoxious facility location on a line segment, where agents wish the facility to be located as far away from them as possible and their utility is their distance from the facility, under the social utility and minimum utility objectives. For social utility, we propose a novel randomized mechanism that breaks the previously best known \(\frac32\)-approximation of [Cheng, Yu, and Zhang, TCS 2013], achieving an approximation ratio of at most \(1.47359\). We also raise the lower bound on the approximation ratio of randomized strategyproof mechanisms from \(\frac{2}{\sqrt{3}}\approx1.15470\) [Feigenbaum et al., JAAMAS 2020] to \(\frac{105}{88}\approx1.19318\). For minimum utility, following the profile-independent approach of [Chan, Lin and Wang, AAMAS 2026], we design a simple randomized mechanism that reduces the approximation guarantee from \(\sqrt{2n}+O(1)\) to \(\sqrt n+O(1)\), where \(n\) is the number of agents. Finally, we prove that no randomized strategyproof mechanism can achieve an asymptotic approximation ratio strictly smaller than \(2\), strengthening the previous asymptotic lower bound of \(\frac32\) [Feigenbaum et al., JAAMAS 2020]. Thus, all four bounds considered in this paper strictly improve upon the corresponding previously known results.