Randomized Strategic Facility Location with Predictions

Authors: eric  balkanski
vasilis  gkatzelis
golnoosh  shahkarami
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 23:18:16

Abstract: In the strategic facility location problem, a set of agents report their locations in a metric space and the goal is to use these reports to open a new facility, minimizing an aggregate distance measure from the agents to the facility. However, agents are strategic and may misreport their locations to influence the facility’s placement in their favor. The aim is to design truthful mechanisms, ensuring agents cannot gain by misreporting. This problem was recently revisited through the learning-augmented framework, aiming to move beyond worst-case analysis and design truthful mechanisms that are augmented with (machine-learned) predictions. The focus of this work was on mechanisms that are deterministic and augmented with a prediction regarding the optimal facility location. In this paper, we provide a deeper understanding of this problem by exploring the power of randomization as well as the impact of different types of predictions on the performance of truthful learning-augmented mechanisms. We study both the single-dimensional and the Euclidean case and provide upper and lower bounds regarding the achievable approximation of the optimal egalitarian social cost.

Main paper: 
 introduction: 
 In the classic facility location problem the goal is to determine the ideal location for a new facility, taking as input the preferences of a group of n agents. Due to the wide variety of applications that this problem captures, it has received a lot of attention from different perspectives. A notable example is the strategic version of this problem which is motivated by the fact that the participating agents may be able to strategically misreport their preferences, leading to a facility location choice that they prefer over the one that would be chosen if they were truthful. In the strategic facility location problem, the goal is to design truthful mechanisms, i.e., mechanisms that elicit the agents' true preferences by carefully removing any incentive for the agents to lie [Moulin, 1980, Procaccia and Tennenholtz, 2013] . This problem has played a central role in the broader literature on mechanism design without money and a lot of prior work has focused on optimizing the quality of the returned location subject to the truthfulness constraint (see Section 1.2 for a brief overview). However, this work has mostly focused on worst-case analysis, often leading to unnecessarily pessimistic impossibility results.Aiming to overcome the limitations of worst-case analysis, a surge of work during the last few years has focused on the design of algorithms in the learning-augmented framework [Mitzenmacher and Vassilvitskii, 2022] . According to this framework, the designer is provided with some machinelearned prediction regarding the instance at hand and the goal is to leverage this additional information in the design process. However, crucially, this information is not guaranteed to be accurate and can, in fact, be arbitrarily inaccurate. The goal is to achieve stronger performance guarantees whenever the prediction happens to be accurate (known as the consistency guarantee), while at the same time maintaining some worst-case guarantee even if the prediction is arbitrarily inaccurate (known as the robustness guarantee). Agrawal et al. [2022] and Xu and Lu [2022] recently introduced the learning-augmented framework to mechanism design problems involving self-interested strategic agents with private information, and both of these works studied the strategic facility location problem. Agrawal et al. [2022] considered both the egalitarian and the utilitarian social cost objectives and provided tight bounds on the bestfeasible robustness and consistency trade-off for truthful mechanisms augmented with a prediction regarding what the optimal facility location would be. However, the achievable trade-offs between robustness and consistency may heavily depend on the specific type of prediction that the mechanism is augmented with: note that the consistency guarantee only binds if the prediction is accurate, so more refined predictions bind on fewer instances (the subset of instances where even the refined prediction is accurate) and could, therefore, enable the design of learning-augmented mechanisms with improved guarantees. This leaves open the question of whether mechanisms equipped with more refined predictions can, indeed, achieve better trade-offs between robustness and consistency. Also, Agrawal et al. [2022] restricted their attention to deterministic mechanisms, leaving open the possibility for truthful randomized mechanisms to achieve even stronger guarantees. In this work we significantly expand our understanding of this problem by studying both the power of randomization and the power of alternative predictions.We revisit the problem of designing truthful learning-augmented mechanisms for the strategic facility location problem. These mechanisms ask each agent to report their preferred location in some metric space (which is private information) and they are also augmented with some (unreliable) prediction related to this private information. Using the agents' reported locations, along with the prediction, the mechanism chooses a facility location in this metric space, aiming to (approximately) minimize some social cost measure. Our focus in this paper is on the egalitarian social cost, i.e., the maximum distance between an agent's preferred location and the location chosen for the facility. Our goal is to evaluate the performance of mechanisms that can leverage randomization, as well as the power of different types of predictions.We first consider the well-studied single-dimensional version of the problem, where all agents lie on a line and the mechanism needs to choose a facility location on that line. Prior work on the strategic facility location problem without predictions, showed that for this class of instances no deterministic truthful mechanism can achieve an approximation better than 2 and no randomized truthful1 mechanism can achieve an approximation better than 1.5; both of these results are shown to be tight [Procaccia and Tennenholtz, 2013] . In the learning-augmented framework, Agrawal et al. [2022] showed there exists a truthful deterministic mechanism provided with a prediction regarding the optimal facility location that achieves the best of both worlds: a perfect consistency of 1 and an optimal robustness of 2.Our main result for the single-dimensional version shows that even if the mechanism is provided with the strongest possible prediction (i.e., a prediction regarding every agent's preferred location), any randomized truthful mechanism that is (1 + δ)-consistent for some δ ∈ [0, 0.5] can be no better than (2 -δ)-robust. This implies that the previously proposed deterministic learning-augmented mechanism that is 1-consistent and 2-robust and the randomized non-learning-augmented mechanism that is 1.5-robust (and hence also 1.5-consistent) are both Pareto optimal among all randomized mechanisms, even if they are augmented with the strongest possible predictions. Beyond these two extreme points, this result proves a lower bound for the achievable trade-off between robustness and consistency for any randomized mechanism, even with the strongest predictions. We complement this bound by observing that this trade-off can, in fact, be achieved by a truthful randomized mechanism that chooses between the optimal learning-augmented deterministic mechanism and the optimal non-augmented randomized mechanism, thus verifying that our bound fully characterizes this Pareto frontier.We then consider the two-dimensional case, for which much less is known about randomized mechanisms. The best-known truthful randomized mechanism is the Centroid, introduced by Tang et al. [2020] , which guarantees a 2-1/n approximation. We provide a truthful randomized mechanism that is equipped with a prediction regarding the identities of the most extreme agents (those who would incur the maximum cost in the optimal solution) and, using this prediction, our mechanism achieves 1.67-consistency and 2-robustness. The idea is to use these predictions to select at most three extreme agents, apply the Centroid mechanism to them, and guarantee a 1.67 approximation if the predictions are accurate not only for these three agents but for all other agents as well, utilizing the properties of the Euler line.An interesting observation is that the lower bound of 1.5 from the single-dimensional case does not extend to two dimensions, so prior work does not imply any lower bound for two dimensions! We prove a lower bound of 1.118 for all truthful randomized mechanisms and then that no deterministic mechanism can simultaneously guarantee better than 2-consistency and better than 1 + √ 2-robustness, even if it is augmented with the strongest predictions. Similarly, no truthful randomized mechanism can simultaneously guarantee 1-consistency and better than 2-robustness. The former result proves the optimality of a previously introduced 1-consistent and 1 + √ 2-robust truthful deterministic mechanism provided only with a prediction regarding the optimal facility location [Agrawal et al., 2022] . We also show that the latter is tight.Strategic facility location. Moulin [1980] provided a characterization of deterministic truthful facility location mechanisms on the line and introduced the median mechanism, which returns the median of the agent location profile x = ⟨x 1 , • • • , x n ⟩. The median mechanism is known to be truthful, providing an optimal solution for the Utilitarian Social Cost and achieving a 2-approximation for the Egalitarian Social Cost, as demonstrated by Procaccia and Tennenholtz [2013] . Notably, Procaccia and Tennenholtz [2013] showed that this 2-approximation factor represents the best performance achievable by any deterministic truthful mechanism. Building on this, Border and Jordan [1983] extended these results to the Euclidean space by employing median schemes independently in each dimension. Subsequently, Barberà et al. [1993] further generalized this outcome to any L 1norms. Other settings explored include general metric spaces [Alon et al., 2010] and d-dimensional Euclidean spaces [Meir, 2019 , Walsh, 2020 , El-Mhamdi et al., 2023 , Goel and Hann-Caruthers, 2020] , as well as circles [Alon et al., 2010 , Meir, 2019] and trees [Alon et al., 2010, Feldman and Wilf, 2013] . Fundamental results in truthful facility location often focus on characterizing the space of truthful mechanisms. For the one-dimensional case, Moulin's characterization [Moulin, 1980] reveals that all deterministic truthful mechanisms belong to the "general median mechanisms (GCM)" family. For the two-dimensional case, a similar characterization was provided by Peters et al. [1993] . For a comprehensive review of previous work on this problem, see the survey by Chan et al. [2021] .Learning-augmented algorithms. Worst-case analysis on its own is often not informative enough, and several alternative measures have been proposed to overcome its limitations [Roughgarden, 2021] . Learning-augmented algorithms, or algorithms with predictions [Mitzenmacher and Vassilvitskii, 2022] , aim to address these limitations by incorporating predictions into the algorithm's design. Lykouris and Vassilvitskii [2021] studied the online caching problem and introduced two main metrics, consistency and robustness, to evaluate the performance of these algorithms. The online version of the facility location problem, introduced by Meyerson [2001] , involves points arriving online, requiring us to assign them irrevocably to either an existing facility or open a new facility. The objective is to minimize the distance of each agent to the assigned facility along with the cost of opening the facilities. Almanza et al. [2021 ], Jiang et al. [2022] , and Fotakis et al. [2021] studied this problem augmented with predictions regarding the location of the optimal facility for each incoming point. We direct interested readers to a curated and frequently updated list of papers in this area [Lindermayr and Megow] .Learning-augmented mechanism design. The framework of learning-augmented mechanism design was first introduced by Agrawal et al. [2022] and Xu and Lu [2022] . Agrawal et al. [2022] focused on the strategic facility location problem, proposing mechanisms that leverage predictions to improve performance while maintaining truthfulness. Their work achieves the best possible consistency and robustness trade-off given a prediction of the optimal facility location. They also evaluated the performance of their mechanisms as a function of the prediction error. More recently, Christodoulou et al. [2024] provided performance bounds based on an alternative measure of prediction error. Barak et al. [2024] studied this problem assuming that the predictions are regarding each agent's location, but a small fraction of these predictions may be arbitrarily inaccurate. Meanwhile, Chen et al. [2024] evaluated non-truthful mechanisms with respect to their price of anarchy. Istrate and Bonchis [2022] and Fang et al. [2024] studied the obnoxious facility location version of this problem, aiming to design truthful mechanisms. Apart from the facility location problem, other works in learning-augmented mechanism design have been conducted in various contexts, including strategic scheduling [Xu and Lu, 2022, Balkanski et al., 2023a] , auctions [Xu and Lu, 2022 , Balkanski et al., 2023b ,a, Lu et al., 2023 , Caragiannis and Kalantzis, 2024 , Gkatzelis et al., 2024] , bicriteria mechanism design [Balcan et al., 2024] , graph problems with private input [Colini-Baldeschi et al., 2024] , and equilibrium analysis [Gkatzelis et al., 2022 , Istrate et al., 2024] . Balkanski et al. [2023b] brought together the line of work on learning-augmented mechanism design with the literature on online algorithms with predictions by studying online mechanism design with predictions. 
