Facility Location Problems with Capacity Constraints: Two Facilities and Beyond

1 Introduction

Mechanism Design aims to establish procedures for aggregating the private information of a group of agents to optimize a social objective. However, optimizing the social objective solely based on reported preferences frequently results in undesirable manipulation due to the self-interested behavior of the agents. Therefore, one of the most crucial requirements for a mechanism is the property of truthfulness, which ensures that no agent can gain an advantage by misreporting their private information. Unfortunately, this strict property often conflicts with optimizing the social objective, so the output of a truthful mechanism is oftentimes sub-optimal. To quantify the loss in efficiency, Nisan and Ronen introduced the concept of approximation ratio. This quantity represents the highest achievable ratio between the social objective obtained by a truthful mechanism and the optimal social objective among all possible agents' reports [Nisan and Ronen, 1999]. One of the classic examples of these problems is the m-Facility Location Problem (m-FLP). In its most basic form, the m-FLP consists in locating m facilities amongst n self-interested agents. Every agent needs to access a facility, so they would prefer to have one of the facilities placed as close as possible to their position. Moreover, each facility can serve any number of agents, thus every mechanism just needs to return the positions of the facilities. The agents are then free to decide which facility to use, without considering any possible overload.

In this paper, we study the m-Capacitated Facility Location Problem (m-CFLP) on the line [Pal et al., 2001]. The m-CFLP is a natural extension of the m-FLP in which every facility has a capacity limit. Considering facilities with capacity constraints is a natural approach for modeling scenarios where facilities offer a limited resource, as it happens in distribution planning [Pochet and Wolsey, 1988] and telecommunication network design [Boffey, 1989; Chardaire, 1999]. For instance, the facilities represent servers while the agents represent tasks awaiting execution, or facilities could be grocery shops and agents the customers in need of service.

From a mechanism design perspective, the study of the m-FLP and m-CFLP differs significantly, allowing to elude the impossibility results known for the m-FLP [Fotakis and Tzamos, 2014; Walsh, 2020]. In particular, we show that this is the case when we have m facilities with equal capacity k and the number of agents is n = km. For this class of problems, we characterize both the upper and lower bounds of the approximation ratio of anonymous, truthful, and deterministic mechanisms for m ≥ 2, showing that both are bounded, and that they coincide, making the bounds tight. It is also noteworthy that the study of the m-CFLP is contingent upon the specifics of the problem. Indeed, the properties of any mechanism depend on factors such as whether different facilities have different capacities [Aziz et al., 2020a], whether the total capacity is larger than the number of agents [Walsh, 2022], or whether the capacity of each facility is lower than a critical threshold[Aziz et al., 2020a]. For this reason, the few results providing tight lower bounds on the approximation ratio are limited to very specific settings [Aziz et al., 2020a].

Our Contribution. In this paper, we study two relevant frameworks for the m-CFLP from a Mechanism Design perspective. First, we study the m-CFLP with equi-capacitated facilities and no spare capacity, i.e. the m-CFLP in which all the facilities have the same capacity, namely k, and the total capacity of the facilities equals the number of agents. We present two truthful and anonymous mechanisms, the Propagating Median Mechanism (PMM) and the Propagating InnerPoint Mechanism (PIPM). We show that both the PMM and the PIPM have a bounded approximation ratio with respect to the Social Cost (SC) and the Maximum Cost (MC), regardless of the value of m. This result stands in contrast with the classic results for the m-FLP, according to which no mechanism can be deterministic, anonymous, truthful, and achieve a finite approximation ratio when m > 2, even on the line [Fotakis and Tzamos, 2014; Walsh, 2020]. We then present three lower bounds for the approximation ratio for the m-CFLP with equi-capacitated facilities and no spare capacities. In particular: (i) no truthful and deterministic mechanism achieves an approximation ratio lower than 2 with respect to MC. Thus, PMM and PIPM are optimal with respect to this metric. (ii) When k > 3, no truthful and deterministic mechanism can achieve an approximation ratio lower than 3 with respect to the SC. (iii) No truthful, deterministic, and anonymous mechanism achieves an approximation ratio with respect to SC lower than ( k(m-1) 2 +1), if m is odd, or lower than ( km 2 - 1) if m is even. In particular, the PMM and the PIPM are the best possible truthful, deterministic, and anonymous mechanisms for odd and even m, respectively.

We then study the 2-CFLP with abundant facilities, in which we have two facilities capable to accommodate at least half of the agents. This framework has been studied under further assumptions: (i) in [Aziz et al., 2020a], the authors studied the case in which n is even, c1 = c2 = n2 , and proposed the InnerPoint (IM) Mechanism, (ii) in [Walsh, 2022], the author studied the case in which n is odd and c1 = ⌈ n2 ⌉, c2 = ⌊ n2 ⌋, and proposed the InnerChoice (IC) Mechanisms introduced, (iii) again, in [Walsh, 2022], the author also studied the case in which n is arbitrary but c1 = c2, and proposed the InnerGap (IG) Mechanism. However, this is the first time that a study of a framework encompassing all these different cases has been conducted. We propose the Extended InnerGap (EIG) Mechanism, which generalizes and includes IM, IC, and IG. The EIG is strong Group Strategyproof, thus truthful, and attains a bounded approximation ratio with respect to the SC and MC. We then provide a lower bound on the approximation ratio of any truthful mechanism with respect to the SC and MC and show that the EIG is optimal with respect to the MC. Moreover, the EIG is optimal with respect to the SC whenever n ≥ ¯ c + √¯ c, where ¯ c = max{c1, c2}.

