# heterogeneous_facility_location_with_limited_resources__586d3c04.pdf

Heterogeneous Facility Location with Limited Resources

Argyrios Deligkas,1 Aris Filos-Ratsikas,2 Alexandros A. Voudouris3

1Department of Computer Science, Royal Holloway University of London 2Department of Computer Science, University of Liverpool 3School of Computer Science and Electronic Engineering, University of Essex argyrios.deligkas@rhul.ac.uk, aris.ﬁlos-ratsikas@liverpool.ac.uk, alexandros.voudouris@essex.ac.uk

We initiate the study of the heterogeneous facility location problem with limited resources. We mainly focus on the fundamental case where a set of agents are positioned in the line segment [0, 1] and have approval preferences over two available facilities. A mechanism takes as input the positions and the preferences of the agents, and chooses to locate a single facility based on this information. We study mechanisms that aim to maximize the social welfare (the total utility the agents derive from facilities they approve), under the constraint of incentivizing the agents to truthfully report their positions and preferences. We consider three different settings depending on the level of agent-related information that is public or private. For each setting, we design deterministic and randomized strategyproof mechanisms that achieve a good approximation of the optimal social welfare, and complement these with nearly-tight impossibility results.

1 Introduction

The truthful facility location problem is one of the most prominent paradigms in environments with strategic participants, and it was in fact the prototypical problem used by (Procaccia and Tennenholtz 2013) to put forward their very successful research agenda of approximate mechanism design without money about a decade ago. Since then, the problem has been extensively studied in the literature of theoretical computer science and artiﬁcial intelligence, with a plethora of interesting variants emerging over the years. Among those, one particularly meaningful variant, which captures several important scenarios, is that of heterogeneous facility location, introduced by (Feigenbaum and Sethuraman 2015) and studied notably by Seraﬁno and Ventre (2015, 2016), Anastasiadis and Deligkas (2018), Fong et al. (2018), Chen et al. (2020) and Li et al. (2020). In this setting, there are multiple facilities, and each of them plays a different role for example, a library and a basketball court. Consequently, the preferences of the agents for the possible outcomes do not only depend on the location of the facility (as in the original model of Procaccia and Tennenholtz (2013)), but also on the type of the facility. As a result, the

Copyright 2022, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

mechanism design problem becomes far more challenging.1 While the literature on heterogeneous facility location is quite rich by this point, there is a fundamental setting that has surprisingly eluded previous investigations. In particular, all previous works have considered the case of multiple (predominantly two) facilities which all have to be located, based on the positions and the preferences of the agents. However, in many real-world applications, resources are limited, and therefore a decision has to be made about which subset of the facilities should be build and where. For instance, the governing body might have sufﬁcient funds to build only one of two options, either a library or a basketball court. The decision must be made based on the preferences of the agents over the two facilities, but also on their positions, in a way that incentivizes the agents to reveal all their private information truthfully; this is clearly a challenging mechanism design problem.

1.1 Our Setting We initiate the study of the heterogeneous facility location problem with limited resources. We focus on the most fundamental case where there are two facilities, and only one of them must be located somewhere in the line segment [0, 1]. In particular, there is a set of agents, each of whom is associated with a position in [0, 1] and an approval preference over the facilities. An agent may approve one of the two facilities or both, and obtains positive utility2 only if a facility that she approves is built; otherwise, she has zero utility irrespectively of her position. Our goal is to design strategyproof mechanisms that choose and locate a single facility, so as to maximize the social welfare (the total utility of the agents) and incentivize the agents to truthfully report their private information. We study the following three settings depending on the level of

1In particular, the preference domain is no longer singlepeaked, and therefore maximizing the happiness of the agents cannot be achieved by simple median mechanisms. 2We remark that in several facility location settings (e.g., see (Procaccia and Tennenholtz 2013; Lu, Wang, and Zhou 2009; Lu et al. 2010)), the agents are associated with costs instead of utilities. In the literature of heterogeneous facility problems however, the setting is commonly deﬁned in terms of utilities, as there is no meaningful way of assigning a cost to undesirable outcomes, such as a facility which the agent does not approve.

The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22)

Deterministic Randomized General 2 (1, 2] Known-preferences 2 [4/3 , 4/3] Known-positions [13/11, 2] (1, 3/2]

Table 1: Overview of our results for deterministic and randomized strategyproof mechanisms. The lower bound 4/3 (marked with ) in the known-preferences setting holds only for the class of Random-Median mechanisms deﬁned in Section 4. For the general and known-preference settings, the bound of 2 also holds for the more general case where we can choose k out of m 2 facilities, for appropriate values of k and m.

information about the positions and the preferences of the agents that is assumed to be public or private.

General setting: Both the positions and the preferences are private information of the agents. Known-preferences setting: The positions are private information of the agents, whereas the preferences are public information. Known-positions setting: The preferences are private information of the agents, whereas the positions are public information.

