# on_discrete_truthful_heterogeneous_twofacility_location__9f1285d1.pdf

On Discrete Truthful Heterogeneous Two-Facility Location

Panagiotis Kanellopoulos , Alexandros A. Voudouris , Rongsen Zhang School of Computer Science and Electronic Engineering, University of Essex, UK {panagiotis.kanellopoulos, alexandros.voudouris, rz19109}@essex.ac.uk

We revisit the discrete heterogeneous two-facility location problem, in which there is a set of agents that occupy nodes of a line graph, and have private approval preferences over two facilities. When the facilities are located at some nodes of the line, each agent derives a cost that is equal to her total distance from the facilities she approves. The goal is to decide where to locate the two facilities, so as to (a) incentivize the agents to truthfully report their preferences, and (b) achieve a good approximation of the minimum total (social) cost or the maximum cost among all agents. For both objectives, we design deterministic strategyproof mechanisms with approximation ratios that signiﬁcantly outperform the state-of-the-art, and complement these results with (almost) tight lower bounds.

1 Introduction In the classic truthful single-facility location problem, there is a set of agents with private positions on the line of real numbers, and a public facility (such as a library or a park) whose location we need to decide. This decision must be made so as to (a) incentivize the agents to truthfully reveal their positions (an agent would be willing to lie if this leads to the facility being located closer to her true position), and (b) optimize a social objective (such as the total distance of the agents from the facility location, or the maximum distance). Since the celebrated paper of Procaccia and Tennenholtz [2013], this problem and its many variants have been studied extensively in the literature on approximate mechanism design without money. For a comprehensive introduction to the various different facility location models that have been considered over the years, we refer the interested reader to the recent survey of Chan et al. [2021]. A recent stream of papers have focused on heterogeneous facility location problems, with multiple facilities (typically, two) that are different in nature (e.g., a school and a bar). As such, the agents care both for the location and the types of the facilities, aiming for the facilities they like the most to be as close to their position as possible. To give an example, a family would like to be closer to a school than to a bar, a single person might want to be closer to the bar, and a young couple

might want to be close to both facilities. Many settings have been proposed to model the different preferences the agents may have about the facilities (see the discussion in the related work). With few exceptions, all of these models assume that both facilities can be placed at any point of the real line, even at the same one. Seraﬁno and Ventre [2016] deviated from these assumptions and studied a discrete version of the problem. In this model, the line is a discrete graph, and each node of this graph is either occupied by a single agent, or is empty. This information is assumed to be common knowledge. There are also two facilities (such as the school and the bar in our example above) which can only be placed at different nodes of the line. Each agent has a private approval preference over the facilities, that is, she either wants to be close to a facility or is indifferent about its location. Given the locations of the facilities, the cost of an agent is then deﬁned as the total distance from the facilities she approves. Seraﬁno and Ventre presented bounds on the approximation ratio of deterministic and randomized mechanisms in terms of both social objectives of interest. In particular, for the social cost, they showed that the best possible approximation ratio of deterministic mechanisms is between 9/8 and n 1, where n is the number of agents. In contrast, they designed a randomized mechanism that always outputs a solution with minimum expected social cost. For the maximum cost objective, they showed that the best possible approximation ratio of deterministic mechanisms is between 3/2 and 3, and that of randomized mechanisms is between 4/3 and 3/2. In this paper, we focus exclusively on deterministic mechanisms, and improve upon the bounds of Seraﬁno and Ventre for both the social and the maximum cost.

1.1 Our Contribution

The main technical difﬁculty of designing deterministic strategyproof mechanisms with low approximation ratio in terms of the social cost is the constraint of locating the two facilities at different nodes. Observe that if each agent approves just a single facility, then locating each facility to the median agent among those that approve it would be a strategyproof mechanism with minimum social cost. However, in general there might exist agents that approve both facilities, in which case the medians for the two facilities might coincide, and any choice of how to break this tie could lead to some agent having incentive to misreport.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

