# twofacility_location_games_with_minimum_distance_requirement__145d341a.pdf

Journal of Artificial Intelligence Research 70 (2021) 719-756 Submitted 07/2020; published 01/2021

Two-Facility Location Games with Minimum Distance Requirement

Xinping Xu xinping.xu@ntu.edu.sg School of Electrical and Electronic Engineering, Nanyang Technological University, 50 Nanyang Ave, Singapore 639798

Bo Li comp-bo.li@polyu.edu.hk Department of Computing, The Hong Kong Polytechnic University, 11 Yuk Choi Rd, Hung Hom, Hong Kong SAR

Minming Li minming.li@cityu.edu.hk Department of Computer Science, City University of Hong Kong, 83 Tat Chee Ave, Kowloon Tong, Hong Kong SAR

Lingjie Duan lingjie duan@sutd.edu.sg Engineering System and Design Pillar, Singapore University and Design, 8 Somapah Rd, Singapore 487372

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.

c 2021 AI Access Foundation. All rights reserved.

Xu, Li, Li & Duan

1. Introduction

In this paper, we study the two-facility location games with minimum distance requirement between two facilities. Here, the minimum distance requirement means that the distance between the two facilities should be at least a certain value. Its origin, the two-facility location game, models the scenario where the social planner is going to build two facilities on a line segment with some self-interested agents who want to minimize (maximize) their own costs (utilities). The agents are required to report their locations which are their private information, and a mechanism will map the reports to two locations to place the two facilities, with the purpose of optimizing the social cost (utility).

When the social planner (e.g., government) plans to build several public facilities (e.g., bus stop, theater, shopping mall, school, park, hospital, etc.) to serve some nearby agents (e.g., residents, users, customers), the distance between any two adjacent facilities can be one of the key factors to be considered. Especially, nowadays, the COVID-19 outbreak has become a great threat to public health and human life worldwide (Cascella et al., 2020). The agents need to go to the facilities to obtain services. If the two facilities are too close, the agents would gather to crowd, which decreases the social distance between people, and increases the possibility of virus spread. Therefore, in order to reduce crowd gathering to prevent rapidly spread of the COVID-19, the social planner needs to setup the minimum distance between any two adjacent facilities (Klise & Bynum, 2020). Other reasons related to decentralized facilities are diversification requirements, where one partial block of houses are not allowed to benefit from all the new projects of facilities (Moore & Stamm, 2012); affordable housing developments and zoning regulations so that public resources can be fairly distributed (Zhong et al., 2019; Sakai et al., 2020). For Game 1 of the heterogeneous two-facility location game, we show an instance that the social planner plans to deploy a theater and a primary school in a street, where all agents prefer living close for easy access to both movie entertainment and education resource. The two facilities should be some distance far away due to diversification requirements. Since each agent needs services from both heterogeneous facilities, the cost of each agent should be the sum of his Euclidean distances to the two facilities (Serafino & Ventre, 2014). For Game 2 of the homogeneous two-facility location game, we show an instance that the social planner plans to deploy two temporary COVID-19 testing sites in a street (Kaplan, 2020). To avoid crowd gathering, the two sites should be some distance far away. Since each agent only needs go to any one of two sites for testing, the cost/utility of each agent is his Euclidean distance to the closer site (Lu et al., 2010).

On the other hand, when the social planner plans to build several obnoxious facilities (e.g., factories), where all agents prefer living far away, the distance constraint between any two adjacent facilities is also a key factor to be considered. To comply with the environmental regulations of the limit on the total emissions, decentralized facilities help to reduce the spread of toxic gases and avoid penalties for any polluter exceeding the environmental limit (Turken et al., 2017). More seriously, if the factories are too close, any explosion hazard of a factory may cause the chain reactions and the disaster of all factories, and thus risk human life (Fu et al., 2016). Therefore, by adding the minimum distance requirement, we study Game 3 of the obnoxious heterogeneous two-facility location game,

Two-Facility Location Games with Minimum Distance Requirement

and Game 4 of the obnoxious homogeneous two-facility location game for the objective of maximizing the social utility. Besides, there exist some facilities (e.g., train station, kindergarten, theme park, parking lot, etc.) for which agents may have triple preferences: favorable, obnoxious, and indifferent; and the distance constraint between any two adjacent facilities should be also considered. Specifically, for Game 5 of the two-facility location game with triple-preference, the social planner plans to build a parking lot and a kindergarten with at least some distance in between for kids safety. Some agents prefer to live close to the parking lot to park their cars more conveniently, while some others want to stay away to avoid vehicle exhaust emissions around the parking lot, and the rest of agents are indifferent to the parking lot. Regarding the kindergarten, some agents prefer to stay close to it to pick up their kids, while some others want to stay away it to avoid noise, and the rest of agents are indifferent to it. An agent may manipulate the mechanism by misreporting his private information in order to decrease his cost or increase his utility. Therefore, we emphasize on the strategyproofness of a mechanism, which guarantees that an agent s utility/cost is optimized by reporting the truth. We aim to design deterministic strategyproof mechanisms whose performances approximate well the optimal social cost/utility. The evaluation of a mechanism is conducted by the approximation ratio, which is the worst ratio between the social cost/utility of the mechanism output and the optimal social cost/utility considering all possible agent profiles. We summarize our results and key novelty as follows.

Two-Facility location games with minimum distance requirement (TFLG): To the best of our knowledge, this is the first time that the distance requirement is considered in the facility location games for strategyproof mechanism design.

Mechanism design for Game 1 of the heterogeneous TFLG: In Section 3, we study the game where the agents prefer to stay close to both two facilities, and the cost of an agent is the sum of his distances to both facilities. We consider objectives of minimizing the social cost and minimizing the maximum cost of all agents, and design strategyproof mechanisms that output the optimal solutions.

Mechanism design for Game 2 of the homogeneous TFLG: In Section 4, we study the homogeneous TFLG where the facilities provide the same service and are favorable for all agents, and the cost of an agent is his distance to the closer facility. We show that for objective of minimizing the social cost, any deterministic strategyproof mechanism has unbounded approximation ratio.

Mechanism design for Game 3 of the obnoxious heterogeneous TFLG: In Section 5, we study the game where each agent prefers to stay far away from two obnoxious heterogeneous facilities, and the utility of an agent is the sum of his distances to both facilities. To maximize the social utility, we design deterministic group strategyproof mechanisms with provable approximation ratios, and prove a lower bound of 7 d

6 . Furthermore, when the objective is to maximize the minimum utility, we design a strategyproof mechanism that returns the optimal solution.

Mechanism design for Game 4 of the obnoxious homogeneous TFLG: In Section 6, we study the game where each agent prefers to stay far away from two obnoxious

Xu, Li, Li & Duan

homogeneous facilities, and the utility of an agent is his distance to the closer facility. We design a deterministic group strategyproof mechanism with an approximation ratio 9 for maximizing the social utility and find a lower bound 4/3. We also show that in most cases, there is no strategyproof mechanism with bounded approximation ratio for maximizing the minimum utility.

Mechanism design for Game 5 of the heterogeneous TFLG with triple-preference: Finally, in Section 7, we study the general game with triple-preference, where each of the two facilities may be favorable, obnoxious or indifferent for any agent. We motivate agents to report their locations and preferences for the two facilities truthfully. We design a deterministic group strategyproof mechanism with an approximation ratio 4 and obtain a corresponding lower bound.

Game 1: Game 2: Game 3: Game 4: Game 5: Hete Homo Obnx Hete Obnx Homo Hete TP Obj min SC min MC min SC or MC max SU max MU max SU max MU max SU

UB 1 1 + [1, 2] 1 [4, 9] + 4 (Me 1) (Me 2) (Me 5) (Me 6) (Me 10) (Me 11) LB 1 1 + 7 d

Table 1: A summary of the results in the paper, where Hete is for heterogeneous two-facility location games with minimum distance requirement, Homo is for homogeneous, Obnx is for obnoxious, TP is for triple-preference, Obj is for objective, UB is for upper bound, LB is for lower bound, SC is for social cost, MC is for maximum cost, SU is for social utility, MU is for minimum utility, Me is for Mechanism, and 0 d 1 is the distance requirement.

Table 1 summarizes our main results in the paper. Our work generalizes the existing studies on facility location games without distance constraints (i.e., d = 0). Particularly, without distance constraints, our heterogeneous TFLG degenerates to the one-facility location games (Procaccia & Tennenholtz, 2009); our homogeneous TFLG degenerates to the two-facility location games (Procaccia & Tennenholtz, 2009; Fotakis & Tzamos, 2014); and our obnoxious heterogeneous TFLG degenerates to the obnoxious one-facility location games (Cheng et al., 2013). The non-trivial distance constraint between the two facilities makes the design of strategyproof mechanisms, and the proof of lower bounds more challenging. In Game 6, for example, we design Mechanism 10 for different regimes 0 d < 5

14, 5 14 d 3

5 < d < 1. The analyses of our mechanisms and the corresponding lower bounds are regarded as the major technical contributions of this paper.

1.1 Related Work

In the algorithmic view of locating one facility, Procaccia and Tennenholtz (2009) first studied strategyproof mechanisms with provable approximation ratios on a line. Then characterizations of deterministic strategyproof mechanisms on line, tree, and cycle networks

1. This infinite lower bound is obatined under the condition that any deterministic strategyproof mechanism f only selects from any k N+ candidates.

Two-Facility Location Games with Minimum Distance Requirement

were provided (Moulin, 1980; Schummer & Vohra, 2002). For the obnoxious facility game, the problem of designing strategyproof mechanisms to approximately maximize the social utility was studied (Cheng et al., 2013). They presented a 3-approximation deterministic group strategyproof mechanism and proved a lower bound of 2. Characterizations of all strategyproof mechanisms with exactly two candidates in the general metric were studied (Han & Du, 2011; Ibara & Nagamochi, 2012). They showed that there exists a lower bound of 3 for strategyproof mechanism in any metric, matching the upper bound of 3 (Cheng et al., 2013). Zhang and Li (2014) the extended mechanism design for both games with weighted agents on a line and provided the corresponding lower and upper bounds on the optimal social utility. Combining the above two models together, the dual-preference game was studied, where some agents want to be close to the facility while the others want to be far away from the facility (Zou & Li, 2015; Feigenbaum & Sethuraman, 2015). Further, Xu et al. (2019) extended the facility point to be an UAV in the dual-preference game. For the two-facility location game, Lu et al. (2009) improved the lower bounds for the two homogeneous facilities scenario and the scenario when one agent possesses multiple locations. Lu et al. (2010) considered the cost of an agent to be the distance between his own location and the closer facility in a general metric space. Sui et al. (2013) proposed a class of percentile mechanisms in the form of generalized median mechanisms. Fotakis and Tzamos (2014) proved that the best approximation ratio achievable by deterministic strategyproof mechanisms for locating 2 facilities on the line to minimize the total cost is n 2. Serafino and Ventre (2014, 2015) initiated the study on two heterogeneous facility location games in the graph where the cost of an agent is the sum of his distances to both facilities. Yuan et al. (2016) proposed the optional preference model for the facility location game with two heterogeneous facilities on a line, where agents are allowed to have optional preference. Anastasiadis and Deligkas (2018) studied heterogeneous k-facility location games on the line segment where the preferences of agents over the facilities are the private information, and the locations of agents are known to the social planner. Fong et al. (2018) proposed a fractional preference model for the facility location game with two facilities that serve the similar purpose on a line where each agent has his location information as well as fractional preference towards the two facilities. In addition, Todo et al. (2011) extended the original model by fully characterizing the deterministic false-name-proof facility location mechanisms for locating a single facility on a line. Then Sonoda et al. (2016) extended the model by characterizing the possible outcomes of false-name-proof mechanisms for locating two facilities on a line as well as on a circle. Wada et al. (2018) studied variable populations in the static and dynamic facility location models and proposed a class of online social choice functions for the dynamic model. Keijzer and Wojtczak (2018) considered a multi-stage facility reallocation problems on the line, where a facility is moved between stages based on the locations reported by n agents, and characterized the optimal mechanisms both in the offline setting and in the online setting. Other extensions of the facility location game can be found (Cai et al., 2016; Mei et al., 2016; Xu et al., 2020). Besides, for minimum distance requirement and decentralized facilities, Moon and Papayanopoulos (1991) proposed non-strategic version of the two-facility location problem where the facilities must be separated by at least a specified distance. White (1993) studied the locations of two facilities with minimal separation. Lei and Church (2013)

