1 Introduction
In the classic truthful singlefacility 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, whereas a single person might want the opposite. 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, where the line is a discrete graph, the agents occupy nodes of the line (which is common knowledge) and have approval preferences over two facilities, which can only be placed at different nodes of the line. Given facility locations, the cost of an agent is 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 and , where 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 and , and that of randomized mechanisms is between and . 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 upper bounds shown by Serafino and Ventre for the social and the maximum cost both follow by the same deterministic mechanism, named TwoExtremes, which works along the lines of the mechanism considered by Procaccia and Tennenholtz (2013) for homogeneous 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 FixedorMedianNearestEmpty (FMNE) mechanism with an approximation ratio of at most . 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; otherwise, if there are empty nodes, 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 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 agent PriorityDictatorship mechanism that achieves the bestpossible bound of .
For the maximum cost, we design a parameterized class of mechanisms LeftRight (LR), each member of which partitions the line into two parts, from the first node to node , and from node 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 . In particular, when the size of the line is an even number, the bound is achieved by LR, and when
is odd, it is achieved by
LR. Finally, we show a tight lower bound of on the approximation ratio of all strategyproof mechanisms, using a construction involving a sequence of five instances with three agents and no empty nodes.Lower bound  Upper bound  

Social cost  ()  () 
Maximum cost  ()  () 
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 in the literature on approximate mechanism design without money. 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, a few ones on characterizations of onto strategyproof mechanisms for the singlefacility location problem in discrete lines, cycles (Dokow et al., 2012) and trees (Filimonov and Meir, 2021), and some related to truthful singlewinner voting on a line metric (e.g., (Feldman et al., 2016; FilosRatsikas and Voudouris, 2021)), the related literature has mainly 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 singlefacility location problem and the obnoxious singlefacility location problem (Cheng et al., 2011, 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 the agents have dual preferences over the facilities; that is, an agent 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 (and can thus lie about them). 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 optional (or, approval) preferences over the facilities; that is, an agent either likes a facility or is indifferent about it. The authors consider two different cost functions of the agents, one that is equal to the distance from the closest facility that the agent approves, and one that is equal to the distance from the farthest such facility. Li et al. (2020) studied an extension of this setting in more general metrics (beyond the line), and designed mechanisms that improve some of results of Chen et al.. Deligkas et al. (2021) considered a similar preference model, but with the difference that the goal is to locate just one of the facilities (and, more generally, out of ), and not all of them.
Anastasiadis and Deligkas (2018) considered a model that combines dual and optional preferences, in the sense that the agents can like, dislike or be indifferent about a facility. Fong et al. (2018) studied a setting with fractional preferences, where each agent has a weight in for each facility indicating how much she likes it. Finally, Xu et al. (2021) focused on the problem where the locations of the locations of the two facilities must satisfy a minimum distance requirement.
2 Preliminaries
We consider the discrete twofacility location problem. An instance of this problem consists of a set of agents, two facilities, and a line graph with nodes. Each agent occupies a node of the line, such that different agents occupy different nodes. By we denote the position profile consisting of the positions of all agents (i.e., the nodes they occupy) as well as the positions of possible empty nodes; the position profile is assumed to be common knowledge. Every agent also has a private approval preference over the two facilities: If , agent approves facility ; otherwise, she disapproves it. By we denote the preference profile consisting of the preferences of all agents. It will be useful to denote by the set of agents that approve facility . Clearly, the two sets and need not be disjoint if there are agents that approve both facilities. As and implicitly include all the information related to an instance, we denote .
A feasible solution determines the node where each facility is located, so that . Given a feasible solution , the cost of any agent in instance is her total distance from the facilities she approves, i.e.,
where is the distance between agent and facility .
A mechanism takes as input an instance and outputs a feasible solution. A mechanism is said to be strategyproof if the solution it computes when given as input the instance is such that no agent has incentive to report a false preference to decrease her cost, i.e.,
where is the preference profile according to which agent ’s preference is , while the preference of any other agent is the same as in .
We consider two wellknown social objectives, which are functions of feasible solutions. Given an instance , the social cost of a feasible solution is the total cost of all the agents, i.e.,
The max cost of is the maximum cost among all agents, i.e.,
Let be the minimum possible social cost for instance , achieved by any feasible solution. Similarly, let be the minimum possible maximum cost for .
For any social objective , the approximation ratio of a mechanism is the worstcase ratio (over all possible instances) between the objective value of the solution computed by over the minimum possible objective value among all feasible solutions, i.e.,
Our goal is to design strategyproof mechanisms with an as low approximation ratio as possible (close to ).
3 A constantapproximation strategyproof mechanism for the social cost
We start with the social cost objective. For general instances with agents, we design the strategyproof mechanism FixedorMedianNearestEmpty (FMNE) with approximation ratio , thus greatly improving upon the previous bound of 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 and ); this is the Fixed part of the mechanism. If there are empty nodes, FMNE locates facility at the node occupied by the median agent among those that approve facility , and facility at the empty node that is nearest to the node occupied by the median agent among those that approve facility ; this is the MedianNearestEmpty part of the mechanism. See Mechanism 1.
Theorem 3.1.
FMNE is strategyproof.
Proof.
Consider an arbitrary instance . The mechanism is clearly strategyproof if there are no empty nodes in as the locations of the facilities are fixed and independent of the preferences of the agents. So, it remains to consider the case where contains empty nodes. Let be an arbitrary agent. We switch between the following three cases:
Agent approves only facility (). Suppose without loss of generality that . Any misreport of agent can only lead to a median among the agents that approve facility which is farther away from . In particular, if misreports that she approves only facility , then , whereas if misreports that she approves both facilities, then .
Agent approves only facility (). Suppose without loss of generality that facility is positioned at some empty node with . Denote by the median node occupied by the agents that approve facility when misreports.