We measure the performance of a strategyproof mechanism by its approximation ratio, deﬁned as the worst-case ratio over all instances of the problem between the maximum possible social welfare and the social welfare achieved by the mechanism. For each of the aforementioned settings, we derive upper and lower bounds on the achievable approximation ratio of strategyproof mechanisms. An overview of our results can be found in Table 1.

1.2 Discussion of our Results

We start our investigation by studying deterministic mechanisms in the general setting, where we show that a simple group-strategyproof mechanism, which we call Middle mechanism, achieves an approximation ratio of 2 (Theorem 1); the same guarantee extends to the other two settings we consider. We complement this result by showing a lower bound of 2 on the approximation ratio of any deterministic strategyproof mechanism, even when the preferences of the agents are assumed to be known (Theorem 2). Combining these two results, we completely resolve the problem of identifying the best possible deterministic strategyproof mechanism for both the general and the known-preferences settings. For the known-positions setting, we show that there is no deterministic strategyproof mechanism with approximation ratio better than 13/11 (Theorem 6). We also consider randomized mechanisms, and provide improved approximation guarantees for both the knownpreferences and the known-positions settings. More specifically, for the known-preferences setting we derive a novel universally group-strategyproof mechanism, termed Mirror mechanism, which achieves an approximation ratio of 4/3 (Theorem 4). This mechanism is in fact a member of a larger

class of universally group-strategyproof mechanisms, and as we prove, it is the best possible mechanism in this class (Theorem 5). For the known-positions setting, we prove that the well-known Random Dictatorship mechanism, equipped with a carefully chosen tie-breaking rule for the agents that approve both facilities, is a universally group-strategyproof mechanism and achieves an approximation ratio of 3/2 (Theorem 7). Finally, we make initial progress in more general settings with m 2 facilities, from which we can choose to locate k < m. We consider three variations based on whether the utility of each agent is determined by all the facilities she approves, or by the one that is the closest to or the farthest away from her position. For such utility classes, we show that an adaptation of the Middle mechanism still has an approximation ratio of 2 in the general setting, it is group-strategyproof for k = 1, but it is only strategyproof for k 2 (Theorem 8 and Lemma 9). We complement this result by showing that when k 2m it is impossible to do better, even when the preferences of the agents are known (Theorem 10).

1.3 Related Work As we mentioned earlier, the literature on truthful facility location is long and extensive; here, we discuss only those works that are most closely related to our setting. Besides the very recent paper of Elkind, Li, and Zhou (2022) who consider a setting similar to ours (where the goal is to choose a subset of facilities given approval preferences), virtually all other papers on heterogeneous facility location is that they consider settings with two facilities, where both facilities have to be built, and the utility/cost of an agent is calculated with respect to the closest or the farthest among the two. Chen et al. (2020) consider a setting in which agents have approval preferences over the facilities, similarly to what we do here, and for which the positions of the agents are known. Li et al. (2020) consider a more general metric setting along the lines of Chen et al. (2020), and design a deterministic mechanism which improves upon the result of Chen et al. (2020) when the metric is a line. Fong et al. (2018) consider a setting in which the agents have fractional preferences in (0, 1); similarly to us, besides studying the general setting, they also consider restricted settings with known preferences or known positions. Seraﬁno and Ventre (2015, 2016) consider a discrete setting, where the agents are positioned on the nodes of a graph, and the facilities must be located on different nodes. Feigenbaum and Sethuraman (2015) were the ﬁrst to study heterogeneous facility location, by presenting a hybrid model combining the standard facility location problem with the obnoxious facility location problem (Cheng, Yu, and Zhang 2011, 2013). This setting was extended by Anastasiadis and Deligkas (2018), who allowed agents to be indifferent between whether a facility would be built or not. Duan et al. (2019) study a setting where the goal is to locate two facilities under the constraint that the distance between the locations of the facilities is at least larger than a predeﬁned bound. Li, Wang, and Zhang (2020) study a conceptually similar but fundamentally different facility location problem under budget constraints. In their setting, the facilities are

strategic and need to be compensated monetarily in order for them to be built; the goal is to maximize an aggregate objective given that the total payment is below a predeﬁned budget. Besides these works, there is long literature of (homogeneous) facility location, studying different objectives (Alon et al. 2010; Cai, Filos-Ratsikas, and Tang 2016; Feigenbaum, Sethuraman, and Ye 2013; Feldman and Wilf 2013), multiple facilities (Escofﬁer et al. 2011; Fotakis and Tzamos 2013; Lu, Wang, and Zhou 2009; Lu et al. 2010), different domains (Schummer and Vohra 2002; Tang, Yu, and Zhao 2020; Sui, Boutilier, and Sandholm 2013; Sui and Boutilier 2015), different cost functions (Filos-Ratsikas et al. 2015; Fotakis and Tzamos 2016), and several interesting variants (Golomb and Tzamos 2017; Kyropoulou, Ventre, and Zhang 2019; Zhang and Li 2014; Filos-Ratsikas and Voudouris 2021). The very recent survey of Chan et al. (2021) provides an excellent overview of the literature on mechanism design for facility location problems and the survey of Anshelevich et al. (2021) provides an overview of the literature on distortion, which has been applied for analyzing facility location settings.

