What type of study is this?

This is a Quantitative Study study.

September 20, 2025

Improved Approximation Ratio for Strategyproof Facility Location on a Cycle

KRKrzysztof RogowskiBialystok University of Technology MDMarcin DziubińskiUniversity of Warsaw

Key Points

An approximation ratio of 7/4 is achieved for strategyproof mechanisms, improving previous limits.
This mechanism combines features of Random Dictator and Proportional Circle Distance mechanisms.
The underlying technique involves cycle-cutting to evaluate the problem's complexity more effectively.
Improved mechanisms may lead to reduced costs in facility location scenarios on cycles.

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.

Ask AI

Helpful

Bookmark

View Full Paper