If agent misreports that she approves both facilities, then , and hence the position of facility as well as the cost of agent remain the same.

If and agent misreports that she only approves facility , then . As a result, either continues to be the nearest empty node to and the cost of remains exactly the same, or another empty node with becomes the nearest empty node to , and the cost of strictly increases.

If and agent misreports that she only approves facility , then . As a result, either continues to be the nearest empty node to , or another empty node with becomes the nearest empty node to . In any case, the cost of does not decrease.
Agent approves both facilities (). Since the cost of agent is the sum of costs she derives from the two facilities and we decide where to locate each facility independently from the other facility, the same arguments for the previous two cases show that no possible misreport can lead to a strictly lower cost. ∎
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; we include the proof for completeness. Here, is equal to if the event is true, and otherwise.
Lemma 3.2 ((Serafino and Ventre, 2016)).
For any instance in which there are agents that approve facility , it holds that
Proof.
We argue about each facility independently. When is odd, the optimal allocation can, at best, have facility at one of these nodes and have two agents at distance , for from ; the total cost due to facility is then . When is even, the optimal allocation can, at best, place facility facility at one of the nodes and have two agents at distance , for , and an agent at distance ; the total cost due to facility in this case is then . ∎
For instances without empty nodes and , we will show that the approximation ratio of FMNE (in particular, its Fixed part) is at most ; note that for , the TwoExtremes mechanism of Serafino and Ventre (2016) is approximate.
Theorem 3.3.
For any instance with agents and no empty nodes, the SCapproximation ratio of FMNE is at most .
Proof.
Consider an instance and recall that denotes the set of agents that approve facility . Let , , and ; clearly, it holds that .
We first consider the case where is even, i.e., . For any agent , with , the maximum distance of to a facility is . Furthermore, each of the agents that approve both facilities faces an added cost of at most due to the distance to the agent’s nearest facility. Therefore, the total cost of the solution computed by the mechanism is bounded by
where the second equality holds since , while the last inequality holds since .
By Lemma 3.2, , and thus the approximation ratio is bounded by
To prove the claim, it suffices to show that, when , it holds that , i.e., . Observe that, when , it holds that ; the claim follows.
We now consider the case where is odd; the analysis is slightly more involved, but follows along similar lines. Observe that the maximum distance of any agent positioned at some of the first nodes from a facility (in particular, facility ) is , while the maximum distance of any agent positioned at some of the last nodes from a facility (in this case, facility ) is . Furthermore, each of the agents that approve both facilities faces an added cost of at most . So, the total cost of the solution computed by the mechanism is bounded by
where, again, the second equality holds since .
By Lemma 3.2, , and thus the approximation ratio is bounded by
To prove the claim it suffices to show that . If , then , and the claim follows since holds in this case. Otherwise, when , then exactly one of is odd and it suffices to show that . Since , this always holds if . ∎
For instances with at least one empty node, we will show that the approximation ratio of FMNE (in particular, its MedianNearestEmpty part) is for any ; observe that the TwoExtremes mechanism of Serafino and Ventre (2016) achieves an approximation ratio of at most when . Our proof for the approximation ratio of FMNE in this case relies on the following technical lemma.
Lemma 3.4.
Let . For nonnegative integers such that , it holds .
Proof.
First, observe that can be written as . It suffices to limit our attention to the values of for which , i.e., to these such that . By rearranging, we obtain , and, therefore, .
Let for some integer and rewrite the last inequality as . Clearly, for the inequality never holds as the lefthandside term is negative and the righthandside term is always nonnegative. Hence, we obtain that . For the remaining values of , i.e., when , recall that , i.e., . When , it must be and the inequality does not hold, as . When , we have and, again, the inequality does not hold, as . For , we obtain and the inequality becomes , which holds only when ; in this case, . Finally, for , we have that and the inequality becomes which holds for . The proof follows by observing that ∎
We are now ready to prove the bound for instances with empty nodes.
Theorem 3.5.
For any instance with and at least one empty node, the SCapproximation ratio of FMNE is at most .
Proof.
Consider any instance . We first argue a bit about the optimal social cost of . A solution that minimizes the social cost locates each facility to the node occupied by a median agent in . However, this solution might not be feasible if , and so the optimal social cost can only be larger. We have that
(1) 
Now, let us focus on the social cost of the solution computed by the mechanism. Let be the empty node where facility is located; without loss of generality, we can assume that . Combined with the fact that facility is located at , we have that , 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 into three sets , and depending on the positions of the agents in compared to and , as follows:

;

;

.
By the definition of median, we have that ; in particular, this is an equality if is even, and a strict inequality if is odd (as also includes the median agent in this case). Observe that

For every agent , there exists a unique agent in such that

For every agent , there exists a unique agent 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 upperbound the total distance of the agents in as follows:
Now observe that (since all agents in are between and ); thus, the last expression in the above derivation is an increasing function in terms of . It is clearly also an increasing function in terms of . Since and , by doing calculations and also using the fact that , we obtain
By putting everything together, we have
By Lemma 3.2, we have , and thus the approximation ratio is bounded by
The bound of follows by applying Lemma 3.4 with and . ∎
We conclude this section by showing that our analysis of the approximation ratio of FMNE is tight.
Lemma 3.6.
There exists an instance with and no empty nodes such that the SCapproximation ratio of FMNE is at least , and an instance with and at least one empty node such that the SCapproximation ratio of FMNE is at least .
Proof.
For the Fixed part of FMNE consider the following instance with agents and no empty nodes. The first two agents approve only facility , and the last three agents approve only facility . The mechanism outputs the solution , that is, it locates facility at the second node and facility at the third node. The social cost of this solution is . However, an optimal solution is with social cost , leading to an approximation ratio of .
For the MedianNearestEmpty part of FMNE consider the following instance with agents and one empty node. The first three nodes are occupied by agents that approve only facility , the next three nodes are occupied by agents that approve only facility , and the last node is empty. The mechanism outputs the solution , that is it locates facility at node and facility at the empty node. This solution has social cost . In contrast, an optimal solution is with , leading to an approximation ratio of . ∎
4 A tight bound for instances with three agents
In this section, we restrict to instances with three agents (and possibly many empty nodes). We show a tight bound of on the approximation ratio of strategyproof mechanisms. In particular, we present a rather simple instance without empty nodes showing that the approximation ratio of any strategyproof mechanism is at least ; this improves upon the previous lower bound of shown by Serafino and Ventre (2016). We complement this result by designing a mechanism that achieves the bound of when given as input any instance with three agents.
Theorem 4.1.
The SCapproximation ratio of any strategyproof mechanism is at least .
Proof.
We consider two instances with three agents and no empty nodes. In the first instance , 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 at the third node.
In the second instance , the first two agents approve both facilities, while the third agent approves only facility (that is, the only difference between and is the preference of the third agent). Since facility is located at the third node in , the same must happen in ; otherwise, agent would have cost at least in and incentive to misreport that she approves both facilities, thus changing to , and decreasing her cost to . However, both possible feasible solutions and have social cost in , whereas an optimal solution (such as ) has social cost ; the theorem follows. ∎
Next, we design the agent mechanism PriorityDictatorship, which is strategyproof and has an approximation ratio of at most . Consider any instance with three agents; for convenience, we call the agents , , and and let . Without loss of generality, we assume that is closer to than to , that is, . Our mechanism gives priority to the central agent over the right agent, and does not take into account the preference of the left agent at all. In particular, the mechanism locates at one of the facilities that agent approves, and decides the location of the other facility based on the preference of agent . See Mechanism 2 for a formal description. We first show that the mechanism is strategyproof.
Theorem 4.2.
PriorityDictatorship is strategyproof.
Proof.
Consider any instance with three agents , and such that . Since the preference of agent is not taken into account, cannot affect the outcome and thus has no incentive to misreport. In addition, the mechanism always locates at one of the facilities that approves, and if approves both facilities, the other facility is located at ; hence, the cost of is always minimized. Finally, to see why agent also has no incentive to misreport, it suffices to observe that in all cases (where the preference of agent is fixed) the location of the facility that approves is either independent of her preference, or is closer to her position than if she misreports. As an example, if , facility is located at independently from the report of , and facility is located at if approves it. Hence, agent minimizes her cost by being truthful. The same holds for the remaining two cases. ∎
Next, we show the upper bound of on the approximation ratio of the mechanism.
Theorem 4.3.
For instances with three agents, the SCapproximation ratio of PriorityDictatorship is at most .
Proof.
Consider any instance with three agents , and . We distinguish between the three cases considered by the mechanism.