Xu, Li, Li & Duan

studied facility dispersion problems involving the locations of a number of facilities where the intention was to place them as far apart from each other as possible. Jung (2016) developed methodologies for determining the optimal distributions of facilities by including a variety of distance constraints, one of which is related to process safety. Chen et al. (2019) proposed the dispersion problem to locate n facilities in a k-dimensional polytope, so that they are far away from each other and from the boundary of the polytope. To the best of our knowledge, our paper is the first study of the facility location games that take the distance requirement and the agents strategic behavior into consideration for strategyproof mechanism design.

2. System Model

Let N = {1, 2, , n} be the set of agents located on a line interval I = [0, 1]. We denote x = (x1, x2, , xn) as the n N+ agents location profile, which is private information and needs to be reported by each agent. Without loss of generality, we assume that xi xi+1 for any 1 i n 1. In the two-facility location game, a mechanism f outputs two facilities locations (y1, y2) based on a given location profile x, i.e., (y1, y2) = f(x) : In I2. Denote the minimum distance requirement between the two facilities as d [0, 1], i.e., |y2 y1| d. If the two facilities are heterogeneous, the cost of agent i is denoted as the sum of his distances to the two facilities, i.e.,

ci(f(x), xi) = |y1 xi| + |y2 xi|. (1)

If the two facilities are homogeneous, the cost of agent i is denoted as his distance to the closer facility, i.e.,

ci(f(x), xi) = min{|y1 xi|, |y2 xi|}. (2)

Let x i = (x1, , xi 1, xi+1, , xn) be the location profile without agent i. Let x S be the location profile with all agent i S N and x S be the location profile without any agent i S N. Following utilitarian objective, the social cost of a mechanism f(x) with respect to x is denoted as the sum of costs of n agents, i.e.,

SC(f(x), x) =

i=1 ci(f(x), xi). (3)

For egalitarian objective, the maximum cost of a mechanism f(x) with respect to x is

MC(f(x), x) = max i N ci(f(x), xi). (4)

As agents may misreport their locations to change y1 and y2 for their own benefits, strategyproofness of f(x) is important to ensure. Next we formally define the strategyproofness and the group strategyproofness respectively.

Definition 1. A mechanism is strategyproof in the two-facility location game if no agent can benefit from misreporting his location. Formally, given agent i, profile x = {xi, x i} In, and any misreported location x i I , it holds that

ci(f(xi, x i), xi) ci(f(x i, x i), xi).

Two-Facility Location Games with Minimum Distance Requirement

Definition 2. A mechanism is group strategyproof in the two-facility location game if for any group of agents, at least one of them cannot benefit if they misreport simultaneously. Formally, given a non-empty set S N, profile x = {x S, x S} In, and the misreported x S I|S|, there exists i S, satisfying

ci(f(x S, x S), xi) ci(f(x S, x S), xi).

In the facility location game, we are interested in designing strategyproof mechanisms that also perform well with respect to minimizing the social cost. For a location profile, let OPT1(x) be the optimal (minimum) social cost. A mechanism f has an approximation ratio γ, if for any possible profile x In, SC(f, x) γOPT1(x). In the obnoxious heterogeneous two-facility location game, the agents prefer to be far away from the two facilities. We define agent i s utility as

ui(f(x), xi) = |y1 xi| + |y2 xi|. (5)

In the obnoxious homogeneous two-facility location game, the agents prefer to be far away from the closer facility. We define agent i s utility as

ui(f(x), xi) = min{|y1 xi|, |y2 xi|}. (6)

Following utilitarian objective, the social utility of a mechanism f(x) with respect to x is

SU(f(x), x) =

i=1 ui(f(x), xi). (7)

For egalitarian objective, the minimum utility of a mechanism f(x) with respect to x is

MU(f(x), x) = min i N ui(f(x), xi). (8)

Definition 3. A mechanism is strategyproof in the obnoxious two-facility location game if no agent can benefit from misreporting his location. Formally, given agent i, profile x = {xi, x i} In, and any misreported location x i I , it holds that

ui(f(xi, x i), xi) ui(f(x i, x i), xi).

Definition 4. A mechanism is group strategyproof in the obnoxious two-facility location game if for any group of agents, at least one of them cannot benefit if they misreport simultaneously. Formally, given a non-empty set S N, profile x = {x S, x S} In, and the misreported x S I|S|, there exists i S, satisfying

ui(f(x S, x S), xi) ui(f(x S, x S), xi).

For a location profile x, let OPT2(x) be the optimal (maximum) social utility. A mechanism f has an approximation ratio γ, if for any profile x In, OPT2(x) γSU(f, x). The heterogeneous two-facility location game with triple-preference will be shown later where we will further allow agents to misreport their preferences towards the two facilities.

Xu, Li, Li & Duan

3. Game 1: Heterogeneous Two-Facility Location Games

In the heterogeneous two-facility location game, where all agents want to get close to the two heterogeneous facilities, we consider the cost of agent i as ci = |y1 xi| + |y2 xi|. Assume, without loss of generality, that facility 1 is on the left of facility 2, i.e., 0 y1 y2 1.

3.1 Minimize the Sum of Costs

Following utilitarian objective, from (1) and (3), we rewrite the social cost as function

g(y1, y2|x) = SC(f(x), x) =

i=1 (|y1 xi| + |y2 xi|) (9)

of two variables (y1, y2) D, and the optimal social cost OPT1(x) can be obtained by solving:

min y1,y2 g(y1, y2|x) = min y1,y2

i=1 (|y1 xi| + |y2 xi|),

s.t. (y1, y2) D = {(y1, y2)|y2 y1 d, 0 y1, y2 1},

given 0 xi 1, for i = 1, ..., n and 0 d 1. (10)

The feasible region D of (y1, y2) is an isosceles right triangle with three corners (0, d), (1 d, 1), (0, 1) and is closed convex.

Proposition 1. g is a convex function with (y1, y2) D and can obtain its minimum in D at y2 y1 = d.

Proof. According to the property of convex functions, agent i s cost function |y1 xi|+|y2 xi| with two variables (y1, y2) is convex, since function |y1 xi| with variable y1 and function |y2 xi| with variable y2 are both convex. Therefore, social cost Pn i=1(|y1 xi|+|y2 xi|) is convex in (y1, y2). As D is a convex set, g is a continuous convex function in D. To obtain the optimal social cost OPT1, we consider the linear optimization problem (10). Further, we define D = D1 D2 D3, as the boundary of the closed convex set D, where

D1 = {(y1, y2)|y2 y1 = d, 0 y1 1 d}, D2 = {(y1, y2)|y1 = 0, d y2 1},

and D3 = {(y1, y2)|y2 = 1, 0 y1 1 d}.

Obviously, D\ D is the largest open convex subset of D. Next we prove that the optimal point in (y1, y2) D can be obtained in D1. It is known that

i=1 |y xi| =

2 +1)] if n is even x n+1

2 if n is odd . (11)

There are two cases according to the parity of n. Case 1: n is even. Due to (11), function g(y1, y2|x) obtains its local minimum at the point (y1, y2) E = [x n

given (y1, y2) [0, 1] [0, 1]. E is a square area and also a closed convex set. There are two subcases depending on the relationship between E and D.

Two-Facility Location Games with Minimum Distance Requirement

(෦ 𝑦1, ෦ 𝑦2)

Figure 1: Connections between the line segment L and convex sets E, D.

1) E D = . The necessary condition for E D = is that E D1 = , due to the shapes of triangle D and square E in [0, 1]2. See convex sets E and D in Figure 1. The optimal point in (y1, y2) D can be obtained in E D1 which is a non-empty subset of D1.

2) E D = . Given (y1, y2) [0, 1] [0, 1], by (11), its global minimum can only be obtained at the point (y1, y2) E. Since g is a convex function, the local minimum of g must be obtained at the point (y1, y2) E. When E D = , there is no local minimum point but one global minimum point (optimal point) in D. The optimal point in D can only be obtained at a point in D. Otherwise, if the optimal point is obtained at a point in open set D\ D, this point must be the point of local minimum, which contradicts the fact that g can only obtain its local minimum at the point (y1, y2) E and E D = . Further, this optimal point can be obtained in D1. Otherwise, we assume the optimal point (y1, y2) is only obtained in D2 D3 as shown in Figure 1. Then we can always draw a line segment L connecting the optimal point (y1, y2) D2 D3 and any point ( y1, y2) E. This line segment L must intersect with line segment D1 at point ( ey1, ey2). Note that ( ey1, ey2) is between points (y1, y2) and ( y1, y2) on line segment L. Recall that the value of g at point ( ey1, ey2) is greater than the values of g at points (y1, y2) and ( y1, y2). However, this contradicts the fact that function g is also convex in convex line segment L.

Xu, Li, Li & Duan

Case 2: n is odd. Due to (11), function g(y1, y2|x) can obtain its local minimum at the point (y1, y2) = (x n+1

2 ), given (y1, y2) [0, 1] [0, 1]. This point cannot overlap with D, i.e., (x n+1

2 ) D = , since any point in D must satisfy that y2 y1 > 0. Thus we can follow the similar proof in subcase 2) of Case 1 and draw the same conclusion that this optimal point in D can be obtained in D1.

According to Proposition 1, we can consider an equivalent linear optimization problem to replace (10):

min y1,y2 g(y1, y2|x) s.t. (y1, y2) D1 = {(y1, y2)|y2 y1 = d, y1 [0, 1 d]}. (12)

Thus, by letting y2 = y1 + d, we only need to find the solution of facility 1 s location to solve (12), which we denote as y 1(d; x):

y 1(d; x) = arg min y1 [0,1 d]

i=1 (|y1 xi| + |y1 + d xi|). (13)

Before solving (13), it is widely known that if n is even,

i=1 |y xi| = [x n

2 +1)]. (14)

Define location profile x d = {x1 d, x2 d, . . . , xn d}. From (13) and (14), we have y 1(d; x) [ xn, xn+1], where xi is denoted as the i-th order statistic of the set {x d, x} I2n. Since y 1(d; x) should be within feasible interval [0, 1 d], we have the solution of facility 1 s location, which is

y 1(d; x) [ xn, xn+1] [0, 1 d] = [max{0, xn}, min{1 d, xn+1}] (15)

