文章基本信息

标题：Two-facility Location Games with Minimum Distance Requirement
本地全文：下载
作者：Xinping Xu ; Bo Li ; Minming Li 等
期刊名称：Journal of Artificial Intelligence Research
印刷版ISSN：1076-9757
出版年度：2021
卷号：70
页码：719-756
出版社：American Association of Artificial
摘要：We study the mechanism design problem of a social planner for locating two facilities on a line interval [0; 1]; where a set of n strategic agents report their locations and a mechanism determines the locations of the two facilities. We consider the requirement of a minimum distance 0 ≤ d ≤ 1 between the two facilities. Given the two facilities are heterogeneous; we model the cost/utility of an agent as the sum of his distances to both facilities. In the heterogeneous two-facility location game to minimize the social cost; we show that the optimal solution can be computed in polynomial time and prove that carefully choosing one optimal solution as output is strategyproof. We also design a strategyproof mechanism minimizing the maximum cost. Given the two facilities are homogeneous; we model the cost/utility of an agent as his distance to the closer facility. In the homogeneous two-facility location game for minimizing the social cost; we show that any deterministic strategyproof mechanism has unbounded approximation ratio. Moreover; in the obnoxious heterogeneous two-facility location game for maximizing the social utility; we propose new deterministic group strategyproof mechanisms with provable approximation ratios and establish a lower bound (7 − d)/6 for any deterministic strategyproof mechanism. We also design a strategyproof mechanism maximizing the minimum utility. In the obnoxious homogeneous two-facility location game for maximizing the social utility; we propose deterministic group strategyproof mechanisms with provable approximation ratios and establish a lower bound 4/3. Besides; in the two-facility location game with triple-preference; where each facility may be favorable; obnoxious; indifferent for any agent; we further motivate agents to report both their locations and preferences towards the two facilities truthfully; and design a deterministic group strategyproof mechanism with an approximation ratio 4.
关键词：game theory;preferences