To overcome this bottleneck, Seraﬁno and Ventre presented a deterministic mechanism, named TWOEXTREMES, which works along the lines of the mechanism considered by Procaccia and Tennenholtz [2013] for homogeneous 2-facility location. TWOEXTREMES locates one of the facilities at the node occupied by the leftmost agent among those that approve it, and the other facility at the node occupied by the rightmost agent among those that approve it; in case of a collision, one of the facilities is moved a node to the left or the right. There are two main reasons for the deﬁciency of TWOEXTREMES: (i) the boundary agents (leftmost and rightmost) among those that approve a facility may be rather far away from the median such agent, whose node would be the ideal location for the facility, and (ii), it does not exploit the available information about the position of the agents in any way. Our improved mechanisms take care of these two reasons: We place the facilities closer to median agents (without breaking strategyproofness), and exploit the information about the agent positions of the agents. For the social cost, we design the FIXED-OR-MEDIANNEAREST-EMPTY (FMNE) mechanism with an approximation ratio of at most 17/4 = 4.25. The mechanism switches between two cases based on the structure of the line: If there are no empty nodes, it ﬁxes the locations of the facilities to be the two central nodes of the line, it locates one of the facilities at the position of the median agent among those that approve it, and the other facility at one of the nearest empty nodes to the median agent among those that approve it. We complement this result with an improved lower bound of 4/3 on the approximation ratio of all mechanisms, which follows by two instances with only three agents and no empty nodes. Motivated by this lower bound construction, we then focus on instances with three agents, and design the 3-agent PRIORITYDICTATORSHIP mechanism that achieves the best-possible bound of 4/3. For the maximum cost, we design a parameterized class of mechanisms α-LEFT-RIGHT (α-LR), each member of which partitions the line into two parts, from the ﬁrst node to node α, and from node α + 1 to the last node. Then, the decision about the locations of the facilities is based on the preferences of the agents included in the two parts. We show that all mechanisms of the class are strategyproof, and there are members with approximation ratio at most 2. In particular, when the size m of the line is an even number, the bound is achieved by m/2-LR, and when m is odd, it is achieved by (m + 1)/2-LR. Finally, we show a tight lower bound of 2 on the approximation ratio of all strategyproof mechanisms, using a construction involving a sequence of ﬁve instances with three agents and no empty nodes. An overview of our bounds, and how they compare to the previously best ones shown by Seraﬁno and Ventre [2016], is given in Table 1.

1.2 Related Work As already mentioned above, the survey of Chan et al. [2021] nicely discusses the many different facility models that have been considered over the years. Here, we will mainly discuss papers on heterogeneous facility location models that are closely related to ours. Besides the work of Seraﬁno and Ventre [2016], our paper here, and a few ones on homoge-

Lower bound Upper bound Social cost 4/3 (9/8) 17/4 (n 1) Maximum cost 2 (3/2) 2 (3)

Table 1: An overview of our bounds on the approximation ratio of deterministic strategyproof mechanisms for the social cost and the maximum cost. The bounds in parentheses are the previously best known ones shown by Seraﬁno and Ventre [2016]. The lower bound of 4/3 marked with a is tight for instances with three agents.

neous truthful facility location (e.g., [Feldman et al., 2016; Filos-Ratsikas and Voudouris, 2021]) and on characterizations of onto strategyproof mechanisms for the single-facility location problem on discrete lines, cycles and trees [Dokow et al., 2012; Filimonov and Meir, 2021], the literature has focused on continuous settings, where the facilities can be located at any point of the line, even the same one. The ﬁrst heterogeneous facility location model, combining elements from the classic single-facility location problem and the obnoxious single-facility location problem [Cheng et al., 2011; Cheng et al., 2013], was independently proposed and studied by Feigenbaum and Sethuraman [2015] and Zou and Li [2015]. In this setting, there are two facilities to be located on the real line, and each agent has dual preferences (either likes or dislikes a facility). The authors showed bounds on the approximation ratio of deterministic and randomized strategyproof mechanisms for different cases depending on whether the positions or the preferences of the agents are their private information. Kyropoulou et al. [2019] considered an extension of this model, where the location space of the two facilities is a constrained region of the Euclidean space. Chen et al. [2020] studied a setting with agents that have approval preferences over the facilities (as we do here). The authors consider two different cost functions of the agents, either the distance from the closest facility that the agent approves, or the distance from the farthest such facility. Li et al. [2020] studied an extension of this setting in more general metrics, and designed mechanisms that improve some results of Chen et al.. Deligkas et al. [2021] considered a similar preference model, but with the objective of locating only one of the facilities (and, more generally, k out of m). Anastasiadis and Deligkas [2018] considered a model that combines dual and approval preferences, in the sense that the agents can like, dislike or be indifferent about a facility. Fong et al. [2018] considered a setting with fractional preferences, where each agent has a weight in [0, 1] for each facility indicating how much she likes it. Finally, Xu et al. [2021] considered the problem where the locations of the two facilities must satisfy a minimum distance requirement.