preliminaries: 
 In the single facility location problem, there are n strategic agents with a location profile denoted by x = ⟨x 1 , • • • , x n ⟩, where x i corresponds to the location of agent i. A mechanism f (x) outputs a, potentially randomized, location for the facility. The cost incurred by agent i is the expected Euclidean distance E[d(x i , f (x))] between the facility location f (x) and their location x i .Two renowned cost functions considered in this scenario are Egalitarian Social Cost and Utilitarian Social Cost. In this work, the goal is to optimize the Egalitarian Social CostC(f, x) = E[max xi∈x d(x i , f (x))],representing the expected maximum cost experienced by a single agent for each possible outcome of f (x). The optimal location for the facility in the two-dimensional Euclidean space corresponds to the center of the smallest circle that encloses all the points, denoted by o(x).To minimize the social cost, a mechanism needs to ask the agents to report their preferred locations, x ∈ R 2n , and then use this information to determine the facility location f (x) ∈ R 2 . However, the preferred location x i of each agent i is private information, and they can choose to misreport their preferred location if that can reduce their own cost. A mechanism f : R 2n → R 2 is considered truthful when no individual agent can benefit by misreporting their location, i.e., for all instances x ∈ R 2n , every agent i ∈ [n], and every deviationx ′ i ∈ R 2 , we have that d(x i , f (x)) ≤ d(x i , f (x -i , x ′ i )), where x -i = ⟨x 1 , • • • , x i-1 , x i+1 , • • • , x n ⟩is the vector of the locations of all agents except agent i.In the context of randomized mechanisms, we can distinguish between two forms of truthfulness: universally truthful and truthful in expectation. A universally truthful mechanism involves a randomization over deterministic truthful mechanisms, with weights that may depend on the input. On the other hand, a mechanism is considered truthful in expectation if truth-telling yields the agent the maximum expected value. Specifically, a mechanism f : R 2n → R 2 is truthful in expectation if for all instances x ∈ R 2n , every agent i ∈ [n], and every deviationx ′ i ∈ R 2 , we have that E[d(x i , f (x))] ≤ E[d(x i , f (x -i , x ′ i ))]. We focus on mechanisms that are both unanimous and anonymous. A mechanism is unanimous if, when all points x are located at the same position (x i = x j for all i, j ∈ [n]), it places the facility at that specific location, i.e., f (x) = x i . To ensure bounded robustness, a mechanism must be unanimous, as the optimal cost is zero when the facility is at the same location as all points, whereas placing it elsewhere incurs a positive cost. A mechanism is anonymous if its outcome is independent of the agents' identities, meaning it remains unchanged under any permutation of the agents. Finally, we also assume the mechanism is scale-independent, i.e., if we multiply every coordinate of every agent by the same factor, the coordinate of the chosen facility location are scaled in the same way; this captures the fact that it is only the relative distances that really matter in this problem.Learning-augmented algorithms encompass a class of algorithms that enhance their decision-making process by integrating pre-computed predictions or forecasts. These predictions, obtained from various sources, like statistical models, serve as inputs without requiring real-time learning from new data. For instance, in the single facility location problem, one might consider predictions x regarding all of the agent's preferred locations, a prediction F * regarding the optimal facility location, or a prediction regarding the identities of the most extreme agents ê (the ones that suffer the maximum cost in the optimal solution), which, as demonstrated in this paper, proves to be quite useful. We denote mechanisms enhanced with predictions in general as f (x, * ). Specifically, for each prediction setting like x or F * , we denote a mechanism enhanced with x and F * by f (x, x) and f (x, F * ), respectively. We define mechanisms enhanced with other kinds of predictions in a similar way.The effectiveness of learning-augmented mechanisms is evaluated using their consistency and robustness. If x ◁ * denotes all instances x for which prediction * is accurate, a mechanism is • α-consistent if it achieves an α-approximation when the prediction is correct, i.e., maxx, * :x◁ * C(f (x, * ), x) C(o(x), x) ≤ α.• β-robust if it maintains a β-approximation regardless of the quality of the prediction, i.e., maxx, * C(f (x, * ), x) C(o(x), x) ≤ β.3 Results for the LineIn this section, we provide a lower bound regarding the performance of any randomized mechanism for the line, even if it is equipped with the strongest type of prediction, i.e., a prediction x regarding the preferred location of every agent. Theorem 1. No mechanism for the line that is truthful in expectation and guarantees 1+δ consistency for some δ ∈ [0, 0.5] can also guarantee robustness better than 2 -δ, even if it is provided with full predictions x containing each of the agents' locations.The proof consists of two main parts. We first show that, for any instance involving two agents, we can without loss of generality restrict our attention to a class of mechanisms that we call ONLYM mechanisms. We then show the desired lower bound for ONLYM mechanisms.We introduce the following notations specific to this section. Let x L be the leftmost reported location and x R be the rightmost reported location on the line. Therefore, we have x L ≤ x R . Let M denote the midpoint of these two extreme points, i.e., M = (x L + x R )/2, which would also correspond to the optimal facility location. For simplicity, we sometimes write f (x 1 , . . . , x n ), dropping the angle brackets ⟨⟩. ONLYM is the class of mechanisms that, whenever they choose a location within the interval (x L , x R ), then this location is always M . Definition 1 (ONLYM mechanisms). A mechanism f for the line is an ONLYM mechanism ifP [f (x) ∈ (x L , x R ) \ {M }] = 0.The main lemma for the proof of Theorem 1 is the following reduction that allows to restrict our attention to ONLYM mechanisms. The complete proof of Lemma 1 can be found in Appendix A. Lemma 1. For any problem instance involving two agents with reported locations x = ⟨x L , x R ⟩ on the line, and any randomized truthful in expectation mechanism achieving α-consistency and β-robustness over this class of instances, there exists a randomized ONLYM mechanism that is truthful in expectation and achieves the same consistency and robustness guarantees.Proof Sketch. Consider a randomized mechanism f (x L , x R ) with probabilities p ℓ = P[f (x L , x R ) ∈ (x L , M )] and p r = P[f (x L , x R ) ∈ (M, x R )],representing the chances of selecting a location in (x L , M ) and (M, x R ), respectively. If p ℓ = p r = 0, the mechanism already satisfies the desired property. Otherwise, for p ℓ > 0 and p r > 0, define the expected locationsπ ℓ = E[f (x L , x R ) | f (x L , x R ) ∈ (x L , M )] and π r = E[f (x L , x R ) | f (x L , x R ) ∈ (M, x R )],which can be expressed as convex combinations π ℓ = q ℓ x L + (1 -q ℓ )M and π r = q r x R + (1 -q r )M for some q ℓ , q r ∈ (0, 1).We then construct a new mechanism f ′ that modifies f by reassigning probability masses to x L , M , and x R as follows:P[f ′ (x L , x R ) = x] =              P[f (x L , x R ) = x] if x < x L or x > x R , 0 if x ∈ (x L , M ) ∪ (M, x R ), P[f (x L , x R ) = x] + q ℓ p ℓ if x = x L , P[f (x L , x R ) = x] + (1 -q ℓ )p ℓ + (1 -q r )p r if x = M, P[f (x L , x R ) = x] + q r p r if x = x R .To show f ′ retains the consistency and robustness guarantees of f , we show that the expected costs of f and f ′ are identical for instances with two agents (Lemma 2). Finally, we show that f ′ maintains the truthfulness in expectation property by verifying that agent costs are unchanged between f and f ′ (Lemma 3).Equipped with Lemma 1, we can now prove Theorem 1.Proof of Theorem 1. We start by proving the result for two-agent instances on the line using any ONLYM mechanism. Then, using Lemma 1, the result follows for any randomized mechanism.First, note that if the chosen facility location y is at distance d(M, y) from the point M = (x L + x R )/2, then its egalitarian social cost is equal to C(o(x), x) + d(M, y). To verify this fact, assume without loss of generality that this location is on the left of M and note that its distance from the agent located at x R is d(x R , M ) + d(M, y). As a result, the expected social cost of a mechanism f with agent locations x isEQUATIONNow, assume that there exists a mechanism that is (1 + δ)-consistent and better than (2 -δ)-robust.For robustness, this would imply that for every instance x, irrespective of the prediction, the mechanism must guarantee thatEQUATIONFor this mechanism to be truthful in expectation, it must ensure that no agent has an incentive to misreport their location. Consider the instance x = ⟨x L , x R ⟩, and note that the agent at x L has the option to misreport their location asx ′ L = x L -d(x L , x R ), which would shift the new midpoint M ′ to x L in the new instance x ′ = ⟨x ′ L , x R ⟩.This deviation would double the optimal cost, i.e., 2), then guarantees that the expected cost for this agent after the deviation would be at most 2(1 -δ) • C(o(x), x) since we haveC(o(x ′ ), x ′ ) = 2 • C(o(x), x). Inequality (EQUATIONAs a result, to ensure that this agent will not misreport, the mechanism needs to ensure that the expected cost of the agent if they report the truth is strictly less than2(1 -δ) • C(o(x), x). If we let P (≤ L) = P[f (x) ≤ x L ]denote the probability that the chosen location is weakly on the left of x L , and P (M ) = P[f (x) = M ] denote the probability that the chosen location is M , then the expected cost of the agent located atx L is at least C(o(x), x)P (M ) + 2C(o(x), x)(1 -P (M ) -P (≤ L))because the mechanism is an ONLYM mechanism. This is even if we assume that the only chosen facility locations weakly on the left of x L (and weakly on the right of x R , respectively) are exactly on x L (and exactly on x R , respectively). Therefore, the mechanism needs to always satisfyEQUATION)If we consider the same instance x = ⟨x L , x R ⟩, and assume that the mechanism is also provided with accurate predictions xL = x L and xR = x R regarding the agent locations, to guarantee 1 + δ consistency, Inequality (1) implies thatEQUATIONFinally, if we once again consider the same instance with inaccurate predictions xL = x L and xR = x R + d(x L , x R ), we observe that in this case the agent located at x R would have the option to instead reportx ′′ R = x R + d(x L , x R ) = xR, and the predictions would then appear to be accurate, forcing the mechanism to satisfy Inequality (5) in order to maintain the required consistency bound. Since the true location x R would now coincide with the middle point M ′′ of the misreported instanceEQUATIONAs a result, to ensure that this agent will not misreport, the mechanism needs to ensure that the expected cost of the agent if they report the truth is at most 2δ • C(o(x), x). If we once again let P (≤ L) denote the probability that the chosen location is weakly on the left of x L , and P (M ) denote the probability that the chosen location is M , then the expected cost of the agent located at x R is at least C(o(x), x)P (M ) + 2C(o(x), x)P (≤ L). This is even if we once again assume that the only chosen facility locations weakly on the left of x L (and weakly on the right of x R , respectively) are exactly on x L (and exactly on x R , respectively). Therefore, the mechanism needs to always satisfyP (M ) + 2P (≤ L) ≤ 2δ ⇒ P (≤ L) ≤ δ - P (M ) 2 .However, this contradicts Inequality (4), so we conclude that no mechanism can simultaneously guarantee (1 + δ) consistency and a robustness better than (2 -δ). 