2 Preliminaries We consider a facility location setting with a set N of n agents and two facilities; we will discuss extensions to settings with more than two facilities in Section 6. Every agent i N has a position xi [0, 1]; let x = (xi)i N be the position proﬁle consisting of the positions of all agents. Furthermore, every agent i N also has an approval preference (or, simply, preference) ti = {0, 1}2 over the two facilities, where tij = 1 denotes that the agent approves facility j {1, 2} and tij = 0 denotes that she does not approve facility j; let t = (ti)i N be the preference proﬁle consisting of the preferences of all agents. Let I = (x, t) denote an instance of this setting. Given an instance I = (x, t), our goal is to choose and locate a single facility so as to optimize some objective function that depends on both the distances of the agents from the facility location and on whether they approve the chosen facility. In particular, if facility j {1, 2} is chosen to be located at y [0, 1], the utility of every agent i N is deﬁned to be ui(j, y|I) = tij 1 d(xi, y) , where d(xi, y) = |xi y| is the distance between xi and y. Then, the social welfare is the sum of the utilities of all agents:

W(j, y|I) := X

i N ui(j, y|I).

We denote the optimal social welfare for instance I as W (I) := max(j,y) W(j, y|I). A mechanism M takes as input an instance I = (x, t) consisting of the position and preference proﬁles of the agents, and outputs an outcome M(I) = (j M, y M) consisting of a facility j M {1, 2} that is to be placed at y M [0, 1]. The approximation ratio ρ(M) of M is deﬁned as the worst-case ratio (over all possible instances) between the optimal social welfare and the social welfare of the outcome chosen by the mechanism, that is,

ρ(M) = sup I

W (I) W(M(I)|I).

A mechanism is strategyproof if it is in the best interest of every agent to report their true position and preferences, irrespectively of the reports of the other agents. Formally, a mechanism M is strategyproof if, for every pair of instances I = (x, t) and I = ((x i, x i), (t i, t i)) in which only a single agent i misreports a different position and preferences, it holds that

ui(M(I)|I) ui(M(I )|I).

Besides mechanisms that deterministically select a facility and its location, we will also study randomized mechanisms, which choose the outcome according to probability distributions. In particular, a randomized mechanism locates each facility j {1, 2} at y [0, 1] with some probability pj(y) such that P j {1,2} R 1 0 pj(y)dy = 1. Denoting by p = (p1, p2) the probability distribution (for both facilities) used by the mechanism, the expected utility of every agent i N is computed as

ui(p|I) = X

j {1,2} tij Z 1

0 (1 |xi y|) pj(y)dy.

A randomized mechanism is strategyproof in expectation if no agent can increase her expected utility by misreporting. Also, we say that a randomized mechanism is universally strategyproof if it is a probability distribution over deterministic strategyproof mechanisms. Clearly, a universally strategyproof mechanism is strategyproof in expectation, but the converse is not necessarily true. We will also discuss about mechanisms that are resilient to misreports by coalitions of agents. In particular, a mechanism is group-strategyproof if no coalition of agents can simultaneously misreport such that the utility of every agent in the coalition strictly increases. We are interested in mechanisms that satisfy strategyproofness properties (like the ones discussed above) and at the same time achieve an as low as possible approximation ratio (that is, an approximation ratio as close as possible to 1). In our technical analysis in the upcoming sections, we will distinguish between the following settings:

In the general setting, the agents can misreport both their positions and preferences. In the known-preferences setting, the preferences of the agents are assumed to be known and the agents can misreport only their positions. In the known-positions setting, the positions of the agents are assumed to be known and the agents can misreport only their preferences.

Observe that positive results (i.e., (group-)strategyproof mechanisms with proven approximation guarantees) for the general setting are also positive results for the knownpreferences and known-positions settings. Moreover, negative results (i.e., lower bounds on the approximation of (group-)strategyproof mechanisms) for the restricted settings are also negative results for the general setting. Finally, results (positive or negative) for one of the two restricted settings do not imply anything for the other restricted setting.

3 General Setting We start the presentation of our technical results by focusing on the general setting; recall that in this setting the agents can misreport both their positions and their preferences. Due to the structure of the problem, which combines voting (based on the preferences of the agents) and facility location (based on the positions of the agents), it is natural to wonder whether simple adaptations of the median mechanism (which is known to be strategyproof and optimal for the original single-facility location problem) lead to good solutions. For example, we could deﬁne mechanisms that locate the majority-winner facility (breaking ties in a consistent way) at the median among the agents that approve it, or at the overall median agent. Unfortunately, it is not hard to observe that the ﬁrst mechanism is not strategyproof, while the second one has an approximation ratio that is linear in the number of agents. Luckily, there is an even simpler deterministic mechanism that is group-strategyproof and achieves an approximation of at most 2 in the general setting. In the next section, we will further show that this mechanism is best possible among all deterministic strategyproof mechanisms in terms of approximation, even when the preferences of the agents are known.

