Strategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio

1 Introduction

Facility location games have been studied extensively in recent years. In the general setting, an authority adopts a mechanism to decide where to place the facilities in the existence of participating agents with their reported locations or preferences. The authority aims to minimize the social cost on the condition that agents will not gain by misreporting their information. This property is called strategyproofness. The cost of an agent is defined as his distance to the facility. In the most classic setting for single facility on a line and private location information of agents, the median mechanism is strategyproof and minimizes the social cost [Moulin, 1980]. Procaccia and Tennenholtz introduced the setting for twofacility location games and initiated the approximate mechanism design for facility location games [Procaccia and Tennenholtz, 2009]. In this two-facility model, an agent's cost is his distance to the closer facility. Unlike the single facility setting, the optimality no longer coincides with strategyproofness in this model. They proved constant lower bound for the approximation ratio and provide a strategyproof mechanism with linear O(n) approximation ratio. This left a huge gap for the ratio. Lu et al. obtained a randomized mechanism which achieves a constant approximation ratio of 4

linear lower bound Ω(n) for all deterministic strategyproof mechanisms [Lu et al., 2010].

In their model, two facilities are identical and an agent is interested in the one closer to him. For two heterogeneous facilities, some agent may only accept one of them and the cost is his distance to that particular one. Of course, if every agent is only interested in one of them, it becomes two separate single facility games and the solutions become trivial. The interesting setting is that some agents are interested in both facilities while others are interested in only one of them, and these preferences are agents' private information. In general, an agent's cost is his distance to the closest facility in his acceptable set. This heterogeneous facilities model was proposed in [Yuan et al., 2016]. To study the effect of private preference, they assumed that the location information is public in this new model. This is also a more realistic model since in many real facility location applications, agents' locations can be publicly verified.

In their paper, they proved a lower bound of 2 and provided a strategyproof mechanism with linear O(n) approximation ratio. This again left a huge gap for the ratio. It is also not clear whether there is a similar large gap between randomized and deterministic mechanisms as the homogeneous two-facility setting.

Besides its application relevance, the facility location game is also a very important playground for the theory of strategyproof mechanisms without money. Due to the remarkable Arrow's impossibility theorem [Arrow, 1950] and GibbardSatterthwaite's impossibility theorem [Gibbard, 1973; Satterthwaite, 1975], the space of strategyproof mechanisms is very limited. Gibbard-Satterthwaite's impossibility theorem states that any strategyproof social choice function onto a set of alternatives with at least three options is a dictatorship in the general preference domain. Basically, there are only two types of strategyproof mechanisms: dictatorship or majority voting on two options. The median mechanism is neither of them. The existence of such non trivial strategyproof mechanisms is due to single-peaked preference structure of the problem while the Gibbard-Satterthwaite's impossibility theorem is for general preferences. Due to this, single-peaked preference is an important direction in the study of strategyproof mechanisms without money. Studying other variants of facility location games may lead to the discovery of other interesting preference structures and non trivial strategyproof mechanisms. In most extended version of facility location games, the proposed strategyproof mechanisms are some versions (maybe randomized) of dictatorship, a majority voting of two boundary options or things like that. The proportional mechanism from [Lu et al., 2010] is one notably nontrivial example. But this one only satisfies a weaker version of strategyproofness, namely strategyproofness in expectation. This might be the reason why there is a huge gap between randomized and deterministic mechanisms. It would be more interesting if there are other nontrivial deterministic mechanisms.

1.1 Our Contribution

In this paper, we design a novel strategyproof mechanism which achieves an approximation ratio of 1 + 2α, where α is the approximation ratio of the offline optimization version. If we do not care about computational complexity or the offline optimization problem is polynomial time solvable such as the line metric case, this is a 3-approximation strategyproof mechanism. This asymptotically resolves the problem of the two heterogeneous facilities game. Our mechanism is very simple. We first ignore agents' preferences and assume that both facilities are acceptable for each agent. We then, purely based on the public location information of agents, compute the optimal locations of two facilities, which we call s1 and s2. On a line, the optimal location can be computed in polynomial time. Then among four possible locations of the two facilities (s1, s1), (s1, s2), (s2, s1), (s2, s2), we choose the one with the minimum social cost based on agents' reported preferences.