the hardness result for the line is tight: 
 We observe that the lower bound regarding the robustness and consistency trade-off shown in Theorem 1 is actually tight. Specifically, it can be achieved by an appropriate randomization between the optimal deterministic learning-augmented mechanism and the optimal non-learning-augmented randomized mechanism. Proposition 1. For any δ ∈ [0, 0.5], there exists a randomized mechanism on the line which, given prediction F * , is truthful in expectation, (1 + δ)-consistent, and (2 -δ)-robust.As a result, the bound of Theorem 1 precisely captures the optimal robustness consistency trade-off over all truthful in expectation mechanisms for instances on the line.To gain a more complete picture of different prediction settings, we study an alternative strong prediction that is not strictly stronger than the predicted optimal facility location F * . Specifically, we consider a setting where predictions are available for all pieces of information except for one of the extreme locations. We show that these predictions are not helpful, even without any robustness constraints, to improve the consistency guarantee alone. Theorem 2. Given a prediction set that provides the identities of all n agents, there exist n -1 agents such that, even if we have their exact locations, there is no deterministic truthful mechanism on the line that is better than 2-consistent, and there is no randomized mechanism on the line that is truthful in expectation and better than 1.5-consistent. 
results for the plane: 
 We now consider instances in the Euclidean plane, with a location profile x = ⟨x 1 , . . . , x n ⟩, where x i ∈ R 2 for each agent i. Missing proofs of this section can be found in Appendix B.Before considering the robustness and consistency guarantees achievable by randomized mechanisms augmented with different types of predictions, we start off by reducing the gap on what is known for mechanisms without predictions.Since the problem of designing good facility location mechanisms in two dimensions is "harder" than the one-dimensional case, it may seem counterintuitive at first, but the lower bound that prior work proved for all one-dimensional instances does not extend to two dimensions. The reason is that the design space for two-dimensional mechanisms is much richer, and the known lower bounds apply only to the more restricted class of one-dimensional mechanisms. For example, consider a simple instance with just two agents in two dimensions. For this two-dimensional instance, the mechanism can return a location for the facility that is not on the line containing the two agents' locations, which it, of course, cannot do in one dimension.Note that, in terms of social cost alone, returning such a location is always Pareto-dominated by returning an appropriate location on the line (e.g., its projection onto the line). However, returning a location that is not on this line also allows the designer to affect the incentives of the participating agents in new and non-trivial ways that are impossible in the one-dimensional case. Specifically, returning points that are not on the line allows us to induce previously impossible cost vectors. For a simple example, in a one-dimensional instance involving two agents at distance 1 from each other, the only facility location that yields the same cost to both agents is the midpoint between them, leading to a cost vector of (0.5, 0.5). However, in two dimensions, we can induce a cost vector of (c, c) for any c ≥ 0.5 by simply returning the appropriate point on the interval's perpendicular bisector.This additional flexibility could potentially provide the designer with novel ways to ensure that the agents do not misreport their locations; for example, the classic technique of "money burning," used to achieve incentive compatibility without monetary payments, heavily depends on the designer's ability to penalize and reward agents based on their reports. Although we conjecture that truthful mechanisms are always better off returning a facility on the line containing the agents' locations in this instance, proving such a result appears non-trivial. Due to this additional flexibility in two dimensions, proving inapproximability results for this broader class of mechanisms is a more challenging problem and seems to require new techniques and insights. Theorem 3. Any randomized mechanism that is truthful in expectation in the Euclidean metric space has an approximation ratio of at least 1.118.Our following two results provide impossibility results for both deterministic and randomized mechanisms augmented with perfect predictions. For deterministic mechanisms, Agrawal et al. [2022] showed that there is a mechanism that, given a prediction about the optimal facility location, is 1-consistent and 1 + √ 2 -robust. Our impossibility result for deterministic mechanisms shows that stronger predictions do not help: even with predictions about the location of each agent, there is no deterministic mechanism that achieves a robustness better than 1 + √ 2 and a consistency that improves over the best approximation achievable without predictions. Theorem 4. For any δ > 0, there is no deterministic truthful mechanism that is (2 -δ)-consistent and 1 + √ 2 -δ -robust, even if it is provided with full predictions x (the location of each agent).The next result shows that there is no hope of achieving the best of both worlds in the randomized setting; to obtain 1 consistency, we would need to sacrifice robustness. Theorem 5. For any δ > 0, there is no randomized mechanism that is truthful in expectation, 1-consistent, and (2 -δ)-robust, even for two-agent instances and even if it is provided with full predictions x (the location of each agent). This is tight, i.e., there exists a randomized mechanism that is truthful in expectation, 1-consistent, and 2-robust for two-agent instances.We now turn to positive results, and provide a learning-augmented randomized mechanism that is provided with a new type of prediction: the prediction does not provide us with any actual location, but instead only provides us with the identities ê = ⟨e 1 , • • • , e k ⟩ of the k agents who would suffer the maximum cost in the optimal solution (we refer to them as "extreme agents"), i.e., {e 1 , . . . , e k } = arg max ei∈[n] d(x ei , o(x)). Note that the smallest circle that encloses all the points is the circumcircle of the locations of the extreme agents. Therefore, the center of this circle is o(x), the optimum solution.We propose a mechanism leveraging predictions derived from IDs of extreme agents. The main idea is to return the centroid of the extreme agents, denoted by G with a probability of half, and each of the extreme points with a probability of 1/2k to prevent misreporting incentives.Tang et al. [2020] run this mechanism over all agents (not only the extreme ones) and achieve a 2 -1/n approximation. We improve the approximation factor (in case of having good predictions) to 2 -1 3 ≈ 1.67 by running this mechanism only on extreme agents. We use their ideas to maintain With probability 1/2k:return each point x e1 , • • • , x e ktruthfulness and we use new techniques to show the approximation guarantees for an arbitrarily number of agents. Moreover, as long as any returned location falls within the minimum enclosing circle of the agents predicted to be extreme (which is the case for Mechanism 1), this ensures an approximation factor of 2 in case of having bad predictions.First, we argue that k ≥ 2, meaning that there are at least two extreme agents on the minimum enclosing circle. Otherwise, one can find a smaller circle containing all the points. As a warm-up, we first consider the k = 2 case and propose a randomized mechanism that is truthful in expectation and achieves 1.5 consistency and 2 robustness for any number of agents. Theorem 6. Assume there are only two extreme agents, i.e., k = 2. Then, given predictions ê = ⟨e 1 , e 2 ⟩ that provides the IDs of the only two extreme agents, there exists a randomized mechanism that is truthful in expectation and achieves 1.5 consistency and 2 robustness for any number of agents.We then show that it is sufficient to only consider the case where we have exactly three extreme agents on the minimum enclosing circle, meaning k = 3. If we have more than three agents located on the minimum enclosing circle, a continuous perturbation of the points makes the probability of having at least four points lying on a circle infinitesimally small [Berg et al., 2008] . For k = 3, we use the properties of the Euler line to prove the 1.67 consistency. Theorem 7. Given a prediction set that provides the IDs of the extreme agents, there exists a randomized mechanism that is truthful in expectation and achieves 1.67 consistency and 2 robustness for any number of agents.Proof. Let us first consider instances with only three extreme agents. Mechanism 1 is truthful since other agents apart from x e1 , x e2 , x e k cannot influence the result and Mechanism 1 is equivalent to the mechanism of Tang et al. [2020] over agents e 1 , . . . , e k and since this mechanism is truthful in expectation, agents e 1 , . . . , e k cannot benefit from misreporting their locations. Since the mechanism returns the reported locations, rather than their predictions, and the centroid is guaranteed to be inside the circumcircle, we can conclude that the mechanism has a robustness factor of 2. The technical aspect of this proof involves establishing the consistency guarantee by considering the Euler line.Euler line. Given three arbitrary points x 1 , . . . , x 3 , their circumcircle is the smallest circle that encloses the three points, their centroid is (x 1 + x 2 + x 3 )/3, and their orthocenter is the point where the three altitudes (the perpendicular line segments from a vertex to the line that contains the opposite side) intersect. In any triangle, the center of the circumcircle (O), the centroid (G), and the orthocenter (H) are collinear, forming the Euler line. One property of the Euler line is that G is positioned midway between O and H. Additionally,d(O, G) = d(G, H)/2, implying d(O, G) = d(O, H)/3.Let R denote the radius of the circumcircle of x e1 , x e2 , x e3 and assume without loss of generality that the optimum cost is R = 1. For any j ∈ [n], we haved(x j , G) ≤ d(x j , O) + d(O, G) ≤ R + d(O, G)where the first inequality is by triangle inequality and the second is because all the points are within the circumcircle of the locations of the extreme agents when the predictions are correct. G, H ).1 2k 1 R k i=1 max j∈[n] d(x ei , x j ) + 1 2 1 R max j∈[n] d(x j , G) ≤ 1 + 1 2 R + d(O, G) R ≤ 1 + 1 2 1 + 1 3 ≈ 1.67.where the first inequality is since d(x ei , x j ) ≤ d(x ei , O) + d(O, x j ) ≤ 2R when the predictions are correct. Next, we show how we can modify the mechanism to achieve the same approximation guarantees as having three extreme agents while maintaining truthfulness.As mentioned previously, the key concept involves perturbing the instance before requesting predictions to have at most three extreme agents. Given any instance x = ⟨x 1 , • • • , x n ⟩, define a perturbed instance x = ⟨x 1 , • • • , xn ⟩, which is the result of a continuous perturbation of x. Consider the set of predictions for the IDs of extreme agents in x. Although the extreme agents of the perturbed instance x might differ from those of the original instance x, their costs remain very close to the maximum cost in case of having good predictions. Therefore, the circumcircle of them is a good representation of the minimum enclosing circle and results in the same approximation guarantees.Since we run the mechanism on the main instance x, truthfulness holds as before. Note that since we ask for the ID of extreme agents of the perturbed instance x, we have consistency guarantees if predictions are accurate based on the perturbed instance x, and in any case we can ensure the robustness factor of 2. 