In Table 1, we summarize our findings in terms of lower and upper bounds for the cases we study. Due to space limits, some proofs are deferred to the Appendix.

Related works. The m-Facility Location Problem (mFLP) and its variants are relevant problems in several applied fields such as disaster relief [Balcik and Beamon, 2008], supply chain management [Melo et al., 2009], healthcare [Ahmadi-Javid et al., 2017], clustering [Hastie et al., 2009], and public facilities accessibility [Barda et al., 1990]. The Mechanism Design study of the m-FLP was first explored by Procaccia and Tennenholtz, who laid the foundation of this field in their pioneering work [Procaccia and Tennenholtz, 2013]. Subsequently, several mechanisms with small constant approximation ratios for locating one or two facilities on trees, circles, and general graphs have been introduced [Alon et al., 2010; Dokow et al., 2012; Feldman and Wilf, 2013; Filimonov and Meir, 2021; Lu et al., 2010; Lu et al., 2009; Filos-Ratsikas et al., 2017; Meir, 2019; Tang et al., 2020]. However, these positive results are limited to cases where the mechanism designer needs to place 2 facilities or the mechanism is not deterministic. Indeed, no deterministic, anonymous, and truthful mechanism can place more than two uncapacitated facilities while achieving a bounded approximation ratio even on the line [Fotakis and Tzamos, 2014; Walsh, 2020].

The m-Capacitated Facility Location Problem (m-CFLP) is a natural extension of the m-FLP, in which each facility has a maximum number of agents that it can serve [Brimberg et al., 2001; Pal et al., 2001; Aardal et al., 2015]. The Mechanism Design aspects of the m-CFLP have received relatively little attention until recently. Indeed, the game theoretical framework for the m-CFLP that we consider was first introduced in [Aziz et al., 2020a]. In this paper, the authors studied various truthful mechanisms (such as the InnerPoint Mechanism and the Extended Endpoint Mechanism) and studied their approximation ratios. Notably, only mechanisms capable of locating two facilities achieve a bounded approximation ratio. A more theoretical analysis of the problem has been then presented in [Walsh, 2022], where the author demonstrated that no mechanism can locate more than two capacitated facilities while being truthful, anonymous, and Pareto optimal. Lastly, papers that deal with different Mechanism Design aspects of the m-CFLP are [Auricchio et al., 2023], where the m-CFLP is studied in a Bayesian setting, and [Aziz et al., 2020b], where the authors investigate the case in which there is only one capacitated facility to place and it cannot accommodate all the agents.

2 Preliminaries

In this section, we introduce the two m-CFLP frameworks and fix the notation. Throughout the paper, we assume that the agents lay on a line and denote with ⃗x := (x1, . . . , xn) ∈ Rn the vector containing their positions. Moreover, we assume m > 1, as 1-CFLP is equivalent to the classic 1-FLP.

The m-CFLP with equi-capacitated facilities and no spare capacity. In the first framework, we havemfacilitieswhose capacity is the same, i.e. cj = k > 1 for every j ∈ [m], and the total capacity of the facilities equals the total number of agents, hence n = mk. We call this framework the m-CFLP with equi-capacitated facilities and no spare capacity. Since in this setting all the facilities have the same capacity, a facility location is defined by two objects: (i) a m-dimensional vector ⃗y = (y1, . . . , ym) whose entries are the positions of the facilities on the line, and (ii) a matching µ ⊂ [n] × [m] that determines how the agents are assigned to facilities, i.e. (i, j) ∈ µ if and only if the agent at xi is assigned to yj. Due to the capacity constraints, the degree of every vertex j ∈ [m] according to µ is at most k. Since every agent is assigned to only one facility, the degree of i ∈ [n] according to µ is 1.

The 2-CFLP with abundant facilities. In the second framework we consider, we have two facilities whose capacities, namely c1 and c2 are such that ⌊ n2 ⌋ ≤ c2, c1 ≤ n-1. We call this framework 2-CFLP with abundant capacities. Since the facilities may have different capacity, eliciting two positions, namely y1 and y2, and an agent-to-facility assignment µ is not sufficient, as we need to also specify the capacity of the two facilities. In particular, in this framework, a facility location is defined by three objects: (i) a bi-dimensional vector ⃗y = (y1, y2) whose entries are the positions of the facilities, (ii) a permutation π : [2] → [2] that specifies the capacity of each facility, so that if π(1) = j the facility at y1 has capacity cj and the facility built at y2 has capacity ci with i ̸= j and i, j ∈ [2], and (iii) a matching µ ⊂ [n] × [2] that determines how the agents are assigned to facilities. The degree of every vertex j ∈ [2] according to µ must be at most cπ(j), while the degree of every i ∈ [n] according to µ is 1.