For the special case of line metric, we further improve the analysis and show that the same mechanism is of 2.75approximation. On the other hand, we construct an example to show that the approximation ratio of our mechanism is at least 1 + √2 and conjecture that this lower bound is tight.

Our mechanism is deterministic and very simple but at the same time highly non-trivial in the sense that its strategyproofness requires an interesting argument. It does not belong to the two exception families of Gibbard-Satterthwaite's impossibility theorem. The reason for the median mechanism being strategyproof is the single-peaked preference. It is an interesting open direction to figure out what kind of preference structure makes our mechanism strategyproof. This may lead to a generalized version of our mechanism, which works for a family of problems.

It is natural to think about the extension of our mechanism for the facility location game with three or more facilities. However, there is an example to show that the mechanism is no longer strategyproof even for line metric. The situation is similar to what happens in the proportional mechanism [Lu et al., 2010], whose three-facility version is no longer strategyproof. It is an interesting open question to extend our result to the facility location game with three or more facilities. We note that the same problem for homogeneous facilities remains open after almost a decade.

1.2 RelatedWorks

There are two major perspectives to approach the facility location game, namely, characterizing strategyproof mechanisms and designing strategyproof mechanisms. The classic agent preference for facility location games on a line is a special case of single-peaked preference for which [Moulin, 1980] characterized all the anonymous, strategyproof and efficient mechanisms and at the same time showed that median mechanism is strategyproof for minimizing social cost. This is the pioneering work in the field. Later on, more characterizations are studied on networks [Schummer and Vohra, 2002], for two facilities [Fotakis and Tzamos, 2014] and for double-peaked preference [Filos-Ratsikas et al., 2017]. There are also characterizations for other variants of facility location games.

When optimality no longer coincides with strategyproofness, Procaccia and Tennenholtz initiated the approximate mechanism design for facility location games [Procaccia and Tennenholtz, 2009]. Since then, facility location games are enriched from many different perspectives.

In terms of preference of agents for a single facility, [Cheng et al., 2011] initiated obnoxious facility location games where agents want to be far away from the facility, followed by [Ibara and Nagamochi, 2012; Oomine and Nagamochi, 2016; Mei et al., 2018b]. [Zou and Li, 2015] and [Feigenbaum and Sethuraman, 2015] studied dual preference where agents have different preferences towards the single facility. [FilosRatsikas et al., 2017] studied double-peaked preference.

In terms of the agents' cost function with respect to the distance to the facility, besides linear functions, there are also other functions studied. For example, threshold based linear function [Mei et al., 2018a], agent dependent linear function (happiness) [Mei et al., 2016] and concave function [Fotakis and Tzamos, 2016].

In terms of social objective, besides the mostly studied social cost/utility and maximum cost/utility, there are also other objectives studied like sum of square of distances[Feldman and Wilf, 2013; Mei et al., 2018b], difference of maximum distance and minimum distance (envy) [Cai et al., 2016].

The studies on heterogeneous facilities was initiated by [Serafino and Ventre, 2014; Serafino and Ventre, 2015], where the cost of an agent who likes both facilities is the sum of the distances to both facilities. When the cost is only affected by the closer facility or the farther facility, it is called optional preference and is studied by [Yuan et al., 2016]. Recently fractional preference is studied by [Fong et al., 2018], where the cost is a weighted sum of the two distances. There are also works setting a distance constraint between the two facilities, either maximum distance [Zou and Li, 2015; Chen et al., 2018] or minimum distance [Duan et al., 2019].

For other metric spaces, [Alon et al., 2010] and [Cheng et al., 2013] studied networks. [Lu et al., 2010] studied Euclidean space where a 4-approximated randomized strategyproof mechanism is proposed.

2 Preliminaries

There are n agents in a metric space with a distance metric d() and the government is to build two facilities (named as F1 and F2) for them. Agent i is located at xi and has a preference pi ∈ {{F1}, {F2}, {F1, F2}}. Here, we call x = {x1, x2, ..., xn} as location profile and p = {p1, p2, ..., pn} as preference profile.

