Improved Approximation Ratio for Strategyproof Facility Location on a Cycle
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_ | 1866918025152692224 |
|---|---|
| author | Rogowski, Krzysztof Dziubiński, Marcin |
| author_facet | Rogowski, Krzysztof Dziubiński, Marcin |
| contents | We study the problem of design of strategyproof in expectation (SP) mechanisms for facility location on a cycle, with the objective of minimizing the sum of costs of $n$ agents. We show that there exists an SP mechanism that attains an approximation ratio of $7/4$ with respect to the sum of costs of the agents, thus improving the best known upper bound of $2-2/n$ in the cases of $n \geq 5$. The mechanism obtaining the bound randomizes between two mechanisms known in the literature: the Random Dictator (RD) and the Proportional Circle Distance (PCD) mechanism of Meir (arXiv:1902.08070). To prove the result, we propose a cycle-cutting technique that allows for estimating the problem on a cycle by a problem on a line. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_12943 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved Approximation Ratio for Strategyproof Facility Location on a Cycle Rogowski, Krzysztof Dziubiński, Marcin Computer Science and Game Theory 91B26 (Primary) 68Q25, 91A80 (Secondary) F.2.2; I.2.11 We study the problem of design of strategyproof in expectation (SP) mechanisms for facility location on a cycle, with the objective of minimizing the sum of costs of $n$ agents. We show that there exists an SP mechanism that attains an approximation ratio of $7/4$ with respect to the sum of costs of the agents, thus improving the best known upper bound of $2-2/n$ in the cases of $n \geq 5$. The mechanism obtaining the bound randomizes between two mechanisms known in the literature: the Random Dictator (RD) and the Proportional Circle Distance (PCD) mechanism of Meir (arXiv:1902.08070). To prove the result, we propose a cycle-cutting technique that allows for estimating the problem on a cycle by a problem on a line. |
| title | Improved Approximation Ratio for Strategyproof Facility Location on a Cycle |
| topic | Computer Science and Game Theory 91B26 (Primary) 68Q25, 91A80 (Secondary) F.2.2; I.2.11 |
| url | https://arxiv.org/abs/2505.12943 |