If , is a median agent for facility .

If , the outcome is , and the approximation ratio is as is a median agent for facility .

If , the outcome is , and the approximation ratio is again as either is a median agent for facility , or all agents approve only facility .


If , due to symmetry to the above case, the approximation ratio is again .

If , is a median agent for both facilities. The approximation ratio is in the following cases: (a) is the unique median for both facilities, which happens when and approve the same set of facilities; (b) is a median for the facility located at (so that this facility is located inbetween median agents), which happens when and approve a single (different) facility, or when and . So, we can consider the remaining three cases. Let and .

, , . One possible optimal solution is with social cost . The solution computed by the mechanism has social cost . Hence, the approximation ratio is . As this is a nonincreasing function in terms of and , it attains its maximum value of for .

, , . One possible optimal solution is with social cost . The solution computed by the mechanism has social cost . Hence, the approximation ration is . This is again a nonincreasing function in terms of and , and thus attains its maximum value of for .

, , . One possible optimal solution is with social cost . The solution computed by the mechanism has social cost . Hence, the approximation ration is , which is maximized once again to for .

The proof is now complete. ∎
5 Maximum cost
We now turn our attention to the maximum cost. For this objective, Serafino and Ventre (2016) showed an upper bound of on the approximation ratio of the TwoExtemes mechanism, and a lower bound of on the approximation ratio of any strategyproof mechanism. We improve both bounds, by showing a tight bound of .
5.1 Improving the upper bound
To achieve the improved upper bound of , 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 inbetween; with some abuse of notation, we denote by the size of exactly this part of the line. These mechanisms, termed LeftRight, are parameterized by an integer , 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 for a formal description. We first show that every LeftRight is strategyproof.
Theorem 5.1.
For any , mechanism LR is strategyproof.
Proof.
Consider any instance. We distinguish between the three cases considered by the mechanism.
True preferences are as in case 1. The mechanism locates facility at the median node of the line defined by , and facility at the median node of the line defined by . It suffices to show that any agent has no incentive to deviate; the case is symmetric. If is the unique agent in , then she occupies the median node of the line defined by , where facility is located, and thus has zero cost. So, we can assume that there is some agent in . If agent misreports by approving either just facility or both facilities, then we transition to case 2 with , meaning that the location of facility remains the median of the line defined by . So, agent cannot decrease her cost, and has no incentive to deviate.
True preferences are as in case 2. Suppose that , while has agents in both and ; all other cases that fall under case 2 are symmetric. So, the mechanism locates facility at the median node of the line defined by , and facility at the leftmost node of . Consider any agent , and switch between all possible preferences of :