Given that F1 is built at y1 and F2 is built at y2, we define the cost of agent i as cx,p,i(y1, y2) = mink:Fk∈pi d(xi, yk). Here, we denote by d(x, y) the distance between x and y in the metric space. The social cost is defined as SCx,p(y1, y2) = ∑ni=1 cx,p,i(y1, y2).

In this model, the government uses a mechanism to decide the places to build the facilities. More specifically, a mechanism takes a location profile x and a preference profile p as input and outputs facilities' locations.

Given that an agent might misreport his preference, which will lead to a different output by the mechanism and might lower his own cost, the government needs to design a strategyproof mechanism to avoid this situation.

Definition 1. (strategyproofness)

A mechanism M is strategyproof if for any agent, cheating will not decrease her cost. Formally, for any location and preference profile x and p and any agent i, if he cheats by misreporting his preference as p′i and the preference profile changes to p′ = {p1, ..., pi-1, p′i , pi+1, ..., pn}, then there must be cx,p,i(M(x, p)) ≤ cx,p,i(M(x, p′ )).

Given that no strategyproof mechanism achieves the minimum social cost [Yuan et al., 2016], we use approximation ratio to evaluate the performance of mechanisms.

Definition 2. (approximation ratio)

A mechanismM has an approximation ratio of γ if for any location and preference profile x and p, SCx,p(M(x, p)) ≤ γ · miny1,y2 SCx,p(y1, y2).

3 Our Strategyproof Mechanism

In this section, we introduce our mechanism and prove its strategyproofness. In Section 4, we will analyze its approximation ratio.

3.1 The Mechanism

Mechanism 1. Denote by q the preference profile {{F1, F2}, {F1, F2}, ..., {F1, F2}}, i.e. every agent prefers both facilities. Let A be the set of all available facility locations and let location pair (s1, s2) satisfy (s1, s2) = argminy1,y2∈A SCx,q(y1, y2). Finally, we output the pair (f1, f2) = arg miny1,y2∈{s1,s2} SCx,p(y1, y2). We break the tie in this order: (s1, s1), (s1, s2), (s2, s1), (s2, s2).

Actually, it is a special case of the k-median problem to calculate s1 and s2, i.e. the case in which k is equal to 2. When |A| is finite, we can enumerate the locations of s1 and s2 in O(|A|2 ) time. However, it might be hard when |A| is not finite and we may only use some approximation algorithm to solve the problem. For instance, [Arora et al., 1998] provides a PTAS for k-median for Euclidean space R2 .

In the rest of this paper, we denote by s′1 and s′2 the result calculated by the 2-median problem approximation oracle with approximation ratio α.

3.2 Strategyproofness

Theorem 1. Mechanism 1 is strategyproof.

Proof. By the definition of Mechanism 1, we can see that s′1 and s′2 do not rely on agents' preferences and the two facilities' locations will always be one among (s′1 , s′1 ), (s′1 , s′2 ), (s′2 , s′1 ) and (s′2 , s′2 ).

We first prove that the agent whose preference is {F1, F2} will not cheat. Suppose pi = {F1, F2}. We assume that s′2 is closer to agent i than s′1 . (The other case is the same except the tie breaking which does not affect the proof much.) Therefore, agent i has incentive to cheat only if Mechanism 1's output is (s′1 , s′1 ). Let p be the preference profile where no agent cheats and p′ be the preference profile where agent i misreports his preference as {F1}. Table 1 shows the difference in social cost for p′ and p.

Since Mechanism 1's output is (s′1 , s′1 ) for preference profile p, SCx,p(s′1 , s′1 ) is the minimum among those four social costs for p. By Table 1, we can see that SCx,p′ (s′1 , s′1 ) is the minimum among those four social costs for p′ . This shows that Mechanism 1's output will still be (s′1 , s′1 ) even if agent i misreports his preference as {F1}. Therefore, agent i has no incentive to misreport his preference as {F1}. Using the same analysis, we can prove that agent i has no incentive to misreport his preference as {F2}. Hence, agent i has no incentive to cheat.

