Improved strategies for fair and random obnoxious facility placement
Improved Randomized Approximations for Strategic Obnoxious Facility Location
Computer Science and Game Theory
Summary
This paper looks at how to fairly decide where to put a facility along a line when people want it as far away from them as possible. The authors propose better random methods that improve fairness and efficiency compared to older ones. They show their methods work closer to the best possible fairness and prove limits on how good any method can be. These results help understand the best ways to balance people’s competing interests in facility placement.
What this means in practice
- •For urban planners: Apply randomized algorithms to decide facility locations like waste sites or noisy equipment that residents want far away, ensuring fair distance outcomes.
- •For network designers: Use improved strategyproof mechanisms to place network elements that users prefer to be distant from due to interference or privacy concerns.
A theory result. No direct application yet.
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.