Middle mechanism (MM)

1. Count the number nj of agents that approve each facility j {1, 2}. 2. Locate the most preferred facility at location 1

2, breaking ties arbitrarily.

Theorem 1. The Middle mechanism is group-strategyproof and has an approximation ratio of at most 2.

Proof. Consider any instance I = (x, t). To show that the mechanism is group-strategyproof, ﬁrst observe that the positions of the agents are not taken into account when deciding which facility to locate and where. Hence, no agent has a reason to misreport her position. It remains to argue that there exists no group of agents who can all strictly increase their utility by misreporting their preferences. To this end, assume that facility j {1, 2} is chosen to be placed at 1/2. Observe that the utility of any agent that approves j is maximized subject to the constraint that the chosen facility is always placed at 1/2. Hence, such agents would not have incentive to participate in a misreporting coalition. Moreover, the count nj of facility j would only increase if any group of agents that truly disapprove facility j, misreported that they approve it. Hence, the outcome would not change in such a case, this proving that is indeed group-strategyproof. We now focus on the approximation ratio of the mechanism. Let j be the facility chosen by the mechanism, and let o be the optimal facility. We make the following simple observations:

Since the facility is placed at 1/2, every agent i that approves j has utility at least 1/2. By the deﬁnition of the mechanism, we have nj no.

Figure 1: The two instances used in the proof of Theorem 2, which differ only on the position of an agent with preferences (1, 0) marked in red.

Since the maximum utility of any agent is 1, we have that W (I) no.

Putting all of these together, we have:

W(MM(I)|I) 1

and the bound on the approximation ratio follows.

4 Known-Preferences Setting

Here, we focus on the known-preferences setting, where we assume that the agents can only strategize over their positions. Our ﬁrst result is a lower bound of 2 on the approximation ratio of any strategyproof deterministic mechanism, thus proving that the Middle mechanism presented in the previous section is best possible for the general and the known-preferences settings.

Theorem 2. In the known-preferences setting, there is no deterministic strategyproof mechanism with approximation ratio better than 2 δ, for any δ > 0.

Proof. Consider an arbitrary deterministic strategyproof mechanism and the following instance I depicted in Figure 1. There are four agents, two with preferences (0, 1) and two with preferences (1, 0). One agent of each type is positioned at some ε (0, 1/2) and the other is positioned at 1. Without loss of generality, we can assume that the mechanism chooses to locate facility 2; the welfare of the agents in this instance is maximized no matter where the facility is actually located. Now consider a second instance I that is obtained from I when only the agent i with preference (1, 0) that is positioned at ε is moved to 1. Since the mechanism is strategyproof, it must choose to locate facility 2 in instance I as well; otherwise, agent i would prefer to misreport her position in instance I as 1, thus leading to instance I and the selection of facility 1, which would increase her utility from 0 to positive. However, the welfare from locating facility 2 in instance I is at most 1+ε (no matter where it is located), whereas the optimal welfare is equal to 2, achieved when facility 1 is located at 1. The bound on the approximation ratio follows by selecting ε to be arbitrarily small.

Next, we turn our attention to randomization and consider the class of Random-Median mechanisms. Every mechanism in this class operates by ﬁrst randomly choosing one of the facilities based on the preferences the agents, which is then located at the median among the agents that approve it.

So, different choices of the probability distribution according to which the facility is chosen lead to different Random Median mechanisms. It is not hard to observe that all such mechanisms are universally group-strategyproof. Lemma 3. Every Random-Median mechanism M is universally group-strategyproof. Probably the simplest Random-Median mechanism one can think of is the Proportional mechanism deﬁned below, which selects every facility with probability proportional to the number of agents that approve it. By exploiting the deﬁnition of this probability, we can show that the Proportional mechanism has an approximation of (1 +

3)/2 1.366, thus signiﬁcantly improving upon the bound of 2 achieved by deterministic mechanisms. In fact, we can further improve upon the bound of the Proportional mechanism to 4/3, by deﬁning the slightly more involved Mirror mechanism deﬁned below, which uses a probability distribution that is a piecewise function of the numbers of agents that approve the two facilities.

Mirror mechanism

1. Count the number nj of agents that approve each facility j {1, 2}; wlog assume n1 n2 (otherwise switch n1 with n2 below). 2. Let α := 3n1 2n2

4n1 2n2 . 3. Choose facility 1 with probability α, and facility 2 with probability 1 α. 4. Locate the chosen facility at the median among the agents that approve it.

Theorem 4. In the known-preferences setting, the Mirror mechanism is universally group-strategyproof and has an approximation ratio of 4/3.