We can also choose a special y 1(d; x) to make it strategyproof as shown in Mechanism 1 below. However, we should note that an arbitrary choice of y 1(d; x) in the range cannot guarantee strategyproofness. For example, we select y1 as (max{0, xn}+min{1 d, xn+1})/2 in the range (15). If location profile is x = {x1, x2} = {0, 0.4} and d = 0.2, we can obtain (y1, y2) = (0.1, 0.3) and the cost of agent 2 is c2((y1, y2), x2) = 0.4. However, if agent 2 misreport his location from x2 = 0.4 to x 2 = 1, the two facilities locations will change to (y 1, y 2) = (0.4, 0.6), and the cost of agent 2 will be c2((y 1, y 2), x2) = 0.2. Thus, agent 2 can misreport to minimize his cost. Next, we provide a strategyproof mechanism.

Mechanism 1. (y1, y2) = (y 1(d; x), y 1(d; x) + d) where

y 1(d; x) = max{0, xn} = 0 if xn d xn if xn > d . (16)

Theorem 1. Mechanism 1 outputs the optimal solution and is strategyproof.

Two-Facility Location Games with Minimum Distance Requirement

Proof. Mechanism 1 select y1 as the infimum of range (15) and thus outputs the optimal solution. Next, we prove the strategyproofness. If xn d, then x1 d, x2 d, . . . , xn d 0. Thus xn = xn d 0, and y 1(d; x) = max{0, xn} = 0. Otherwise if xn > d, then xn min{x1, xn d} 0. Thus y 1(d; x) = max{0, xn} = xn. Therefore we design y 1(d; x) in (16) and f(x) = (y 1(d; x), y 1(d; x) + d). Suppose that agent i misreports his location from xi to x i. Define x = {x1, . . . , xi 1, x i, xi+1, . . . , xn} and xn(x ) = max{x }. Define xn(x ) as the n-th order statistic of the set {x d, x } I2n. Define y 1(d; x ) as the location of facility 1 in (16) after agent i s misreporting. We divide our discussion of strategyproofness into three cases according to xi. Case 1: y 1(d; x) xi y 1(d; x) + d. Agent i has no incentive to misreport his location since he has obtained the minimum cost d. Case 2: xi < y 1(d; x). Agent i misreports his location from xi to x i. We divide this case into two parts according to x i.

1. x i < xi. There are two choices of y 1(d; x) in (16).

(a) If xn d, then we choose 0 as y 1(d; x) in (16). We have y 1(d; x) = 0, which contradicts the fact that y 1(d; x) > xi 0. Hence, this choice never exists.

(b) If xn > d, then we choose xn as y 1(d; x) in (16). After agent i s misreporting, since x i < xi < y 1(d; x), we still have xn(x ) = xn > d and y 1(d; x ) = xn(x ) in (16). Since x i < xi < y 1(d; x) = xn, we have xn(x ) = xn, which means y 1(d; x ) = xn and new locations of the two facilities do not change.

2. x i > xi. After agent i misreports, xn(x ) xn, and thus y 1(d; x ) y 1(d; x) in (16). Hence,

ci(f(x ), xi) = 2y 1(d; x ) + d 2xi ci(f(x), xi) = 2y 1(d; x) + d 2xi

and agent i increases his cost.

Case 3: xi > y 1(d; x) + d. Agent i misreports his location from xi to x i. We divide this case into two parts.

1. x i < xi. After agent i s misreporting, we have xn(x ) xn, xn(x ) xn, and thus y 1(d; x ) y 1(d; x) in (16). Hence,

ci(f(x ), xi) = 2xi 2y 1(d; x ) d ci(f(x), xi) = 2xi 2y 1(d; x) d,

and agent i increases his cost.

2. x i > xi. There are two choices of y 1(d; x) in (16).

(a) If xn d, then we choose 0 as y 1(d; x) in (16). We have xi xn d, which contradicts the fact that xi > y 1(d; x) + d. Hence, this choice never exists.

(b) If xn > d, then we choose xn as y 1(d; x) in (16). After agent i s misreporting, since x i > xi > y 1(d; x) + d, we still have xn(x ) xn > d and y 1(d; x ) = xn(x ) in (16). Since x i d > xi d > y 1(d; x) = xn, we have xn(x ) = xn, which means y 1(d; x ) = xn and new locations of the two facilities do not change.

Xu, Li, Li & Duan

Therefore, Mechanism 1 is strategyproof.

3.2 Minimize the Maximum Cost

Following egalitarian objective, we consider minimizing the maximum cost. From (1) and (4), we need to solve the problem:

min (y1,y2) D max i N {|xi y1| + |xi y2|},

where D = {(y1, y2)||y1 y2| d, 0 y1 y2 1}. We design the following mechanism.

Mechanism 2. If d xn x1, return y1 = min{x1, 1 d} and y2 = y1 + d; if d < xn x1, return y1 = x1 and y2 = xn.

Theorem 2. Mechanism 2 outputs the optimal solution for minimizing the maximum cost and is also strategyproof.

Proof. Let f be Mechanism 2. We first prove f outputs the optimal solution for minimizing the maximum cost. Given d xn x1, for the cost of any agent i N,

ci = |xi y1| + |xi y2| |y2 y1| d.

Thus, the optimal solution for minimizing the maximum cost should be min(y1,y2) D maxi N ci((y1, y2), x) d. In Mechanism 2, for any agent i N, y1 = min{x1, 1 d} x1 xi; and y2 = y1 + d = min{x1 + d, 1} xn xi. Thus the cost of agent i under Mechanism 2 is

ci(f, x) = |xi y1| + |xi y2| = (xi y1) + (y2 xi) = y2 y1 = d

and the maximum cost under Mechanism 2 is MC(f, x) = maxi N ci(f, x) = d. Therefore, Mechanism 2 outputs the optimal solution. Given d < xn x1, for the maximum cost,

max i N ci = max i N (|xi y1| + |xi y2|) = max{|x1 y1| + |x1 y2|, |xn y1| + |xn y2|},

due to function |xi y1| + |xi y2| is convex for variable xi. Then the optimal solution for minimizing the maximum cost should be

min (y1,y2) D max ci((y1, y2), x) = min (y1,y2) D max{|x1 y1| + |x1 y2|, |xn y1| + |xn y2|}

min (y1,y2) D 1 2(|x1 y1| + |x1 y2| + |xn y1| + |xn y2|)

= min (y1,y2) D 1 2((|x1 y1| + |xn y1|) + (|x1 y2| + |xn y2|)) xn x1.

The cost of agent i under Mechanism 2 is

ci(f, x) = |xi y1| + |xi y2| = (xi x1) + (xn xi) = xn x1,

Two-Facility Location Games with Minimum Distance Requirement

and the maximum cost under Mechanism 2 is MC(f, x) = maxi N ci(f, x) = xn x1. Therefore, Mechanism 2 outputs the optimal solution. Next, we prove Mechanism 2 is strategyproof. Given xn x1 d, no agent has incentive to misreport since they have already obtained the minimum cost d. Given xn x1 > d, then y1 = x1 and y2 = xn. Suppose that agent i misreports his location xi to x i, x = {x i, x i} and (y 1, y 2) = f(x ). There are three cases. Case 1: agent 1 misreports his location x1 to x 1. If x 1 < x1, due to

max{x } min{x } = xn x 1 > xn x1 > d,

then y 1 = min{x } = x 1 and y 2 = max{x } = xn Thus,

c1(f(x ), x1) = |x1 y 1| + |x1 y 2| = xn x 1 > xn x1 = c1(f(x), x1).

If x 1 > x1, There are two subcases.

max{x } min{x } > d. Then y 1 = min{x } x1 and y 2 = max{x } xn. Thus,

c1(f(x ), x1) = |x1 y 1| + |x1 y 2| = y 1 + y 2 2x1 x1 + xn 2x1 = xn x1 = c1(f(x), x1).

max{x } min{x } d. Then y 1 = min{min{x }, 1 d} x1 and y 2 = y 1 + d. Thus,

c1(f(x ), x1) = |x1 y 1| + |x1 y 2| = 2y 1 + d 2x1 =2 min{min{x }, 1 d} + d 2x1 2 min{max{x } d, 1 d} + d 2x1 =2(max{x } d) + d 2x1 2xn d 2x1 > 2xn (xn x1) 2x1 =xn x1 = c1(f(x), x1).

Case 2: agent n misreports his location xn to x n. This case is similar with Case 1. Case 3: agent i with x1 < xi < xn misreports his location xi to x i. It is obvious that min{x } x1, max{x } xn. Thus max{x } min{x } xn x1 > d and y 1 = min{x }, y 2 = max{x }. For agent i s cost,

ci(f(x ), xi) = |xi y 1| + |xi y 2| = y 2 y 1 xn x1 = ci(f(x), xi).

Therefore, Mechanism 2 is strategyproof.

Note that not all mechanisms outputting an optimal solution are strategyproof. Only carefully chosen optimal solution can be strategyproof. For example, consider the mechanism that returns y1 = min{x1, 1 d} and y2 = y1+d, if d xn x1; returns y1 = (x1+xn d)/2 and y2 = (x1 + xn + d)/2, if d < xn x1. This mechanism also outputs an optimal solution but is not strategyproof.

Xu, Li, Li & Duan

4. Game 2: Homogeneous Two-Facility Location Games

In this section, we study the homogeneous two-facility location game, where all agents want to get close to the two homogeneous facilities. From (2) and (3), the cost of agent i is ci((y1, y2), xi) = min{|y1 xi|, |y2 xi|} and the social cost is SC((y1, y2), x) = P i N ci((y1, y2), xi). The problem can be shown as below:

min (y1,y2) D

i=1 min{|y1 xi|, |y2 xi|},

where D = {(y1, y2)||y1 y2| d, 0 y1 y2 1}. Given d = 1, the optimal solution is (y1, y2) = (0, 1) and is obviously strategyproof. Given d = 0, the stratgyproof mechanism that (y1, y2) = (x1, xn) provides the best approximation ratio of (n 2) (Fotakis & Tzamos, 2014). However, when 0 < d < 1, it is not clear to what extent strategyproof mechanisms can approximate the optimal solution. Unfortunately, in the following, we show that no strategyproof mechanism has a bounded approximation when 0 < d < 1.

Theorem 3. Given n 5, no strategyproof mechanism in the homogeneous two-facility location game with minimum distance requirement 0 < d < 1 has bounded approximation ratio.

Proof. Before we prove the theorem, we first recall the classic setting without the distance constraint, where the authors characterized all possible strategyproof mechanisms that have bounded approximation to the optimal algorithmic solution (Fotakis & Tzamos, 2014).

Claim 1. Theorem 3.1 in Fotakis and Tzamos (2014): Given n 5, in the homogeneous two-facility location game without distance constraint, for all 3-location instance1 x, the only mechanisms that are strategyproof and with bounded approximation ratios are either (1) Extreme Points (i.e., y1 = x1 and y2 = xn), or (2) Single Dictator (i.e., there is a unique dictator i such that for all x, y1 = xi or y2 = xi).

