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≥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.
@inproceedings{rogowski2025,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={Kwok, James},pages={4032--4039},year={2025},month=aug,note={Main Track},doi={10.24963/ijcai.2025/449},url={https://doi.org/10.24963/ijcai.2025/449},}