Strategyproof Facility Location for Five Agents on a Circle using PCD
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_ | 1866909857783742464 |
|---|---|
| author | Farjoun, Ido Meir, Reshef |
| author_facet | Farjoun, Ido Meir, Reshef |
| contents | We consider the strategyproof facility location problem on a circle. We focus on the case of 5 agents, and find a tight bound for the PCD strategyproof mechanism, which selects the reported location of an agent in proportion to the length of the arc in front of it. We methodically "reduce" the size of the instance space and then use standard optimization techniques to find and prove the bound is tight. Moreover we hypothesize the approximation ratio of PCD for general odd $n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_17435 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Strategyproof Facility Location for Five Agents on a Circle using PCD Farjoun, Ido Meir, Reshef Multiagent Systems We consider the strategyproof facility location problem on a circle. We focus on the case of 5 agents, and find a tight bound for the PCD strategyproof mechanism, which selects the reported location of an agent in proportion to the length of the arc in front of it. We methodically "reduce" the size of the instance space and then use standard optimization techniques to find and prove the bound is tight. Moreover we hypothesize the approximation ratio of PCD for general odd $n$. |
| title | Strategyproof Facility Location for Five Agents on a Circle using PCD |
| topic | Multiagent Systems |
| url | https://arxiv.org/abs/2510.17435 |