It is easy to see that any strategyproof mechanism with distance constraint 0 < d < 1 is a strategyproof mechanism for the setting without distance constraint. To distinguish the two settings, for a location profile x, we use OPTd(x) to denote the optimal social cost with distance constraint d and OPT(x) without distance constraint. Next, we show that the Extreme Points mechanism and Single Dictator mechanism either are not feasible or do not have bounded approximation to OPTd( ) for all location profiles. Consider the following location profile x where agents 1 to n 2 are located at 0, agent n 1 is at ϵ > 0 (sufficiently small), and agent n is at xn = d ϵ < d. Thus OPTd(x) = 2ϵ by placing two facilities at 0 and d. It is easy to see that Extreme Points mechanism is not feasible as (xn x1) < d violating the distance constraint. Next we consider the Single Dictator mechanism and suppose n is the dictator. This is without loss of generality as we can always reorder the agents such that the dictator is at d ϵ. For any Single Dictator mechanism, by placing one facility at xn, if d > 1 xn, there is no feasible position for the second facility, thus this mechanism is not feasible; otherwise, we

1. A 3-location instance means that there are three different locations x1, x2, x3, and a partition of N into three coalitions N1, N2, N3 such that all agents in coalition Ni occupy location xi for any {1, 2, 3}.

Two-Facility Location Games with Minimum Distance Requirement

have 2d ϵ 1 and the second facility can only be placed within [2d ϵ, 1]. However, this makes the social cost to be at least (n 2)(d ϵ) OPTd(x) = 2ϵ. Now, for contradiction, suppose a mechanism f satisfying distance constraint d is strategyproof and has bounded approximation ratio K to OPTd(x) for any instance x. Note that we have discussed that f cannot be Extreme Point or Single Dictator. Let x be any 3-location profile. Note that under Fotakis and Tzamos (2014) s model, the three locations can be anywhere on the real line (not restricted to be within [0, 1]), thus x is immune to scale. Without loss of generality, denote by 0 x1 < x2 < x3 1 the corresponding generic locations and x2 x1 x3 x2. Assume ki agents are at xi, where ki 1 for all i and k1 + k2 + k3 = n. Let ϵ = d 2n(x2 x1) < d 2n. Then we scale location profile x to x by placing x1 at 0, x3 at d ϵ, and keeping the relative distances between x2 and x1, x3 the same, i.e.,

x 1 = 0, x 2 = x2 x1

x3 x1 (d ϵ), x 3 = d ϵ.

We claim that for location profile x , OPTd(x ) (n 1)OPT(x ). We prove this by enumerating all possible structures of OPT(x ) and compare it with the social cost SC(0, d) by placing two facilities at 0 and d, which is one possible solution to the problem with distance constraint thus OPTd(x ) SC((0, d), x ). Note that

SC((0, d), x ) k2(x 2 x 1) + k3ϵ (n 2)(x 2 x 1) + (x 2 x 1) = (n 1)(x 2 x 1),

where the second inequality is because

k3ϵ < nϵ = d

2(x2 x1) < d

2 1 d ϵ (x 2 x 1) < x 2 x 1.

There are only three cases for OPT(x ). (1) If OPT(x ) is obtained by placing the two facilities at x 1 and x 2, then OPT(x ) = k3(x 3 x 2) x 2 x 1. (2) If OPT(x ) is obtained by placing the two facilities at x 1 and x 3, then OPT(x ) = k2(x 2 x 1) x 2 x 1. (3) If OPT(x ) is obtained by placing the two facilities at x 2 and x 3, then OPT(x ) = k1(x 2 x 1) x 2 x 1. No matter which case happens, it holds that

SC((0, d), x ) (n 1)(x 2 x 1) (n 1)OPT(x ).

Accordingly, OPTd(x ) (n 1) OPT(x ). Thus, if f has bounded approximation ratio K for OPTd(x ) and is not Extreme Point or Single Dictator, f is also strategyproof and has bounded approximation ratio K(n 1) for OPT(x), which is a contradiction with Claim 1.

Using a similar analysis, we note that Theorem 3 also holds when the objective is to minimize the maximum cost.

5. Game 3: Obnoxious Heterogeneous Two-Facility Location Games

In this section, we study the obnoxious heterogeneous two-facility location game, where all agents dislike the two facilities. From (5), we consider agent i s utility as ui(f(x), xi) = |y1 xi| + |y2 xi|.

Xu, Li, Li & Duan

5.1 Maximize the Sum of Utilities

Following utilitarian objective, from (5), (7) and (9), we need to solve the problem:

max g(y1, y2|x) s.t. (y1, y2) D.

Proposition 2. Social utility g can reach its maximum if (y1, y2) is at one out of three points (0, d), (1 d, 1), (0, 1).

Proof. Since function g is a convex function according to Proposition 1, g has a global maximum in D. Further, g can obtain its global maximum on boundary D. Otherwise, if g obtains its global maximum at point (y1, y2) in open set D\ D, that point must be a local maximum point, which contradicts the fact that g is a convex function. Then finding the maximum point of g on D is equivalent to finding the maximum point of g on D = D1 D2 D3. Di s (i = 1, 2, 3) are line segments and thus convex sets. Similarly, the convex function g in each line segment Di reaches its maximum at the boundary of Di, i.e., two endpoints of Di. Overall, the maximum point (y1, y2) of g over the three line segments can only be among the three corner points of D : (0, d), (1 d, 1), (0, 1).

It is easy to obtain OPT2 by using Proposition 2. However, a mechanism outputting the optimal solution OPT2 is not strategyproof given d < 1. Taking an example when d = 0, the obnoxious heterogeneous two-facility location game degenerates to the obnoxious one-facility location game, where the optimal location is not strategyproof (Cheng et al., 2013). Next, we propose strategyproof mechanisms.

Mechanism 3. Given a location profile x, return f(x) = (y1, y2) = (0, 1).

Lemma 1. Mechanism 3 is group strategyproof with an approximation ratio γ = 2 d.

Proof. Mechanism 3 is group strategyproof since (y1, y2) is fixed at (0, 1). The social utility of Mechanism 3 is SU((0, 1), x) = n. For any agent i s utility,

d |y1 y2| ui((y1, y2), xi) = |y1 xi| + |y2 xi| |y1 + y2 2xi| 2 d,

due to |y2 y1| d. Thus, the optimal utility is

OPT2(x) = max (y1,y2) D

i=1 (|y1 xi| + |y2 xi|) (2 d)n.

Therefore, γ = OPT2(x)/SU((0, 1), x) 2 d, which is within [1, 2].

Mechanism 3 does not take agents locations into account. By counting agent numbers in different location intervals, we propose Mechanism 4 which selects (y1, y2) among all the three candidate optimal points (0, d), (1 d, 1), (0, 1).

Mechanism 4. Denote l1 = 1

2(1 d) and l2 = 1

2(1 + d). Given a location profile x, if more than n

2 agents are located in [0, l1], f(x) = (y1, y2) = (1 d, 1), if more than n

2 agents are located in [l2, 1], f(x) = (y1, y2) = (0, d), and otherwise, f(x) = (y1, y2) = (0, 1).

Two-Facility Location Games with Minimum Distance Requirement

Lemma 2. Mechanism 4 is group strategyproof with an approximation ratio

γ = max{3 3d

1 + d , 2 1 + d}.

Proof. We first prove group strategyproofness. For any xi [0, l1],

ui((1 d, 1), xi) = 2 d 2xi ui((0, 1), xi) = 1 ui((0, d), xi) = xi + |d xi|; (17)

for any xi [l2, 1],

ui((0, d), xi) ui((0, 1), xi) ui((1 d, 1), xi);

for any xi (l1, l2),

ui((0, 1), xi) ui((1 d, 1), xi), ui((0, d), xi).

Let S N be an agent coalition. We must prove that the agents in S cannot all gain by misreporting. We denote n1, n2, n3 as the numbers of agents in [0, l1], [l2, 1], (l1, l2) without misreporting, respectively. n 1, n 2, n 3 are the numbers of agents in [0, l1], [l2, 1], (l1, l2) with misreporting, respectively. The new location profile is x to mislead the two facilities locations to (y 1, y 2). There are three cases. Case 1: n1 > n

2 , thus (y1, y2) = (1 d, 1).

1. If n 1 > n

2 , then (y 1, y 2) = (1 d, 1) and ui(f(x), xi) = ui(f(x ), xi) for any agent i N.

2. If n 2 > n

2 , then (y 1, y 2) = (0, d). Since n2 + n3 n

2 , at least one agent i in [0, l1] misreports his location to x i [l2, 1]. Thus ui(f(x ), xi) ui(f(x), xi) due to (17).

3. Otherwise, (y 1, y 2) = (0, 1). Since n 1 n

2 , at least one agent i in [0, l1] misreports his location to x i [l2, 1] (l1, l2). Due to (17), ui(f(x ), xi) ui(f(x), xi).

Case 2: n2 > n

2 , thus (y1, y2) = (0, d). Strategyproofness analysis of Case 2 is the same as Case 1. Case 3: Otherwise, (y1, y2) = (0, 1). There are three subcases and can similarly follow the proof of Case 1 to draw the same conclusion that f is group strategyproof. Next, we analyze the ratio γ. There are three cases. Case 1: n1 > n

2 and then (y1, y2) = (1 d, 1). We have

SU((1 d, 1), x) X

i:xi [0,l1] (2 d 2xi) + n3d + n2d n1 + n2d + n3d, (18)

SU((0, d), x) X

i:xi [0,l1] (xi + |d xi|) + n3 + n2(2 d)

n1 max{d, 1 2d} + n2(2 d) + n3, (19)

SU((0, 1), x) = n. (20)

Xu, Li, Li & Duan

Due to (18), (19), (20) and n1 > n

SU((0, d), x) SU((1 d, 1), x) n1 max{d, 1 2d} + (n n1)(2 d)

n1 + (n n1)d

n 2 max{d, 1 2d} + n

2 (2 d) n 2 + (n n

2 )d = max{3 3d

1 + d , 2 1 + d},

SU((0, 1), x) SU((1 d, 1), x) n n1 + (n n1)d n n 2 + n

2 d = 2 1 + d,

and thus according to Proposition 2,

γ = max{SU((0, d), x), SU((0, 1), x)}

SU((1 d, 1), x) = max{3 3d

1 + d , 2 1 + d}.

Case 2: n2 > n

2 . The analysis is similar to Case 1. Case 3: Otherwise, (y1, y2) = (0, 1). By (19), we have

SU((0, d), x) n1 + n2(2 d) + n3 = n2(1 d) + n n

2 (1 d) + n (21)

and SU((1 d, 1), x) n

2 (1 d) + n. Thus

γ = max{SU((0, d), x)

SU((0, 1), x), SU((1 d, 1), x)

SU((0, 1), x) }

n 2 (1 d) + n

In conclusion,

γ max{max{3 3d

1 + d , 2 1 + d}, 3 d

2 } = max{3 3d

1 + d , 2 1 + d},

which is within [1, 3].

By combining Mechanism 3 and Mechanism 4, we have the following mechanism which is also group strategyproof and can obtain a smaller approximation ratio for d [0, 1].

Mechanism 5. Given a location profile x, if 0 d 2

3, use Mechanism 3 to return (y1, y2); if 2

3 < d < 1, use Mechanism 4 to return (y1, y2).

Theorem 4. Mechanism 5 has an approximation ratio

γ = min{2 d, max{3 3d

1 + d , 2 1 + d}} (1, 2].

The next theorem establishes the lower bound for any deterministic strategyproof mechanism.

Theorem 5. In the obnoxious heterogeneous two-facility location game, given d [0, 1], for any n 3 agents, any deterministic strategyproof mechanism f has an approximation ratio γ of at least 7 d

The proof of Theorem 5 is shown in Appendix A. We can see the upper bound and the lower bound of deterministic strategyproof mechanisms in Figure 2.

Two-Facility Location Games with Minimum Distance Requirement

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 d