We then prove that the agent whose preference is {F1} or {F2} will not cheat. Suppose that pi = {F1}. (Using a similar analysis we can prove the case that pi = {F2}.) Again, We just assume that s′2 is closer to agent i than s′1 since the proof for the other case is similar. Hence, agent i might cheat only when F1 is built at s′1 . At this time, F2 may be built at s′1 or s′2 . Let p be the preference profile where no agent cheats, p′ be the preference profile where agent i misreports his preference as {F2} and p′′ be the preference profile where agent i misreports his preference as {F1, F2}. Table 2 shows the difference in social cost for p′ and p and for p′′ and p.

If F2 is built at s′1 for p, then

By Table 2, we can see that

This means F1 will not be built at s′2 even if agent i misreports his preference as {F2} or {F1, F2}.

If F2 is built at s′2 for p, then

By Table 2, we can see that

Similarly, this means that agent i's misreporting will not make F1 closer. Therefore agent i has no incentive to cheat.

4 Analysis of the Approximation Ratio

4.1 Preparation

Before we analyze the approximation ratio of Mechanism 1, we introduce some lemmas.

Lemma 1. Denote Mechanism 1 by M. Suppose there is an instance (x, p) such that SCx,p(M(x, p)) = α · miny1,y2 SCx,p(y1, y2) and pi = {F1, F2}. Then there exists a preference profile ˜ p which differs only at agent i's preference such that ˜ pi ̸= {F1, F2} and SCx,˜ p(M(x, ˜ p)) ≥ α · miny1,y2 SCx,˜ p(y1, y2).

Proof. Suppose (x, p) is an instance as above. Let (opt1, opt2) be the locations such that SCx,p(opt1, opt2) = miny1,y2 SCx,p(y1, y2). Define

Let ˜ p be the preference profile obtained by replacing pi with ˜ pi in p.

We first prove SCx,p(M(x, p)) ≤ SCx,˜ p(M(x, ˜ p)). Since the location profiles in (x, p) and (x, ˜ p) are the same, (s′1 , s′2 ) in M(x, p) and M(x, ˜ p) are the same. Note that for any (y1, y2) we have SCx,p(y1, y2) ≤ SCx,˜ p(y1, y2), since ˜ pi ⊆ pi and other agents' preferences are the same. Therefore, we have SCx,p(y1, y2) ≤ SCx,˜ p(y1, y2) for y1, y2 ∈ {s′1 , s′2 }, which implies

We then prove min y1,y2 SCx,p(y1, y2) ≥ min y1,y2 SCx, ˜ p(y1, y2). By the definition of ˜ pi, we have

Therefore, we have

Since analyzing the approximation ratio is just finding an instance with maximum α as above, by Lemma 1 and simple induction, we can assume pi ̸= {F1, F2} for every i ∈ {1, 2, ..., n} when we analyze the approximation ratio of Mechanism 1.

Lemma 2. SCx,q(s′1 , s′2 ) ≤ α · miny1,y2 SCx,p(y1, y2) holds for any location profile x and preference profile p.

Proof. Since SCx,q(s′1 , s′2 ) gives an α-approximation for SCx,q(s1, s2), we have

4.2 Analysis of the Approximation Ratio of 1+2α

We first introduce some notations to simplify the description of later analysis.

Given location profile x and preference profile p, by Lemma 1, we can divide all agents into two sets {i|pi = {F1}} and {i|pi = {F2}}. Let opt1 be the geometric median of multiset S1 = {xi|pi = {F1}} and opt2 be the geometric median of multiset S2 = {xi|pi = {F2}}. Then we have SCx,p(opt1, opt2) = miny1,y2 SCx,p(y1, y2).

Given point set S and point v, we define d(S, v) = ∑u∈S d(u, v). (This definition differs from the common one where d(S, v) is defined as minu∈S d(u, v).) We define some notations as follows.

• SCk ≜ min{d(Sk, s′1 ), d(Sk, s′2 )}, k = 1, 2. SC ≜ SC1 + SC2.
• OPTk ≜ d(Sk, optk), k = 1, 2. OPT ≜ OPT1 +OPT2.
• BESTk ≜ ∑x∈Sk min{d(x, s′1 ), d(x, s′2 )}, k = 1, 2. BEST ≜ BEST1 + BEST2.

