---
title: "Improved Approximation Ratio for Strategyproof Facility Location on a Cycle"
authors:
  - "Krzysztof Rogowski"
  - "Marcin Dziubiński"
doi: "10.24963/ijcai.2025/449"
url: "https://ijcai.org/proceedings/2025/449"
pdf: "https://ijcai.org/proceedings/2025/0449.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "4032-4039"
track: "Main Track"
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"
---

# Improved Approximation Ratio for Strategyproof Facility Location on a Cycle

Krzysztof Rogowski, Marcin Dziubiński

*Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence*, pages 4032-4039. DOI: [10.24963/ijcai.2025/449](https://doi.org/10.24963/ijcai.2025/449)

## 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.