future directions: 
 The = P[f (x L , x R ) ∈ (x L , M )] and p r = P[f (x L , x R ) ∈ (M, x R )], π ℓ = E[f (x L , x R ) | f (x L , x R ) ∈ (x L , M )] and π r = E[f (x L , x R ) | f (x L , x R ) ∈ (M, x R )],and q ℓ and q r are such that π ℓ = q ℓ x L + (1 -q ℓ )M and π r = q r x R + (1 -q r )M .A Missing Proof of Section 3Lemma 1. For any problem instance involving two agents with reported locations x = ⟨x L , x R ⟩ on the line, and any randomized truthful in expectation mechanism achieving α-consistency and β-robustness over this class of instances, there exists a randomized ONLYM mechanism that is truthful in expectation and achieves the same consistency and robustness guarantees.Proof. Consider any randomized mechanism f (x L , x R ) and letp ℓ = P[f (x L , x R ) ∈ (x L , M )] and p r = P[f (x L , x R ) ∈ (M, x R )]represent the probabilities that this mechanism chooses a facility location in (x L , M ) and (M, x R ), respectively. If p ℓ = p r = 0, the mechanism already satisfies the desired property, and the proof is complete. Otherwise, if p ℓ > 0, defineπ ℓ = E[f (x L , x R ) | f (x L , x R ) ∈ (x L , M )] and, if p r > 0, define π r = E[f (x L , x R ) | f (x L , x R ) ∈ (M, x R )]as the expected locations returned by the mechanism when restricted to (x L , M ) and (M, x R ), respectively.Since π ℓ lies in (x L , M ) and π r lies in (M, x R ), we can express these two points as convex combinations of x L , M , and x R : π ℓ = q ℓ x L + (1 -q ℓ )M and π r = q r x R + (1 -q r )M for some q ℓ , q r ∈ (0, 1). We then modify the original mechanism f to a new ONLYM mechanism f ′ defined asP[f ′ (x L , x R ) = x] =              P[f (x L , x R ) = x] if x < x L or x > x R 0 if x ∈ (x L , M ) ∪ (M, x R ) P[f (x L , x R ) = x] + q ℓ p ℓ if x = x L P[f (x L , x R ) = x] + (1 -q ℓ )p ℓ + (1 -q r )p r if x = M P[f (x L , x R ) = x] + q r p r if x = x RThe construction of f ′ is illustrated in Figure 2 . To show that mechanism f ′ achieves the same consistency and robustness guarantees as mechanism f , we show that their expected costs are equal on all instances with two agents.Lemma 2. For all mechanisms f for the line and instances x = ⟨x L , x R ⟩ with two agents, the expected costs of f and f ′ over x are equal, i.e., C(f, x) = C(f ′ , x).Proof. First, note thatE max xi∈{x L ,x R } d(x i , f (x)) | f (x) ∈ (x L , M ) • P[f (x) ∈ (x L , M )] = E [d(x R , f (x)) | f (x) ∈ (x L , M )] • p ℓ = d(x R , π ℓ ) • p ℓ .Similarly, we haveE max xi∈{x} d(x i , f (x)) | f (x) ∈ (M, x R ) • P[f (x) ∈ (M, x R )] = d(π r , x L ) • p r , which implies that C(f ′ , x) -C(f, x) = E max xi∈{x L ,x R } d(x i , f ′ (x)) -E max xi∈{x L ,x R } d(x i , f (x)) = d(x R , x L ) • (P[f ′ (x) ∈ {x L , x R }] -P[f (x) ∈ {x L , x R }]) + d(x R , M ) • (P[f ′ (x) = M ] -P[f (x) = M ]) -d(x R , π ℓ ) • p ℓ -d(x L , π r ) • p r = d(x R , x L ) • (q ℓ p ℓ + q r p r ) + d(x R , M ) • ((1 -q ℓ )p ℓ + (1 -q r )p r ) -d(x R , π ℓ ) • p ℓ -d(x L , π r ) • p r = d(x R , x L ) • (q ℓ p ℓ + q r p r ) + d(x R , M ) • ((1 -q ℓ )p ℓ + (1 -q r )p r ) -d(x R , x L ) • q ℓ p ℓ -d(x R , M ) • (1 -q ℓ )p ℓ -d(x L , x R ) • q r p r -d(x L , M ) • (1 -q r )p r = 0.Next, to show that mechanism f ′ is also truthful in expectation, we first show that the costs of the agents do not change between f and f ′ .Lemma 3. For all mechanisms f for the line and instances x = ⟨x L , x R ⟩ with two agents, the cost of the agent at location x L is identical under both f and f′ , i.e., E [d(x L , f (x))] = E [d(x L , f ′ (x))] . Similarly, we have E [d(x R , f (x))] = E [d(x R , f ′ (x))] .Proof. By definition of f ′ , we haveE [d(x L , f (x))] -E [d(x L , f ′ (x))] = d (x L , E [f (x) | f (x) ∈ (x L , M )] = π ℓ ) • P [f (x) ∈ (x L , M )] + d (x L , E [f (x) | f (x) ∈ (M, x R )] = π r ) • P [f (x) ∈ (M, x R )] + d (x L , M ) • (P [f (x) = M ] -P [f ′ (x) = M ]) + d (x L , x R ) • (P [f (x) = x R ] -P [f ′ (x) = x R ]) = d(x L , q ℓ x L + (1 -q ℓ )M ) • p ℓ + d(x L , q r x R + (1 -q r )M ) • p r -d(x L , M )((1 -q ℓ )p ℓ + (1 -q r )p r ) -d(x L , x R )(q r p r ) = d(x L , M )(1 -q ℓ )p ℓ + d(x L , x R )q r p r + d(x L , M )(1 -q r )p r -d(x L , M )(1 -q ℓ )p ℓ -d(x L , M )(1 -q r )p r -d(x L , x R )q r p r = 0.Next, we use the previous lemma to show that mechanism f ′ preserves the truthful in expectation guarantee of f . Lemma 4. If a mechanism f for the line is truthful in expectation over instances with two agents, then f ′ is also truthful in expectation over instances with two agents.Proof. Assume that f is truthful in expectation over instances with two agents. Assume that one of the agents deviates and reports a false location in mechanism f ′ . Due to symmetry, and without loss of generality, assume that the agent located at x L deviates and reports a false location x ′ L . We need to showEQUATIONCombining these two inequalities with Lemma 3, it suffices to showE [d(x L , f ′ (x ′ L , x R ))] ≥ E [d(x L , f (x ′ L , x R ))] .To prove the above inequality, we consider two main cases. First, we focus on the scenario where the agent located at x L deviates to the right, i.e.,x L < x ′ L . Let M ′ = x ′ L +x R 2 . Assume x ′ L ≤ x R , define p ′ ℓ = P[f (x ′ L , x R ) ∈ (x ′ L , M ′ )] and p ′ r = P[f (x ′ L , x R ) ∈ (M ′ , x R )]. If p ′ ℓ = p ′ r = 0, then f ′ (x ′ L , x R ) = f (x ′ L , x R ), and hence E [d(x L , f ′ (x ′ L , x R ))] = E [d(x L , f (x ′ L , x R ))].Therefore, the proof is complete in this case.Next, consider the distribution where the mechanism f (x ′ L , x R ) returns a random facility location within the intervals(x ′ L , M ′ ) if p ′ ℓ > 0, or within (M ′ , x R ) if p ′ r > 0.The expected locations within these intervals are π ′ ℓ ∈ (x ′ L , M ′ ) and π ′ r ∈ (M ′ , x R ), which can be expressed asπ ′ ℓ = q ′ ℓ x ′ L + (1 -q ′ ℓ )M ′ and π ′ r = q ′ r x R + (1 -q ′ r )M ′, where q ′ ℓ and q ′ r are the respective convex coefficients.In the first case, where x L < x ′ L , we show that the cost to the left agent is the same across the two mechanisms. The key idea is that the difference between the two mechanisms, in terms of their returned locations, lies within the intervals (x ′ L , M ′ ) and (M ′ , x R ), both on the right side of x L . Thus, the agent's cost is fully determined by the expected locations in these intervals. Specifically we haveE [d(x L , f (x ′ L , x R ))] -E [d(x L , f ′ (x ′ L , x R ))] = d (x L , E [f (x ′ L , x R ) | f (x ′ L , x R ) ∈ (x ′ L , M ′ )] = π ′ ℓ ) • P [f (x ′ L , x R ) ∈ (x ′ L , M ′ )] + d (x L , E [f (x ′ L , x R ) | f (x ′ L , x R ) ∈ (M ′ , x R )] = π ′ r ) • P [f (x ′ L , x R ) ∈ (M ′ , x R )] + d (x L , x ′ L ) • (P [f (x ′ L , x R ) = x ′ L ] -P [f ′ (x ′ L , x R ) = x ′ L ]) + d (x L , M ′ ) • (P [f (x ′ L , x R ) = M ′ ] -P [f ′ (x ′ L , x R ) = M ′ ]) + d (x L , x R ) • (P [f (x ′ L , x R ) = x R ] -P [f ′ (x ′ L , x R ) = x R ]) = d(x L , q ′ ℓ x ′ L + (1 -q ′ ℓ )M ′ ) • p ′ ℓ + d(x L , q ′ r x R + (1 -q ′ r )M ′ ) • p ′ r -d(x L , x ′ L )q ′ ℓ p ′ ℓ -d(x L , M ′ )((1 -q ′ ℓ )p ′ ℓ + (1 -q ′ r )p ′ r ) -d(x L , x R )q ′ r p ′ r = d(x L , x ′ L )q ′ ℓ p ′ ℓ + d(x L , M ′ )(1 -q ′ ℓ )p ′ ℓ + d(x L , x R )q ′ r p ′ r + d(x L , M ′ )(1 -q ′ r )p ′ r -d(x L , x ′ L )q ′ ℓ p ′ ℓ -d(x L , M ′ )((1 -q ′ ℓ )p ′ ℓ + (1 -q ′ r )p ′ r ) -d(x L , x R )q ′ r p ′ r = 0.Note that in the case of x R < x ′ L , the same arguments hold with a minor change in notation. Definep ′ ℓ = P[f (x ′ L , x R ) ∈ (M ′ , x ′ L )] and p ′ r = P[f (x ′ L , x R ) ∈ (x R , M ′ )].Consider the expected locations π ′ ℓ and π ′ r within the intervals (M ′ , x ′ L ) and (x R , M ′ ), respectively. Focusing our attention on the more interesting case where x ′ L < x L , we aim to show thatE [d(x L , f ′ (x ′ L , x R ))] ≥ E [d(x L , f (x ′ L , x R ))]. If we focus on the interval (x ′ L , M ′ ) and assume x L ≤ M ′ , the expected location of the facility returned by the two mechanisms, f (x ′ L , x R ) and f ′ (x ′ L , x R ), conditioned on the facility being in the interval (x ′ L , M ′ ), is the same; this is true by construction (our reduction maintains the expected location π ′ ℓ between the reported location and the midpoint). The crucial difference between the two mechanisms is that although f (x ′ L , x R ) may return any facility location in the (x ′ L , M ′ ) interval, the mechanism f ′ (x ′ L , x R ) returns the same expected location using only x ′ L and M ′ in its support. We show that the cost to an agent located at any point x L in the(x ′ L , M ′ ) interval is weakly higher in f ′ (x ′ L , x R ) than it is in f (x ′ L , x R ), thus maintaining the truthfulness guarantee. Intuitively, this is true because the two mechanisms return the same expected location π ′ ℓ in that interval, but f ′ (x ′ L , x R ) only returns the extreme points of the interval, which hurt the agent at x L the most.More formally, we replace any probability assigned to a point in (x ′ L , M ′ ) with a convex combination between x ′ L and M ′ , and each time we do this, we weakly increase the cost to an agent who is located at any point in (x ′ L , M ′ ). Specifically, for any outcome y ∈(x ′ L , M ′ ) of the mechanism f (x ′ L , x R ) and any x L ∈ (x ′ L , M ′ ), if we have y = w • x ′ L + (1 -w) • M ′ then d(x L , y) < w • d(x L , x ′ L ) + (1 -w) • d(x L , M ′ ). Since π ′ ℓ = q ′ ℓ x ′ L + (1 -q ′ ℓ )M ′, at the end of this process, we will end up with q ′ ℓ p ′ ℓ probability increase on x ′ L , and (1 -q ′ ℓ )p ′ ℓ probability increase on M ′ . Therefore, we haveE [d(x L , f (x ′ L , x R ))] < d(x L , x ′ L )q ′ ℓ p ′ ℓ + d(x L , M ′ ) ((1 -q ′ ℓ )p ′ ℓ + (1 -q ′ r )p ′ r ) + d(x L , x R )q ′ r p ′ r = E [d(x L , f ′ (x ′ L , x R ))] .In the case where x L > M ′ , similar arguments apply in the interval (M ′ , x R ).The proof of Lemma 1 then immediately follows from Lemma 2 and Lemma 4.Proposition 1. For any δ ∈ [0, 0.5], there exists a randomized mechanism on the line which, given prediction F * , is truthful in expectation, (1 + δ)-consistent, and (2 -δ)-robust.Proof. We show that the bound of the robustness consistency trade-off in Theorem 1 is tight. To verify the tightness for δ = 0.5, note that it is possible to achieve a robustness of 1.5 (and therefore also a consistency of 1.5) using the following randomized truthful in expectation mechanism of Procaccia and Tennenholtz [2013]:Mechanism 1 (LRM). Given input x, return x L with probability 1/4, x R with probability 1/4, and M with probability 1/2.On the other extreme, to verify the tightness of the theorem for δ = 0, note that it is possible to achieve a robustness of 2 with a consistency of 1 using the following truthful deterministic learning-augmented mechanism of Agrawal et al. [2022] :Mechanism 2 (MinMaxP). Given x, and a prediction F * regarding the optimal facility location, returnF * if F * ∈ [x L , x R ], otherwise return x L if F * < x L , and return x R if F * > x R .In fact, for any δ ∈ [0, 0.5], we can achieve a robustness of 2 -δ and a consistency of 1 + δ by randomly choosing which one of these two mechanisms to run. Specifically, we can achieve these bounds by running the LRM mechanism with probability 2δ and the MinMaxP mechanism with probability 1-2δ. Note that since the decision regarding which one of the two truthful mechanisms to run is independent of the agents' reports, the resulting randomized mechanism is truthful as well.Theorem 2. Given a prediction set that provides the identities of all n agents, there exist n -1 agents such that, even if we have their exact locations, there is no deterministic truthful mechanism on the line that is better than 2-consistent, and there is no randomized mechanism on the line that is truthful in expectation and better than 1.5-consistent.Proof. We first address the deterministic case with two agents whose locations are given by x = ⟨x L , x R ⟩. Assume we have a prediction xL , which predicts the location of the leftmost agent. We will show that even if xL is accurate, there is no truthful mechanism with a consistency better than 2.We use the same argument as in Theorem 3.2 of Procaccia and Tennenholtz [2013] . Assume, for contradiction, that f : R 2 → R is a truthful mechanism with a consistency less than 2. Consider the location profile x = ⟨x L = 0, x R = 1⟩ and the prediction xL = 0. To achieve consistency better than 2, the mechanism needs to choose a facility location y = f (x) such that y ∈ (0, 1).Now consider an alternative location profile x ′ = ⟨x ′ L = 0, x ′ R = y⟩ with the prediction xL = 0. The optimal facility location for this profile is at y/2, yielding a maximum cost of y/2. To maintain consistency better than 2, the mechanism should place the facility within the interval (0, y). However, if this were to occur, the rightmost agent would have an incentive to report a location of 1 instead of y, as this lie would place the facility exactly at y, rather than within (0, y). This contradicts the truthfulness of the mechanism. This argument extends to cases with arbitrary n by situating all other agents at 0 in both profiles x and x ′ , with accurate predictions for them at 0. Similar reasoning holds true.For the randomized setting, we use the idea from the proof of Theorem 3.4 in Procaccia and Tennenholtz [2013] . We first focus on the case with two agents and then extend the result to any x = ⟨x 1 = (0, 0), x 2 = • • • = x n-1 = (1/2, 0), x n = (1, 0)⟩, and x ′ = ⟨x ′ 1 = (0, 0), x ′ 2 = • • • = x ′ n-1 = (1/2, 0), x ′ n = (2, 0)⟩ in the proof of Theorem 2. It is assumed that d(x n , f (x)) ≥ 1/2 and x ⋆ ∈ arg min y:d(xn,y)≥1/2 C(y, x).number of agents. Let f be a randomized truthful in expectation mechanism. Consider the location profile x = ⟨x L = 0, x R = 1⟩. We have f (x) = P, where P is a probability distribution over R.There exists x i ∈ x such that E[d(x i , P)] ≥ 1/2. If this agent's location prediction is unavailable, we can prove that consistency better than 1.5 cannot be achieved.Assume E[d(x R , P)] ≥ 1/2 and that we have an accurate prediction xL = 0 for the leftmost agent x L . Consider the profilex ′ = ⟨x ′ L = 0, x ′ R = 2⟩, with an accurate prediction xL = 0. For truthfulness, the expected distance from the location 1 should still be 1/2, otherwise the rightmost agent would lie in profile x. We know that if E[d(M, P)] = ∆, then the expected maximum cost is ∆ + 1. With ∆ ≥ 1/2, the expected cost is at least 1.5, whereas the optimal cost is 1, resulting in a consistency of at least 1.5.This argument extends to arbitrary n by situating all other agents at 1/2 in both profiles x and x ′ , with accurate predictions for them at 1/2. Similar reasoning holds true.Theorem 3. Any randomized mechanism that is truthful in expectation in the Euclidean metric space has an approximation ratio of at least 1.118.Proof. Let f (x) = P be a randomized truthful in expectation mechanism, where P is a probability distribution over R 2 . Consider the location profile x = ⟨x 1 = (0, 0),x 2 = • • • = x n-1 = (1/2, 0), x n = (1, 0)⟩. There exists an x i (either x 1 or x n ) such that d(x i , f (x)) = E y∼P d(x i , y) ≥ 1/2. Without loss of generality, assume that d(x n , f (x)) ≥ 1/2. Now consider the location profile x ′ = ⟨x ′ 1 = (0, 0), x ′ 2 = • • • = x ′ n-1 = (1/2, 0), x ′ n = (2, 0)⟩.To maintain truthfulness, we must have d(x n = (1, 0), f (x ′ )) ≥ 1/2, preventing the agent at location x n = (1, 0) in the profile x from having an incentive to lie about being at location x ′ n = (2, 0). Extending the result of Theorem 3.4 in Procaccia and Tennenholtz [2013] from the line to the Euclidean metric, if we have d(o(x), f (x)) ≥ ∆, then the expected maximum cost is at least∆ 2 + C(o(x), x) 2 .Therefore, the expected cost of x ′ is at least 1 4 + 2 2 2 , resulting in a √ 1.25 ≈ 1.118 approximation, as the optimum cost isd(x ′ 1 ,x ′ n ) 2 = 1.Theorem 4. For any δ > 0, there is no deterministic truthful mechanism that is (2 -δ)-consistent and 1 + √ 2 -δ -robust, even if it is provided with full predictions x (the location of each agent).Proof. Using the characterization provided by Peters et al. [1993] , we know that any deterministic, strategyproof, anonymous, and unanimous mechanism can be expressed as a Generalized Coordinatewise Median (GCM) mechanism with n -1 constant points in P . The GCM mechanism takes as input the reported locations x of the n agents and a multiset P of fixed points (known as phantom points), which are constant and independent of the agents' reported locations. It then outputs the coordinatewise median of the combined set x ∪ P .Consider a five-agent instance with x containing four agents at (0, 20) and one agent at (0, 10). Our proof first shows that to achieve a consistency better than 2, this mechanism needs to introduce four constant points all with y-coordinates greater than 10. Otherwise, even if the predictions are correct, the y-coordinate of GCM(x, P ) will be at most 10, leading to consistency greater than or equal to 2, since the optimal point would be (0, 15).Then, we show that if all these four constant points have y-coordinates greater than 10, the robustness of the GCM mechanism is at least 1 + √ 2. Let x be the median of the x-coordinates of the four constant points, and now consider the following instance, where the optimal cost is 1.Consider a five-agent instance with x containing three agents at (x, 0), one agent at (x -1, 1), andone agent at x -1 -1 √ 2 , -1 √ 2 .Since x is the median of the x-coordinates of both true agent locations x and constant points P , x will be the x-coordinate of the GCM(x, P ). Since all the constant points have y-coordinates greater than 10, the y-coordinate of the GCM(x, P ) will be 1.Since (x, 1) has a distance of 1 + √ 2 from x -1 -1 √ 2 , -1 √ 2while (x -1, 0), the optimal point, has a distance of 1 from all the points, we can conclude that the robustness factor is at least 1 + √ 2.Theorem 5. For any δ > 0, there is no randomized mechanism that is truthful in expectation, 1-consistent, and (2 -δ)-robust, even for two-agent instances and even if it is provided with full predictions x (the location of each agent). This is tight, i.e., there exists a randomized mechanism that is truthful in expectation, 1-consistent, and 2-robust for two-agent instances.Proof. Consider the instance x = ⟨x L = 0, x R = 2⟩, and assume we have predictions x = ⟨x L = 0, xR = 2⟩. To achieve 1-consistency, a mechanism should return M = 1 with probability 1. Now consider another instance x ′ = ⟨x ′ L = 0, x ′ R = 1⟩ with incorrect predictions x = ⟨x L = 0, xR = 2⟩. To ensure that the rightmost agent will not misreport to x R = 2 and have a cost of zero, the mechanism needs to ensure that the expected cost of the agent if they report the truth is at most zero, which means returning x ′ R with probability 1. This results in a robustness factor of 2. Agrawal et al. [2022] proposed a deterministic Minimum Bounding Box mechanism that is 1consistent and 1 + √ 2-robust. We argue that this mechanism is 1-consistent and 2-robust for two-agent instances.Mechanism 3 (Minimum Bounding Box). Given n points x = ⟨(x 1 , y 1 ), • • • , (x n , y n )⟩, and a predictionF * = (x F , y F ), return (M inM axP (⟨x 1 , • • • , x n ⟩, x F ), M inM axP (⟨y 1 , • • • , y n ⟩, y F )).Observation 1. Mechanism 3 is 1-consistent and 2-robust for instances with only two agents.Proof. One of the two diagonals of the minimum bounding box has two agents on its vertices. Therefore, any point inside or on this box has the approximation factor of 2.Therefore, the upper and lower bounds match for instances with two agents, but it remains unclear where the exact value is even for three agents. Theorem 6. Assume there are only two extreme agents, i.e., k = 2. Then, given predictions ê = ⟨e 1 , e 2 ⟩ that provides the IDs of the only two extreme agents, there exists a randomized mechanism that is truthful in expectation and achieves 1.5 consistency and 2 robustness for any number of agents.Proof. If we only have two agents x e1 and x e2 located on the minimum enclosing circle, x e1 x e2 represent a diameter of this circle; otherwise, we can find a smaller circle containing all the points. Therefore, the middle point of these two locations, (x e1 + x e2 )/2, is the optimum location of the facility. Mechanism 1 runs LRM mechanism on the diameter of the minimum enclosing circle, meaning that it returns the optimum location with a probability of 1/2 and each of the reported locations of the extreme agents with a probability of 1/4, resulting in a 1.5 consistency.In terms of truthfulness, since no other agent besides x e1 and x e2 impacts the mechanism, it suffices to show that they do not have an incentive to lie. Agents x e1 and x e2 lack such incentive for reasons similar to those in LRM Mechanism. Additionally, as any returned location falls within the minimum enclosing circle, it ensures a robustness factor of 2.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [NA] Justification: The contributions of our paper are mainly theoretical. Guidelines:• The answer NA means that paper does not include experiments requiring code. Justification: Although the contributions of our paper are mainly theoretical, we explain in the introduction section how they can positively impact society. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The contributions of our paper are mainly theoretical and pose no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: We utilize models of learning-augmented algorithms and learning-augmented mechanisms, and our related work discussion appropriately cites all prior work and its contributions.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 13. New Assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [NA] Justification: The contributions of our paper are mainly theoretical and we did not introduce a new assets. Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.38th Conference on Neural Information Processing Systems (NeurIPS 2024).A truthful randomized mechanism guarantees truthfulness in expectation. See Sectionfor more details. 
 
 Appendix:  