Approximation ratio

Upper bound under Mechanism 5 Lower bound under Theorem 5

Figure 2: The upper bound and the lower bound of deterministic strategyproof mechanisms for d [0, 1).

5.2 Maximize the Minimum Utility

Following egalitarian objective, we consider maximizing the minimum utility. From (5) and (8), we need to solve the problem:

max (y1,y2) D min i N {|xi y1| + |xi y2|},

where D = {(y1, y2)||y1 y2| d, 0 y1 y2 1}. We design the following mechanism.

Mechanism 6. If d < 2x1 1, return (y1, y2) = (0, d); if d < 1 2xn, return (y1, y2) = (1 d, 1); if d 2x1 1 and d 1 2xn, return (y1, y2) = (0, 1).

Theorem 6. Mechanism 6 outputs the only optimal solution for maximizing the minimum utility if d = 2x1 1 and d = 1 2xn; it outputs the optimal solution for maximizing the minimum utility if d = 2x1 1 or d = 1 2xn. Mechanism 6 is also strategyproof.

Proof. Let f be Mechanism 6. Before proving, we first claim that the solution of maximizing the minimum utility, i.e., arg max(y1,y2) D mini N ui((y1, y2), xi) must be (y1, y2) = (y 1, y 2) = (0, d), or (1 d, 1), or (0, 1). Otherwise, for contradiction, if the solution is (y 1, y 2) / {(0, d), (1 d, 1), (0, 1)}, there exists some i N satisfying that

max (y1,y2) D min i N ui((y1, y2), xi) = ui ((y 1, y 2), xi ) ui ((y1, y2), xi ).

However, by Proposition 2, ui ((y1, y2), xi ) can only obtain its maximum when (y1, y2) = (0, d), or (1 d, 1), or (0, 1), which contradicts (y1, y2) = (y 1, y 2) / {(0, d), (1 d, 1), (0, 1)}.

Xu, Li, Li & Duan

We first prove Mechanism 6 outputs the optimal solution for maximizing the minimum utility. There are three cases for any agent s utility. Case 1: d < 2x1 1. The utility of any agent i N is

ui((0, d), xi) = 2xi d 2x1 d > 1,

due to xi x1 > 1+d

ui((1 d, 1), xi) = |1 d xi| + 1 xi

max{|1 d 1 + d

2 | + 1 1 + d

2 , d} = max{1 2d, d} 1,

2 < x1 xi 1; and ui((0, 1), xi) = 1. Thus,

ui((y1, y2), xi) max{ui((0, d), xi), ui((1 d, 1), xi), ui((0, 1), xi)} = ui((0, d), xi).

Accordingly, the optimal solution for maximizing the minimum utility should be

max (y1,y2) D min i N ui((y1, y2), xi) min i N max (y1,y2) D ui((y1, y2), xi)

= min i N ui((0, d), xi) = min i N 2xi d = 2x1 d.

In Mechanism 6, (y1, y2) = (0, d) and thus the minimum utility of agents is

MU(f, x) = min i N ui((0, d), xi) = min i N 2xi d = 2x1 d.

Therefore, Mechanism 6 outputs the only optimal solution as d < 2x1 1. Case 2: d < 1 2xn. We rewrite Case 2 as xn < 1 d

2 and Case 1 as x1 > 1+d

2 . We can see that due to symmetry, Case 2 is similar with Case 1. Case 3: d 2x1 1 and d 1 2xn. We have that for the minimum utilities,

MU((0, d), x) = min i N ui((0, d), xi) = u1((0, d), x1)

= x1 + |x1 d| max{d, 2x1 d} < 1 for 2x1 1 < d < 1 = 1 for d = 1 or d = 2x1 1 , (22)

due to 0 x1 1+d

MU((1 d, 1), x) = min i N ui((1 d, 1), xi) = un((1 d, 1), xn)

=|1 d xn| + 1 xn max{2(1 xn) d, d} < 1 for 1 2xn < d < 1 = 1 for d = 1 or d = 2xn 1 , (23)

2 xn 1; and

MU((0, 1), x) = min i N ui((0, 1), xi) = 1.

Thus, by comparing with (22) and (23), (0, 1) is the only optimal solution for maximizing the minimum utility, if d > 2x1 1 and d > 1 2xn; (0, 1) is one of the optimal solutions

Two-Facility Location Games with Minimum Distance Requirement

for maximizing the minimum utility, if d = 2x1 1 or d = 1 2xn. In Mechanism 6, (y1, y2) = (0, 1), so Mechanism 6 outputs the only optimal solution, if d > 2x1 1 and d > 1 2xn, and also outputs the optimal solution, if d = 2x1 1 or d = 1 2xn. Next, we prove Mechanism 6 is strategyproof. There are three cases. Case 1: d < 2x1 1, (y1, y2) = (0, d). We have xi x1 1+d

2 , and thus max(y1,y2) D ui((y1, y2), xi) = ui((0, d), xi). Therefore, no agent has incentive to misreport his location since he has already obtained the maximum utility. Case 2: d < 1 2xn, (y1, y2) = (1 d, 1). Due to symmetry, this case is similar with Case 1. Case 3: d 2x1 1 and d 1 2xn, (y1, y2) = (0, 1). There are three subcases.

Subcase 1: any agent i with xi [0, 1 d

2 ) misreports his location. Note that i can not be n since xn 1 d

2 . We assume agent i can increase his utility after misreporting. Then (y 1, y 2) must be (1 d, 1) due to

ui((1 d, 1), xi) ui((0, 1), xi) = 1 ui((0, d), xi)

from (17). We must have the condition that d < 1 2 max{x }. Thus max{x } < 1 d

2 , which contradicts max{x } xn 1 d

Subcase 2: any agent i with xi (1+d

2 , 1] misreports his location. This subcase is similar with Subcase 1.

Subcase 3: No agent i with xi [1 d

2 ] has incentive to misreport his location since he has already obtained the maximum utility 1.

Therefore, Mechanism 6 is strategyproof.

6. Game 4: Obnoxious Homogeneous Two-Facility Location Games

In this section, we study the obnoxious homogeneous two-facility location game, where all agents dislike the two facilities. From (6), we consider agent i s utility as ui(f(x), xi) = min{|y1 xi|, |y2 xi|}.

6.1 Maximize the Sum of Utilities

From (6) and (7), the social utility is SU((y1, y2), x) = P i N min{|y1 xi|, |y2 xi|}. Following utilitarian objective, the problem is shown as

max (y1,y2) D

i=1 min{|y1 xi|, |y2 xi|},

where D = {(y1, y2)||y1 y2| d, 0 y1 y2 1}. Given d = 1, the optimal solution is (y1, y2) = (0, 1) and is obviously strategyproof. However, given any d < 1, the optimal solution is not strategyproof, since this game is a generalization of obnoxious one-facility game, where there is no strategyproof optimal

Xu, Li, Li & Duan

solution (Cheng et al., 2011). As will be clear by our lower bound result, the optimal solution is not strategyproof. Now we find strategyproof mechanisms given d < 1. Define T1 = {i|xi [0, 1

2], xi x} and T2 = {i|xi (1

2, 1], xi x}. Obviously, N = T1 T2.

Mechanism 7. Given 0 d < 1

2, if |T1| |T2|, return (y1, y2) = (1 d, 1); if |T1| < |T2|, return (y1, y2) = (0, d).

Lemma 3. Mechanism 7 is group strategyproof with an approximation ratio γ = 4 4d

Proof. Given d < 1

2, for any agent i in T1,

ui((1 d, 1), xi) = 1 d xi ui((0, d), xi) = min{xi, |xi d|};

for any agent i in T2,

ui((1 d, 1), xi) = min{|1 d xi|, 1 xi} ui((0, d), xi) = xi d.

By the similar proof of strategyproofness in Lemma 2, Mechanism 7 is group strategyproof. Now we prove the approximation ratio. Without loss of generality, assume that |T1| |T2|, so we have (y1, y2) = (1 d, 1) in Mechanism 7. The approximation ratio is

