Truthful Two-Obnoxious-Facility Location Games with Optional Preferences and Minimum Distance Constraint
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913984610828288 |
|---|---|
| author | Han, Xiaojia Liu, Wenjing Fang, Qizhi |
| author_facet | Han, Xiaojia Liu, Wenjing Fang, Qizhi |
| contents | In this paper, we study a truthful two-obnoxious-facility location problem, in which each agent has a private location in [0, 1] and a public optional preference over two obnoxious facilities, and there is a minimum distance constraint d between the two facilities. Each agent wants to be as far away as possible from the facilities that affect her, and the utility of each agent is the total distance from her to these facilities. The goal is to decide how to place the facilities in [0, 1] so as to incentivize agents to report their private locations truthfully as well as maximize the social utility. First, we consider the special setting where d = 0, that is, the two facilities can be located at any point in [0, 1]. We propose a deterministic strategyproof mechanism with approximation ratio of at most 4 and a randomized strategyproof mechanism with approximation ratio of at most 2, respectively. Then we study the general setting. We propose a deterministic strategyproof mechanism with approximation ratio of at most 8 and a randomized strategyproof mechanism with approximation ratio of at most 4, respectively. Furthermore, we provide lower bounds of 2 and 14/13 on the approximation ratio for any deterministic and any randomized strategyproof mechanism, respectively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_08036 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Truthful Two-Obnoxious-Facility Location Games with Optional Preferences and Minimum Distance Constraint Han, Xiaojia Liu, Wenjing Fang, Qizhi Computer Science and Game Theory In this paper, we study a truthful two-obnoxious-facility location problem, in which each agent has a private location in [0, 1] and a public optional preference over two obnoxious facilities, and there is a minimum distance constraint d between the two facilities. Each agent wants to be as far away as possible from the facilities that affect her, and the utility of each agent is the total distance from her to these facilities. The goal is to decide how to place the facilities in [0, 1] so as to incentivize agents to report their private locations truthfully as well as maximize the social utility. First, we consider the special setting where d = 0, that is, the two facilities can be located at any point in [0, 1]. We propose a deterministic strategyproof mechanism with approximation ratio of at most 4 and a randomized strategyproof mechanism with approximation ratio of at most 2, respectively. Then we study the general setting. We propose a deterministic strategyproof mechanism with approximation ratio of at most 8 and a randomized strategyproof mechanism with approximation ratio of at most 4, respectively. Furthermore, we provide lower bounds of 2 and 14/13 on the approximation ratio for any deterministic and any randomized strategyproof mechanism, respectively. |
| title | Truthful Two-Obnoxious-Facility Location Games with Optional Preferences and Minimum Distance Constraint |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2508.08036 |