. Since all agents in approve only facility , we can never transition to case when misreports. Also, agent is indifferent between cases 1 and case 2 if she only approves facility , and prefers case 2 to case 1 if she approves both facilities (since her position is closer to the leftmost node of than to the median node of ). So, agent has no incentive to misreport.

. Similarly to the above case, we can never transition to case when misreports. Now, strictly prefers case 2 to case 1, as she wants facility to be located at the leftmost node of , so her cost is minimized, and has no incentive to misreport.

. Note that approves only facility . If she misreports that she approves both facilities, then we transition to case 3, where the location of facility remains the same. If she misreports that she approves only facility , then either the outcome remains the same if there is another agent in , or we transition to a symmetric case of case 2, where (while has agents in both and ), thus changing the location of facility from the leftmost node of to the median node of the line defined by . As this would increase the cost of agent , she has no incentive to misreport.
True preferences are as in case 3. Since each of and contains agents from both and , the mechanism locates facility at the rightmost node of , and facility at the leftmost node of . Consider any agent , where and . Observe that if for each facility there exists some agent in that approves , then agent cannot affect the outcome; no matter what reports, we are still in case 3. So, we can assume that for some , all agents in approve only facility . Since we are in case 3, we can also assume that (of course, agent might also approve ). To change the case considered by the mechanism, must completely agree with the other agents in and report that she approves only facility . This leads to a symmetric case of case 2, where (and contains agents in both and ), and hence facility is located at the median node of the line defined by and facility is still located at either or . Clearly, the cost of agent can only increase as facility has moved farther away. ∎
Next, we focus on the approximation ratio of LR mechanisms for the max cost. We distinguish between cases where the size of the line is an even or odd number, and show that there are values of such that LR achieves an approximation ratio of at most . Before we do this, we prove a lemma providing lower bounds on the optimal max cost of a given instance, which we will use extensively.
Lemma 5.2.
Let be an instance. The following are true:

If there are two agents positioned at and , and is the number of facilities they both approve, then

If there is an agent positioned at that approves both facilities, an agent positioned at that approves facility , and an agent positioned at that approves facility , then
Proof.
To show the two properties, we use the fact that the optimal cost for an instance is at least the optimal cost when we restrict to any subset of agents and any subset of facilities, in which case we aim to balance the cost of all the agents involved. We have:
(a) We begin with the case as the claim holds trivially when . Clearly, if we place the facility before or after , the claim holds. So, let us assume that we place the facility at node such that . The cost of the agent at node is then (at least) , while the cost of the agent at node is (at least) . The claim follows since it cannot be that both and are strictly less than .
When , the claim follows if at least one facility is placed before or after . Let us assume that we place the facilities at nodes and such that . The cost of the agent at node is then , while the cost of the agent at node is . The claim follows since it cannot be that both and
Comments
There are no comments yet.