Facility Location with Public Locations and Private Doubly-Peaked Costs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913856000884736 |
|---|---|
| author | Cole, Richard Jangir, Pranav |
| author_facet | Cole, Richard Jangir, Pranav |
| contents | In the facility location problem, the task is to place one or more facilities so as to minimize the sum of the agent costs for accessing their nearest facility. Heretofore, in the strategic version, agent locations have been assumed to be private, while their cost measures have been public and identical.
For the most part, the cost measure has been the distance to the nearest facility.
However, in multiple natural settings, such as placing a firehouse or a school, this modeling does not appear to be a good fit. For it seems natural that the agent locations would be known, but their costs might be private information. In addition, for these types of settings, agents may well want the nearest facility to be at the right distance: near, but not too near. This is captured by the doubly-peaked cost introduced by Filos-Ratsikas et al. (AAMAS 2017).
In this paper, we re-examine the facility location problem from this perspective: known agent locations and private preferred distances to the nearest facility.
We then give lower and upper bounds on achievable approximations, focusing on the problem in 1D, and in 2D with an $L_1$ distance measure. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_18114 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Facility Location with Public Locations and Private Doubly-Peaked Costs Cole, Richard Jangir, Pranav Computer Science and Game Theory Multiagent Systems In the facility location problem, the task is to place one or more facilities so as to minimize the sum of the agent costs for accessing their nearest facility. Heretofore, in the strategic version, agent locations have been assumed to be private, while their cost measures have been public and identical. For the most part, the cost measure has been the distance to the nearest facility. However, in multiple natural settings, such as placing a firehouse or a school, this modeling does not appear to be a good fit. For it seems natural that the agent locations would be known, but their costs might be private information. In addition, for these types of settings, agents may well want the nearest facility to be at the right distance: near, but not too near. This is captured by the doubly-peaked cost introduced by Filos-Ratsikas et al. (AAMAS 2017). In this paper, we re-examine the facility location problem from this perspective: known agent locations and private preferred distances to the nearest facility. We then give lower and upper bounds on achievable approximations, focusing on the problem in 1D, and in 2D with an $L_1$ distance measure. |
| title | Facility Location with Public Locations and Private Doubly-Peaked Costs |
| topic | Computer Science and Game Theory Multiagent Systems |
| url | https://arxiv.org/abs/2505.18114 |