Proof. Since the mechanism is Random-Median, it is universally group-strategyproof due to Lemma 3. To bound the approximation ratio, let Wj be the welfare of the agents that approve facility j when it is chosen (and located at the median of those agents). Observe that for any facility j {1, 2} it holds that Wj nj since the maximum possible utility of any agent is 1, and Wj nj/2. To see why the latter is true, consider the agents that approve facility 2 in pairs, where one is on the left of the median (among those that approve facility 2) and the other is on the right of the median, and observe that the total utility of this pair of agents is at least 1. Since there are n2/2 such pairs, the claim follows. We distinguish between the following two cases:

W1 W2. Then, the approximation ratio is:

ρ(Mirror) = W1 α W1 + (1 α) W2

= 1 3n1 2n2 4n1 2n2 + n1 4n1 2n2 W2

3n1 2n2 4n1 2n2 + n1 4n1 2n2 n2/2

Figure 2: Instances used in the proof of Theorem 6. If any mechanism chooses to locate facility 1 in instance I, then its location must be y < 1/2, as otherwise the agents with preferences (1, 1) marked in red would have incentive to change her preferences as in instance I , where the mechanism must necessarily locate facility 2 at some y < 1/2 to have an approximation smaller than 13/11. However, such a choice of location in I leads to approximation at least 13/11.

W2 > W1. We have:

ρ(Mirror) = W2 α W1 + (1 α) W2

= 1 3n1 2n2 4n1 2n2 W1

W2 + n1 4n1 2n2

3n1 2n2 4n1 2n2 n1/2

n2 + n1 4n1 2n2

= 2n2(4n1 2n2)

It is not hard to observe that this last expression is maximized to 4/3 when n1 = n2.

Hence, in any case the approximation ratio of the mechanism is at most 4/3.

We conclude this section by showing that the Mirror mechanism is best possible among all Random-Median mechanisms in terms of approximation.

Theorem 5. In the known-preferences setting, the approximation ratio of any Random-Median mechanism is at least 4/3 δ, for any δ > 0.

5 Known-Positions Setting We now turn our attention to the known-positions setting, in which the positions of the agents are ﬁxed, and thus the agents can misreport only their preferences. Our ﬁrst result is a lower bound of 13/11 on the approximation ratio of any deterministic strategyproof mechanism.

Theorem 6. In the known-positions setting, there is no deterministic strategyproof mechanism with approximation ratio smaller than 13/11.

Proof. Suppose towards a contradiction that there exists a deterministic strategyproof mechanism that has an approximation ratio strictly smaller than 13/11, and consider the following instance I depicted in Figure 2. There is an agent with preferences (0, 1) positioned at 0, an agent with preferences (1, 1) positioned at 1/6, an agent with preferences (1, 1) positioned at 5/6, and an agent with preferences (1, 0) positioned at 1. Due to the symmetry of the instance, without loss of generality, we can assume that the mechanism chooses to place facility 1 at some location y [0, 1].

If y 1/2, the social welfare achieved by the mechanism is 1 y 1

6 y + 1 (1 y)

Since the optimal social welfare is 13/6 (achieved by placing either facility 1 at 5/6 or facility 2 at 1/6), the approximation ratio of the mechanism is then 13/11, contradicting the assumption that it is strictly smaller than 13/11. Consequently, it must be y > 1/2. Now consider the instance I that is obtained from I by changing the preference of the agent at 1/6 to (0, 1). In I , the maximum possible social welfare one can hope to achieve by placing facility 1 is 11/6 (when it is located anywhere in the interval [5, 6, 1] is 11/6) and by placing facility 2 is 13/6 (when it is located at 1/6). Hence, to have an approximation ratio strictly smaller than 13/11, the mechanism must choose to locate facility 2 in I at some position z [0, 1]. Similarly to instance I, we can show that it must be z < 1/2 as otherwise the approximation ratio of the mechanism would be at least 13/11. Hence, the agent positioned at 1/6 with preferences (1, 1) in instance I has incentive to misreport her preferences as (0, 1) so that the facility is located closer to her, and thus increase her utility. However, this contradicts the assumption that the mechanism is strategyproof, and the theorem thus follows.

Designing a deterministic mechanism with approximation ratio strictly smaller than the bound of 2 achieved by the Middle mechanism is quite challenging, and we leave it as an open question. Instead, we continue by considering randomized mechanisms. Observe that the instances from Figure 2 show that there is no randomized strategyproof mechanism with approximation ratio 1 for the known-positions setting. This is because no matter how the mechanism locates the facilities on instance I, it has to locate facility 2 on Instance I , thus the agent positioned at 1/6 has incentives to misreport her preferences. For the upper bounds, we propose the following variant of the well-known Random Dictatorship (RD) mechanism, equipped with a carefully chosen tie-breaking rule for the agents who approve both facilities; in particular, the mechanism chooses an agent at random and locates her favorite facility at her position, breaking ties in favor of the optimal facility in case she likes both facilities.

Random Dictatorship (RD) mechanism

1. Choose an agent i uniformly at random. 2. If agent i approves a single facility j, then locate j at xi. 3. If agent i approves both facilities, then locate the optimal one at xi.