Intuitively, SC is equal to the social cost calculated by Mechanism 1, i.e. SCx,p(M(x, p)). OPT is equal to the minimum social cost for p, i.e. miny1,y2 SCx,p(y1, y2). BEST is equal to the approximated minimum social cost for q, i.e. SCx,q(s′1 , s′2 ). (q is defined in Mechanism 1.) With these notations, Lemma 2 implies BEST ≤ α · OPT .

Now, we introduce our result on the approximation ratio of Mechanism 1.

Theorem 2. Mechanism 1 has an approximation ratio of 1+ 2α, i.e. SC ≤ (1+2α) · OPT.

Proof. We try to prove SC -OPT ≤ 2 · BEST . It suffices to show SCk -OPTk ≤ 2 ·BESTk, k = 1, 2. By symmetry, we only show SC1 - OPT1 ≤ 2 · BEST1.

We divide S1 into A and B using the following rule. For each x ∈ S1, if d(x, s′1 ) < d(x, s′2 ), then let x ∈ A. Otherwise, let x ∈ B. Without loss of generality, suppose that |A| ≥ |B|. Observe that for any two agents' locations x and y, by triangle inequality we have

Hence, we divide A into A1 and A2 such that |A1| = |B| and A = A1 ∪ A2 and match each location in B with a location in A1. Using the observation above, we have

By Lemma 2, we have SC - OPT ≤ 2 · BEST ≤ 2α · OPT . Hence, SC ≤ (1 + 2α) · OPT .

Consider the following two special metric spaces:

• The metric space is R2 . In this case, for any fixed ϵ > 0, by [Arora et al., 1998] we have a (1 + ϵ/2)- approximation polynomial time algorithm for 2-median problem, i.e. α = 1 + ϵ/2. Thus, Mechanism 1 guarantees an approximation of 3 + ϵ.
• The metric space is a line, i.e. R. In this case, it is easy to find exact 2-median in polynomial time. Thus, Mechanism 1 guarantees an approximation of 3, which is a substantial improvement given the best result achieved by [Yuan et al., 2016] is n/2 + 1.

4.3 Improvement for Line Metric

In this section, we only consider the line metric case, i.e. the metric space is R. For simplicity of later analysis, let ∆k = (SCk - OPTk)/2, k = 1, 2 and ∆ = ∆1 + ∆2. In this case, we can calculate exact s1 and s2 in polynomial time, thus we just use sℓ and sr in the analysis instead and suppose sℓ ≤ smid ≤ sr where smid is the midpoint of sℓ and sr. Since the metric is R, opt1 and opt2 are the median values of S1 and S2. Without loss of generality, we can assume both |S1| and |S2| are even. (Otherwise we just double the number of agents by making a copy of original agents. This does not change the approximation ratio.)

We observe that our analysis can be tightened by doing some trade-off so as to get the following result.

Theorem 3. Mechanism 1 has an approximation ratio of 2.75, i.e. SC ≤ 2.75 · OPT .

Proof. We bound ∆1 first. By symmetry, we assume that opt1 ≤ smid. Let sc be the point satisfying d(sc, smid) = c · d(sℓ, sc). Here, c is a constant parameter to be determined later.

We analyze in the following three cases, according to the position of opt1.

In this case, we divide S1 into four parts: X1, X2, X3 and X4.

1. X1 contains the points on the left of opt1.
2. X2 contains the points between opt1 and sℓ.
3. X3 contains the points between sℓ and smid.
4. X4 contains the points on the right of smid.

We allocate points on the boundary in such a way that |X1| = |X2| + |X3| + |X4| (This can be achieved since opt1 divides S1 into two parts, left part and right part, of the same size).

Since opt1 ≤ sℓ, we find that ∆1 is equal to the distance between sℓ and points in S1 which lie between opt1 and sℓ, i.e. d(X2, sℓ). Hence, we have

In this case, we have