MechanismDesign Framework for them-CFLP. In both frameworks, given the positions of the facilities ⃗y and a matching µ, we define the cost of an agent positioned in xi as ci,µ(xi, ⃗y) = |xi - yj|, where (i, j) is the unique edge in µ adjacent to i. Finally, a cost function is a map Cµ : Rn × Rm → [0,+∞) that associates to (⃗x, ⃗y) the overall cost of placing the facilities at ⃗y and assigning the agents positioned at ⃗x according to µ. 1 For both frameworks, given a vector ⃗x ∈ Rn containing the agents' positions, the m-Capacitated Facility Location Problem with respect to the cost C, consists in finding the locations for m facilities and a matching µ that minimize the function ⃗y → C(⃗x, ⃗y). Throughout the paper, we consider the Social Cost (SC), defined as the sum of all the agents' costs, i.e., SC(⃗x, ⃗y) = ∑i∈[n] ci(xi, ⃗y) = ∑i∈[n] |xi - yj | and the Maximum Cost (MC), defined as the maximum cost among all agents' costs, i.e. MC(⃗x, ⃗y) := maxi∈[n] ci(xi, ⃗y).

Amechanism for the m-CFLP is a function f that takes the private information of n self-interested agents as input and returns a facility location. Thus, for the m-CFLP with equicapacitated facilities and no spare capacity, the mechanism returns a set of locations ⃗y and a matching µ between the agents and the facilities. A mechanism f is said to be truthful (or strategy-proof ) if, for every agent, its cost is minimized when it reports its true position, i.e., for any x′i ∈ R, we have ci(xi, f(⃗x)) ≤ ci(xi, f(⃗x-i, x′i )) where xi is the agent's real position and ⃗x-i is the vector ⃗x without its i-th component.

1 In what follows, we omit µ from the indexes of c and C if it is clear from the context which matching we are considering.

A mechanism f is strong Group Strategyproof (GSP) if no group of agents can misreport their positions in such a way that (i) the cost of every agent in the group after manipulating is less than or equal to the cost they would get by reporting truthfully, (ii) at least one of the agents in the group incurs a strictly lower cost after the group manipulation.

Albeit a truthful mechanism prevents agents from misreporting their positions, their output is usually suboptimal. To evaluate this efficiency loss, we consider the approximation ratio of the mechanism introduced in [Nisan and Ronen, 1999]. Given a truthful mechanism f, its approximation ratio with respect to the SC is defined as arSC(f) := sup⃗x∈Rn SCf (⃗x) SCopt(⃗x) , where SCf(⃗x) is the SC of the solution returned by f and SCopt(⃗x) is the optimal SC achievable on instance ⃗x. Similarly, the approximation ratio of f with respect to the MC (namely, arMC(f)) is the highest ratio between the MC achieved by f and the optimal MC.

3 The m-CFLP with Equi-capacitated Facilities and No Spare Capacity

In this section, we focus on the Mechanism Design aspects of the m-CFLP with equi-capacitated facilities and no spare capacity, i.e. given m the number of facilities and their capacity k, it holds n = mk. Given j ∈ [m] and a vector ⃗x containing the agents' positions ordered from left to right, i.e. xi ≤ xi+1 for every i ∈ [n - 1], we define Ij as follows

Notice that, since every facility has the same capacity, the optimal solution to the m-CFLP with respect to the SC places the facilities at the positions ⃗y = (y1, . . . , ym), where each yj is a median of set Ij, and then it assigns every agent whose position is in Ij to yj. Likewise, the optimal solution with respect to the MC places the facilities at yj = x(j-1)k+1+xjk 2 and then it assigns the agents in Ij to yj.

3.1 The PropagatingMedianMechanism

We now introduce and study our first truthful mechanism for the m-CFLP with equi-capacitated facilities and no spare capacity, the Propagating Median Mechanism (PMM).

Mechanism 1 (Propagating Median Mechanism (PMM)). Let n be the total number of agents, m the number of facilities to place, and k = nm ∈ N the capacity of each facility.

Let us set r = ⌊ m+1 2 ⌋. The routine of the PMM is as follows: (i) First, we locate the facility yr at one of the medians of Ir, i.e. yr = xk(r-1)+⌊ k+1 2 ⌋ . (ii) Second, we determine the positions of the other facilities via the following iterative routine. For any l ≥ r, let us be given the position of the l-th facility, namely yl. Then the position of the (l + 1)-th facility is yl+1 = max{xkl+1, xkl +dl}, where dl is the distance between yl and xkl := maxx∈Il x. Similarly, given l ≤ r and the position of the l-th facility, namely yl, the (l -1)-th facility is placed at yl-1 = min{xk(l-1), xk(l-1)+1 - dl}, where dl is the distance between yl and xk(l-1)+1 := minx∈Il x. (iii) Finally, all the agents in Ij are assigned to yj.