To bound the approximation ratio of RD, we exploit a series of structural properties of the worst-case instances, in

which the approximation ratio of the mechanism is maximized. In particular, we will show that there exists a worstcase instance satisfying the following three properties: There are no agents that approve both facilities. Every agent that approves the non-optimal facility is positioned at 0 or 1. Every agent that approves the optimal facility is positioned at 0, or some median position x [0, 1], or 1. To show these properties, we start with an arbitrary instance and gradually change the preferences and the positions of the agents in a speciﬁc order so that the aforementioned properties are satisﬁed. Every change we make leads to a transformed instance in which the approximation ratio of RD does not decrease. It then sufﬁces to deﬁne a worst-case instance satisfying these properties and bound the approximation ratio of the mechanism for this instance. This will be a function of a handful of variables representing the number of agents that are positioned at {0, x, 1} and approve one of the two facilities. We have the following statement. Theorem 7. In the known-positions setting, RD is universally group-strategyproof and has approximation ratio 3/2.

6 Extensions to Choosing k out of m Facilities So far we have exclusively focused on the fundamental case where there are two facilities and one of them must be located. In this section, we deﬁne and make initial progress for natural generalizations when there are m 2 different facilities from which we can choose to locate k < m. There is a plethora of ways to deﬁne the utility of an agent. For instance, we can deﬁne it as the utility the agent derives from a subset of the facilities that are located and are among the ones she approves. This subset may include all such facilities, or just the facility that is the closest or the farthest from the agent s position. For such cases, it is quite easy to see that a straightforward adaptation of the Middle mechanism satisﬁes strategyproofness constraints and has an approximation ratio of at most 2. In addition, by extending the proof of Theorem 2, we can show for particular values of m and k that this is the best-possible approximation among deterministic mechanisms, even when the preferences of the agents are assumed to be known. Formally, let I = (x, t, m, k) be an instance with position proﬁle x, preference proﬁle t, and m 2 facilities out of which we must chose and locate k 1. Let S a subset of k facilities that are chosen to be located, and denote by yj [0, 1] the location of facility j S; let y = (yj)j S. Then, we can deﬁne the following three classes of utilities functions, to which we refer as sum, min and max:

usum i (S, y|I) = X

j S tij 1 d(xi, yj)

umin i (S, y|I) = max j S

tij 1 d(xi, yj)

umax i (S, y|I) = min j S

tij 1 d(xi, yj) .

For these three classes of utility functions, we will show that the (k, m)-Middle mechanism deﬁned below is either group-strategyproof or strategyproof (depending on the number of facilities it must choose) and has an approximation ratio of 2.

(k, m)-Middle mechanism

1. Count the number nj of agents that approve each facility j {1, . . . , m}. 2. Locate the k most preferred facilities at location 1 2, breaking ties arbitrarily.

Theorem 8. For any utility class C {sum, min, max}, the (k, m)-Middle mechanism is group-strategyproof when k = 1, strategyproof when k 2, and has an approximation ratio of at most 2. For completeness, we present a simple instance showing that the (k, m)-Middle mechanism is not groupstrategyproof when k 2 for any of the utility classes we consider. Lemma 9. For any utility class C {sum, min, max}, the (k, m)-Middle mechanism is not group-strategyproof when k 2. By appropriately extending the proof of Theorem 2, we can show that, for any m and k 1 such that m 2k, the approximation ratio of any deterministic mechanism is at least 2, even when the preferences of the agents are known. As a result, the (k, m)-Middle mechanism is the best possible strategyproof deterministic mechanism in terms of approximation in the general and in the known-preferences settings for any such choice of m and k. Theorem 10. For any utility class C {sum, min, max} and any m, k such that m 2k, the approximation ratio of every deterministic strategyproof mechanism that locates k out of m facilities is at least 2 δ, for any δ > 0, even when the preferences of the agents are known.

7 Conclusion and Open Problems There are several interesting problems that either remain open or arise from our work. The ﬁrst natural direction is to tighten our results for deterministic and randomized mechanisms for the different settings we have considered. For deterministic mechanisms, while the general and the knownpreferences settings are resolved by our work, it would still be quite interesting to close the gap between 13/11 and 2 for the known-positions setting. For randomized mechanisms, the most intriguing open question is whether there exists such a mechanism with approximation ratio signiﬁcantly smaller than 2 in the general setting. An obvious candidate is the RD mechanism that we presented in the context of the known-positions setting. Unfortunately, the particular variant of RD is no longer strategyproof when both the positions and the preferences of the agents are private, as shown by the following lemma. Lemma 11. RD is not strategyproof in the general setting.

