Strategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio
Abstract
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.
Cite
Text
Li et al. "Strategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio." International Joint Conference on Artificial Intelligence, 2020. doi:10.24963/IJCAI.2020/34Markdown
[Li et al. "Strategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio." International Joint Conference on Artificial Intelligence, 2020.](https://mlanthology.org/ijcai/2020/li2020ijcai-strategyproof/) doi:10.24963/IJCAI.2020/34BibTeX
@inproceedings{li2020ijcai-strategyproof,
title = {{Strategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio}},
author = {Li, Minming and Lu, Pinyan and Yao, Yuhao and Zhang, Jialin},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2020},
pages = {238-245},
doi = {10.24963/IJCAI.2020/34},
url = {https://mlanthology.org/ijcai/2020/li2020ijcai-strategyproof/}
}