2 Preliminaries

We consider the discrete two-facility location problem. An instance I of this problem consists of a set N of n 2 agents, two facilities, and a line graph with m n nodes. Each agent occupies a node xi of the line, such that different agents occupy different nodes. By x we denote the position proﬁle which includes information about which nodes are occupied by which agents and which nodes are left empty (if

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

any); the position proﬁle is assumed to be common knowledge. Every agent i also has a private approval preference ti {0, 1}2 over the two facilities: If tij = 1, agent i N approves facility j {1, 2}; otherwise, she disapproves it. By t = (ti)i N we denote the preference proﬁle consisting of the preferences of all agents. It will be useful to denote by Nj the set of agents that approve facility j {1, 2}. Clearly, the two sets N1 and N2 need not be disjoint if there are agents that approve both facilities. As x and t implicitly include all the necessary information related to an instance, we denote I = (x, t). A feasible solution z = (z1, z2) determines the node zj where each facility j {1, 2} is located, so that z1 = z2. Given a feasible solution z, the cost of any agent i in instance I is her total distance from the facilities she approves, i.e.,

costi(z|I) = X

j {1,2} tij d(i, j),

where d(i, j) = |xi zj| is the distance between agent i and facility j. A mechanism takes as input an instance and outputs a feasible solution. A mechanism M is said to be strategyproof if the solution M(I) it computes when given as input the instance I = (x, t) is such that no agent i has incentive to report a false preference t i = ti to decrease her cost, i.e.,

costi(M(I)|I) costi(M(x, (t i, t i))|I),

where (t i, t i) is the preference proﬁle according to which agent i s preference is t i, while the preference of any other agent is the same as in t. We consider two well-known social objectives, which are functions of feasible solutions. Given an instance I, the social cost of a feasible solution z is the total cost of all the agents, i.e.,

SC(z|I) = X

i N costi(z|I).

The max cost of z is the maximum cost among all agents, i.e.,

MC(z|I) = max i N costi(z|I).

Let SC (I) = minz SC(z|I) be the minimum possible social cost for instance I, achieved by any feasible solution. Similarly, let MC (I) = minz MC(z|I) be the minimum possible maximum cost for I. For any objective f {SC, MC}, the f-approximation ratio of a mechanism M is the worst-case ratio (over all possible instances) between the objective value of the solution computed by M over the minimum possible objective value among all feasible solutions, i.e.,

ρ(M) = sup I

Our goal is to design strategyproof mechanisms with an as low f-approximation ratio as possible (close to 1). Due to lack of space, the proofs of some statements are omitted.

Mechanism 1: FIXED-OR-MEDIAN-NEARESTEMPTY (FMNE)

1 Input: Instance I with n agents ;

2 Output: Feasible solution z = (z1, z2) ;

3 if there are no empty nodes then // FIXED part

5 z2 n/2 + 1;

6 else // MEDIAN-NEAREST-EMPTY part

7 for j {1, 2} do

8 yj position of the leftmost median agent in Nj;

10 z2 nearest empty node to y2, breaking ties in favor of the rightmost such empty node;