Let ⃗y = (y1, . . . , ym) be the position of the facilities returned by the PMM on a given instance ⃗x. It is easy to see that the entries of ⃗y are non-decreasing, i.e. yj ≤ yj+1 for every j ∈ [m- 1]. Moreover, the PMM assigns every agent to its closest facility, so that minℓ∈[m] |xi - yℓ| = |xi - yj|, where j ∈ [m] is the only index for which it holds xi ∈ Ij.

Theorem 1. The PMM is truthful.

Proof. Toward a contradiction, let xi be the real position of an agent able to manipulate by reporting x′i instead of its real position xi. We denote with ⃗y and Ij the positions of the facilities returned by the PMM and the sets in (1) on the truthful input, respectively. Similarly, we denote with ⃗y ′ and I ′j the positions of the facilities returned by the PMM and the sets in (1) when the agent at xi reports x′i , respectively. Since the other case is symmetric, we assume that yr ≤ xi, where r = ⌊ m+1 2 ⌋ and yr = xk(r-1)+⌊ k+1 2 ⌋ , is a median of Ir.

We show that no agent in Ir can manipulate, the case in which xi /∈ Ir is similar and deferred to the Appendix. Toward a contradiction, let us assume that xi ∈ Ir. Then, if xi = yr, the cost of the agent is null, thus it cannot benefit by misreporting. Therefore, it must be that yr < xi. If x′i < yr, we have that x′i ∈ I ′ℓ with ℓ ≤ r. In this case, we have that y′r ≤ yr, thus y′ l ≤ · · · ≤ y′r ≤ yr < xi, which means that the manipulating agent is assigned to a facility that is not closer than yr, hence its cost does not decrease after the manipulation. Finally, let us consider the case yr < x′i . In this case, we have that y′r = yr, since the median of Ir is the same regardless of whether the manipulating agent reports truthfully or not. Thus, if x′i ∈ I ′r , it will still be assigned to y′r = yr, which brings no benefit to the manipulative agent. So it must be that x′i /∈ I ′r , then x′i ∈ I ′ℓ , where ℓ > r, thus the manipulating agent is assigned to y′ℓ ≥ y′r+1 , since ℓ > r. Let us denote with x′rk the position of the (rk)- th agent from the left in the manipulated instance (x′i , x-i). Since x′i > xi, we have x′rk ≥ xrk ≥ xi. We have that y′r+1 = max{x′rk+1 , x′rk + |y′r -x′rk |} ≥ x′rk + |y′r -x′rk | ≥ xi+|yr-x′rk | ≥ xi+|yr-xi|, thus the cost of being assigned to y′ℓ is no less than the cost of being assigned to yr.

Although the PMM is truthful, it is not strong GSP, as the following example shows.

Example 1. Let us fix n = 9, m = 3, and k = 3. Let us consider the following instance: x1 = x2 = x3 = 0, x4 = x5 = 1, x6 = 2, x7 = 2.5, and x8 = x9 = 4. The PMM places the facilities at y1 = 0, y2 = 1, and y3 = 3. In this instance, the agents at x6 and x7 can collude: indeed, if x6 reports x′6 = 1, the PMM places the facilities at y1 = 0, y2 = 1, and y3 = 2.5, thus the cost of x7 decreases.

To conclude, we provide an analysis of the approximation ratio of the PMM with respect to the SC and MC. In particular, we prove that arSC(PMM) and arMC(PMM) are finite.

Proof. Let r = ⌊ m+1 2 ⌋ and ⃗x be a vector containing all the agents' reports ordered from left to right. Let SCopt(⃗x) be the optimal SC for ⃗x, then it holds that SCopt(⃗x) = ∑j∈[m] SCopt(Ij), where SCopt(Ij) is the SC of the agents whose report is in Ij according to the optimal solution. Similarly, let SCPMM(⃗x) be the SC of instance ⃗x according to the output of PMM, then it holds that SCPMM(⃗x) = ∑j∈[m] SCPMM(Ij), where SCPMM(Ij) is the SC of the agents whose report is in Ij according to the output of PMM. We denote with ⃗y the vector containing the locations of the facilities returned by the PMM and define J ⊂ [m] as the set of indexes j ∈ [m] such that yj ∈ [x(j-1)k+1, xjk]. We notice that J is non-empty since r ∈ J by definition of the PMM. We notice that SCopt(Ir) = SCPMM(Ir). Let us now consider j ∈ J such that j ̸= r. Since yj ∈ [x(j-1)k+1, xjk], we have that SCPMM(Ij) ≤ (k - 1)|x(j-1)k+1 - xjk| ≤ (k - 1)SCopt(Ij). Let us now consider j /∈ J and, without loss of generality, let us assume that r < j since the other case is symmetric. Since j /∈ J, there exists an index ℓ ∈ J such that yj = xkℓ + |yℓ - xkℓ|. If ℓ ̸= r, we have that SCPMM(Ij) ≤ k|yℓ - xkℓ| ≤ kSCopt(Iℓ) since, for every xt ∈ Ij , we have xkℓ ≤ xt ≤ yj . Similarly, if ℓ = r, we have that SCPMM(Ij) ≤ k|yr - xkr|. Therefore, it holds