Decision: The paper studies strategic facility location in 1 and 2 dimensions with expert advice. Specifically, it considers achieving a consistent and robust (randomized) mechanism, focusing on the Egalitarian cost.

The main **contributions** are:
1. They are characterizing the Pareto frontier for the line. The authors show that two previous papers provide Pareto optimal solutions. Flipping coins between them can characterize a Pareto frontier (Proposition 1 + Theorem 1).
2.	They provide negative (impossibilities) and positive (Mechanism 1) results for the plane. 

The main **strengths** I see in this paper are:
1. Strong technical results on 1d, answering questions from previous papers, and initial results for 2d.
2.	Relating to a vibrant line of work on mechanisms with expert advice.

**The first weakness** (and the less important one) is the narrow impact of publishing this paper on the community. The paper belongs to the intersection of the “algorithms with expert advice” and the “strategic facility location,” which is relatively small. I consider this as a weakness since the techniques the authors use (seem to) apply to this intersection only. 

The second and **main weakness** I see in this paper, which also surfaced in the reviews, is the quality of the technical writing. The paper includes typos and cumbersome writing in mathematical statements, which are usually a red flag. Beyond that, some proofs are hard-to-impossible to follow (e.g., Lemma 1).

The first weakness cannot be overcome. As for the second weakness, the authors have done an excellent rebuttal addressing reviewers’ comments about this concern. They have rephrased statements, facilitated proofs, and attached figures to ease readability. 

