On Discrete Truthful Heterogeneous Two-Facility Location

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. Serafino 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 defined as the total distance from the facilities she approves.

Serafino 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 Serafino and Ventre for both the social and the maximum cost.

1.1 Our Contribution

The main technical difficulty 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.

To overcome this bottleneck, Serafino 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 deficiency 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 fixes 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 first 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 five instances with three agents and no empty nodes. An overview of our bounds, and how they compare to the previously best ones shown by Serafino and Ventre [2016], is given in Table 1.

1.2 RelatedWork

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 Serafino and Ventre [2016], our paper here, and a few ones on homogeneous 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 first 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 profile which includes information about which nodes are occupied by which agents and which nodes are left empty (if any); the position profile 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 profile 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.,

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.,

where (t′i , t-i) is the preference profile 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.,

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

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.,

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 4 z1 ← ⌊n/2⌋; 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 ; 9 z1 ← y1; 10 z2 ← nearest empty node to y2, breaking ties in favor of the rightmost such empty node;

3 AConstant-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 Serafino and Ventre [2016]. Our mechanism exploits the known information about the position profile, 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 ([Serafino and Ventre, 2016]). For any instance I in which there are nj agents that approve facility j ∈ {1, 2}, it holds that

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 Serafino 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.

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 [Serafino and Ventre, 2016]. Our proof for the approximation ratio in this case relies on the following technical lemma.

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 first 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

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

The first 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 definition 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

• For every agent i ∈ R, we match i to a unique agent j ∈ L such that

Hence, we have that

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:

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

By putting everything together, we have

By Lemma 1, we have SC∗ (I) ≥ 14 (n21 + n22 - 2), and thus the approximation ratio is bounded by

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 first present a rather simple instance without empty nodes showing that the approximation ratio of

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); 6 else 7 z ← (xc, xℓ); 8 else if c ∈ N2 \N1 then 9 if r ∈ N1 then 10 z ← (xr , xc); 11 else 12 z ← (xℓ, xc); 13 else 14 if r ∈ N2 then 15 z ← (xc, xc + 1); 16 else 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 Serafino 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 first instance I1, all agents approve both facilities. Clearly, any mechanism must locate a facility to the first 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 first 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 defined by N(X) (ties in favor of nodes farther from α); 9 z2 ← median node of line defined 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 12 X ← L; 13 zℓ ←median node of line defined by N(X) (ties in favor of nodes farther from α); 14 z3-ℓ ← β ∈ {α, α + 1} \ X; // (case 3): Both parts include agents fromN1 and N2 15 else 16 z1 ← α (i.e., rightmost node of L); 17 z2 ← α + 1 (i.e., leftmost node of R);

5 MaximumCost

We now turn our attention to the maximum cost. For this objective, Serafino and Ventre [2016] showed an upper bound of 3 achieved by the TwoExtemes 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 first 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.

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 2 .

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 yL (with 1 ≤ yL ≤ ⌊ m+2 4 ⌋) of the line defined by N(L), and facility 2 at node m2 + 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 defined by N(L), the cost of any agent that approves only facility 1 can be at most max{⌊ m+2 4 ⌋-1, m2 - ⌊ m+2 4 ⌋} ≤ m4 . Since facility 2 is located at node m2 + 1, the cost of any agent that approves only facility 2 can be at most m2 + 1 - 1 = m2 . Hence, MC(z|I) ≤ m2 . As N2 contains at least one agent in N(L), there exists at least one agent at a node x ≤ m2 that approves facility 2. By applying Lemma 4 with x and y = m, we have that MC∗ (I) ≥ m-x 2 ≥ m4 , 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 - yL| + m2 + 1 - x.

If x > yL, we have MC(z|I) = m2 +1-yL ≤ m2 . Similarly to Case 2a, MC∗ (I) ≥ m4 , and thus the approximation ratio is at most 2.

If x ≤ yL, we have MC(z|I) = m2 + 1 + yL - 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.