Hence SCPMM ≤ ∑j∈J,j̸=r (kλj + k - 1)SCopt(Ij ) + (kΓ + 1)SCopt(Ir) where (i) λj, for j ∈ J and j ̸= r, is the number of i ∈ [m] such that i ̸= j and yi = xjk + |yj - xjk| if j > r and the number of i ∈ [m] such that i ̸= j and yi = xjk-|yj -xjk| if j < r, (ii) γl is the number of i ∈ [m] such that i < r and yi = xk(r-1)+1 - |yr - xk(r-1)+1|, (iii) γr is the number of i ∈ [m] such that i > r and yi = xkr + |yr - xkr|, and (iv) Γ = max{γr, γl}.

If we set Kr = (kΓ + 1) and Kj = (kλj + k - 1) for every j ∈ J such that j ̸= r, we have arSC(PMM) ≤ ∑j∈J Kj SCopt(Ij ) ∑j∈J SCopt(Ij) , thus arSC(PMM) ≤ maxj∈J{Kj}. Since, λj ≤ ⌊ m2 ⌋-1 and Γ ≤ ⌊ m2 ⌋, we have Kj ≤ k ⌊ m2 ⌋+1 for every j ∈ J, therefore arSC(PMM) ≤ k ⌊ m2 ⌋ + 1.

Finally, to prove that ar(PMM) = (k ⌊ m2 ⌋ + 1), consider the following instance: x1 = · · · = xkr-1 = 0 and xkr = · · · = xn = 1. The optimal cost of this instance is 1. The PMM places the facilities as it follows y1 = · · · = yr = 0 and yr+1 = · · · = ym = 2, thus the Social Cost of the mechanism is n - (k ⌊ m+1 2 ⌋ - 1) = k ⌊ m2 ⌋ + 1.

Through a similar argument, we retrieve the approximation ratio of PMM with respect to the MC.

Theorem 3. It holds arMC(PMM) = 2.

3.2 The Propagating InnerPoint Mechanism

We now present our second truthful mechanism for the mCFLP with equi-capacitated facilities and no spare capacity, the Propagating InnerPoint Mechanism (PIPM). The routine of the PIPM is similar to the routine of the PMM, the main difference lies in how it determines the initial facilities. Indeed, the PMM places a facility at the median of I⌊ m+1 2 ⌋ , while the PIPM places two facilities: one at the maximum value of I⌊ m2 ⌋ and one at the minimum value of I⌊ m2 ⌋+1 .

Mechanism 2 (Propagating InnerPoint Mechanism). Let n be the total number of agents, m be the number of facilities to place, and k = nm ∈ N be the capacity of each facility. Let us set r = ⌊ m2 ⌋. The mechanism runs as follows: (i) First, we locate the facilities yr and yr+1 at the positions xrk and xrk+1, respectively. (ii) To place the other facilities, we run an iterative routine. For l ≥ r + 1, given the position of the l-th facility, namely yl, we place the (l + 1)-th facility at the position yl+1 = max{xkl+1, xkl + dl}, where dl is the distance between yl and xkl. For l ≤ r, we run a similar iterative routine. Given the position of the l-th facility yl, the (l - 1)-th facility is placed at min{xk(l-1), xk(l-1)+1 - dl}, where dl is the distance between yl and xk(l-1)+1. (iii) Finally, all the agents in Ij are assigned to yj.

Due to the similarities between the definition of the PMM and the PIPM, it is possible to adapt the arguments used in the proof of Theorem 1, 2, and 3 to this mechanism. In particular, the PIPM is truthful and achieves a bounded approximation ratio with respect to both the SC and MC.

Theorem 4. The PIPM is truthful. Moreover, we have that arSC(PIPM) = k ⌈ m2 ⌉ - 1 and arMC(PIPM) = 2.

Albeit arMC(PMM) = arMC(PIPM), the approximation ratios of the two mechanisms with respect to the SC are different. Indeed, we have that arSC(PMM) < arSC(PIPM) when m is odd and, vice-versa, arSC(PIPM) < arSC(PMM) when m is even. Finally, it is easy to adapt Example 1 to show that PIPM is not strong GSP.

3.3 Lower Bounds for the Approximation Ratio

To conclude the section, we study the lower bounds for the approximation ratio of truthful mechanisms for the m-CFLP with equi-capacitated facilities and no spare capacity. First, we show that 2 is the best approximation ratio for any truthful and deterministic mechanism with respect to the MC.

Theorem 5. No deterministic truthful mechanism for the mCFLP with equi-capacitated facilities and no spare capacity can achieve an approximation ratio with respect to the Maximum Cost that is lower than 2.