I want to note that in private communication with the other reviewers, they expressed their lack of confidence about the extent of this paper’s contribution. Furthermore, no reviewer wanted to champion it.

After carefully reading the paper, the reviews, and the rebuttal, I see this paper as borderline, yet **I tend to accept it**. However, I understand it is a borderline paper and might be rejected due to the low acceptance rate.

Reviews: review: paper_summary: paper_summary: The authors study the problem of designing incentive-compatible mechanisms for the facility location game, in particular a learning-augmented variant of ABGOT22 where an oracle returns (potentially inaccurate) predictions about optimal solutions. The paper focuses on considering when predictions are available for the preferences of individual participants/which participants are extremal.

In the 1d setting, the authors show that randomizing between known algorithms is already optimal---allowing predictions about individual preferences cannot result in a mechanism that dominates prior algorithms which depend at most only on optimal facility predictions. In the 2d setting, the authors show that a slight improvement over state-of-art is possible by only assuming prediction access to identification of extremal agents; the authors also provide a few factoids e.g. minor improvement in approximation ratio lower bound for the general (non learning-augmented) setting.
strength_weakness: strength_weakness: I only have minor notes on polishing the writing. Theorem 5 can make more explicit that an assumption is being made on the number of extreme agents---it was a bit confusing when initially skimming the paper. It would also be helpful to clarify if Lemma 1 is novel; from my reading it's just an consequence of the linearity of in-expectation honesty and seems to be implied by PT13---if this is correct, it would be helpful to note in the text. Also, L372-L377 were a bit difficult to understand without drawing it out graphically by hand; perhaps a diagram would help readability.
questions: questions: See weaknesses section.
limitations: limitations: Yes the authors have addressed any negative societal impacts.
paper_summary: paper_summary: The paper revisits the strategic facility location problem, focusing on the role of randomization in designing truthful mechanisms enhanced by machine-learned predictions. The authors build on a recent framework that refines worst-case results by incorporating potentially incorrect predictions about agents' true locations. They aim to achieve both strong consistency, which provides optimal guarantees when predictions are accurate, and near-optimal robustness, ensuring acceptable performance even with inaccurate predictions. The paper specifically investigates the power and limitations of randomization within this context, analyzing the best achievable approximation guarantees concerning the egalitarian (max) social cost measure on one- and two-dimensional Euclidean spaces.