Intuitively, the reason that makes RD manipulable in the general setting is the tie-breaking rule that we use for the agents who approve both facilities; recall that such ties are broken in favor of the optimal facility. Breaking ties in this way is crucial for our characterization of the worst-case instances in Section 5, but can be exploited by agents who are allowed to misreport their positions. Designing a variant of RD that is strategyproof in the general setting is straightforward, for example, by breaking ties between the two facilities equiprobably. Importantly however, the aforementioned characterization no longer holds in that case, which makes the analysis much more challenging. As a matter of fact, we can show that for any variant that uses a ﬁxed probabilistic tie-breaking rule, the approximation ratio is strictly larger than 3/2! In the following theorem, we show this for the version of RD that breaks ties by locating facility 1 with probability p and facility 2 with probability 1 p; we refer to this mechanism as p-RD. Lemma 12. p-RD has approximation ratio at least 1.518, for every ﬁxed p [0, 1]. Finding the exact approximation ratio of p-RD is an intriguing open question. Perhaps more interestingly, one can deﬁne yet another strategyproof variant of RD, whose approximation ratio is not ruled out by Lemma 12. For example, we can count how many agents approve each facility and break ties proportionally to those numbers. It is quite easy to observe that the RD mechanism using the proportional tiebreaking rule is strategyproof for the general setting, and is a promising candidate for achieving a better approximation ratio. To this end, we state the following conjecture. Conjecture 13. For the general setting, the RD mechanism with the proportional tie-breaking rule has approximation ratio 3/2. Besides strengthening our results, there are several meaningful extensions of our model that could be the subject of future work. For the k out of m facilities setting, while we have made an important ﬁrst step, there is still signiﬁcant work to be done, particularly in the known-positions setting. One could also consider several different variants of our basis model. For example, the agents may have fractional preferences rather than approval preferences (that is, each agent may assign weights in [0, 1] to the facilities, instead of weights in {0, 1}). Other possible variants include settings in which some facilities are obnoxious (Mei, Ye, and Zhang 2018; Feigenbaum and Sethuraman 2015), meaning that agents would like to be far from them if they are built, and discrete settings in which the facilities can only be built at predeﬁned locations on the line (e.g., see (Dokow et al. 2012; Feldman, Fiat, and Golomb 2016; Seraﬁno and Ventre 2015, 2016)). Finally, an interesting generalization of our problem is when every facility comes at a different cost, and the objective is to maximize the social welfare by choosing and locating k facilities under the constraint that their accumulated costs is below a predeﬁned budget. This latter setting is directly motivated by participatory budgeting, which has recently drawn the attention of the computational social choice community (Benade et al. 2020; Aziz and Shah 2020).

References Alon, N.; Feldman, M.; Procaccia, A. D.; and Tennenholtz, M. 2010. Strategyproof approximation of the minimax on networks. Mathematics of Operations Research, 35(3): 513 526. Anastasiadis, E.; and Deligkas, A. 2018. Heterogeneous Facility Location Games. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 623 631. Anshelevich, E.; Filos-Ratsikas, A.; Shah, N.; and Voudouris, A. A. 2021. Distortion in Social Choice Problems: The First 15 Years and Beyond. In Proceedings of the 30th International Joint Conference on Artiﬁcial Intelligence (IJCAI), 4294 4301. Aziz, H.; and Shah, N. 2020. Participatory Budgeting: Models and Approaches. Co RR, abs/2003.00606. Benade, G.; Nath, S.; Procaccia, A. D.; and Shah, N. 2020. Preference elicitation for participatory budgeting. Management Science. Cai, Q.; Filos-Ratsikas, A.; and Tang, P. 2016. Facility Location with Minimax Envy. In Kambhampati, S., ed., Proceedings of the 25th International Joint Conference on Artiﬁcial Intelligence (IJCAI), 137 143. Chan, H.; Filos-Ratsikas, A.; Li, B.; Li, M.; and Wang, C. 2021. Mechanism Design for Facility Location Problems: A Survey. In Proceedings of the 30th International Joint Conference on Artiﬁcial Intelligence (IJCAI), 4356 4365. Chen, Z.; Fong, K. C.; Li, M.; Wang, K.; Yuan, H.; and Zhang, Y. 2020. Facility location games with optional preference. Theoretical Computer Science, 847: 185 197. Cheng, Y.; Yu, W.; and Zhang, G. 2011. Mechanisms for obnoxious facility game on a path. In Combinatorial Optimization and Applications, 262 271. Springer. Cheng, Y.; Yu, W.; and Zhang, G. 2013. Strategy-proof approximation mechanisms for an obnoxious facility game on networks. Theoretical Computer Science, 497: 154 163. Dokow, E.; Feldman, M.; Meir, R.; and Nehama, I. 2012. Mechanism design on discrete lines and cycles. In Proceedings of the 13th ACM Conference on Electronic Commerce (EC), 423 440. Duan, L.; Li, B.; Li, M.; and Xu, X. 2019. Heterogeneous Two-facility Location Games with Minimum Distance Requirement. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 1461 1469. Elkind, E.; Li, M.; and Zhou, H. 2022. Facility Location With Approval Preferences: Strategyproofness and Fairness. In Proceedings of the 2022 International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS). Escofﬁer, B.; Gourves, L.; Thang, N. K.; Pascual, F.; and Spanjaard, O. 2011. Strategy-proof mechanisms for facility location games with many facilities. In Algorithmic decision theory, 67 81. Springer. Feigenbaum, I.; and Sethuraman, J. 2015. Strategyproof Mechanisms for One-Dimensional Hybrid and Obnoxious Facility Location Models. In Proceedings of the 2015 AAAI