Proof. Let k be the capacity of m facilities, hence n = mk is the total number of agents. Toward a contradiction, let M be a truthful and deterministic mechanism such that arMC(M) = 2 - δ where δ > 0. Let us consider the following instance: x1 = 0 and x2 = · · · = xn = 2. It is easy to see that the optimal MC is 1. Let y1 denote the position at which M places the facility to which agent at x1 and k - 1 of the agents at 2 are assigned. Since arMC(M) < 2, we have that y1 ∈ [0, 2]. Given t > 0, let us now consider the instance x′1 = -t and x2 = · · · = xn = 2. For every t > 0, the optimal MC of these instances is t+2 2 . SinceM is truthful, we have that y′1 ≥ y1, thus arMC(M) ≥ t t+2 2 = 2t t+2 . Finally, we notice that the right hand-side of the inequality converges to 2 as t → ∞, thus we have that ar(M) > 2 - δ for every δ > 0, which is a contradiction.

We now move to the lower bound for the Social Cost.

Theorem 6. No deterministic truthful mechanism for the mCFLP with equi-capacitated facilities and no spare capacity can achieve an approximation ratio with respect to the Social Cost that is lower than 3 whenever k > 3.

Proof. Given m facilities with capacity k, let n = mk be the number of agents. Let us consider the following instance: x1 = · · · = xk+1 = 0 and xk+2 = · · · = xn = 2. It is easy to see that the optimal Social Cost is 2. We now show that the mechanism must place at least one facility at 0 and at least one facility at 2. If all the facilities are placed at 0, the approximation ratio of the mechanism would be higher than k - 1, which would conclude the proof. Similarly, we conclude that not all the facilities are placed at 2. Finally, let us assume that the facility serving the agents placed at 2 and one of the agents placed at 0, namely y is such that y ∈ (0, 2). Without loss of generality, it suffices to consider the case in which one agent at 0 shares the facility with agents at 2, since in all other cases the cost of the mechanism increases. In this case, if we move the agent placed at 0 to y, we have that the facility does not change its position (as otherwise an agent placed at y could manipulate by reporting 0), thus the approximation ratio of the mechanism would be at least equal to k-1. So the facility that serves both an agent at 0 and k-1 agents at 2 must be placed at 2.

Let us consider one of the agents placed at 0 that is not assigned to a facility placed at 2. For every ϵ > 0, we have that if the agent was placed at 1-ϵ, it would be still assigned to a facility at 0, as otherwise, it could manipulate by reporting 0 rather than its real position. In this case, the cost of the mechanism is 3-ϵ, while the optimal cost is 1+ϵ. Since this holds for every ϵ > 0, the approximation ratio with respect to the SC of the mechanism is greater or equal to 3.

Finally, we present a lower bound for the approximation ratio with respect to the SC of deterministic, anonymous, and truthful mechanisms. We recall that a mechanism M is anonymous if every agent's outcome depends only on its reports, i.e. two agents swapping two different reports causes the mechanism to swap their outcomes.

Theorem 7. No deterministic, anonymous, and truthful mechanism for the m-CFLP with equi-capacitated facilities and no spare capacity can achieve an approximation ratio with respect to the Social Cost that is lower than ( k(m-1) 2 +1) if m is odd or lower than ( km 2 -1) if m is even.

Proof. Let M be a deterministic, anonymous, and truthful mechanism. Let us consider the following instance x1 = · · · = xkr+1 = 0 and xkr+2 = · · · = xn = 1, where Since the PMM and the PIPM are anonymous, the lower bound in Theorem 7 is tight. Indeed PMM achieves the lower bound for odd m, while PIPM does so for even m. Therefore, for the m-CFLP with equi-capacitated and no spare capacity, PMM and PIPM are the best anonymous, deterministic, and truthful mechanisms for odd and even m, respectively.

r = ⌊ m2 ⌋. The optimal cost of this instance is 1. First, we show that, according to M, the locations of the facilities serving the agents at 0 are all placed at the same distance from 0. Toward a contradiction, let us assume that M places two facilities at two positions, namely y and y′ , such that |y - 0| ̸= |y′ - 0| and that both facilities serve an agent that reported 0. Without loss of generality, let us assume that |y - 0| = |y| < |y′ | = |y′ - 0|. Let us denote with xi one of the agents who reported 0 that is assigned to y. Let us now consider the instance (y, x-i). Since M is truthful, we must have that the mechanism places a facility at y and that the agent at y is assigned to it, as otherwise, it could misreport by reporting 0. Let us now denote with xj one of the agents in 0 that is assigned to y′ . Since M is anonymous, if xj reports y, it is assigned to y, which is closer to 0 than y′ , which contradicts the truthfulness of M. In particular, we infer that all the agents placed at 0 incur the same cost. Similarly, all the agents placed at 1 incur the same cost. Since there is no spare capacity, there exists at least one facility that serves an agent placed at 0 and an agent placed at 1, let us denote with λ ∈ R its position on the line. Then, the total cost of the mechanism is C = |λ|(k ⌊ m2 ⌋ +1) + |1-λ|(n-k ⌊ m2 ⌋ -1). Finally, we notice that C ≥ ( k(m-1) 2 +1) if m is odd and C ≥ ( km 2 -1) if m is even, which concludes the proof.

4 The 2-CFLPWith Abundant Facilities