For the single-dimensional version, the paper shows that even with the strongest possible prediction, any $1+\delta$ consistent randomized truthful mechanism can be no better than $2+\delta$-robust. This implies that the previously proposed mechanisms by Procaccia and Tennenholtz, and Agrawal et al. are both Pareto optimal. They further show that this trade-off can be achieved.

For the two-dimensional version of the problem, the authors provide a lower bound of 1.11 for all randomized mechanisms, and further show that no deterministic mechanism can combine better than 2-consistency with $1+ \sqrt{2}$​-robustness, and no randomized mechanism can combine 1-consistency with better than 2-robustness. Additionally, they present a truthful randomized mechanism that achieves 1.5 consistency and 2 robustness.
strength_weakness: strength_weakness: Some of the technical writing is unclear.  I will list some in the following sections.

- Lemma 1 should quantify $\alpha$ and $\beta$.  Theorem 3 should quantify $\epsilon$
questions: questions: Major:

I do not follow the proof of Lemma 1. In particular, is the OnlyM mechanism at line 248 well defined? The distribution needs the knowledge of $x_L$, which is not part of the input.


Minor: 
- What is formal definition of OnlyM mechanisms? Given report $\mathbf{x}$, and prediction $*$, if $x_L = \min \mathbf{x}$ and $x_R = \max \mathbf{x}$, $supp(M(\mathbf{x}, *)) = \{x_L, x_R, M\}$
- Does Lemma 1 require the original randomized mechanism to be truthful?
limitations: limitations: Yes
paper_summary: paper_summary: In this paper, the authors study the metric space facility location problem with machine-learned predictions. Specifically, they focus on the setting that the mechanism has predictions of every agent’s preferred location and with randomized mechanisms. The goal is to find truthful mechanisms that minimize the egalitarian social cost. The effectiveness of the algorithms are evaluated by their consistency (approximation ratio when the prediction is correct) and robustness (approximation ratio regardless of the quality of the prediction). 

