2025/05/19 by Krzysztof Rogowski, Rogowski, Krzysztof, Marcin Dziubiński +1 · 1 citation
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #91A80 (Secondary) #91B26 (Primary) 68Q25 #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Constraint Satisfaction and Optimization #F.2.2 #FOS: Computer and information sciences #Game Theory and Voting Systems #I.2.11
paper · pdf · doi:10.48550/arxiv.2505.12943
openalex publication_date 2025/05/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 (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.