Strategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio

Strategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio

Minming Li, Pinyan Lu, Yuhao Yao, Jialin Zhang

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 238-245. https://doi.org/10.24963/ijcai.2020/34

In this paper, we study the two-facility location game with optional preference where the acceptable set of facilities for each agent could be different and an agent's cost is his distance to the closest facility within his acceptable set. The objective is to minimize the total cost of all agents while achieving strategyproofness. For general metrics, we design a deterministic strategyproof mechanism for the problem with approximation ratio of 1+2alpha, where alpha is the approximation ratio of the optimization version. In particular, for the setting on a line, we improve the earlier best ratio of n/2+1 to a ratio of 2.75.
Keywords:
Agent-based and Multi-agent Systems: Algorithmic Game Theory
Agent-based and Multi-agent Systems: Computational Social Choice