TY - JOUR
T1 - Facility location games with optional preference
AU - Chen, Zhihuai
AU - Fong, Ken C.K.
AU - Li, Minming
AU - Wang, Kai
AU - Yuan, Hongning
AU - Zhang, Yong
PY - 2020/12/22
Y1 - 2020/12/22
N2 - In this paper, we study the optional preference model of the facility location game problem with two heterogeneous facilities on a line. The preference of each agent is one of the two facilities or both facilities, and the cost of each agent is a function of the distances to the facilities that the agent prefers. We consider two cost functions: Minimum Distance and Maximum Distance functions. Aiming at minimizing the maximum cost or the social cost of agents, we propose different strategyproof mechanisms without monetary transfers and derive both lower and upper bounds of the approximation ratios with respect to strategyproof mechanisms. In the variant of Minimum Distance, we propose a 2-approximation deterministic strategyproof mechanism for the maximum cost objective, and prove a lower bound of 4/3, while for the social cost objective we propose a (n/2+1)-approximation deterministic strategyproof mechanism and prove a lower bound of 2, also a lower bound of 3/2 for randomized mechanisms. In the variant of Maximum Distance, we propose an optimal deterministic strategyproof mechanism for the maximum cost objective and a 2-approximation deterministic strategyproof mechanism for the social cost objective.
AB - In this paper, we study the optional preference model of the facility location game problem with two heterogeneous facilities on a line. The preference of each agent is one of the two facilities or both facilities, and the cost of each agent is a function of the distances to the facilities that the agent prefers. We consider two cost functions: Minimum Distance and Maximum Distance functions. Aiming at minimizing the maximum cost or the social cost of agents, we propose different strategyproof mechanisms without monetary transfers and derive both lower and upper bounds of the approximation ratios with respect to strategyproof mechanisms. In the variant of Minimum Distance, we propose a 2-approximation deterministic strategyproof mechanism for the maximum cost objective, and prove a lower bound of 4/3, while for the social cost objective we propose a (n/2+1)-approximation deterministic strategyproof mechanism and prove a lower bound of 2, also a lower bound of 3/2 for randomized mechanisms. In the variant of Maximum Distance, we propose an optimal deterministic strategyproof mechanism for the maximum cost objective and a 2-approximation deterministic strategyproof mechanism for the social cost objective.
KW - Algorithmic mechanism design
KW - Approximation
KW - Facility location game
KW - Game theory
KW - Algorithmic mechanism design
KW - Approximation
KW - Facility location game
KW - Game theory
KW - Algorithmic mechanism design
KW - Approximation
KW - Facility location game
KW - Game theory
UR - http://www.scopus.com/inward/record.url?scp=85093084935&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85093084935&origin=recordpage
U2 - 10.1016/j.tcs.2020.10.004
DO - 10.1016/j.tcs.2020.10.004
M3 - 21_Publication in refereed journal
VL - 847
SP - 185
EP - 197
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
ER -