We now consider the case in which we have to place two facilities capable of accommodating half of the agents. We present the Extended InnerGap (EIG) mechanism, a truthful mechanism that generalizes and includes mechanisms that operate under further assumptions: the InnerPoint (IM) Mechanism [Aziz et al., 2020a], the InnerGap (IG) Mechanism [Walsh, 2022], and the InnerChoice (IC) Mechanism [Walsh, 2022] (see Table 2). We show that EIG achieves a finite approximation ratio with respect to the SC and the MC and corroborate these results by providing lower bounds on the approximation ratio achievable by truthful and deterministic mechanisms with respect to SC and MC. As a consequence, we infer the approximation ratio of the IC and IG mechanisms, which, to the best of our knowledge, were previously unknown.

Mechanism 3 (Extended InnerGap Mechanism). Let ¯ c := max{c1, c2} and let ⃗x ∈ Rn be the vector containing the agents' report ordered from left to right. Let us fix y1 = xn-¯ c, y2 = x¯ c+1, and z = y1+y2 2 , let n1 be the number of agents in [y1, z]∩{xi}i∈[n] and n2 be the number of agents in (z, y2]∩ {xi}i∈[n]. Finally, the output of the EIG over ⃗x is (i) to place the facility with the largest capacity at y1 and the other at y2 if n1 ≥ n2; or (ii) to place the facility with the lowest capacity at y1 and the other at y2 if n2 > n1. In both cases, every agent is assigned to the facility closer to its report.

Theorem 8. The EIG is strong GSP, hence truthful.

Proof. Let ⃗x be the true positions of the agents. We denote with y1 ≤ y2 the positions of the facilities according to the EIG on the truthful input. Let I := {xi1 , . . . , xis } be the real positions of the agents that form a coalition able to manipulate the output of the EIG. Without loss of generality, we assume that I is minimal, that is no subset of the agents in I can collude. We recall that the EIG places the two facilities: one at the (n- ¯ c)-th agents' report from the left, namely y1, and one at the (¯ c + 1)-th agents' report from the left, namely y2. Since I is minimal, none of the agents whose true position coincides with y1 or y2 takes part in the group manipulation. Hence, if we denote with y′1 and y′2 the positions of the facilities after the group manipulation, we cannot have that y′1 < y1 and y2 < y′2 at the same time. Let us now consider a coalition of agents I that is able to lower the cost of an agent, whose real location is xi1 , without increasing the cost of the other agents in I. Without loss of generality, let us assume that xi1 < y1, hence y′1 < y1. If y′1 < y1, it must be the case that at least one agent whose real position, namely xt, was on the right of y1 reports a position on the left of y1, i.e. x′t ∈ I ′1 , where x′t is the misreport of the agent whose real position was xt. If that agent was assigned to y2 in the truthful input, it must be that |xt -y2| ≥ |xt -y1| > |xt -y′1 |, since y′1 < y1 ≤ xt. Thus, the agent at xt is increasing its cost, which contradicts xt ∈ I. Similarly, if xt was assigned to y1 according to the truthful input, its cost still increases after the manipulation, which concludes the proof.

The EIG mechanism determines the facility position using the same routine used by a percentile mechanism, [Sui et al., 2013]. However, the percentile mechanisms are not strong GSP in general, while the EIG mechanism is (see Example in the Appendix). This difference is due to the fact that the EIG forces the agents to use a specific facility, while the percentile mechanism does not.

Proof. We prove the statement only for the MC, the study of the SC is deferred to the Appendix. Let us denote with Ii the set of agents that are assigned to the facility with capacity ci according to the optimal solution and, without loss of generality, we assume that all the agents in I1 are placed to the left of the agents in I2. The optimal MC is then

12 max{|min{I1}-max{I1}|, |min{I2}-max{I2}|}. Let y1 ≤ y2 be the position at which the mechanism places the two facilities. Then the MC of the EIG is lower or equal to the MC of assigning all the agents in Ii to the facility at yi. Finally, since xn-¯ c ∈ I1 and x¯ c+1 ∈ I2, we infer that

thus arMC(EIG) ≤ 2. Lastly, let us define ⃗x as x1 = · · · = x¯ c+1 = 0, and x¯ c+2 = · · · = xn = 1. The optimal cost is 0.5, while the cost of the EIG mechanism is 1.

We now provide lower bounds on the approximation ratio with respect to both the MC and SC of any truthful and deterministic mechanism for this framework. Our results show that the EIG is optimal or almost optimal for both costs.

Theorem 10. Let M be a truthful and deterministic mechanism that places two facilities with capacity c1, c2 ≥ ⌊ n2 ⌋, then we have that arMC(M) ≥ 2 and arSC(M) ≥ 3. If M is also anonymous, then we have that arSC(M) ≥ (n- ¯ c - 1).