This implies ∆1 ≤ 1/2 · BEST1.

In this case, we divide S1 into five parts: X1, X2, X3, X4 and X5.

1. X1 contains the points between sℓ and opt1.
2. X2 contains the points between smid and sr.
3. X3 contains the points between opt1 and smid.
4. X4 contains the points on the left of sℓ.
5. X5 contains the points on the right of sr.

Similarly, we can assume |X1|+|X4| = |X2|+|X3|+|X5|. By the definition of ∆1, using a similar proof as Theorem 2, we have

In this case, we have

Since d(sc, smid) = c · d(sℓ, sc) and d(sℓ, smid) = d(smid, sr), we have d(sc, sr) = (2c + 1) · d(sℓ, sc). Given that opt1 ≥ sc in this case, d(v, sr) ≤ (2c + 1) · d(v, sℓ) holds for every v ∈ X3. Thus, we have d(X3, sr) ≤ (2c + 1) · d(X3, sℓ). Hence,

If d(X1, sℓ) ≤ (2c + 1)/(2c + 2) · BEST1, then

Otherwise, d(X1, sℓ) > (2c + 1)/(2c + 2) · BEST1. Then,

Therefore, in this case, we have ∆1 ≤ (2c + 1)/(2c + 2) · BEST1.

In this case, we divide S1 into the same five parts defined in Case 2. Similar to Case 2, we have

Let β be a constant parameter in (0, 1). We will determine the value of β later.

This implies that ∆1 ≤ 1/(1 + β) · BEST1.

Otherwise, d(X2, sr) + d(X3, sℓ) < β · d(X1, sℓ). Then we have

Now we use OPT1 to bound ∆1. By definition, we have

Note that d(v, opt1) = d(opt1, sr) - d(v, sr) holds for every v ∈ X2 and d(v, opt1) ≥ d(opt1, sr) holds for every v ∈ X5. Hence, we have

Note that we have d(X1, sℓ) ≤ |X1| · d(sℓ, opt1) ≤ |X1| · d(sℓ, sr)/(2c + 2). Hence,

OP T1

This means that we have

We summarize those three cases. Let c = 1 and β = 1/(2c + 1) = 1/3. At least one of the following will happen:

or

Similarly, we can get the for ∆2:

Since there is no relationship between OPT1 and BEST1, we consider ∆1 and ∆2 together, using ∆ = ∆1 +∆2. Without loss of generality, we assume BEST1 ≥ BEST2. We analyze in the following 4 cases:

Case 1: ∆1 ≤ 3/4 · BEST1, ∆2 ≤ 3/4 · BEST2. In this case, we have

Case 2: ∆1 ≤ 1/2 · OPT1, ∆2 ≤ 1/2 · OPT2. In this case, we have

Case 3: ∆1 ≤ 1/2 · OPT1, ∆2 ≤ 3/4 · BEST2. In this case, we have

Case 4: ∆1 ≤ 3/4 · BEST1, ∆2 ≤ 1/2 · OPT2. In this case, we have

It is easy to see that ∆ ≤ 7/8 · OPT holds for all these four cases. Therefore, we have SC - OPT = 2 · ∆ ≤ 2 · 7/8 · OPT = 7/4 · OPT , i.e. SC ≤ 2.75 · OPT .

4.4 A Lower Bound of the Approximation Ratio of Mechanism 1

We provide a lower bound for the approximation ratio of Mechanism 1.

Consider the line metric R. Let N be a positive integer. Let N agents be located at x = 0 with preference {F1}, ⌊(1 + √2)N⌋ agents be located at x = 1 with preference {F1} and almost infinite (far greater than N) agents be located at x = √2 with preference {F2}. We can see that (sℓ, sr) will be (0, √2). Note that the minimum social cost is N while the social cost calculated by Mechanism 1 is min(⌊(1 + √2)N⌋, √2N + ⌊(1 + √2)N⌋(√2 - 1)). When N increases to infinity, the ratio of social cost by Mechanism 1 to the minimum social cost approaches 1 + √2. Therefore, 1+ √2 is a lower bound of the approximation ratio of Mechanism 1.