3 A Constant-Approximation Strategyproof Mechanism for the Social Cost For general instances with n agents, we design the strategyproof mechanism FIXED-OR-MEDIAN-NEAREST-EMPTY (FMNE) with approximation ratio 17/4 for the social cost, thus greatly improving upon the previous bound of n 1 of Seraﬁno and Ventre [2016]. Our mechanism exploits the known information about the position proﬁle, and distinguishes between two cases depending on whether the given instance contains empty nodes or not. If there are no empty nodes, FMNE locates the facilities next to each other at central nodes of the line (in particular, nodes n/2 and n/2 + 1); this is the FIXED part of the mechanism. If there are empty nodes, FMNE locates facility 1 at the node occupied by the median agent among those that approve facility 1, and facility 2 at the empty node that is nearest to the node occupied by the median agent among those that approve facility 2; this is the MEDIAN-NEAREST-EMPTY part of the mechanism. See Mechanism 1. Theorem 1. FMNE is strategyproof. To argue about the approximation ratio of FMNE, we will distinguish between instances with and without empty nodes. In our proofs, we exploit the following lower bounds on the optimal social cost. Here, 1 {X} is equal to 1 if the event X is true, and 0 otherwise. Lemma 1 ([Seraﬁno and Ventre, 2016]). For any instance I in which there are nj agents that approve facility j {1, 2}, it holds that

n2 1 + n2 2 1 {n1 odd} 1 {n2 odd}

n2 1 + n2 2 2 .

For instances without empty nodes and n 5, we will show that the approximation ratio of the FIXED part of FMNE is at most 3; note that for n 4, the TWOEXTREMES mechanism of Seraﬁno and Ventre [2016] is 3-approximate. Theorem 2. For instances with n 5 agents and no empty nodes, the SC-approximation ratio of FMNE is at most 3.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

For instances with empty nodes, we show that the approximation ratio of the MEDIAN-NEAREST-EMPTY part of FMNE is 17/4 for n 6; observe that TWOEXTREMES achieves an approximation ratio of at most 4 when n 5 [Seraﬁno and Ventre, 2016]. Our proof for the approximation ratio in this case relies on the following technical lemma.

Lemma 2. Let f(x, y) = y2+4xy+2y+1

x2+y2 2 . For non-negative integers x, y such that x + y 6, it holds f(x, y) 13/4. We are now ready to prove the bound. Theorem 3. For instances with n 6 and at least one empty node, the SC-approximation ratio of FMNE is at most 17/4.

Proof. Consider any instance I. We ﬁrst argue a bit about the optimal social cost of I. A solution that minimizes the social cost locates each facility j {1, 2} to the node yj occupied by a median agent in Nj. However, this solution might not be feasible if y1 = y2, and so the optimal social cost can only be larger. We have that

i N1 d(xi, y1) + X

i N2 d(xi, y2). (1)

Now, let us focus on the social cost of the solution z computed by the mechanism. Let e be the empty node where facility 2 is located; without loss of generality, we can assume that xe > y2. Combined with the fact that facility 1 is located at y1, we have that z = (y1, xe), and

SC(z|I) = X

i N1 d(xi, y1) + X

i N2 d(xi, xe).

The ﬁrst term appears in the lower bound of the optimal social cost given by Inequality (1), so all we need to do is bound the second term of the above expression. We partition the set N2 into three sets L, M and R depending on the positions of the agents in N2 compared to y2 and xe, as follows: L = {i N2 : xi y2}, M = {i N2 : xi (y2, xe)}, R = {i N2 : xi > xe}. By the deﬁnition of median, we have that |L| |M|+|R|; in particular, this is an equality if n2 = |N2| is even, and a strict inequality if n2 is odd (as L also includes the median agent in this case). Due to this, we have the following: For every agent i M, we match i to a unique agent in j L such that d(xj, xe) = d(xj, xi) + d(xi, xe) = d(xj, y2) + d(xi, y2) + d(xi, xe).

For every agent i R, we match i to a unique agent j L such that d(xj, xe) + d(xi, xe) = d(xj, y2) + d(y2, xe) + d(xi, xe) = d(xj, y2) + d(xi, y2).

Hence, we have that X

i N2 d(xi, xe) = X

i L d(xi, xe) + X

i M d(xi, xe) + X

i R d(xi, xe)

i N2 d(xi, y2) + d(y2, xe)1 {n2 odd}

i M d(xi, xe).

Next, we will bound the second and third terms of the above expression. Since each agent occupies a different node, we can upper-bound the total distance of the agents in M as follows:

d(y2, xe)1 {n2 odd} + 2 X

