Improved Approximation Ratio for Strategyproof Facility Location on a Cycle

Rogowski, Krzysztof; Dziubiński, Marcin

doi:10.24963/ijcai.2025/449

Improved Approximation Ratio for Strategyproof Facility Location on a Cycle

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 4032-4039.

https://doi.org/10.24963/ijcai.2025/449

Keywords

Game Theory and Economic Paradigms: GTEP: Mechanism design
Multidisciplinary Topics and Applications: MTA: Economics
Game Theory and Economic Paradigms: GTEP: Auctions and market-based systems
Game Theory and Economic Paradigms: GTEP: Noncooperative games

Abstract

We study the problem of design of strategy-proof 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 ≥ 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 (2019). 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.

Krzysztof Rogowski, and Marcin Dziubiński. 2025. Improved Approximation Ratio for Strategyproof Facility Location on a Cycle. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 4032–4039. https://doi.org/10.24963/ijcai.2025/449

@inproceedings{ijcai2025p449,
  title     = {Improved Approximation Ratio for Strategyproof Facility Location on a Cycle},
  author    = {Rogowski, Krzysztof and Dziubiński, Marcin},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {4032--4039},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/449},
  url       = {https://doi.org/10.24963/ijcai.2025/449},
}

TY  - CPAPER
TI  - Improved Approximation Ratio for Strategyproof Facility Location on a Cycle
AU  - Rogowski, Krzysztof
AU  - Dziubiński, Marcin
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 4032
EP  - 4039
DO  - 10.24963/ijcai.2025/449
UR  - https://doi.org/10.24963/ijcai.2025/449
ER  -