Proof. We prove only the lower bound with respect to the SC for truthful, deterministic, and anonymous mechanisms. The proof for the other two cases, follow an argument similar to the ones used in the proof of Theorem 5 and 6 and are reported in the Appendix. Let us consider the following instance: x1 = · · · = x¯ c+1 = 0 and x¯ c+2 = · · · = xn = 1. By the same argument used in Theorem 7, any truthful, deterministic, and anonymous mechanism places the two facilities at the same distance from 0. Since we have that ¯ c ≥ ⌊ n2 ⌋, we have that ¯ c + 1 ≥ n - ¯ c - 1, hence we get that the approximation ratio of any truthful, anonymous, and deterministic mechanism is larger than (n - ¯ c - 1).

In particular, the EIG is the best truthful, anonymous, and deterministic mechanism whenever n ≥ ¯ c + √¯ c.

4.1 The EIG and Previous Mechanisms

To conclude, we show that the EIG mechanisms extends and includes three already-known mechanisms. In particular, (i) when n is an even number and c1 = c2 = n2 , the EIG mechanism coincides with the InnerPoint Mechanism, presented in [Aziz et al., 2020a]. (ii) When n = 2k + 1 is odd, c1 = k + 1, and c2 = k, the EIG mechanism coincides with the InnerChoice Mechanism, presented in [Walsh, 2022]. (iii) When c1 = c2, the EIG mechanism coincides with the InnerGap Mechanism, presented in [Walsh, 2022].

For the sake of argument, we limit our discussion to the InnerChoice (IC) mechanism, and defer the other two cases to the Appendix. Given an odd number n = 2k + 1 and two facilities whose capacities are c1 = k + 1 and c2 = k, the routine of the IC mechanism is as follows: (i) Given ⃗x = (x1, . . . , xn) the vector containing the agents' reports ordered from left to right, i.e. xi ≤ xi+1, we define δ1 = |xk+1 - xk| and δ2 = |xk+2 - xk+1|. (ii) If δ1 ≤ δ2, we locate the facility with capacity c1 at xk and the other one at xk+2. Otherwise, we locate the facility with capacity c1

at xk+2 and the other one at xk. (iii) Lastly, every agent is assigned to its closest facility.

Since ¯ c = k + 1, we have that xn-¯ c = xk and x¯ c+1 = xk+2, hence, for every ⃗x ∈ Rn , the output of EIG and IC are the same, thus the two mechanisms do coincide. It was shown in [Walsh, 2022] that the IC is truthful, however, owing to Theorem 8, we have that IC is strong GSP.

Theorem 11. The IC is strong Group Strategyproof.

Similarly, we extend the results on the approximation ratio of the IC mechanism with respect to the SC and MC.

Theorem 12. Let n be an odd number, then arMC(IC) = 2. Moreover, if n > 5, it holds arSC(IC) = k - 1 = n-3 2 , otherwise arSC(IC) = 1.

Since n ≥ k + 1 + √k + 1, the IC is the optimal truthful, deterministic, and anonymous mechanisms to place two facilities of capacities k + 1 and k amongst n = 2k + 1 agents. Moreover, the IC is also optimal with respect to the MC.

Theorem 13. Given k ∈ N, let n = 2k + 1 > 1. Then, every truthful deterministic mechanismM that places two facilities with capacity k+1 and k is such that arMC(M) ≥ 2. Moreover, if k > 2, arSC(M) ≥ 3. Lastly, if M is also anonymous, then arSC(M) ≥ k - 1.

Lastly, we notice that the only other mechanism known that is not extended by the EIG is the Extended Endpoint Mechanism (EEM). However, the approximation ratio of EEM is equal to 3n 2 , which is larger than the one attained by the EIG, making it suboptimal [Aziz et al., 2020a].

5 Conclusion and FutureWorks

In this paper, we investigated two frameworks for the mCFLP from a Mechanism Design perspective. First, we considered the m-CFLP with equi-capacitated facilities and no spare capacity. We propose two truthful mechanisms: the Propagating Median Mechanism (PMM) and the Propagating InnerPoint Mechanism (PIPM). Both the mechanisms have bounded approximation ratios with respect to the Social and Maximum Costs. We then established lower bounds on the approximation ratio of any truthful and deterministic mechanism for the m-CFLP with equi-capacitated facilities and no spare capacity. Notably, both PMM and PIPM achieved optimal approximation ratios for the Maximum Cost. Additionally, we demonstrated that PMM and PIPM achieve the minimum possible approximation ratio for the Social Cost among truthful, deterministic, and anonymous mechanisms. In the second framework, we considered the case in which we have two facilities to place and both facilities can accommodate half of the agents. We proposed the Extended InnerGap mechanism, which is strong Group Strategyproof, achieves finite approximation ratio, is optimal with respect to the MC and almost optimal with respect to the SC.

In future research avenues, we aim to improve the lower bounds for non-anonymous mechanisms concerning the Social Cost, to explore higher-dimensional scenarios for agent placements, and to adapt existing randomized mechanisms to enhance approximation ratios results for this problem class [Procaccia and Tennenholtz, 2013].

Acknowledgments

Zihe Wang was partially supported by the National Natural Science Foundation of China (Grant No. 62172422). Jie Zhang was partially supported by a Leverhulme Trust Research Project Grant (2021 - 2024) and the EPSRC grant (EP/W014912/1).