i M d(xi, xe)

d(y2, xe)1 {n2 odd} + 2 d(y2, xe) 1 + d(y2, xe) 2

+ . . . + d(y2, xe) |M|

= |M|2 + (2d(y2, xe) 1)|M| + d(y2, xe)1 {n2 odd} .

Now observe that d(y2, xe) > |M| (since all agents in M are between y2 and e); thus, the last expression in the above derivation is an increasing function in terms of |M|. It is clearly also an increasing function in terms of d(y2, xe). Since |M| 1

2(n2 1 {n2 odd}) and d(y2, xe) n1 + 1 + |M| n1 + 1 + 1

2(n2 1 {n2 odd}), by doing calculations and using the fact that 1 {n2 odd} 1, we obtain

d(y2, xe)1 {n2 odd} + 2 X

i M d(xi, xe)

n2 2 + 4n1n2 + 2n2 + 1 .

By putting everything together, we have

i N1 d(xi, y1) + X

i N2 d(xi, y2)

n2 2 + 4n1n2 + 2n2 + 1

n2 2 + 4n1n2 + 2n2 + 1 .

By Lemma 1, we have SC (I) 1

4 n2 1 + n2 2 2 , and thus the approximation ratio is bounded by

SC (I) 1 + n2 2 + 4n1n2 + 2n2 + 1

n2 1 + n2 2 2 .

The bound of 17/4 follows by applying Lemma 2 with x = n1 and y = n2.

We conclude this section by showing that our analysis of the approximation ratio of FMNE is tight. Lemma 3. There exists an instance with n 5 and no empty nodes such that the SC-approximation ratio of FMNE is at least 3, and an instance with n 6 and at least one empty node such that the SC-approximation ratio of FMNE is at least 17/4.

4 A Tight Bound for Three Agents In this section, we restrict to instances with three agents (and possibly many empty nodes). We show a tight bound of 4/3 on the approximation ratio of strategyproof mechanisms. In particular, we ﬁrst present a rather simple instance without empty nodes showing that the approximation ratio of

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

Mechanism 2: PRIORITY-DICTATORSHIP

1 Input: Instance I with three agents ℓ, c, and r such that xℓ< xc < xr ;

2 Output: Feasible solution z ;

3 if c N1 \ N2 then

4 if r N2 then

5 z (xc, xr);

7 z (xc, xℓ);

8 else if c N2 \ N1 then

9 if r N1 then

10 z (xr, xc);

12 z (xℓ, xc);

14 if r N2 then

15 z (xc, xc + 1);

17 z (xc + 1, xc);

any strategyproof mechanism is at least 4/3, which improves upon the previous lower bound of 9/8 shown by Seraﬁno and Ventre [2016].

Theorem 4. The SC-approximation ratio of any strategyproof mechanism is at least 4/3.

Proof. We consider two instances with three agents and no empty nodes. In the ﬁrst instance I1, all agents approve both facilities. Clearly, any mechanism must locate a facility to the ﬁrst or the third node (or, perhaps, both). Without loss of generality, suppose the mechanism locates facility 2 at the third node. In the second instance I2, the ﬁrst two agents approve both facilities, while the third agent approves only facility 2 (that is, the only difference between I1 and I2 is the preference of the third agent). Since facility 2 is located at the third node in I1, the same must happen in I2; otherwise, agent 3 would have cost at least 1 in I2 and incentive to misreport that she approves both facilities, thus changing I2 to I1, and decreasing her cost to 0. However, both possible feasible solutions z1 = (1, 3) and z2 = (2, 3) have social cost 4 in I2, whereas an optimal solution (such as z = (1, 2)) has social cost 3; the theorem follows.

Next, we design the 3-agent strategyproof mechanism PRIORITY-DICTATORSHIP which achieves the approximation ratio of 4/3. Consider any instance with three agents, called ℓ, c, and r, and let xℓ< xc < xr. Without loss of generality, let xr xc xc xℓ. Our mechanism gives priority to the central agent over the right agent, and does not take into account the preference of the left agent. In particular, the mechanism locates at xc one of the facilities approved by c, and decides the location of the other facility based on the preference of r. See Mechanism 2.