Workshop on Incentive and Trust in E-Communities, volume WS-15-08. Feigenbaum, I.; Sethuraman, J.; and Ye, C. 2013. Approximately Optimal Mechanisms for Strategyproof Facility Location: Minimizing Lp Norm of Costs. Co RR, abs/1305.2446. Feldman, M.; Fiat, A.; and Golomb, I. 2016. On Voting and Facility Location. In Proceedings 2016 ACM Conference on Economics and Computation (EC), 269 286. Feldman, M.; and Wilf, Y. 2013. Strategyproof facility location and the least squares objective. In Proceedings of the 14th ACM Conference on Electronic Commerce (EC), 873 890. Filos-Ratsikas, A.; Li, M.; Zhang, J.; and Zhang, Q. 2015. Facility Location with Double-Peaked Preferences. In Proceedings of the 29th AAAI Conference on Artiﬁcial Intelligence (AAAI), 893 899. Filos-Ratsikas, A.; and Voudouris, A. A. 2021. Approximate mechanism design for distributed facility location. In Proceedings of the 14th International Symposium on Algorithmic Game Theory (SAGT). Fong, C. K. K.; Li, M.; Lu, P.; Todo, T.; and Yokoo, M. 2018. Facility location games with fractional preferences. In Proceedings of the 32nd AAAI Conference on Artiﬁcial Intelligence (AAAI), 1039 1046. Fotakis, D.; and Tzamos, C. 2013. Winner-imposing strategyproof mechanisms for multiple Facility Location games. Theoretical Computer Science, 472: 90 103. Fotakis, D.; and Tzamos, C. 2016. Strategyproof facility location for concave cost functions. Algorithmica, 76(1): 143 167. Golomb, I.; and Tzamos, C. 2017. Truthful facility location with additive errors. Co RR, abs/1701.00529. Kyropoulou, M.; Ventre, C.; and Zhang, X. 2019. Mechanism design for constrained heterogeneous facility location. In Proceedings of the 12th International Symposium on Algorithmic Game Theory (SAGT), 63 76. Li, M.; Lu, P.; Yao, Y.; and Zhang, J. 2020. Strategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio. In Proceedings of the 29th International Joint Conference on Artiﬁcial Intelligence (IJCAI), 238 245. Li, M.; Wang, C.; and Zhang, M. 2020. Budgeted Facility Location Games with Strategic Facilities. In Proceedings of the 29th International Joint Conference on Artiﬁcial Intelligence (IJCAI), 400 406. Lu, P.; Sun, X.; Wang, Y.; and Zhu, Z. A. 2010. Asymptotically optimal strategy-proof mechanisms for two-facility games. In Proceedings of the 11th ACM conference on Electronic Commerce (EC), 315 324. Lu, P.; Wang, Y.; and Zhou, Y. 2009. Tighter bounds for facility games. In Proceedings of the 5th International Workshop on Internet and Network Economics (WINE), 137 148. Mei, L.; Ye, D.; and Zhang, Y. 2018. Approximation strategy-proof mechanisms for obnoxious facility location

on a line. Journal of Combinatorial Optimization, 36(2): 549 571. Procaccia, A. D.; and Tennenholtz, M. 2013. Approximate Mechanism Design without Money. ACM Transactions on Economics and Computation, 1(4): 18:1 18:26. Schummer, J.; and Vohra, R. V. 2002. Strategy-proof location on a network. Journal of Economic Theory, 104(2): 405 428. Seraﬁno, P.; and Ventre, C. 2015. Truthful Mechanisms without Money for Non-Utilitarian Heterogeneous Facility Location. In Proceedings of the 29th AAAI Conference on Artiﬁcial Intelligence (AAAI), 1029 1035. Seraﬁno, P.; and Ventre, C. 2016. Heterogeneous facility location without money. Theoretical Computer Science, 636: 27 46. Sui, X.; and Boutilier, C. 2015. Approximately strategyproof mechanisms for (constrained) facility location. In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 605 613. Sui, X.; Boutilier, C.; and Sandholm, T. 2013. Analysis and optimization of multi-dimensional percentile mechanisms. In Proceedings of the 23rd International Joint Conference on Artiﬁcial Intelligence (IJCAI), 367 374. Tang, P.; Yu, D.; and Zhao, S. 2020. Characterization of group-strategyproof mechanisms for facility location in strictly convex space. In Proceedings of the 21st ACM Conference on Economics and Computation (EC). Zhang, Q.; and Li, M. 2014. Strategyproof mechanism design for facility location games with weighted agents on a line. Journal of Combinatorial Optimization, 28(4): 756 773.