Metraipolis › archive › dc_61da27f1d623

Improved Randomized Approximations for Strategic Obnoxious Facility Location — arXiv:2609.07261

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.07261
License (as archived)
CC0-1.0
Archived
2026-10-16T13:30:07.691Z
SHA-256 of the archived text
2048fc2162261d6304ce56bb5cfcbc8ab57896de4ea04bc19d7e815b4bf59edc
Stable URL of this page
https://metraipolis.com/documento/dc_61da27f1d623

How to cite

Improved Randomized Approximations for Strategic Obnoxious Facility Location — arXiv:2609.07261 — arXiv (en), https://arxiv.org/abs/2609.07261 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_61da27f1d623 (Metraipolis archive dc_61da27f1d623, sha256 2048fc2162261d6304ce56bb5cfcbc8ab57896de4ea04bc19d7e815b4bf59edc)
BibTeX
@misc{dc61da27f1d623,
  title = {Improved Randomized Approximations for Strategic Obnoxious Facility Location — arXiv:2609.07261},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.07261},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_61da27f1d623; sha256 2048fc2162261d6304ce56bb5cfcbc8ab57896de4ea04bc19d7e815b4bf59edc},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.07261. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-09 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2609.07261 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T13:06:09.172Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).