Theorem 5. PRIORITY-DICTATORSHIP is strategyproof and its SC-approximation ratio is at most 4/3.

Mechanism 3: α-LEFT-RIGHT

1 Input: Instance I with n agents;

2 Output: Feasible solution z = (z1, z2);

3 L left part of line from node 1 to node α;

4 N(L) agents that occupy nodes in L;

5 R right part of line from node α + 1 to node m;

6 N(R) agents that occupy nodes in R;

// (case 1): Each part includes agents that approve only one, different facility

7 if X, Y {L, R}: N1 = N(X) and N2 = N(Y ) then

8 z1 median node of line deﬁned by N(X) (ties in favor of nodes farther from α);

9 z2 median node of line deﬁned by N(Y ) (ties in favor of nodes farther from α); // (case 2): One part includes agents that approve only one facility

10 else if ℓ {1, 2}, X {L, R}: Nℓ N(X) then

11 if Nℓis empty then

13 zℓ median node of line deﬁned by N(X) (ties in favor of nodes farther from α);

14 z3 ℓ β {α, α + 1} \ X; // (case 3): Both parts include agents from N1 and N2

16 z1 α (i.e., rightmost node of L);

17 z2 α + 1 (i.e., leftmost node of R);

5 Maximum Cost

We now turn our attention to the maximum cost. For this objective, Seraﬁno and Ventre [2016] showed an upper bound of 3 achieved by the Two Extemes mechanism, and a lower bound of 3/2 on the approximation ratio of any strategyproof mechanism. We improve both bounds, by showing a tight bound of 2.

5.1 Improving the Upper Bound

We consider a class of mechanisms that use only the part of the line that is occupied, from the ﬁrst to the last occupied node, with possible empty nodes in-between; with some abuse of notation, we denote by m the size of exactly this part of the line. These mechanisms, termed α-LEFT-RIGHT, are parameterized by an integer α {1, . . . , m 1}, and their general idea is as follows: They partition the line into two parts depending on the value of α, and then decide where to locate the facilities based on the preferences of the agents occupying nodes in these two parts. See Mechanism 3.

Theorem 6. For any α {1, . . . , m 1}, mechanism α-LR is strategyproof.

Next, we focus on the approximation ratio of α-LR mechanisms for the max cost. We distinguish between cases where m even or odd, and show that there are values of α such that α-LR achieves an approximation ratio of at most 2. Before we do this, we prove a lemma providing a lower bound on the optimal max cost of a given instance.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

Lemma 4. Let I be an instance. If there are two agents positioned at x and y > x, and q {0, 1, 2} is the number of facilities they both approve, then MC (I) q y x

We are now ready to bound the approximation ratio of particular α-LR mechanisms. For instances with even m, we use α = m/2.

Theorem 7. When m is even, the MC-approximation ratio of m/2-LR is at most 2.

Proof sketch. Consider any instance I. We distinguish between the three cases considered by the mechanism; in this proof sketch we present only Cases 1 and 2.

Case 1. Since the agents in N(X) approve only facility 1 and the agents in N(Y ) approve only facility 2, the mechanism outputs the optimal solution in this case.

Case 2. Suppose that N1 N(L) and that N2 contains agents in both N(L) and N(R); this is one of the symmetric instances captured by case 2. The mechanism locates facility 1 at the median node y L (with 1 y L m+2

4 ) of the line deﬁned by N(L), and facility 2 at node m

2 + 1 (the leftmost node of R). We distinguish between the following cases:

Case 2a: The cost of the mechanism is equal to the cost of an agent that approves a single facility. As all agents that approve facility 1 are in N(L), and facility 1 is located at the median of the line deﬁned by N(L), the cost of any agent that approves only facility 1 can be at most max{ m+2

4 . Since facility 2 is located at node m

2 + 1, the cost of any agent that approves only facility 2 can be at most m

2 + 1 1 = m

2 . Hence, MC(z|I) m

2 . As N2 contains at least one agent in N(L), there exists at least one agent at a node x m

2 that approves facility 2. By applying Lemma 4 with x and y = m, we have that MC (I) m x

4 , yielding that the approximation ratio is at most 2.

Case 2b: The cost of the mechanism is equal to the cost of an agent that approves both facilities. Since we are in case 2 with N1 NL, let x m/2 be the position of the agent i that approves both facilities and has the maximum cost among all such agents. The cost of agent i, and thus of the mechanism, is MC(z|I) = |x y L| + m

2 + 1 x. If x > y L, we have MC(z|I) = m

2 . Similarly to Case 2a, MC (I) m

4 , and thus the approximation ratio is at most 2. If x y L, we have MC(z|I) = m

2 + 1 + y L 2x 3(m+2)

4 2x. Since agent i and the agent at node m both approve facility 2, Lemma 4 implies MC (I) m x

2 . Hence, the approximation ratio is at most 3m+6 8x

2m 2x . This is a nonincreasing function in terms of x, and attains its maximum value of 3m 2

2m 2 for x = 1. For every m 2, it holds that 3m 2 2m 2 2.

The proof of the following theorem is only slightly more complicated than the one for even m.

Theorem 8. When m is odd, the MC-approximation ratio of (m + 1)/2-LR is at most 2.

5.2 A Tight Lower Bound for all Mechanisms We conclude with a tight lower bound of 2 on the MCapproximation ratio of any strategyproof mechanism.

Theorem 9. The MC-approximation ratio of any strategyproof mechanism is at least 2.

Proof. Suppose that there exists a strategyproof mechanism M with approximation ratio strictly smaller than 2. Consider an instance I1, where agents 1 and 3 approve facility 1, while agent 2 approves facility 2. M must return (2, 3) or (2, 1) as MC((2, 3)|I1) = MC((2, 1)|I1) = 1, and the max cost of any other solution is 2. Suppose that M returns (2, 3). Next, consider instance I2, where agent 1 approves facility 1, while the other two approve facility 2. M must output either (2, 3) or (1, 3) due to strategyproofness. Any solution where facility 2 is not placed at the third node leads to a cost of at least 1 for agent 3, who would misreport that she only approves facility 1 to lead to instance I1 and thus obtain a cost of 0 from the resulting solution (2, 3). If M returns (2, 3) for I2, consider instance I3, where agent 1 approves both facilities, while the other two approve facility 2. M must return the optimal solution (1, 2) with max cost 1, since any other solution has max cost at least 2. However, agent 1 in I2 would misreport that she approves both facilities to reduce her cost from 1 to 0; this contradicts that M is strategyproof. If M returns (1, 3) for I2, consider instance I4, where agent 1 approves facility 1, agent 2 approves both facilities, and agent 3 approves facility 2. The (2, 3) and (1, 2) are both optimal with max cost 1; any other solution has max cost 2. Out of these, (1, 2) would give agent 2 in I2 incentive to misreport that she approves both facilities to reduce her cost from 1 to 0. Hence, M must return (2, 3) for I4. Finally, consider instance I5, where agents 1 and 2 approve both facilities, while agent 3 approves facility 2. The optimal solution is (1, 2) with max cost 1; any other solution has max cost at least 2. But then, agent 1 in I4 will misreport that she approves both facilities to reduce her cost from 1 to 0; this again contradicts the fact that M is strategyproof.

6 Conclusion and Open Problems

In this paper, we showed improved bounds on the approximation ratio of deterministic strategyproof mechanisms in terms of the social and the maximum cost objectives for the discrete truthful heterogeneous two-facility location problem. There are many open questions and directions for future research. While we managed to improve the previous linear bound for the social cost to a small constant, we were unable to completely close the gap between the lower bound of 4/3 and the upper bound of 17/4. Besides deterministic mechanisms, it would be interesting close the gap between 4/3 and 3/2 for randomized mechanisms and the max cost objective. Going beyond the particular model studied here, one could study settings with more than two facilities, settings where the positions of the agents are their private information and can report empty nodes as their positions, settings with different heterogeneous preferences such as fractional or obnoxious ones, and settings with more general location graphs.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

[Anastasiadis and Deligkas, 2018] Eleftherios Anastasiadis and Argyrios Deligkas. Heterogeneous facility location games. In Proceedings of the 17th International Conference on Autonomous Agents and Multi Agent Systems (AAMAS), pages 623 631, 2018. [Chan et al., 2021] Hau Chan, Aris Filos-Ratsikas, Bo Li, Minming Li, and Chenhao Wang. Mechanism design for facility location problems: A survey. In Proceedings of the Thirtieth International Joint Conference on Artiﬁcial Intelligence (IJCAI), pages 4356 4365, 2021. [Chen et al., 2020] Zhihuai Chen, Ken C. K. Fong, Minming Li, Kai Wang, Hongning Yuan, and Yong Zhang. Facility location games with optional preference. Theoretical Computer Science, 847:185 197, 2020. [Cheng et al., 2011] Yukun Cheng, Wei Yu, and Guochuan Zhang. Mechanisms for obnoxious facility game on a path. In Proceedings of the Combinatorial 5th International Conference Optimization and Applications (COCOA), pages 262 271, 2011. [Cheng et al., 2013] Yukun Cheng, Wei Yu, and Guochuan Zhang. Strategy-proof approximation mechanisms for an obnoxious facility game on networks. Theoretical Computer Science, 497:154 163, 2013. [Deligkas et al., 2021] Argyrios Deligkas, Aris Filos Ratsikas, and Alexandros A. Voudouris. Heterogeneous facility location with limited resources. Co RR, abs/2105.02712, 2021. [Dokow et al., 2012] Elad Dokow, Michal Feldman, Reshef Meir, and Ilan Nehama. Mechanism design on discrete lines and cycles. In Proceedings of the 13th ACM Conference on Electronic Commerce (EC), pages 423 440, 2012. [Feigenbaum and Sethuraman, 2015] Itai Feigenbaum and Jay Sethuraman. Strategyproof mechanisms for onedimensional hybrid and obnoxious facility location models. In AAAI Workshop on Incentive and Trust in ECommunities, volume WS-15-08, 2015. [Feldman et al., 2016] Michal Feldman, Amos Fiat, and Iddan Golomb. On voting and facility location. In Proceedings of the 2016 ACM Conference on Economics and Computation (EC), pages 269 286, 2016. [Filimonov and Meir, 2021] Alina Filimonov and Reshef Meir. Strategyproof facility location mechanisms on discrete trees. In Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 510 518, 2021. [Filos-Ratsikas and Voudouris, 2021] Aris Filos-Ratsikas and Alexandros A. Voudouris. Approximate mechanism design for distributed facility location. In Proceedings of the 14th International Symposium on Algorithmic Game Theory (SAGT), pages 49 63, 2021. [Fong et al., 2018] Chi Kit Ken Fong, Minming Li, Pinyan Lu, Taiki Todo, and Makoto Yokoo. Facility location games with fractional preferences. In Proceedings of the

32nd AAAI Conference on Artiﬁcial Intelligence (AAAI), pages 1039 1046, 2018. [Kyropoulou et al., 2019] Maria Kyropoulou, Carmine Ventre, and Xiaomeng Zhang. Mechanism design for constrained heterogeneous facility location. In Proceedings of the 12th International Symposium on Algorithmic Game Theory (SAGT), pages 63 76, 2019. [Li et al., 2020] Minming Li, Pinyan Lu, Yuhao Yao, and Jialin Zhang. Strategyproof mechanism for two heterogeneous facilities with constant approximation ratio. In Proceedings of the 29th International Joint Conference on Artiﬁcial Intelligence (IJCAI), pages 238 245, 2020. [Procaccia and Tennenholtz, 2013] Ariel D. Procaccia and Moshe Tennenholtz. Approximate mechanism design without money. ACM Transactions on Economics and Computation, 1(4):18:1 18:26, 2013. [Seraﬁno and Ventre, 2016] Paolo Seraﬁno and Carmine Ventre. Heterogeneous facility location without money. Theoretical Computer Science, 636:27 46, 2016. [Xu et al., 2021] Xinping Xu, Bo Li, Minming Li, and Lingjie Duan. Two-facility location games with minimum distance requirement. Journal of Artiﬁcial Intelligence Research, 70:719 756, 2021. [Zou and Li, 2015] Shaokun Zou and Minming Li. Facility location games with dual preference. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 615 623, 2015.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)