5 Generalization

We have tried to generalize our mechanism to k facilities (k ≥ 3). Our generalized mechanism first ignores agents' preferences and assumes all facilities are acceptable for each agent. Then it only uses the location profile to calculate the optimal locations of all k facilities, which we denote as s1, s2, ..., sk. Finally, the mechanism enumerates Fi's location being at sj, kk cases in total, and chooses the one that minimizes the social cost.

However, unfortunately, this generalized mechanism is not strategyproof when there are more than two facilities. We use an example to show that this mechanism is not able to prevent agents from misreporting their preferences when there are three facilities.

Example 1. Consider the line metric. Suppose that l1 and l2 are two positive numbers satisfying 2l2 < l1 < 3l2. Let

• two agents whose preferences are {F2} be located at x = 0,
• one agent whose preference is {F2} be located at x = l1 - l2,
• one agent whose preference is {F2} be located at x = l1,
• one agent whose preference is {F2, F3} be located at x = l1 + l2,
• almost infinite agents whose preferences are {F1} be located at x = 0,
• almost infinite agents whose preferences are {F3} be located at x = 2l1 + l2.

We can see that if we use the generalized mechanism on this instance, (s1, s2, s3) will be (0, l1, 2l1 + l2). (See Figure 1.) The almost infinite agents at s1 with preferences {F1} force F1 to be built at s1. (Otherwise, the social cost will be almost infinite.) For the same reason, F3 will be built at s3.

By enumerating all three possible locations of F2 and calculating the social costs, we find that if all agents report their true preferences, then F2 will be built at s1. However, if the agent at l1+l2 (with preference {F2, F3}) misreports his preference as {F2}, then F2 will be built at s2 and the cost of this agent will decrease from l1 to l2. Therefore, this generalized mechanism fails to prevent this agent from misreporting his preference.

In this example, we find that the preferred facilities of the agent at l1 + l2 are built at the second nearest and the third nearest possible location in {s1, s2, s3}. By hiding his preference to the facility which is built at the second nearest possible location, the agent increases the social cost and thus the generalized mechanism chooses another solution where another preferred facility of the agent is built at the nearest possible location to the agent. However, this situation will not happen when there are only two facilities because the mechanism chooses the facilities' locations only between two possible locations s1 and s2. That is the reason why the mechanism is strategyproof when there are only two facilities but not strategyproof for three facilities.

Consider the facility location game with k facilities, where k > 3. For every i ∈ {4, 5, ..., k}, we add almost infinite agents whose locations are x = (i - 1) · l1 + l2 and preferences are {Fi} to the example above. We can see that the new example shows that the generalized mechanism is not strategyproof when there are k > 3 facilities. Hence, this generalized mechanism is not strategyproof for the facility location game with more than two facilities.

6 Conclusion

To summarize, we have designed a strategyproof mechanism whose approximation ratio is no more than 1+2α and no less than 1+ √2, where α is the approximation ratio of the offline optimization version. It is an open question whether the exact approximation ratio of this mechanism for line metric is 1+ √2. Furthermore, the bounds for approximation ratios of strategyproof mechanisms for two facilities do not match yet.

Besides, it is also an interesting open question to design a strategyproof mechanism with constant approximation ratio for the facility location game with three or more facilities.

Acknowledgements

Yuhao Yao and Jialin Zhang are supported in part by the 973 Program of China Grant No. 2016YFB1000201, the National Natural Science Foundation of China Grants No. 61832003, 61872334, 61761136014.

Minming Li is also from City University of Hong Kong Shenzhen Research Institute, Shenzhen, P. R. China. He is supported by a grant from Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. CityU 11200518) and is partially sponsored by the National Natural Science Foundation of China Grants No.11771365.

Pinyan Lu is supported by Science and Technology Innovation 2030 -"New Generation of Artificial Intelligence" Major Project No. 2018AAA0100903, the National Natural Science Foundation of China Grants No. 61922052, Innovation Program of Shanghai Municipal Education Commission, Program for Innovative Research Team of Shanghai University of Finance and Economics (IRTSHUFE) and the Fundamental Research Funds for the Central Universities.