For the single-dimensional setting, they first show that prior work with weaker predictions only on the optimal facility location are already Pareto optimal. Then, they further complete the full Pareto frontier by randomizing between the deterministic and randomized mechanisms.

For the two-dimensional setting, they prove an improved lower bound of 1.11 approximate ratio for all randomized mechanisms. They also show that no deterministic mechanism can be better than 2-consistency and (1+$\sqrt{2}$)-robustness, and no randomized mechanism can be better than 1-consistency and (1+$\sqrt{2}$)-robustness. Finally, they show that a truthful randomized mechanism that only has a prediction of the identities of the most suffered agent can achieve 1.5-consistency and 2-robustness.
strength_weakness: strength_weakness: * Several related papers [Procaccia and Tennenholtz, 2013],  [Agrawal et al. 2022], [Tang et al., 2020] study both the total social cost and egalitarian social cost, but this paper only focuses on the egalitarian cost. I understand that the egalitarian cost matches well with the “extreme ID prediction” assumption in Section 4.2, but I think this paper would be much stronger with some results of the total social cost setting. 
* Minor comments
  * I was initially confused about line 83-85, as it is first claimed no deterministic mechanism can combine better than 2-consistency with 1 + $\sqrt{2}$-robustness, and then mentioned previous work achieved 1-consistency with 1 + $\sqrt{2}$-robustness. Maybe replace “combine better” with a more concrete statement, like the statement in Theorem 3.
  * Page 2, line 70: 2 + $\delta$ robust -> 2 - $\delta$ robust
  * Page 3, line 121: need a space in “design,Agrawal”
  * Page 5, line 230: “cause at least as much cost to the agent on $x_R$ as to the other agent” Would you explicitly point out what “the other agent” means?
questions: questions: * In Lemma 1, line 235 assumes the agent at $x_L$ reports a false location. Is this assumption general enough to show that no agent would misreport? Also in Lemma 1, line 238 to 248 considered two cases that $x_L < x’_L$ or  $x_L > x’_L$. How about the case $x’_L > x_R$?
* As mentioned above, several related papers [Procaccia and Tennenholtz, 2013],  [Agrawal et al. 2022], [Tang et al., 2020] study both the total social cost and egalitarian social cost. I wonder if you have explored the total social cost objective.
* Have you considered this problem in a general metric space? Are there any straightforward results?
limitations: limitations: Future directions including closing the gap between upper and lower bounds are discussed in the paper. I think there are also other interesting directions like extending the setting to general metric or consider total social cost and the objective function.
paper_summary: paper_summary: The paper considers the strategic (single) facility location problem where the goal is to decide on the location of a single facility given the preferred locations {p_i} of n agents. The preferred locations p_i are private information and the goal is to design strategyproof mechanisms so that the agents reveal their true preferences. The quality of a solution is measured by its egalitarian cost, i.e., the maximum distance between any agent location (p_i) and the facility. The paper considers the problem when the mechanism has as input some predictions regarding agent's private preferences. This problem has been initially considered by Agrawal et al in EC'22 where they assume that the prediction is a single point denoting the location of the optimal facility.

The paper mainly shows lower bounds on the achievable consistency / robustness in different settings. First, on a line metric, the authors show that any mechanism that is (1+delta) consistent (for 0 < delta < 0.5) must be >=(2-delta)-robust, even with strong predictions about the preferences of each agent. This trade-off is also tight and every point on this frontier can be attained by a simple mechanism that randomizes between the (1-consistent, 2-robust) mechanism of Agrawal et al and a classical 1.5-robust (and 1.5 consistent) randomized mechanism. Second, in two dimensional Euclidean metrics, the authors first provide a new lower bound of 1.11 in the classical (no predictions) setting. In the learning augmented setting, they show two other lower bounds - (i) no deterministic mechanism can have better than 2 consistency and better than 1+\sqrt(2)-robustness; (ii) no randomized mechanism can have 1-consistency and better than 2-robustness. Lastly, the authors consider a new setup where the mechanism has access to the identities of the most extreme agents, i.e, agents who incur the maximum cost in the optimal solution. In this setting, the paper shows that a variant of the centroid mechanism is 1.67-consistent and 2-robust.
strength_weakness: strength_weakness: - The paper mainly gives lower bounds in the different settings. The only positive result is obtained via running the centroid mechanism on the (predicted) extreme agents.
- The proofs are terse and a bit hard to follow - for example, adding a small picture would help improve readability of many proofs (e.g. proof of Thm 2 could use a diagram illustrating the pythagoras ineq used).
questions: questions: - Could you add a discussion / reference for why the 1-d lower bound does not hold in 2 dimensions?
limitations: limitations: N/A

Comments: title: Lemma 1
Response
comment: That sounds reasonable. We would be happy to instead present this transition from distribution $f$ to distribution $g$ by gradually replacing the probability that $f$ may assign to points in $(x'_L, M')$ with probability assigned to just $x'_L$ and $M'$, while maintaining the same expected location. During this process, the convexity of the cost function of any agent located within the interval can be used to verify truthfulness. This way, we can skip the intermediate distribution that the reviewer finds confusing.
I thank the authors for their response. I will keep my score and don't have more questions.
I see. The intermediate construction confuses me. Alternatively, you may use the convexity argument of the distance function.  Thank you for your clarification.  I do not have further questions.
Dear reviewer hDFx,

Thank you once again for your helpful comments and suggestions. As the discussion period is coming to an end soon, it appears like you still maintain a negative score with high confidence, so we were wondering whether our responses did not address all of your concerns, and whether you would like us to provide any additional support for our submission while we still can.
Thank you very much. Note that in our latest response to reviewer vBqc, we now unpack that last part of the proof of Lemma 1 a bit further, which points to some of the subtleties that make this proof non-trivial and one of our main contributions. We thought we should point this out to you as well, given your original hesitation regarding the significance of this result.
Thank you very much for following up. The reviewer is correct that if we wanted to ensure that the cost of the agent located at $x_L$ remains the same in that last change in the distribution, then we would need to depend on where exactly $x_L$ lies, which would be problematic. However, note that **the cost for the agent at $x_L$ is actually not maintained during this last change in the probability distribution**. As Line 253 mentions, the cost of the agent located at $x_L$ can increase (thus hurting the agent for misreporting their true location). It is only the expected coordinate of the facility location returned within $(x'_L, M')$ that is maintained, which does not require knowledge of $x_L$, and this expected coordinate is exactly what our reduction maintains.

Let us provide a different way of phrasing the argument, which may hopefully make it easier to follow:

Let $x'_L<x_L$ be the location reported by the agent actually located at $x_L$, and let $f$ be the original mechanism and $g$ be the OnlyM mechanism that we construct using our reduction on $f$. If we focus on the interval $(x'_L, M')$, the expected coordinate of the facility returned by the two mechanisms, $f$ and $g$, conditioned on the facility being in the interval $(x'_L, M')$, is the same; this is true by construction (our reduction maintains the expected coordinate between the reported location and the mid-point). The crucial difference between the two mechanisms is that although $f$ may return any facility location in the $(x'_L, M')$ interval, mechanism $g$ returns the same expected coordinate using only $x'_L$ and $M'$ in its support. Our proof shows that the cost of an agent located at **any point $x_L$** in the $(x'_L, M')$ interval is weakly higher in $g$ than it is in $f$, thus maintaining the truthfulness guarantee. Intuitively, this is true because the two mechanisms return the same expected coordinate in that interval, but $g$ only returns the extreme points of the interval, which hurt the agent at $x_L$ the most. More formally, the proof in our submission proves this intuition by first constructing an "intermediate" distribution (Line 251) which has *the same cost as $f$ for the agent located at $x_L$ and also has the same expected coordinate as both $f$ and $g$*. Then, we observe that $g$ has weakly higher cost for the agent located at $x_L$ compared to this "intermediate" distribution, because the latter may assign some probability on $x_L$, whereas $g$ instead distributes that probability between $x'_L$ and $M'$, which increases the cost of the agent located at $x_L$.

Hopefully this addresses the reviewer's concern. If not, we would be happy to provide additional details. We acknowledge that the subtleties discussed above (which, we believe, make the result technically demanding and interesting) were written too densely, due to space limitations. We would be happy to either unpack this proof further within the main body of the paper, or to include a more detailed proof in the full version or the appendix.
Thank you for your clarification. I understand the final ``mechanism'' in Line 251 does not output $x_L$. However, do the weights of the convex combination (probabilities) depend on $x_L$ as they need to be set to maintain the same cost for the agent at $x_L$?
I appreciate the clarifications and look forward to the revisions. I also appreciate the clarifications regarding Lemma 1---I didn't actually feel that the proof was too compressed but agree that it could be clarified (the diagram is nice). I maintain my positive review otherwise.