γ = OPT2(x) SU((1 d, 1), x) = maxy1,y2(P i N ui((y1, y2), xi) P i T1(1 d xi) + P i T2 min{|1 d xi|, 1 xi}

P i N(1 d) P i T1(1 d 1/2) + P i T2 0 = n(1 d) |T1|(1/2 d) 4 4d

We first show the following lemma for the proof of Lemmas 5 and 6.

Lemma 4. For any agent i, we have

|xi y1| |xi 1 + d| + 1 d, |xi y2| 1 xi + 1 d, |xi y1| xi + 1 d; (24)

|xi y1| |xi 1 d

2 , |xi y2| |xi 1 + d

Proof. Since 0 y1 1 d,

|xi y1| = |(xi (1 d)) + (1 d) y1| |xi (1 d)| + |1 d y1|

|xi (1 d)| + 1 d,

|xi y1| xi + y1 xi + 1 d,

|xi y1| |xi (1 d)/2| + |(1 d)/2 y1| |xi (1 d)/2| + (1 d)/2.

Since d y2 1,

|xi y2| |xi 1| + |1 y2| |xi 1| + 1 d

|xi y2| |xi (1 + d)/2| + |(1 + d)/2 y2| |xi (1 + d)/2| + (1 d)/2.

Two-Facility Location Games with Minimum Distance Requirement

Define T3 = {i|xi [0, 1 d

2 ), xi x}, T4 = {i|xi [1 d

2), xi x}, T5 = {i|ti [1

2 ), xi x}, and T6 = {i|ti [1+d

2 , 1], xi x}. Obviously, N = T3 T4 T5 T6.

Mechanism 8. Given 1

2 d < 1, if |T3| + |T5| |T4| + |T6|, return (y1, y2) = (1 d, 1); if |T3| + |T5| < |T4| + |T6|, return (y1, y2) = (0, d).

Lemma 5. Mechanism 8 is group strategyproof with an approximation ratio

γ = max{4, 3 2d

Proof. Given d 1

2, for any agent i in T3,

ui((1 d, 1), xi) = 1 d xi ui((0, d), xi) = xi;

for any agent i in T5,

ui((1 d, 1), xi) = min{xi 1 + d, 1 xi} ui((0, d), xi) = |xi d|;

for any agent i in T4,

ui((1 d, 1), xi) = |1 d xi| ui((0, d), xi) = min{xi, d xi};

for any agent i in T6,

ui((1 d, 1), xi) = 1 xi ui((0, d), xi) = xi d.

By the similar proof of strategyproofness in Lemma 2, Mechanism 8 is group strategyproof. Now we prove the approximation ratio. Without loss of generality, assume that |T3| + |T5| |T4| + |T6|, and hence (y1, y2) = (1 d, 1) in Mechanism 8. The social utility is

SU((1 d, 1), x) = X

i N min{|xi (1 d)|, |xi 1|}

|T3|(1 d)/2 + X

i T5 min{|xi 1 + d|, 1 xi} + X

i T4 T6 min{|xi 1 + d|, 1 xi}. (26)

By (24) in Lemma 4 and |T4| + |T6| |T3| + |T5|, the optimal social utility is

OPT2(x) = max (y1,y2) D

i N min{|y1 xi|, |y2 xi|}

max (y1,y2) D

i T3 ui((y1, y2), xi) + max (y1,y2) D

i T5 ui((y1, y2), xi) + max (y1,y2) D

i T4 T6 ui((y1, y2), xi)

|T3|(1 d) + X

i T5 (1 xi) + X

i T4 T6 (min{|xi 1 + d|, 1 xi} + 1 d)

2|T3|(1 d) + X

i T5 ((1 xi) + (1 d)) + X

i T4 T6 min{|xi 1 + d|, 1 xi}. (27)

Xu, Li, Li & Duan

By (26) and (27), the approximation ratio is

γ = OPT2(x) SU((1 d, 1), x) 2|T3|(1 d) + P i T5(2 xi d) |T3|(1 d)/2 + P i T5 min{|xi 1 + d|, 1 xi}

max{ 2|T3|(1 d)

|T3|(1 d)/2,

P i T5(2 xi d) P i T5 min{|xi 1 + d|, 1 xi}}

max{ 2|T3|(1 d)

|T3|(1 d)/2, max{ 2 xi d

|xi 1 + d|, 2 xi d

= max{ 2(1 d)

(1 d)/2, 2 1/2 d

d 1/2 , 2 (1 + d)/2 d

1 (1 + d)/2 } = max{4, 3 2d

Define T7 = {i|xi [1 d

4 ], xi x}, and T8 = {i|xi [0, 1 d

4 , 1], xi x}.

Mechanism 9. Given d < 1, if |T7| |T8|, return (y1, y2) = (0, 1); if |T7| < |T8|, return (y1, y2) = ( 1 d

Lemma 6. Mechanism 9 is group strategyproof with an approximation ratio γ = 9.

Proof. For any agent i in T7,

ui((0, 1), xi) = min{xi, 1 xi} ui((1 d

2 ), xi) = min{|xi 1 d

2 |, |xi 1 + d

for any agent i in T8,

ui((0, 1), xi) = min{xi, 1 xi} ui((1 d

2 ), xi) = min{|xi 1 d

2 |, |xi 1 + d

By the similar proof of strategyproofness in Lemma 2, Mechanism 9 is group strategyproof. Now we prove the approximation ratio. If |T7| |T8|, we have (y1, y2) = (0, 1) in Mechanism 9. The social utility is

SU((0, 1), x) = X

i N min{xi, 1 xi} X

i T7 min{xi, 1 xi} |T7|(1 d)/4.

By (24) in Lemma 4, the optimal social utility is

OPT2(x) = max (y1,y2) D

i N min{|y1 xi|, |y2 xi|}

i N min{xi + 1 d, 1 xi + 1 d} = SU((0, 1), x) + (1 d)n.

The approximation ratio is

γ = OPT2(x) SU((0, 1), x) 1 + (1 d)n SU((0, 1), x) 1 + (1 d)n |T7|(1 d)/4 = 9.

Two-Facility Location Games with Minimum Distance Requirement

If |T7| < |T8|, we have (y1, y2) = ( 1 d

2 ) in Mechanism 9. The social utility is

2 ), x) = X

i N min{|xi 1 d

2 |, |xi 1 + d

i T8 min{|xi 1 d

2 |, |xi 1 + d

2 |} |T8|1 d

By (25) in Lemma 4, the optimal social utility is

OPT2(x) = max (y1,y2) D

i N min{|y1 xi|, |y2 xi|}

i N min{|xi 1 d

2 , |xi 1 + d

2 } = SU((1 d

2 ), x) + 1 d

The approximation ratio is

γ = OPT2(x) SU((0, 1), x) 1 + (1 d)n/2 SU(((1 d)/2, (1 + d)/2), x) 1 + (1 d)n/2 |T8|(1 d)/4 = 5.

In conclusion, the approximation ratio is 9.

By combining Mechanisms 7, 8 and 9, we have the following mechanism.

Mechanism 10. Given a location profile x, if 0 d < 5 14, use Mechanism 7 to return (y1, y2); if 5 14 d 3

5, use Mechanism 9 to return (y1, y2); if 3

5 < d < 1, use Mechanism 8 to return (y1, y2).

Theorem 7. Mechanism 10 is also group strategyproof and can obtain an approximation ratio γ = 4 4d

1 2d, if 0 d < 5

14; 9 if 5 14 d 3

10 < d < 1, which is within [4, 9] for d [0, 1).

Theorem 8. In the obnoxious homogeneous two-facility location game, given d [0, 1), for any n 2 agents, any deterministic strategyproof mechanism f has an approximation ratio γ of at least 4/3.

The proof of Theorem 8 is shown in Appendix B. Interestingly, we notice that the lower bound is not continuous when d is close to 1. If d [1/3, 1), the lower bound is always 5/3 but if d = 1, the lower bound drops to 1 immediately. The upper and lower bounds of deterministic strategyproof mechanisms are illustrated in Figure 3.

6.2 Maximize the Minimum Utility

For egalitarian objective, we consider maximizing the minimum utility. From (6) and (8), the utility of agent i is ui((y1, y2), xi) = min{|y1 xi|, |y2 xi|} and the minimum utility is MU((y1, y2), x) = mini N ui((y1, y2), xi). We need to solve the problem:

max (y1,y2) D min i N {min{|y1 xi|, |y2 xi|}},

Xu, Li, Li & Duan

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 d

Approximation ratio

Upper bound under Mechanism 10 Lower bound under Theorem 8

Figure 3: The upper bounds under Mechanism 10 and the lower bounds under Theorem 8 for d [0, 1).

where D = {(y1, y2)||y1 y2| d, 0 y1 y2 1}. Given d = 1, the optimal solution is (y1, y2) = (0, 1) and is obviously strategyproof. Given d = 0, our obnoxious homogeneous two-facility location game degenerates to obnoxious one-facility location game, and by 5.4 in Han and Du (2011), there is no strategyproof mechanism with bounded ratio for maximizing the minimum utility. Given 0 < d < 1, in the following, we show that in most cases, there is no strategyproof mechanism with bounded approximation ratio for maximizing the minimum utility.

Theorem 9. Given 0 < d < 1, for any n 2k agents, any deterministic strategyproof mechanism f which only selects from any k N+ candidates has an approximation ratio γ of at least + for maximizing the minimum utility.

Proof. Suppose strategyproof mechanism f = (y1, y2) only selects from any k 1 candidates, which are (y1,1, y1,2), (y2,1, y2,2), . . . , (yk,1, yk,2), with yi,2 yi,1 d for i = 1, 2, . . . , k. For n 2k agents, we select the location profile x satisfying

{y1,1, y1,2, y2,1, y2,2, . . . , yk,1, yk,2} x.

Note that for any strategyproof mechanism f, the minimum utility MU((y1, y2), x) = mini N{min{|y1 xi|, |y2 xi|}} = 0, because there are always agents which are located at y1, y2. Obviously, given location profile x, the optimal solution for maximizing the minimum utility must be greater than 0, because we can always choose y1, y2 which are not located at any location in x, respectively. Hence, we can conclude that there is no any deterministic strategyproof mechanism f with bounded approximation ratio γ.

Two-Facility Location Games with Minimum Distance Requirement

7. Game 5: Heterogeneous Two-Facility Location Games with Triple-preference

In this section, we design the deterministic strategyproof mechanism for the heterogeneous two-facility location game with triple-preference. Each agent has his own preference towards one out of the two heterogeneous facilities and we denote preference of agent i to facility j as pj i which is 1, 0 or 1. An agent i with pj i = 1 prefers to be close to facility j, an agent i with pj i = 1 prefers to be far away from facility j and an agent i with pj i = 0 is indifferent to facility j where j = 1, 2. We denote pi = {p1 i , p2 i } { 1, 0, 1}2 and p = {p1, p2, . . . , pn} represents the profile of all n agents preferences. We allow any agent to misreport both his location and his preferences. The social planner needs to gather information of both agents locations x and preferences p to determine the two facilities locations (y1, y2). Given the two facilities s locations (y1, y2) = f(x, p), we define agent i s utility towards facility j as

|yj xi| if pj i = 1 1 if pj i = 0 1 |yj xi| if pj i = 1 . (28)

Note that in the case that pj i = 1, to make the approximation ratio positive and meaningful, we require non-negative utilities and purposely add 1 to the utility; in the case of pj i = 0, we define agent i s utility as 1. Those methods are widely used (Zou & Li, 2015; Anastasiadis & Deligkas, 2018). Denote agent i s utility as

ui = u1 i + u2 i . (29)

The social utility of a mechanism f is defined as:

SU(f(x, p), (x, p)) =

i=1 ui(f(x, p), xi, pi). (30)

OPT3(x, p) is the optimal social utility. Next, we formally define the strategyproofness in the two-facility location game with triple-preference.

Definition 5. A mechanism f is strategyproof in the heterogeneous two-facility location game with triple-preference if no agent can benefit from misreporting his location or preferences. Formally, given agent i, location profile x = {xi, x i} In, preference profile p = {p1 i , p2 i , p i} { 1, 0, 1}2n, any misreported location x i I and any misreported preferences {p 1 i , p 2 i } { 1, 0, 1}2, it holds that

ui(f((xi, x i), (p1 i , p2 i , p i)), xi, pi) ui(f((x i, x i), (p 1 i , p 2 i , p i), xi, pi).

The group strategyproofness in the two-facility location game with triple-preference can be similarly defined as in Definition 2. A mechanism f has an approximation ratio γ, if for any profile x In and p { 1, 0, 1}2n, OPT3(x, p) γSU(f, x, p).

Xu, Li, Li & Duan

Set of agents {p1 i , p2 i } = {1,1} {1,-1} {-1,1} {-1,-1}

2] Q1 Q2 Q3 Q4 (1

2, 1] Q5 Q6 Q7 Q8

Set of agents {p1 i , p2 i } = {0,1} {0,-1} {1,0} {-1,0} {0,0}

2] Q9 Q10 Q11 Q12 Q13 (1

2, 1] Q14 Q15 Q16 Q17 Q18

Table 2: Sets of agents Q1 Q18.

Define eighteen sets of agents Q1 Q18 = N as shown in Table 2, depending on their locations and preferences. Then define the following sets based on Q1, . . . , Q18 :

R1 = {i|p1 i = 1} = Q1 Q2 Q5 Q6 Q11 Q16,

R2 = {i|p2 i = 1} = Q1 Q3 Q5 Q7 Q9 Q14,

R3 = {i|p1 i = 1} = Q3 Q4 Q7 Q8 Q12 Q17,

R4 = {i|p2 i = 1} = Q2 Q4 Q6 Q8 Q10 Q15. (31)

Define the social utility function SU(f(x, p), (x, p)) by (28), (29), (30), Table 2, and (31):

SU((y1, y2), (x, p)) = X

i R1 (1 |y1 xi|) + X

i R2 (1 |y2 xi|)

i R3 |y1 xi| + X

i R4 |y2 xi| + |Q13| + |Q18| +

i=9 |Qi|. (32)

To obtain OPT3 is to solve

max SU((y1, y2), (x, p)), s.t. (y1, y2) G = {(y1, y2)||y2 y1| d, 0 y1, y2 1}.

Note that different from the feasible region D in problem (10), the feasible region G includes two isosceles right triangles, as the two facilities are different to any agent. A mechanism outputting OPT3 is not strategyproof since this triple-preference game s special case is the obnoxious two-facility location game. We need to design a new deterministic strategyproof mechanism. Define N = R5 R6 R7, where

R5 = Q2 Q7 Q10 Q11 Q14 Q17,

R6 = Q3 Q6 Q9 Q12 Q15 Q16,

R7 = Q1 Q4 Q5 Q8 Q13 Q18. (33)

Mechanism 11. If |R5| |R6|, f(x, p) = (y1, y2) = (0, 1), otherwise, f(x, p) = (y1, y2) = (1, 0).

Theorem 10. Mechanism 11 is group strategyproof with an approximation ratio 4.

Two-Facility Location Games with Minimum Distance Requirement

Proof. By (28), (29) and Table 2, we have that for any agent i R5, ui((0, 1), xi, pi) ui((1, 0), xi, pi); for any agent i R6, ui((1, 0), xi, pi) ui((0, 1), xi, pi); and for any agent i R7, ui((0, 1), xi, pi) = ui((1, 0), xi, pi). Note that, in Mechanism 11, there are only two options of the two facilities locations, which are (0, 1) and (1, 0). By following the similar proof of group strategyproofness in Lemma 2, obviously, we can also prove Mechanism 11 is group strategyproof. Next, we prove the approximation ratio γ. Without loss of generality, assume that |R5| |R6|, and therefore (y1, y2) = (0, 1). Because |R5| |R6|, the optimal utility is

OPT3(x, p) = max (y1,y2) G SU((y1, y2), (x, p)) = X

i N max (y1,y2) G(u1 i + u2 i ) 2N

=2(|R5| + |R6| + |R7|) 4|R5| + 2|R7|. (34)

By (32) and (33), the social utility of Mechanism 11 is

SU((0, 1), (x, p)) = X

i R1 R4 (1 xi) + X

i R2 R3 xi + |Q13| + |Q18| +

(|Q1| + |Q2| + |Q11| + |Q2| + |Q4| + |Q10|) (1 0.5)

+ (|Q5| + |Q7| + |Q14| + |Q7| + |Q8| + |Q17|) 0.5 + |Q13| + |Q18| +

=|R5| + 0.5|R7| + 0.5(|Q10| + |Q11| + |Q14| + |Q17|) + (|Q9| + |Q12| + |Q15| + |Q16|)

+ 1.5(|Q13 + Q18|) |R5| + 0.5|R7|. (35)

By (34) and (35), the approximation ratio is

γ OPT3(x, p) SU((0, 1), (x, p)) 4|R5| + 2|R7|

|R5| + 0.5|R7| = 4.

The lower bound result of Theorem 5 for the obnoxious heterogeneous two-facility location game can carry over to the heterogeneous two-facility location game with triplepreference as we have remarked that the obnoxious facility location game is a special case of the two-facility location game with triple-preference.

8. Conclusions

We considered the mechanism design problem of a social planner for locating two facilities with minimum distance requirement on a line interval, where a set of n strategic agents report their locations. In the heterogeneous two-facility location game, we found the optimal solution and proved carefully choosing one optimal solution as output is strategyproof. We also designed a strategyproof mechanism minimizing the maximum cost. In the homogeneous two-facility location game, we proved any deterministic strategyproof mechanism has infinity approximation ratio. In the obnoxious heterogeneous two-facility location game, we proposed new deterministic group strategyproof mechanisms with provable approximation

Xu, Li, Li & Duan

ratios and obtained the lower bound 7 d

6 . We also designed a strategyproof mechanism maximizing the minimum utility. In the obnoxious homogeneous two-facility location game, we propose deterministic group strategyproof mechanisms with provable approximation ratios and also establish a lower bound 4/3. In the heterogeneous two-facility location game with triple-preference, we designed a deterministic group strategyproof mechanism with an approximation ratio 4. In the future, we will study the randomized mechanism design in the obnoxious twofacility location game and in the two-facility location game with triple-preference. Moveover, it would be interesting to extend our model to include more than two facilities with minimum distance requirement or consider the facility location games in more general metric spaces such as circles and trees.

Acknowledgments

Part of work has been presented in the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), Montreal, Canada, May 13-17, 2019 (Duan et al., 2019). Bo Li was supported by The Hong Kong Polytechnic University (Grant NO. P0034420). Minming Li is also from City University of Hong Kong Shenzhen Research Institute, Shenzhen, China. Minming Li was supported by a grant from Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. City U 11200518) and was partially sponsored by Project 11771365 supported by NSFC. Lingjie Duan is also with Shenzhen Institute of Artificial Intelligence and Robotics for Society, Shenzhen, China 518040. Lingjie Duan was supported by the Ministry of Education, Singapore, under its Academic Research Fund Tier 2 Grant (Project No. MOE2016T2-1173).

Appendix A. Proof of Theorem 5

Proof. Assume N = {1, 2, 3}. Let f be a deterministic mechanism. Consider the profile x = {x1, x2, x3} = {1+3d

4 } and f(x) = (y1, y2). Note that given d [0, 1], d x1 x2 x3 1. For easy access of agents utilities in the following proof, we make Table 3. For the social utilities, we have SU((0, d), x) = 3,

ui((x, y), xi) i = 1 i = 2 i = 3 (x, y) = (0, d) 1+d

2 (x, y) = (1 d, 1) 3 3d+|3 7d|

4 (x, y) = (0, 1) 1 1 1

Table 3: Agent s utility in (0, d), (1 d, 1), (0, 1).

SU((1 d, 1), x) = (6 6d + |3 7d| + |2 6d| + |1 5d|)/4 3,

and SU((0, 1), x) = 3. Hence, the optimal solution of x is

OPT2(x) = max{SU((0, d), x), SU((1 d, 1), x), SU((0, 1), x)} = 3. (36)

Two-Facility Location Games with Minimum Distance Requirement

Denote x as the location profile after one of the three agents misreports. Let (y 1, y 2) = f(x ) and (y 1, y 2) satisfies y 2 y 1 d and 0 y 1, y 2 1. We have the following cases. Case 1: y1 > x1 and y2 x3. We have d y2 y1 x3 x1 = 1 d

2 , which implies d 1

3. Since x1 < y1 y2 x3, by similar analysis and conclusion of Proposition 2, the social utility can reach its maximum when (y1, y2) is one out of (x1, x1 + d), (x1, x3), (x3 d, x3), which is

SU((y1, y2), x) max{SU((x1, x1 + d), x), SU((x1, x3), x), SU((x3 d, x3), x)}

= max{5 5d + |5d 1|

2 , 5 5d + |5d 1|

4 } 1.5. (37)

Accordingly, by (36) and (37), γ OPT2(x)/SU((y1, y2), x) 2.

v x1 = 1+3d

y2 Figure 4: Case 2 for the proof of Theorem 5.

Case 2: y1 x1 and y2 x1, as shown in Figure 4. In this case, u1((y1, y2), x1) 2x1 d = 1+d

2 . Consider x 1 = 0 and x = {x 1, x2, x3}. Note that SU((0, d), x ) = 5+d

SU((1 d, 1),x ) = 11 7d + |2 6d| + |1 5d|

> 3 if d [0, 1

9) 3 if d [1

and SU((0, 1), x ) = 3. Thus the optimal solution of x is

OPT2(x ) = max{SU((1 d, 1),x ), SU((0, 1), x )} 3. (38)

As f is strategyproof and agent 1 cannot gain by misreporting from x1 to x 1, the utility of agent 1 must satisfy

u1((y 1, y 2), x1) = |y 1 x1| + |y 2 x1| u1((y1, y2), x1) 1 + d

2 y 1 + y 2 2x1 + 1+d

2 |y 1 y 2| 1+d

2 y 1 + y 2 1 + 2d y 2 y 1 1+d

By (39), the domain of (y 1, y 2) is a convex polygon with corner points:

1. (0, d), (0, 1+d

4 ) if d [0, 1

2. (0, d), (0, 1+d

2 , 1), (2d, 1) if d (1

3. (0, d), (0, 1+d

2 , 1), (1 d, 1) if d (1

Hence, for the profile x , by similar analysis and conclusion of Proposition 2, the social utility of x under f can obtain its maximum if (y1, y2) is at one out of all corner points.

Xu, Li, Li & Duan

By some calculations, the social utility of x under f is

SU((y 1, y 2), x )

SU((0, d), x ) if d [0, 1

5] max{SU((0, d), x ), SU((1 d

2 , 1), x ), SU((2d, 1), x )} if d (1

3] max{SU((0, d), x ), SU((1 d

2 , 1), x ), SU((1 d, 1), x )} if d (1

2 if d [0, 1

2 , 3 2d} if d (1

2 , 2 + d} if d (1

3, 1] = 5 + d

Accordingly, by (38) and (40), γ OPT2(x )/SU((y 1, y 2), x ) 6 5+d. Case 3: y1 x1 and x1 < y2 x3. In this case,

SU((y1, y2), x) = (x1 + x2 + x3 y1) + (x3 x1 + |y2 x2|)

=x2 + 2x3 y1 + |y2 x2| x2 + 2x3 0 + (x3 x2) = 3(3 + d)

Accordingly, by (36) and (41), γ OPT2(x)/SU((y1, y2), x) = 4 3+d.

v x1 = 1+3d

y2 Figure 5: Case 4 for the proof of Theorem 5.

Case 4: y2 > x3, as shown in Figure 5. In this case, u3((y1, y2), x3) = y2 y1 1. Consider x 3 = 1 and x = {x1, x2, x 3}. Note that

SU((0, d), x ) = 2x1 d + 2x2 d + 2x 3 d = 7 d

SU((1 d, 1), x ) = 5 d + |3 7d| + |2 6d|

and SU((0, 1), x ) = 3. Thus the optimal solution of x is

OPT2(x ) = SU((0, d), x ) = 7 d

As f is strategyproof and agent 3 cannot gain by misreporting from x3 to x 3, the utility of agent 3 must satisfy

u3((y 1, y 2), x3) = |y 1 x3| + |y 2 x3| u3((y1, y2), x3) 1

2x3 1 y 1 + y 2 2x3 + 1 1 + d

2 y 1 + y 2. (43)

By (43), the feasible region of (y 1, y 2) is a convex quadrangle with corner points (0, 1+d

2 ), (0, 1), (1 d, 1) and (1 d

4 ). Hence, for the profile x , by similar analysis and conclusion

Two-Facility Location Games with Minimum Distance Requirement

of Proposition 2, the social utility of x under f can obtain its maximum if (y1, y2) is at one out of all four corner points, which is

SU((y 1, y 2), x )

max{SU((0, 1 + d

2 ), x ), SU((0, 1), x ), SU((1 d, 1), x ), SU((1 d

= max{5 + d

2 , 3, 5 d + |3 7d| + |2 6d|

4 , 2 + d} = 3. (44)

Accordingly, by (42) and (44), γ OPT2(x )/SU((y 1, y 2), x ) = 7 d

6 . In conclusion, f has an approximation ratio γ of at least

min{2, 6 5 + d, 4 3 + d, 7 d

Appendix B. Proof of Theorem 8

Proof. Assume N = {1, 2}. Let f be a deterministic mechanism. Consider the profile x = {x1, x2} = {1 d

4 } and f(x) = (y1, y2). Denote x as the location profile after one of the two agents misreports. Let (y 1, y 2) = f(x ). (y 1, y 2) satisfies y 2 y 1 d and 0 y 1, y 2 1.

4 v x2 = 3+d

y2 Figure 6: The proof of Theorem 8 given d < 1/5.

Note that given d [0, 1/5), 0 d x1 x2 1 d 1, as shown in Figure 6. We have the following cases. Case 1.1: y1 x1. In this case, u1((y1, y2), x1) = min{|y1 x1|, |y2 x1||} (1 d)/4. Consider x 1 = 0 and x = {x 1, x2}. The optimal social utility is

OPT2(x ) = SU((1 d, 1), x ) = (1 d) + (1 d) (3 + d)/4 = (5 9d)/4.

As f is strategyproof and agent 1 cannot gain by misreporting from x1 to x 1, the utility of agent 1 must satisfy u1((y 1, y 2), x1) u1((y1, y2), x1) (1 d)/4, which implies that y 1 (1 d)/2. The social utility under f is

SU((y 1, y 2), x ) max{SU(1 d

2 + d), x ), SU((1 d

2 , 1), x )}

2 + |x2 (1 d

2 + d)|), 1 d

2 + min{|x2 1 d

2 |, 1 x2}}

The approximation ratio is γ = OPT2(x )/SU((y 1, y 2), x ) 5 9d

Xu, Li, Li & Duan

Case 1.2: y2 x2. Due to symmetry, this case is similar with Case 1.1. Case 1.3: x1 y1 y2 x2. In this case,

SU((y1, y2), x) SU((x1, x1 + d), x) = x2 x1 d = 1 d

The optimal social utility is OPT2(x) = SU((0, d), x) = x1 d+x2 d = 1 2d. Accordingly, γ = OPT2(x)/SU((y1, y2), x) 2 4d

1 d . In conclusion, for d [0, 1/5), f has an approximation ratio γ of at least

1 d } = 5 9d

4 v x2 = 3+d

y2 Figure 7: The proof of Theorem 8 given d 1/5.

Now considering d [1/5, 1), we note that

0 x1 min{1 d, d} max{1 d, d} x2 1,

as shown in Figure 7. We have the following cases. Case 2.1: y1 x1 y2 x2, as shown in Figure 7. In this case, u1((y1, y2), x1) = x1 y1 (1 d)/4. Consider x 1 = 0 and x = {x 1, x2}. The optimal social utility is

OPT2(x ) = SU((1 d, 1), x ) = (1 d) 0 + min{|1 d x2|, 1 x2}

=1 d + min{5d 1

4 } = min{3 + d

As f is strategyproof and agent 1 cannot gain by misreporting from x1 to x 1, the utility of agent 1 must satisfy u1((y 1, y 2), x1) u1((y1, y2), x1) (1 d)/4, which implies that y 1 (1 d)/2. The social utility under f is

SU((y 1, y 2), x ) max{SU((1 d

2 + d), x ), SU((1 d

2 , 1), x )}

2 + min{|1 d

2 x2|, 1 x2}}

The approximation ratio is γ = OPT2(x )/SU((y 1, y 2), x ) min{5

3 3d}. Case 2.2: x1 y1 y2 x2. In this case,

SU((y1, y2), x) SU((x1, x1 + d), x) = (3 + d)/4 (1 d)/4 d = (1 d)/2.

For the optimal social utility,

OPT2(x) = SU((0, d), x) = min{x1 0, d x1} + x2 d

4 = min{1 d, 1 + d

Two-Facility Location Games with Minimum Distance Requirement

Accordingly, γ = OPT2(x)/SU((y1, y2), x) = min{2, 1+d

1 d}. Case 2.3: x1 y1 x2 y2. Due to symmetry, this case is similar with Case 2.1. Case 2.4: y1 x1 x2 y2. In this case,

SU((y1, y2), x) SU((0, 1), x) = (1 d)/4 + (1 d)/4 = (1 d)/2.

For the optimal social utility, OPT2(x) = min{1 d, (1 + d)/2}. Accordingly,

γ = OPT2(x)/SU((y1, y2), x) min{2, (1 + d)/(1 d)}.

In conclusion, for d [1/5, 1], f has an approximation ratio γ of at least

3 3d}, min{2, 1 + d

1 d}} = min{5

Therefore, f has an approximation ratio γ of at least 5 9d

3 3d if d [0, 1

5); 3+d 3 3d if d [1

3, 1), which is within [4

Anastasiadis, E., & Deligkas, A. (2018). Heterogeneous facility location games. In Proceedings of the 17th International Conference on Autonomous Agents and Multi Agent Systems (AAMAS), pp. 623 631.

Cai, Q., Filos-Ratsikas, A., & Tang, P. (2016). Facility location with minimax envy. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), pp. 137 143.

Cascella, M., Rajnik, M., Cuomo, A., Dulebohn, S. C., & Di Napoli, R. (2020). Features, evaluation and treatment coronavirus (covid-19). In Statpearls [internet]. Stat Pearls Publishing.

Chen, J., Li, B., & Li, Y. (2019). Efficient approximations for the online dispersion problem. SIAM Journal on Computing, 48(2), 373 416.

Cheng, Y., Yu, W., & Zhang, G. (2011). Mechanisms for obnoxious facility game on a path. In International Conference on Combinatorial Optimization and Applications (COCOA), pp. 262 271. Springer.

Cheng, Y., Yu, W., & Zhang, G. (2013). Strategy-proof approximation mechanisms for an obnoxious facility game on networks. Theoretical Computer Science, 497, 154 163.

Keijzer, B., & Wojtczak, D. (2018). Facility reallocation on the line. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pp. 188 194.

Duan, L., Li, B., Li, M., & Xu, X. (2019). Heterogeneous two-facility location games with minimum distance requirement. In Proceedings of the 18th International Conference on Autonomous Agents and Multi Agent Systems (AAMAS), pp. 1461 1469.

Xu, Li, Li & Duan

Feigenbaum, I., & Sethuraman, J. (2015). Strategyproof mechanisms for one-dimensional hybrid and obnoxious facility location models. In Workshop on Incentive and Trust in E-Communities at the 29th AAAI Conference on Artificial Intelligence (AAAI), pp. 8 13.

Fong, K. C., Li, M., Lu, P., Todo, T., & Yokoo, M. (2018). Facility location games with fractional preferences. In Proceedings of the 32th AAAI Confererence on Artificial Intelligence (AAAI), pp. 1039 1046.

Fotakis, D., & Tzamos, C. (2014). On the power of deterministic mechanisms for facility location games. ACM Transactions on Economics and Computation, 2(4), 15.

Fu, G., Wang, J., & Yan, M. (2016). Anatomy of tianjin port fire and explosion: Process and causes. Process Safety Progress, 35(3), 216 220.

Han, Q., & Du, D. (2011). Moneyless Strategy-proof Mechanism on Single-sinked Policy Domain: Characterization and Applications. Faculty of Business Administration, University of New Brunswick.

Ibara, K., & Nagamochi, H. (2012). Characterizing mechanisms in obnoxious facility game. In Proceedings of the 6th International Conference on Combinatorial Optimization and Applications (COCOA), pp. 301 311. Springer.

Jung, S. (2016). Facility siting and plant layout optimization for chemical process safety. Korean Journal of Chemical Engineering, 33(1), 1 7.

Kaplan, A. (2020). New jersey reverses decision to open two covid-19 testing sites to people without symptoms. https://www.nbcnews.com/health/health-care/ new-jersey-reverses-decision-open-two-covid-19-testing-sites-n1190016.

Klise, K. A., & Bynum, M. L. (2020). Facility location optimization model for covid-19 resources.. Tech. rep., Sandia National Lab.(SNL-NM), Albuquerque, NM (United States).

Lei, T. L., & Church, R. L. (2013). A unified model for dispersing facilities. Geographical Analysis, 45(4), 401 418.

Lu, P., Sun, X., Wang, Y., & Zhu, Z. A. (2010). Asymptotically optimal strategy-proof mechanisms for two-facility games. In Proceedings of the 11th ACM conference on Electronic commerce (ACM-EC), pp. 315 324.

Lu, P., Wang, Y., & Zhou, Y. (2009). Tighter bounds for facility games. In Proceedings of the 5th International Workshop on Internet and Network Economics (WINE), pp. 137 148.

Mei, L., Li, M., Ye, D., & Zhang, G. (2016). Strategy-proof mechanism design for facility location games: Revisited (extended abstract). In Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 1463 1464.

Moon, I. D., & Papayanopoulos, L. (1991). Minimax location of two facilities with minimum separation: interactive graphical solutions. Journal of the Operational Research Society, 42(8), 685 694.

Two-Facility Location Games with Minimum Distance Requirement

Moore, B., & Stamm, J. L. H. (2012). Impact of decentralized decision-making on access to public health facilities. In IIE Annual Conference. Proceedings, p. 1. Institute of Industrial and Systems Engineers (IISE).

Moulin, H. (1980). On strategy-proofness and single peakedness. Public Choice, 35(4), 437 455.

Procaccia, A. D., & Tennenholtz, M. (2009). Approximate mechanism design without money. In Proceedings of the 10th ACM conference on Electronic commerce (ACMEC), pp. 177 186.

Sakai, T., Beziat, A., & Heitz, A. (2020). Location factors for logistics facilities: Location choice modeling considering activity categories. Journal of Transport Geography, 85, 102710.

Schummer, J., & Vohra, R. V. (2002). Strategy-proof location on a network. Journal of Economic Theory, 104(2), 405 428.

Serafino, P., & Ventre, C. (2014). Heterogeneous facility location without money on the line. In Proceedings of the 21st European Conference on Artificial Intelligence (ECAI), pp. 807 812.

Serafino, P., & Ventre, C. (2015). Truthful mechanisms without money for non-utilitarian heterogeneous facility location. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI), pp. 1029 1035.

Sonoda, A., Todo, T., & Yokoo, M. (2016). False-name-proof locations of two facilities: Economic and algorithmic approaches. In Proceedings of the 30th AAAI Confererence on Artificial Intelligence (AAAI), pp. 615 621.

Sui, X., Boutilier, C., & Sandholm, T. W. (2013). Analysis and optimization of multidimensional percentile mechanisms. In Proceedings of the 27th AAAI Confererence on Artificial Intelligence (AAAI), pp. 367 374.

Todo, T., Iwasaki, A., & Yokoo, M. (2011). False-name-proof mechanism design without money. In Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems-Volume 2 (AAMAS), pp. 651 658.

Turken, N., Carrillo, J., & Verter, V. (2017). Facility location and capacity acquisition under carbon tax and emissions limits: To centralize or to decentralize?. International Journal of Production Economics, 187, 126 141.

Wada, Y., Ono, T., Todo, T., & Yokoo, M. (2018). Facility location with variable and dynamic populations. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 336 344.

White, D. (1993). Location of two facilities with minimal separation. Journal of the Operational Research Society, 1053 1057.

Xu, X., Duan, L., & Li, M. (2019). Strategic learning approach for deploying uav-provided wireless services. IEEE Transactions on Mobile Computing.

Xu, X., Li, M., & Duan, L. (2020). Strategyproof mechanisms for activity scheduling.. In Proceedings of the 19th International Conference on Autonomous Agents and Multi Agent Systems (AAMAS), pp. 1539 1547.

Xu, Li, Li & Duan

Yuan, H., Wang, K., Fong, K. C., Zhang, Y., Li, M., et al. (2016). Facility location games with optional preference. In Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI), pp. 1520 1527.

Zhang, Q., & Li, M. (2014). Strategyproof mechanism design for facility location games with weighted agents on a line. Journal of Combinatorial Optimization, 28(4), 756 773.

Zhong, Q., Karner, A., Kuby, M., & Golub, A. (2019). A multiobjective optimization model for locating affordable housing investments while maximizing accessibility to jobs by public transportation. Environment and Planning B: Urban Analytics and City Science, 46(3), 490 510.

Zou, S., & Li, M. (2015). Facility location games with dual preference. In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 615 623.