TY - JOUR
T1 - Facility location games with distinct desires
AU - Mei, Lili
AU - Li, Minming
AU - Ye, Deshi
AU - Zhang, Guochuan
PY - 2019/7/15
Y1 - 2019/7/15
N2 - In facility location games, one aims at designing a mechanism to decide the facility location based on the addresses reported by all agents. In the facility location game, each agent wants to minimize his/her distance from the facility, while in the obnoxious facility game, each agent prefers to be as far away from the facility as possible. In this paper we revisit the two games on a line network by finely defining another reasonable agent utility function in terms of their satisfaction degree with respect to the facility location. Namely, a happiness factor within [0,1] is introduced to measure the difference between the best facility location for an agent and the one given by the mechanism. An agent wants to gain a largest possible happiness factor while the social satisfaction is to maximize the sum of the factors. For the facility location game, we first show that the median mechanism (Procaccia and Tennenholtz, 2009) is 3/2-approximation. We then devise a 5/4-approximate group strategy-proof mechanism. Subsequently, we investigate the variant of maximizing the smallest happiness factor over all agents for this setting. For the obnoxious facility game, we show that the majority mechanism (Cheng et al., 2011) remains the best possible with approximation ratio of two. Finally, we devise a 4/3 -approximate randomized mechanism.
AB - In facility location games, one aims at designing a mechanism to decide the facility location based on the addresses reported by all agents. In the facility location game, each agent wants to minimize his/her distance from the facility, while in the obnoxious facility game, each agent prefers to be as far away from the facility as possible. In this paper we revisit the two games on a line network by finely defining another reasonable agent utility function in terms of their satisfaction degree with respect to the facility location. Namely, a happiness factor within [0,1] is introduced to measure the difference between the best facility location for an agent and the one given by the mechanism. An agent wants to gain a largest possible happiness factor while the social satisfaction is to maximize the sum of the factors. For the facility location game, we first show that the median mechanism (Procaccia and Tennenholtz, 2009) is 3/2-approximation. We then devise a 5/4-approximate group strategy-proof mechanism. Subsequently, we investigate the variant of maximizing the smallest happiness factor over all agents for this setting. For the obnoxious facility game, we show that the majority mechanism (Cheng et al., 2011) remains the best possible with approximation ratio of two. Finally, we devise a 4/3 -approximate randomized mechanism.
KW - Approximation ratio
KW - Facility location game
KW - Happiness
KW - Strategyproofness
UR - http://www.scopus.com/inward/record.url?scp=85062420281&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85062420281&origin=recordpage
U2 - 10.1016/j.dam.2019.02.017
DO - 10.1016/j.dam.2019.02.017
M3 - 21_Publication in refereed journal
VL - 264
SP - 148
EP - 160
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
SN - 0166-218X
ER -