Randomized Strategic Facility Location with Predictions
Authors: Eric Balkanski
Vasilis Gkatzelis
Golnoosh Shahkarami
Venue: NeurIPS 2024 poster (2024)
Keywords: Algorithmic Game Theory
Mechanism Design
Learning Augmented Algorithms
Strategic Facility Location
Primary area: algorithmic_game_theory

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

Randomized Strategic Facility Location with Predictions
Eric Balkanski Columbia University, IEOR eb82248columbia.c edu
Vasilis Gkatzelis
Drexel University, Computer Science gkatzodrexel, edu
Golnoosh Shahkarami
Max Planck Institut für Informatik, Universität des Saarlandes gshahkar 1oppi-ii -inf .nf.ing.dee................ mpg.de
Abstract
In the strategic facility location problem, a set of agents report their locations in a metric space and the goal is to these reports open 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 's placement in their favor. The aim to design truthful mechanisms, ensuring agents cannot gain by misreporting. This problem augmented framework, aiming to move beyond worst-case analysis and design truthful mechanisms that are augmented with (machine-learned) predictions. The focus of this prior work was on mechanisms that are deterministic and augmented with a prediction regarding the optimal facility location. In this paper, provide deeper understanding of this problem by exploring the power of randomization as well the impact of different types of predictions on the performance of truthful learning-augmenter 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.
recently revisited through the learning-
Introduction
In the classic facility location problem the goal is determine the ideal location for new facility, taking as input the preferences of 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. notable example is the strategic version of this problem which is motivated by the fact that the participating agents may be able strategically misreport their preferences, leading to 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 central role 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-augmenter framework [Mitzenmacher and Vassilvitskii, 2022]. According this framework, the designer is provided with some machine- learned prediction regarding the instance at hand and the goal is to leverage this additional information the design process. However, crucially, this information not guaranteed to be accurate and can,
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 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 deaming-augmentee 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 best- feasible robustness and consistency trade-off for truthful mechanisms augmented with 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 saaminggaugmented 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 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.
1.1 Our Results
We revisit the problem of designing truthful dearning-augmente 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 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 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-dimensione version of the problem, where all agents lie on 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 truthful' 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- auggnnttd 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: perfect consistency of 1 and an optimal robustness of 2.
Our main result for the minllediieesiionll version shows that even if the mechanism is provided with the strongest possible prediction (i.c., a prediction regarding every agent's 's preferred location), any randomized truthful mechanism that is (1 + 8) -consisttttt for some ò E [0, 0.5] can be no better than (2 - robbst.. This implies that the previously proposed deterministic learning-augmentee mechanism that is 1-consistent and 2-robust and the randomized won-learing--uugmeetee mechanism that is 1.3-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 augment- deterministic mechanism and the optimal non-augmented randomized mechanism, thus verifying that our bound fully characterizes this Pareto frontier.
'A truthful randomized mechanism guarantees truthfulness in expectation. See Section for more details.
2

---

We then consider the two-dimensional case, for which much less is known about randomized mechanisms. The best-known truthful randomized mechanism the Centroid, introduced by Tang al. [2020]. which guarantees a 2 2-1/ approximation. We provide a truthful randomized mechanism that 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 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 consistency and better than + v2 robustness, even if it is augmented with the strongest predictions. Similarly, no truthful randomized mechanism can simultaneously guarantee consistency and better than 2 robustness. The former result proves the optimality of a previously introduced 1-consistent and + /2-robust truthful deterministic mechanism provided only with prediction regarding the optimal facility location [Agrawal et al., 2022]. We also show that the latter is tight.
1.2 Related Work
Strategic facility location. Moulin [1980] provided a characterization of deterministic truthful facility location mechanisms the line and introduced the median mechanism, which returns the median the agent location profile x = (I'1... ,In) The median mechanism is known to be truthful, providing an optimal solution for the Utilitarian Social Cost and achieving a 2- 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 the Fuclidean space by employing median schemes independently in each dimension. Subsequently, Barberà et al. [1993] further generalized this outcome to any T1- norms. Other settings explored include general metric spaces [Alon al., 2010] and d-dimensional Euclidean spaces [Meir, 2019, Walsh, 2020, El-Mhamdi et al., 2023, Goel and Hann-Caruther 2020], as well as circles [Alon et al., 2010, Meir, 2019] and trees [Alon al., 2010, Feldman and Wilf, 2013]. Fundamental results in truthful facility location often focus on characterizing the space of truthful mechanisms. For the oie-dimensional case, Moulin's 's characterization [Moulin, 1980] reveals that all deterministic truthful mechanisms belong to the "general median mechanisms (GCM)" family. For the wwo-dimensional case, a similar characterization was provided by Peters al. [1993]. For comprehensive review of previous work on this problem, see the survey by Chan et al. [2021].
serrinng-uggmnteed algorithms. Worst-case analysis on its own is often not informative enough, and several alternative measures have been proposed overcome its limitations [Roughgarden, 2021]. Learning-ai augmeente algorithms, or algorithms with predictions [Mitzenmacher and Vassilvitskii, 2022], aim 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-augmmnterr mechanism design. The framework of 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 prediction of the optimal facility location. They also
mechanism
3

---

evaluated the performance of their mechanisms as function of the prediction error. More recently, Christodoulou et al. [2024] provided performance bounds based on an alternative measure of predic- tion 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 parming-augmenter
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., 20, Lu et al., 2023, Caragiannis and Kalantzis, 2024, Gkatzelis et al., 2024], bicriteria mechanism design [Balcan et al., 2024], graph problems with private input CColini-Baldesee 2024), and equilibrium analysis [Gkatzelis et al., 2022, Istrate et al., 2024). Balkanski et al. [2023b] brought together the line of work on carning-augmenter mechanism design with the literature on online algorithms with predictions by studying online mechanism design with predictions.
et al.,
2 Preliminaries
In the single facility location problem, there are n strategic agents with location profile denoted by x = (Z1, ,In), where x; 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 B[d(x;, [x)] between the facility location f(x) and their location z;.
Two renowned cost functions considered in this scenario are Egalitarian Social Cost and Utili- tarian Social Cost. In this work, the goal is to optimize the Egalitarian Social Cost C(J,x) x) E[max,, Ex d(x,,, I' [x))), representing the expected maximum cost experienced by a single agent for each possible outcome of fxx). 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 oxx).
To minimize the social cost, a mechanism needs to ask the agents to report their preferred locations, R and then use this information to determine the facility location f(x) R However, the preferred location z; of each agent is private information, and they can choose to misreport their preferred location if that reduce their own cost. A mechanism f 2n - R is considered truthful when no individual agent can benefit by misreporting their location, i.c., for all instances x E R²", every agent E [m.]. and every deviation xi E R.? we have that d(x,,, fx)) I d(x1,, f(x_;, x!)), where x-; = (I11 ... I, Ti+1, ... ,T,) 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 ran- domization 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, mechanism f 22an - IR2 is truthful in expectation if for all instances x E R2n, every agent i E [m]. and every deviation s/ E R2, we have that E[d(z,, ff (x)) < [[d((;; x()].
We focus on mechanisms that are both unanimous and anonymous. A mechanism is unanimous if, when all points x are located the same position (x; = Iy for all all i E [m]). places the facility at that specific location, i.e., fxx = Fi. 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 remains unchanged under any permutation of the agents. Finally, we also assume the mechanism is scale-independent i.c., 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.
augmented algorithms encompass 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 's preferred locations, 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 & or F*, we denote a mechanism enhanced with & and F by f'x, x) and f(x, F"), respectively. We define mechanisms enhanced with other kinds of predictions a similar way.
The effectiveness of ness. If < * denotes all instances x for which prediction is accurate, a mechanism is
mechanisms is evaluated using their consistency and robust-
a-consistent if it achieves an a-approximatton when the prediction is correct, i.c.,
C(J(x, +)
max x, x
a.
C(o(x),x)
3-robust if maintains 8 3-approximation regardless of the quality of the prediction, i.c.,
[(f((, x).
}
max C(o(x),x) 5 S SB.
Results for the Line
In this section, we provide lower bound regarding the performance of any randomized mechanism for the line, even if is equipped with the strongest type of prediction, i.c., a prediction X regarding the preferred location of every agent.
Theorem No mechanism for the line that is truthful in expectation and guarantees 1+8 consistency for some 5 E [0, 0.5) can also guarantee robustness better than 2 - 8, even if it is provided with full predictions & containing each of the agents' locations.
The proof consists two main parts. We first show that, for any instance involving two agents, we without loss of generality restrict our attention to 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 z be the leftmost reported location and æR be the rightmost reported location on the line. Therefore, we have zy S œ. Let M denote the midpoint of these two extreme points, i.e., M = (I + zn)/2, which would also correspond to the optimal facility location. For simplicity, we sometimes write f (#1...., ,....,,,,,, dropping the angle brackets ()- ONLYM is the class of mechanisms that, whenever they choose a location within the interval (IL, RR) then this location is always M.
Definition (ONLYM mechanisms). A mechanism I for the line is ONLYM mechanism if
P(f(x) E (x) (M)) = O.
The main lemma for the proof of Theorem is the following reduction that allows to restrict our attention to ONLYM mechanisms. The complete proof of Lemma can be found in Appendix A. Lemma 1. For any problem instance involving two agents with reported locations x (IL, an) on the line, and any randomized truthful in expectation mechanism achieving a a-consistency and 3-robustness over this class of instances, there exists a randomized ONLYM mechanism that is truthful in expectation and achieves the same consistency and robusiness guarantees.
Proof Sketch. Consider randomized mechanism f(L1, with probabilities pæ (1 (eLM) and p, = Pif RR) E (M, æ1),, representing the chances of selecting a location in (vr., M) and (M,RR). respectively. If pa Pr O. the mechanism already satisfies the desired property. Otherwise, for pe > 0 and > 0, define the expected locations n. = [ TR) (() E (II,, M)) and ,, B (*L. [(II,,
E (M,#R)), which can be expressed as convex combinations xe = 4 + (1 - 96) M and n, = J + (1 - 4.) 4.M
M for some qes E (0. 1).
We then construct new mechanism f' that modifies f by reassigning probability masses to FT, M, and I as follows:
P[f(zz, =
if v < 3t or T. > En.
if x E (æ1, M) U (M, xR),
Pl IR) =
P[f(IL, = x] + gePe
if = IL.
P[f(FL, z] (1 ge)pe + (1 qr)p,
if M,
P([(I), x| q-Pr
if IR.
5

---

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 and f' (Lemma 3).
Equipped with Lemma 1, we can now prove Theorem 1.
Proof of Theorem I. We start by proving the result for two-agent instances on the line using any ONLYM mechanism. Then, using Lemma I, the result follows for any randomized mechanism.
First, note that if the chosen facility location y is distance d(M, y) from the point M (vr, + /22 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 on the left of M and note that its distance from the agent located at ZR is d( M) + d(M, y). As result, the expected social cost of mechanism f with agent locations is
C(f.x) x) C(o(x). x) + E[d(M,
Now, assume that there exists a mechanism that (1 + 8)-cosiitt and better than (2 8) roobust.. For robustness, this would imply that for every instance x, irrespective of the prediction, the mecha- nism must guarantee that
C(f,x) C(o(x)xx) 6
F(x( C()(x),x)
< 61
For this mechanism be truthful in expectation, it must ensure that no agent has incentive to misreport their location. Consider the instance x = (II, 2R), and note that the agent at z has the option to misreport their location x'y Ft, d(II, which would shift the new midpoint M' to Ty in the new instance x' = (a5 &g)- This deviation would double the optimal cost, i.e., C(o(x'),x) = 2- C(o(x), x). Inequality (2), then guarantees that the expected cost for this agent
after the deviation would be at most 2(1 - 8)- C(o(x), x) since we have
E f(x'M) f(x(2,,(xx))) < <1- 6. C(o(x',,x)
2 C(o(x),x)
As a result, to ensure that this agent will not misreport, the mechanism needs to ensure that the expected cost of the agent they report the truth strictly less than 2(1 - 6) C(o(x), x). If we let P(s L) = (xx() < z denote the probability that the chosen location is weakly on the left of IL and P(M)= = (() = .M] denote the probability that the chosen location is M, then the expected cost of the agent located at zy is at least C(o(x),x) P(M) + (C(x(x), x) P(M) P(s L)) because the mechanism is an ONLYM mechanism. This is even if we assume that the only chosen facility locations weakly the left of æ (and weakly the right of x,, respectively) exactly on IL (and exactly on Fn, respectively). Therefore, the mechanism needs to always satisfy
C(o(x).x) + 2(1 - P(M)- p(s L))) < 2(1 - 8)C(o(x), x)
P(M) 2
(4)
= -PMM) + 2(1 - P(M) - P(s L)) < 2(1 - 8) = P( L)
If we consider the same instance x = (IL, and assume that the mechanism is also provided with accurate predictions å = xy and Φ FR regarding the agent locations, to guarantee 1 + consistency, Inequality (1) implies that
((x, C(o(x),x)
C(o(x),x) <1+8
S 8.
(5)
Finally, if we once again consider the same instance with inaccurate predictions ê. = xy and fR = FR + d(Ir,,, FR., we observe that in this case the agent located at æR would have the option to instead report x² xn + ((II,,RR) = RR, 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 Tg would now coincide with the middle point M1 of the misreported instance

---

x" = (IL,2R) this would yield the agent located at who misreported an expected cost of 26 C(o(x), x) since have
B|d(M", f(x", x))] LId( f(x, 8))] ((o(x"),x'
((o(x),x) S 6.
(6)
As 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 most 26 C(o(x),,). If we once again let P(s L) denote the probability that the chosen location is weakly on the left of z1, and P(M) denote the probability that the chosen location M, then the expected cost of the agent located zg is at least ( + (C(o(x), P(s L). This is even if we once again assume that the only chosen facility locations weakly on the left of æ (and weakly on the right of æR, respectively) are exactly on (and exactly on In, respectively). Therefore, the mechanism needs to always satisfy
P(M) 2
P(M) + 2P L) 1 25 = P(s L) S
However, this contradicts Inequality (4), so we conclude that no mechanism can simultaneously guarantee (1 6) consistency and a robustness better than (2 - 6).
3.1 The hardness result for the line is tight
We observe that the lower bound regarding the robustness and consistency trade-off shown in Theorem is actually tight. Specifically,, it can be achieved by an appropriate randomization between mechanism and the optimal aop-laarning-uugmees
the optimal deterministic randomized mechanism.
For any 8 E [0, 0.5]. there exists randomized mechanism on the line which, given prediction F", is truthful in expectation, (1 + coonsistet,,, and (2 50) rrrroutt
Proposition 1.
As 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.
3.2 Other prediction settings
To gain 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 setting where predictions are available for 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 agents, there exist 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.
4 Results for the Plane
We now consider instances in the Euclidean plane, with a location profile x = (x),..., In), where I; 2 for each agent i. Missing proof' of this section can be found Appendix B.
4.1
Impossibility Results
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 known for mechanisms without predictions.
Since the problem designing good facility location mechanisms in two dimensions "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 two dimensions. The reason is that the design space for -vo-dimensional mechanisms is much richer, and the known lower bounds apply
7

---

fei...., = arg max,, d( d( o(x)). Note that the smallest circle that encloses all the points only to the more restricted class of one-dimensional mechanisms. For example, consider a simple instance with just two agents 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 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 simple example, in a 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, e) for any 0.5 by simply returning the appropriate point on the interval's perpendicular bisector.
instance involving two agents at distance 1 from each other, the
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 s ability to penalize and reward agents based on their reports. Although 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 this additional flexibility in two dimensions, proving inapproximability results for this broader class of mechanisms is a more challenging problem and seems to require techniques and insights.
Theorem 3. Any randomized mechanism that is truthiful 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 + v2) -robust... Our impossibility result for deterministic mechanisms shows that stronger predictions do not help: even with predictions about the location of each agent, there no deterministic mechanism that achieves a robustness better than 1 + v2 and a consistency that improves over the best approximation achievable without predictions.
Theorem 4. For any > O, there is no deterministic truthful mechanism that is (2 5)-cosiist and (1 + v2- - 5) -robust, even if it is provided with full predictions & containing each of the agents' locations.
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 8 > O, there is no randomized mechanism that is truthful in expectation, 1-consistent, and (2 5)-robust, even for two-agent instances and even if it is provided with full predictions & (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.
4.2 Positive Results Using Extreme ID Prediction
We now turn to positive results, and provide a Gaaning-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 would suffer the maximum cost in the optimal solution (we refer to them as "extreme agents"). " i.e.
with the identities è (ci,... .k) of the ic agents who
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 9 with a probability of half, and each of the extreme points with 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
8

---

Mechanism 1: Centroid Mechanism on Extreme Agents
Input :ocatton profile x = (f1,''. ,In,, Predictions = (61, ; ((k)
Output: : Probability distribution P on location of the facility
With probability 1 1/2:
return the centroid G = Ie, 4u
K
With probability 1/2k:
return each point Tetr" 1. .ee
2 - 3 R 1.67 by running this mechanism only on extreme agents. We use their ideas to maintain truthfulness 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 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 Assume there are only two extreme agents, ie., k = 2. Then, given predictions é (2) that provides the IDs of the only two extreme agents, there exists a randomized mechanism that 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 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 prediction set that provides the IDs of the extreme agents, there exists randomized mechanism that is truthful in expectation and achieves 1.67 consistency and robustness for any number of agents.
Proof. Let us first consider instances with only three extreme agents. Mechanism is truthful since other agents apart from Tej Feg Tea cannot influence the result and Mechanism I equivalent to the mechanism of Tang et al. [2020] over agents e and since this mechanism is truthful in expectation, agents C1,, eg 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 cireumcircle, 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 Fuler line.
Euler line. Given three arbitrary points I Ti,..., I3, their circumeirele is the smallest circle that encloses the three points, their centroid is (xi + 22 + za)/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, dl d(O,9) g) d(G, H)/2, implying d(O,9) = d(O, H3/3.
Let R denote the radius of the circumcircle of Æe, Tezs Tes and assume without loss of generality that the optimum cost is R = 1. For any j [ri], we have
d(z,,9) < d(a;, O) + d(O, < <R+d(0 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. Since H lies within the cireumeircle, we infer d(O, H) S R, conclusively showing that d(O,9) 9) S R/3. Since R is the optimum cost and any agent can reach O by paying that cost, the cost of returning G for any agent upper bounded by R + d(O,9), which most 1.34R. Consequently, the approximation of Mechanism 1 in case of having accurate predictions is less equal than

---

Altitudes
Medians
As mentioned previously, the key concept involves perturbing the instance before requesting predic- tions have most three extreme agents. Given any instance instance X = (ā),- ... .n), 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 Perpendicular Bisectors
H
Figure 1: G = (Ie, + Zez + E/3) is the centroid of Zei..... Bry, which is the intersection of the three medians. H the orthocenter, which is the intersection of the three altitudes, and the center of the circumcircle, which is the intersection of the three perpendicular bisectors. In any triangle, the circumcenter (O), the centroid (9), and the orthocenter (H) are collinear, forming the Fuler line. Moreover, d(O,g) Hd(G,H) H).
1 2k R
max d d(e,,) kz) + max dz 1++ 1R+ d(0,9) 1 1
1
( (1+
/ 1.67.
JE
2 R jE(n]
where the first inequality since d m3) < d(Fezy 0) d(O, m3) 2R when the predictions are correct. Next, we show how we can modify the mechanism to achieve the same approximation guarantees having three extreme agents while maintaining truthfulness.
(xI,,.. ,In), define perturbed
X might differ from those of the original instance their costs remain very close to the maximum cost case of having good predictions. Therefore, the circumeirele of them is good representation of the minimum enclosing circle and results in the same approximation guarantees.
Since run the mechanism 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 predictions are accurate based on the perturbed instance and in any case we can ensure the robustness factor of 2.
5
Future Directions
The problem of designing randomized facility location mechanisms in the Euclidean space is very natural and several open questions remain, even without predictions. While numerous studies have addressed this problem in restricted spaces, there remains gap regarding between the best possible approximation guarantee in (1.118, 2 1/n). The possibility of truthful expectation mechanism achieving better than a 2 - 1/n approximation is intriguing. Obtaining a stronger lower bound than 1.118 would also be very interesting.
Augmenting these mechanisms with predictions introduces a new dimension to the problem. While we have explored various prediction settings and provided both positive and negative results, many of the current findings in Fuclidean space lack tightness. Finding tight results for different types of predictions would enable meaningful comparisons and help identify which prediction strategy most effective in different scenarios.
10

---

Acknowledgments
Eric Balkanski and Vasilis Gkatzelis were partially supported by NSF grant CCF-2210502, Eric Balkanski was also supported by NSF grant IIS-2147361. Vasilis Gkatzelis was also supported by NSF CAREER award CCF-2047907.
References
Priyank Agrawal, Eric Balkanski, Vasilis Gkatzelis, Tingting Ou, and Xizhi Tan. Learning -agginntge Leveraging predictions for facility location. In EC '22: The 23rd ACM Conference on Economics and Computation. ACM, 2022. doi: 10. 10.1145/2490486.3588300
mechanism design:
Matteo Almanza, Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi, and Giuseppe Re. Online facility location with multiple advice. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, pages 4661-4673, 2021.
Noga Alon, Michal Feldman, Ariel D Procaccia, and Moshe Tennenholtz. Strategyproof approx- imation of the minimax on networks. Mathematics of Operations Research, 35(3):513-526, 2010.
Maria-Florina Balcan, Siddharth Prasad, and Tuomas Sandholm. Bicriteria multidimensional mecha- nism design with side information. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS 233, Red Hook, NY, USA, 2024. Curran Associates Inc.
Eric Balkanski, Vasilis Gkatzelis. and Xizhi Tan. Strategyproof Scheduling with Predictions. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), 2023a. doi: 10.4230/ LIPIcs. 11..
Eric Balkanski, Vasilis Gkatzelis, Xizhi Tan, and Cherlin Zhu. Online mechanism design with predictions. arXiv 23eprint:2310.0288) (to appear in the 25th ACM Conference on Economics and Computation (EC '24)), 2023b.
Zohar Barak, Anupam Gupta, and Inbal Talgam-Cohen. Mac advice for facility location mecha- nism design. arXiv preprint:2403 2403. 12181 (to appear in 38th Conference on Neural Information Processing Systems (NeurIPS)). 2024.
Salvador Barberå, Faruk Gul, and Stacchetti Ennio. Generalized median voter schemes and commit- tees. Journal of Economic Theory, 61(2):222-289 1993.
Mark Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer, Berlin, Germany, 3rd edition, 2008. ISBN 978-3-540- 77973-5.
Kim C. Border and James Jordan. Straightforward elections, unanimity and phantom voters. Review of Economic Studies, 50(1):153-170, 1983.
Ioannis Caragiannis and Georgios Kalantzis. Randomized leaming-augmented auctions with revenue guarantees. In Proceedings of the Thirty- Third International Joint Conference on Artificial Intelligence, IJCAI-24, 2024. doi: 10. 10.24963/ijcai.202444 20224/997.
Hau Chan, Aris Filos-Ratskkas, Bo Li, Minming Li, and Chenhao Wang. Mechanism design for facility location problems: A survey. In Zhi-Hua Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pages 4365. International Joint Conferences on Artificial Intelligence Organization, 2021.
Qingyun Chen, Nick Gravin, and Sungjin Im. Strategic facility location via predictions. arXiv 2eeprint:240000744: (to appear in the 20th International Conference of Web and Internet Eco- nomics, WINE), 2024.
George Christodoulou, Alkmini Sgouritsa, and loannis Vlachos. Mechanism design augmented with output advice. arXiv preprint:2406. 14165 (to appear 38th Conference on Neural Information Processing Systems (NeurIPS)), 2024.
11

---

Riccardo Goini-Baldeschie Sophie Klumper, Guido Schäfer, and Artem Tsikiridis. To trust or not trust: Assignment mechanisms with predictions in the private graph model. arXiv 2teprimt:24030037255 (to appear in the 25th ACM Conference on Economics and Computation ECC '24)), 2024.
El-Mahdi El-Mhamdi, Sadegh Farhadkhani, Rachid Guerraoui, and Lê-Nguyèn Hoang. On the strategyproofness of the geometric median. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, pages 2603-2640, 2023.
Jiazhu Fang. Qizhi Fang, Wenjing Liu, and Qingqin Nong. Mechanism design with predictions for facility location games with candidate locations. In Annual Conference on Theory and Applications of Models of Computation, pages 38-49. Springer, 2024.
Michal Feldman and Yoav Wilf. Strategyproof facility location and the least squares objective. In Proceedings of the fourteenth ACM conference Electronic commerce, pages 873-890, 2013.
Dimitris Fotakis, Evangelia Gergatsouli, Themis Gouleakis, and Nikolas Patris. Learning augmented online facility location. CoRR, abs/2107.08277, 2021.
Vasilis Gkatzelis, Kostas Kollias, Alkmini Sgouritsa, and Xizhi Tan. Improved price of anarchy via predictions. In Proceedings of the 23rd ACM Conference Economics and Computation, EC '22, page 529-557, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 97814503915 504. doi: 10.1 (401144444044663533339
Vasilis Gkatzelis, Daniel Schoepflin, and Xizhi Tan. Clock auctions augmented with unreliable advice. arXiv preprint:2408. 06483 (to appear in the 2025 ACM-SIAM Symposium on Discrete Algorithms, SODA), 2024.
Sumit Goel and Wade Hann-Caruthers. Optimality of the coordinate- wise median mechanism for strategyproof facility location in two dimensions. Social Choice and Welfare, 2020.
Gabriel Istrate and Cosmin Bonchis. Mechanism design with predictions for obnoxious facility location. arXiv preprint arX1v:2212.0952). 2022.
Gabriel Istrate, Cosmin Bonchis, and Victor Bogdan. Equilibria in multiagent online problems with predictions, 2024.
Shaofeng H.-C. Jiang, Erzhi Liu, You Lyu, Zhihao Gavin Tang, and Yubo Zhang. Online facility location with predictions. In The Tenth International Conference Learning Representations, ICLR 2022. OpenReview.net, 2022.
Alexander Lindermayr and Nicole Megow. Alps. https://algorithmms wwwpeimmmwwittt-----iitiiiiieiie aethub.io/.
Pinyan Lu, Zongqi Wan, and Jialin Zhang, Competitive auctions with imperfect predictions. arXiv preprint:2309. 15444 (to appear the 25th ACM Conference on Economics and Computation| ECC '24)), 2023.
Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. J. ACM, 68(4):24:1 2021.
Reshef Meir. Strategyproof facility location for three agents on a circle. In International Symposium on Algorithmic Game Theory, pages 18-33. Springer, 2019.
Adam Meyerson. Online facility location. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, pages 426-431. IEEE Computer Society, 2001. doi: 10. 10.1100/SFCS.200. 959917.
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Commun, ACM, 65(7): 33-35, jun 2022. ISSN 0001-0782, doi: 10.1145/3528087
Hervé Moulin. On strategy-proofness and single peakedness. Public Choice, 35(4):437-455, 1980.
Hans Peters, Hans van der Stel, and Ton Storcken. Range convexity, continuity, and strategy strategy-proofness of voting schemes. Zeitschrift für Operations Research, 38:213-229, 1993.
12

---

Ariel D. Procaccia and Moshe Tennenholtz. Approximate mechanism design without money, ACM Trans. Economics and Comput.. 1(4):18:1-1:26, 2013. doi: 10.144/2542274:252177..
Tim Roughgarden. Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, 2021.
Pingzhong Tang, Dingli Yu, and Shengyu Zhao. Characterization of group-strategyprod mechanisms for facility location strictly convex space. In EC '20: The 2 ACM Conference on Economics and Computation, pages 133-157. ACM, 2020. doi: 00.1145/391400333999.
Toby Walsh. Strategy proof mechanisms for facility location in Euclidean and Manhattan space. arXiv preprint urXiv:2009.07990 2020.
Chenyang Xu and Pinyan Lu. Mechanism design with predictions. In Lud De Raedt, editor. IJCAI '22: The s1 International Joint Conference on Artificial Intelligence, pages 571-577, 2022.
13

---

ArbitraryMMcchaninn Mechanism
Pe
Pr
L
M
JR
Agents' reported locations
Mid
ONLYM Mechanism
Non-zero probsbility outcomes
PqpPt
+(1 uope + (1 2. 2r)
+.PPr
LL
M
2R
Figure 2: The original mechanism f(.) and the new ONLYM mechanism f((.) in the proof of Lemma 1, where Pt = (f (M), and p, = Pf TR) *R) me [[f("1, f(IL,IR) E (IL, M)] and n. E[f(=L, f(IL, E (M,RR), and qe and gr are such that ne q + - M and म. = 9 + +1--
A Missing Proof of Section 3
Lemma 1. For any problem instance involving two agents with reported locations x (IL, R.) on the line, and any randomized truthful expectation mechanism achieving a-consistency and 3-robustness over this class of instances. there exists randomized ONLYM mechanism that is truthful in expectation and achieves the same consistency and robustness guarantees.
Proof. Consider any randomized mechanism f( zR) and let ps = P[S E (xz,, and pr (R) E (M, xR)] represent the probabilities that this mechanism chooses facility location in (æT., .) and (M,æR), respectively. If ps Pr 0, the mechanism al- ready satisfies the desired property, and the proof is complete. Otherwise. if pt > 0, define Ty = [E[ .RR f(z xR) (ZL,M) and, if pr >> 0, define म, Eff zR) f(zL, xR)] as the expected locations returned by the mechanism when restricted to (I M) and (M) respectively.
Since Te lies in (Iz, M) and n, lies in (M, RR), we can express these two points as convex com- binations of ZL, M, and TR: le, Or E (0, 1). We then modify the original mechanism of to a new ONLYM mechanism f defined as
g&F + (1 (1-4))M and म, 9, + (1 9r G.M for some
P[f(Iz, = x]
if < or >> ER if E (æz, M) U (M,uR)
(1), P[f(FZ, x| qCpe
if x IL
P[[(1,, = x] ++11 de + -1- -r))pr
if =
P([(1L, TR) = =x] GrPr
if JR
The 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 For all mechanisms for the line and instances x IR) 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 that
d(z,, f(x)) f(x) (xt, (zr, M) P(f((x M))
E max
E (d(aa, f(x)) fx() E (I), Pe
d(æR, Tt) Pe.
Similarly, we have
E max d(z;, fx)) | f(x) E (M, P[f(() E (M, = d( Pr.
[x((x
14

---

which implies that
=
max d(a,, f' (xx)
-E
max
d(r,, (()))
=d(rR, FL) (P( E - E (xL,
+ dd(R (PP] -M]] -x)
- d( - - Pr
=( 21) ((0) 9:P.) + M) ((1 -elpe + (1 q-)p,)
d() - - d(z,, m.) Pr
d( -q + q-p,)
d(zR, (M) ((1 gelpe (1 p.)pp))
- (L) . qePt - d(ER. M) (1 qe
d(LL q-Pr d(zr, M) (1 4-
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 = (LI, IR) with two agents, the cost of the agent location FT, is identical under both I and J', i.e. [dd(x,, [(x)] E (' Similarly, we have E [d( [(x))] = 1E ['(xx,
Proof. By definition of f', we have
E [[]( - [[d(zz,
= =d(z, f(x) - Pf)- (x),
+ +d [[[(x) [[(x) E (M, - E (M,vR))
+ M) ()P((()) P
+d(IL, [P[((x) ([(x)=xx) zgl Pf = =x))
d(FL, 9006 (1-9))M -2 MM) Pr
MM)
xn) (n)
d(EL, M1 (((p))/))(.l. d(EL, 9r)p
(1) -1) FR)
0.
Next, the previous lemma to show that mechanism f' preserves the truthful in expectation guarantee of f-
Lemma 4. If mechanism f for the line is truthful in expectation over instances with 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 æ deviates and reports a false location 2/,-- We need to show
Bdd(rz, f' (x',, ax)) 2 E [[d( ((c,,
Since the original mechanism f(11, an) is truthful in expectation, we have
E [d((1 f('2 xR)) 2 E [d(#1, f(
Combining these two inequalities with Lemma 3, it suffices to show
E [d((L (1 æR))] 2 [d(L, f(z/, #R))]
15

---

To prove the above inequality, we consider two main cases. First, we focus on the scenario where the agent located at z1 deviates to the right, i.e., JL < zzz Let M' z,, Hen
Assume z'2 S zR- [M'FRR) If 14, then
define //2 Pl #R) (4'2, M')] and p/, (()(F(, f' RR) = f fazz, RR), and hence E [d(rL, I (F22, E [d(æL, (42, Therefore, the proof is complete in this case.
Next, consider the distribution where the mechanism f(z2,, IR) returns random facility location within the intervals (a',, M²) if p/ > O, or within (M', RR) if p/. > The expected locations within these intervals are o E (2y,, and of E (M", æR), which can be expressed as T/ da', + (1 - M)M and oí = G. + M.M where of and g. are the respective convex coefficients.
In the first case, where TL < Z/z, we show that the cost the left agent 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 MM") and (M', æn), both on the right side of zt. Thus, the agent's s cost is fully determined by the expected locations in these intervals. Specifically we have
E[d(ai,
= Ed(,,, + - P([(v(,, E (M')
= E M')]
+ dd +
E (M',
+ +d (P[(()))))) d',] =[((((,,=)==dd
dd ( (P[f(2),.))= M'| - Pf = MD)
+ +d(ar, xR) :(P (f(2, = =n] - [[)(<() = =xR)
= =d(rr, d64'2 + +1 (1 -() -1' + d(EI, + (1-1)) p'-
- d(ø1, Dng - 21)1,24))9' d(),, + d(1 M1) - d))p'
= ((LL,11LV + d(Ez M') ()0p +
- d(ær, (o006dd((z..) d(II, M¹) (1- - ((I1,
= O.
Note that in the case of RR < x'y the same arguments hold with a minor change in notation. Define 2/2 = P[[(xz), xR) E (M', x1)] and = ((f(((,, E (IR, M').. Consider the expected locations n/ and nh within the intervals (M' x')) and (IR, M'), respectively.
Focusing our attention on the more interesting case where x²2 < IL, we aim to show that E [d(x [d( f'(=2,,=))] 2 E [d(IL, f(x [R)] If we focus the interval (x',, M') and assume It < M', the expected location of the facility returned by the two mechanisms, f(z2,, xR) and (R), conditioned on the facility being in the interval (x/,- M'), is the same; this is true by construction (our reduction maintains the expected location T/ between the reported location and the midpoint). The crucial difference between the two mechanisms is that although far (x) may return any facility location in the (x/,, MM) interval, the mechanism f f'('', zR) returns the same expected location using only x'y, and M' in its support. We show that the cost to an agent located at any point , in the (z',, .M') interval is weakly higher in f' (z(zz In) than it is in Tn), thus maintaining the truthfulness guarantee. Intuitively, this is true because the two mechanisms return the same expected location o. in that interval, but f (2'2, RR) only returns the extreme points of the interval, which hurt the agent at FT the most.
More formally, we replace any probability assigned to point in (z',- M') with convex combination between s'z and M', and each time we do this, we weakly increase the cost to an agent who is located at any point in (4'z, M'). Specifically, for any outcome y E (4/, M') of the mechanism
(u',,,n) and any FT. E M"), if we have y = w x' + (1 w) M' then (x1.2) y) < w d(zL,)')) + (1 w) ddLL, M').
16

---

Since o/. ooyz + (1 M,M, at the end of this process, we will end up with Lp' probability increase on 2'L2 and (1 4e P probability increase on M'. Therefore, we have
E Eld(E ((2 d(x +' + d(z,, M') ((1 d0) + +(1 - -1-))())) + d(IL, RR)
=E [ =n))
In the case where 1y M', similar arguments apply in the interval (M', .n))
The proof of Lemma 1 then immediately follows from Lemma and Lemma 4.
Proposition For any ô & [0, 0.5), there exists a randomized mechanism on the line which, given prediction F", is truthful in expectation, (1 + consisten, and (2 8)-robust.
Proof. We show that the bound of the robustness consistency off in Theorem is tight. To verify the tightness for 8 0.5, note that it possible to achieve robustness of 1.5 (and therefore also consistency of 1.5) using the following randomized truthful in expectation mechanism of Procaccia and Tennenholtz [2013]:
Mechanism 1 (LRM). Given an inpul x, the mechanism returns Ty with probability 1/4, DR with probability 1/4, and M with probability 1/2.
On the other extreme, verify the tightness of the theorem for 8 = O. note that it is possible to achieve a robustness of with a consistency of using the following truthful deterministic Baaning-auggment mechanism of Agrawal et al. [2022]:
Mechanism (MinMaxP). Given an input x and a prediction F* regarding the optimal facility location, the mechanism returns F if F E [L I if F < L. and n if F* I---
In fact, for any 8 E [0, 0.5), we can achieve a robustness of 2 5 5 and a consistency of 1 + by randomly choosing which one of these two mechanisms to Specifically, we can achieve these bounds by running the LRM mechanism with probability 26 and the MinMaxP mechanism with probability 1 26. Note that since the decision regarding which one of the truthful mechanisms to run independent of the agents' reports, the resulting randomized mechanism is truthful as well. LI
Theorem Given a prediction set that provides the identities of all n agents, there exist n - 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 L.5-consistent.
Proof. We first address the deterministic case with two agents whose locations are given by x (F1,, RR) Assume we have a prediction år,, which predicts the location of the leftmost agent. We will show that even if &t. is accurate, there is no truthful mechanism with a consistency better than 2.
We use the same argument as Theorem 3.2 of Procaccia and Tennenholtz [2013]. Assume, for contradiction, that f 2 > IR is truthful mechanism with consistency less than 2. Consider the location profile x (ar, , 0, æ = 1) and the prediction ä, = 0. To achieve consistency better than 2, the mechanism needs choose a facility location
f(x) such that y E (0. 1).
Now consider an alternative location profile x' = (azz = 0, a'R = y) with the prediction क = The optimal facility location for this profile is at y/2, yielding 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 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 in both profiles x and x', with accurate predictions for them at O. 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
17

---

x²
d(x
(1,1/2)
xx Re
1.118
I1 Ø'1
12, 22, :. In o
En
T n
(0,0)
(1/2,0)
(1,0)
(2,0)
Figure 3: Instances = (20)) In-1 (1/2,0), (1) and x = (2) (0, 00 xn-1 (1/2,0), = (2,0) in the proof of Theorem 2. It is assumed that f(x)) 2 1/2 and x* E arg 2)) C(v,
number of agents. Let f be a randomized truthful in expectation mechanism. Consider the location profile x (=z = 0, R 1). We have fx) P, where P is a probability distribution over IR. There exists 24 E x such that E[d(x;, P)] 1/2. If this agent's location prediction is unavailable, we can prove that consistency better than 1.5 cannot be achieved.
Assume [[d(ZR. P)] 2 1/2 and that we have an accurate prediction 2 for the leftmost agent æ.. Consider the profile x' = (z', O, R = 2). with an accurate prediction ã = O. For truthfulness, the expected distance from the location should still be 1/2, otherwise the rightmost agent would lie in profile x. We know that if [Ed P)] A, then the expected maximum cost is A + 1. With 2 1/2, the expected cost is least 1.5, whereas the optimal cost is 1, resulting in a consistency of at least 1.5.
This argument extends 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.
B Missing Proofs of Section 4
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 fxx P be randomized truthful in expectation mechanism. where P is a probability distribution over 2 Consider the location profile x = {x) (0,0).
= In-1 (1/2, 0), x (1, 0)). There exists an x; (either 21 or ar,)) such that d(z,, f(x)) = Eyy-pd(z y) 1/2. Without loss of generality, assume that d( fx)) 2 1 1/2. Now consider the location profile -i, (1/2, 0). x/ (2, 0)). To maintain truthfulness, we must have d( = (), f(x')) 2 1/2, preventing the agent at location I, (1,0) in the profile x from having an incentive lie about being at location x/ = (2, 0).
( (0. 0). x
Extending the result of Theorem 3.4 in Procaccia and Tennenholtz [2013] from the line to the Fuclidean metric, if we have d(((x), [ fx)) 2 A, then the expected maximum cost is at least
A² C(o(x))
Therefore, the expected cost of x' is at least / / + (2) resulting in V1.2 ~ 1.118 approximation,
as the optimum cost is d(x),=")) 1.
Theorem 4. For any 8 > O, there is deterministic truthful mechanism that is (2 8) consiistet and (1 /2 6) -robust, even it is provided with full predictions & containing each of the agents' locations.
Proof. Using the characterization provided by Peters et [1993], we know that any deterministic, truthful, anonymous, and unanimous mechanism can be expressed Generalized Coordinatewise
18

---

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 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 five-agent instance with x containing four agents at (0, 20) and one agent at (0, 10). Our proof first shows that 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 GC,(x, P) will 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 at least v2. Let ă be the median of the z-coordinates of the four constant points, and now consider the following instance, where the optimal cost is 1.
Consider five-agent instance with x containing three agents (ž, 0), one agent at (ă 1), and one agent at i- /2
Since T is the median of the x-coordinates of both true agent locations x and constant points P, T will be the a-coordinate of the GCM(x, P). Since all the constant points have y-coordinates greater than 10, the y-coordinate of the GCM(x, will be 1.
Since (i, 1) has a distance of + 2 from point, has distance of from all the points, 1 1+ 2
- 1- 2 V2 - while (# - (.),. the optimal conclude that the robustness factor is at least
Theorem 5. For any 8 > O, there is randomized mechanism that is truthful in expectation, 1-consistent, and (2- -0)-bbuust, even for two-agent instances and even if it is provided with full predictions & (the location of each agent). This is tight, i.e., there exists randomized mechanism that is truthful in expectation, 1-consistent, and 2-robust for two-agent instances.
R = 2), and assume we have predictions & = ( = 0, R 2). To achieve 1-consistency, mechanism should return M with probability
Proof. Consider the instance x = ( = 0
Now consider another instance x' = (x'2 = 0, 2 = 1) with incorrect predictions & = (# 0, f 2). To ensure that the rightmost agent will not misreport to æı 2 and have 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 d'R with probability This results in robustness factor of 2.
Agrawal et al. [2022] proposed a deterministic Minimum Bounding Box mechanism that is 1- consistent and + /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 = ((I1,81), ... (In vn)), and a pre- diction F (FF, return (M (MinM AMinMarP((2aa P((1,, IF), MinMax ((y), Mn), 9F)).
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 Assume there are only two extreme agents, i.e., k 2. Then, given predictions é = (e1, e2) that provides the IDs of the only two extreme agents, there exists randomized mechanism that truthful expectation and achieves 1.5 consistency and 2 robustness for any number of agents.
19

---

Proof. If we only have two agents Ze, and Te, located on the minimum enclosing circle, Te represent a diameter of this circle; otherwise, we can find smaller circle containing all the points. Therefore, the middle point of these two locations, (Tey + 22 is the optimum location of the facility. Mechanism 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 probability of 1/4, resulting in a 1.5 consistency.
In terms of truthfulness, since no other agent besides dez and Tey impacts the mechanism, it suffices to show that they do not have an incentive to lie. Agents dez and Tey lack such incentive for reasons similar to those in LRM Mechanism. Additionally, any returned location falls within the minimum enclosing circle, it ensures a robustness factor of 2.
20

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We describe all our results in the introduction section, specifically in the 'Our Results' subsection.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
We discuss the limitations of our results in the last section, the Future Direc- tions.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiiatinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
21

---

Answer: [Yes]
Justification:
Due to the page limit, we have moved some of our proofs to the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
The contributions of paper mainly theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
22

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The contributions of our paper are mainly theoretical.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: ctsps.cc/public//eee guwdee/eee/ee// /CodeSubmia sgionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
The contributions of our paper are mainly theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
The contributions of our paper are mainly theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
23

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The contributions of our paper are mainly theoretical.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:///uurpps..ccppppe/l/eaaaaa
Answer: [Yes]
Justification: We have reviewed the NeurIPS Code of Ethics, and our research was conducted in accordance with it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
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 particular applications, let alone deployments. However, if there is 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 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The contributions of paper mainly theoretical and pose such risks.
Guidelines:
The answer NA means that the paper poses 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 best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [Yes]
algorithms and Bearning-augmentnn mechanisms, and our related work discussion appropriately cites all prior work and its contributions.
Justification:
We utilize models
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 dataset.
The authors should state which version of the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi wwwode.tcod...c. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
25

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's 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 new assets.
Guidelines:
The answer NA means that the paper does release 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.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
26


Reviews:
[{"review_id": "3ntQsqPtRQ", "reviewer": "Reviewer_zBmc", "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.\n\nIn 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.", "questions": "See weaknesses section.", "limitations": "Yes the authors have addressed any negative societal impacts.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper's results are novel, cleanly presented, and indeed strictly improve upon several bounds in literature. The results on the line are not particularly surprising---e.g. Theorem 1 is just a short proof-by-contradiction given the reduction of Lemma 1 which seems to be largely implied by PT13---but are well-written and an accessible warmup to the plane results, which appear to be the main contributions of the paper. \nIn terms of the results on the plane, although Theorem 6 also is not particularly surprising---circles have three degrees of freedom and one should expect mechanisms to really only depend on the reports of extremal agents, which on a plane should always be about three in practice---verifying the result is still non-trivial and the paper gives a clean exposition and proof.\nThe paper also benefits from a collection of various observations; for example, the lower bound of Theorem 2 seems to just be a short note that PT13's 1d lower bound can be easily lifted to 2d. \nOverall the paper is also very well written and gentle.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful comments and suggestions. We actually think that our 1-dimensional results are quite significant on their own and much more than a warm-up for the two-dimensional ones. We provide some justification for this fact in response to the reviewer's question below.\n\n\n\n* **Reviewer:** \"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.\" \n\n**Response:** Lemma 1 is, indeed, novel, and we do not see how it could be implied by any argument in PT13. To maintain the robustness, consistency, and truthfulness guarantees throughout this reduction, we do make use of linearity of expectation, however, there is much more to this proof than that. Specifically, note that there can be an infinite number of ways to rearrange the probability that a mechanism assigns to outcomes in $(x_L, x_R)$ to get an OnlyM mechanism without affecting the expected cost of the two agents located at $x_L$ and $x_R$. For example, we could first replace the outcomes in $(x_L, x_R)$ with a single outcome whose coordinate corresponds to the expected coordinate of these outcomes, and then express this single outcome as a convex combination of $M$, $x_L$, and $x_R$ (and there can many such convex combinations). However, maintaining the robustness and consistency guarantees limits the ways in which we can do that, and the particular way in which we rearrange the probability is really crucial for us to maintain the very delicate truthfulness property. The part of our argument that really leverages this subtlety starts at Line 244, and it argues that if the agent located at $x_L$ were to lie and report a location further away from the other agent (i.e., $x'_L < x_L$), then the amount of probability that the modified mechanism would assign to $x'_L$ instead of $x_L$ would penalize the agent for the lie more than any benefit that the agent could get from this lie. \n\nAlthough this is one of the more technical parts of the proof, we had to really compress it in order to fit the results within the page limit, but we would be happy to emphasize this part of the proof much more in the next revision of the paper and to explain how some alternative approaches would fail to maintain truthfulness, robustness, or consistency.\n\nFurthermore, to make the reduction of Lemma 1 easier to follow, we have added a figure. You can find it as Figure 1 in the PDF file that we uploaded in the general response.\n\n\n\n\n* **Reviewer:**\"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.\"\n\n**Response:** We agree with the reviewer. We will rephrase the statement to more clearly emphasize this assumption, as follows:\n\n>**Theorem 5 (Reworded).** Consider any instance that has only two extreme agents, i.e., $k = 2.$ Then, given predictions $\\hat{\\mathbf{e}} = \\langle e_1, e_2 \\rangle$ regarding the IDs of the 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.\n\n\n\n\n* **Reviewer:**\"Also, L372-L377 were a bit difficult to understand without drawing it out graphically by hand; perhaps a diagram would help readability.\"\n\n**Response:** We agree with the reviewer. We added a figure to make the proof of Theorem $6$ easier to follow. You can find it as Figure 3 in the PDF file that we uploaded in the general response.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aSGqFABAUg", "reviewer": "Reviewer_vBqc", "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.\n\n\nFor 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.\n\nFor 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.", "questions": "Major:\n\nI 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.\n\n\nMinor: \n- 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\\}$\n- Does Lemma 1 require the original randomized mechanism to be truthful?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "+) The paper gives pretty good results for one- and two-dimensional strategic facility locations.  In particular, the paper provides a complete characterization of Parato optimal mechanisms for the one-dimensional setting.  \n+) The writing is pretty good.  \n+) The consideration of various prediction settings may enrich the mechanism with prediction literature.", "weaknesses": "Some of the technical writing is unclear.  I will list some in the following sections.\n\n- Lemma 1 should quantify $\\alpha$ and $\\beta$.  Theorem 3 should quantify $\\epsilon$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful comments and suggestions.\n\n* **Reviewer:** Lemma 1 should quantify $\\alpha$ and $\\beta$.  Theorem 3 should quantify $\\epsilon$.\n\n\n**Response:** Thank you for pointing this out. We have now quantified all these parameters and we provide the reworded statements below. Furthermore, we took this opportunity to change $\\epsilon$ to $\\delta$ in the statements of Theorem 3 and Theorem 4 to be consistent with our notation in Section 3.\n\n>**Lemma 1 (Reworded).** For any problem instance involving two agents with reported locations $\\mathbf{x} = \\langle x_L, x_R \\rangle$ on the line, and any randomized mechanism that is truthful in expectation and achieves $\\alpha$-consistency and $\\beta$-robustness for some $1 \\leq \\alpha \\leq \\beta$ over this class of instances, there exists a randomized $OnlyM$ mechanism that is truthful in expectation and achieves the same consistency and robustness guarantees.\n\n>**Theorem 3 (Reworded).** For any $\\delta > 0$, there is no deterministic truthful mechanism that is $(2-\\delta)$-consistent and $(1+\\sqrt{2}-\\delta)$-robust, even if it is provided with full predictions $\\hat{\\mathbf{x}}$ (the location of each agent).\n\n\n\n>**Theorem 4 (Reworded).** For any $\\delta > 0$, there is no randomized mechanism that is truthful in expectation, $1$-consistent, and $(2 - \\delta)$-robust, even for two-agent instances and even if it is provided with full predictions $\\hat{\\mathbf{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.\n\n\n\n* **Reviewer:** \"is the OnlyM mechanism at line $248$ well defined? \nThe distribution needs the knowledge of $x_L$, which is not part of the input.\"\n\n**Response:** The line that the reviewer is referring to is actually not proposing a mechanism. The mechanism that is being analyzed throughout the proof is the one already defined in the second paragraph of the proof. The argument here starts with the distribution that the original mechanism, f, would output if the agent were to report $x'_L < x_L$. Then, it modifies this distribution to get one that yields the same cost for the agent at $x_L$ but only outputs no locations in $(x'_L, M')$ other than $x_L$ and $M$. It is this distribution that Line 248 describes and the reviewer is correct that a mechanism could not guarantee this, as it would require knowledge of $x_L$, which is private. However, this \"intermediate\" distribution is then further modified, starting at Line 251, to yield a probability distribution which never returns any outcomes in $(x'_L, M')$. It is this final distribution that is equivalent to the output of the mechanism defined in the second paragraph of the proof if it were provided with input $x'_L$ and $x_R$. Note that this mechanism does not need to know $x_L$, so it is a valid mechanism. Due to space limitations, we have to really compress this part of the proof, which makes it harder to read, but we will make sure to dedicate a bit more space to it in the next revision. We would also be more than happy to clarify this proof further, or even provide a fully rewritten version of the proof, if this would help convince the reviewer that there is no correctness issue here. \n\n\n\n* **Reviewer:** \" Does Lemma 1 require the original randomized mechanism to be truthful?\"\n\n**Response:** Yes, the original randomized mechanism is required to be truthful and we have updated the statement of the Lemma 1 to mention this explicitly (see the reworded lemma statement in our first response, above).\n\n\n* **Reviewer:** What is formal definition of $OnlyM$ mechanisms? Given report $x$, and prediction $*$, $supp (M(x, *)) = x_L, x_R, M$\n\n**Response:** No, the support of $OnlyM$ mechanisms can also include any point outside the $[x_L, x_R]$ interval. The only restriction is that their support within $(x_L, x_R)$ is just $M$ (see Line 203). To make this part clearer, we will include the following formal definition: \n\n> **Definition ($OnlyM$ mechanisms)** A mechanism $f$ is an $OnlyM$ mechanism if $P[f(\\mathbf{x}) \\in (x_L, x_R) \\setminus \\{M\\}] = 0$, where $x_L$ is the leftmost reported location, $x_R$ is the rightmost report location, and $M = (x_L + x_R)/2$ is the midpoint of the two.\n\nFurthermore, to make the reduction of Lemma 1 easier to follow, we have added a figure. You can find it as Figure 1 in the PDF file that we uploaded in the general response.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sRUnRxO4dB", "reviewer": "Reviewer_MNoo", "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). \n\nFor 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.\n\nFor 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.", "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$?\n* 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.\n* Have you considered this problem in a general metric space? Are there any straightforward results?", "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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is nicely built on prior work of both the classic facility location problem and mechanism augmentation with machine-learned predictions, which gained much attention in recent years. The paper is mostly well written and I enjoyed reading it. The theoretical results are solid and I think would be valuable for the research community.", "weaknesses": "* 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. \n* Minor comments\n  * 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.\n  * Page 2, line 70: 2 + $\\delta$ robust -> 2 - $\\delta$ robust\n  * Page 3, line 121: need a space in “design,Agrawal”\n  * 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful comments and suggestions.\n\n* **Reviewer:** Minor comments. \n\n**Response:** We agree with all the suggested changes and have applied all of them.\nRegarding the first comment, we have edited the statement as follows:\n\n> We then turn to mechanisms augmented with the strongest predictions and show that no such deterministic mechanism can simultaneously guarantee better than $2$-consistency and better than $1 + \\sqrt{2}$-robust, and no randomized one can simultaneously guarantee $1$-consistency and better than $2$-robustness.\n\n\n* **Reviewer:** \"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$?\" \n\n**Response:** Yes, the analysis of Lemma 1 does imply that neither one of the two agents would misreport. Note that while we focus on the potential misreporting of $x_L$, we could directly apply symmetric arguments for the potential misreporting of the other agent. Furthermore, while we analyze the incentives of the agent located at $x_L$, we do not need to make any assumption regarding the report of the other agent, i.e., we do not need to assume that the other agent reports truthfully. Therefore, the analysis proves that an agent has no incentive to misreport, irrespective of what the other agent reports. Finally, the argument that we provide for the case that $x'_L > x_L$ (i.e., that \"the cost of the agent is the same across the two mechanisms'') also applies if $x_L'> x_R$. Specifically, the only thing that this argument uses is that the points that are affected by the lie are all on on the same side of $x_L$ (in this case all the points that are affected have coordinates greater than $x_L$). As a result, the cost of the agent located at $x_L$ is uniquely determined by the expected coordinate value of these points (the ones that lie on its right), and the two mechanisms yield the same expected coordinate value for these points. \n\nAlthough our analysis is correct and the mechanism is well-defined, we agree with the reviewer that the writing is somewhat confusing (e.g., not being clear enough regarding the distinction between reported locations and true locations), so we plan to revisit the part of the proof that discusses truthfulness and add more details. In the meantime, we would be more than happy to provide the reviewer with any additional details to convince them that there is no issue with the proof (e.g., we would be happy to provide a completely rewritten version of the proof).\n\n* **Reviewer:** \"I wonder if you have explored the total social cost objective.\" \n\n**Response:** We believe that exploring this problem with total social cost is a very interesting direction.\n\nWe know that the median mechanism gives the optimum solution in one dimension. Therefore, there is no need for prediction in the line metric. The coordinate-wise median achieves a $\\sqrt{2}$ approximation in the Euclidean plane metric, and Agrawal et al. (2022) studied this problem with predictions in the deterministic setting.\n\nSince there are no known randomized mechanisms that strictly improve the total social cost over the best-known deterministic mechanisms, we decided to focus solely on egalitarian social cost (for which there are more studies beyond the line metric, such as Alon et al. (2010), who studied truthful mechanisms on circles and trees with egalitarian social cost) and explore randomized mechanisms with several prediction settings.\n\nMoreover, we believe that for any learning-augmented problem, studying different prediction settings (ideally all possible settings) and establishing different bounds (ideally tight) is important and currently missing from the literature.\n\n* **Reviewer:** \"Have you considered this problem in a general metric space?\"\n\n**Response:** We believe that exploring this problem in more general metrics is also a very interesting direction. However, we are still a few steps away from addressing it.\n\nCurrently, there are no tight results in the randomized setting, even in the Euclidean plane. When no tight bounds are available, it is unclear whether an improvement with predictions is due to the power of predictions alone or if it is also possible without predictions.\n\nThe main challenge is the lack of characterization for randomized mechanisms, both in the Euclidean plane and in more general metric spaces. Although we could not find a characterization for randomized mechanisms in the Euclidean plane or make our results (with or without predictions) tight, we have made progress toward this goal.\n\nMoreover, we believe that some of our techniques can be extended to more general metrics. For instance, with more complicated arguments, we could modify our Centroid Mechanism on Extreme Agents for Euclidean space to achieve better than 2-consistency and 2-robustness.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1r3s2Ivmsq", "reviewer": "Reviewer_hDFx", "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.\n\nThe 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.", "questions": "- Could you add a discussion / reference for why the 1-d lower bound does not hold in 2 dimensions?", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper considers a very natural problem. The proposed mechanism is very accessible and easy to follow.\n- The paper has been well-written and is nice to read.", "weaknesses": "- 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.\n- 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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful comments and suggestions.\n\n* **Reviewer:** \"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.\"\n\n**Response:** Although many of our results take the form of impossibility results, we do prove that all these lower bounds are tight, i.e., achievable by truthful mechanisms. These tight bounds provide a complete picture for a natural problem, they fully capture the power and limitations of learning-augmented mechanisms in this setting, and they can be very useful information for designers, even beyond their theoretical value. \n\n\n* **Reviewer:** \"adding a small picture would help improve readability of many proofs\"\n\n**Response:** We agree with the reviewer and we have now enhanced our paper with additional figures: we have added one figure in Section 3 to clarify the proof of Lemma 1, and two figures in Section 4 to make the proofs of Theorem 2 and Theorem 6 easier to follow. You can find these three figures in the PDF file that we uploaded in the general response.\n\n\n * **Reviewer:** Could you add a discussion / reference for why the 1-d lower bound does not hold in 2 dimensions?\n \n**Response:** This was, indeed, quite surprising for us as well when we first realized it, and it appears like no prior work has made this interesting observation. To provide more intuition regarding this fact, we have now added the following paragraph before Theorem 2. Thank you for the suggestion.\n\n\n> Since the problem of designing good facility location mechanisms in 2-dimensions is ``harder'' than the 1-dimensional one, it may seem counter-intuitive at first, but the lower bound that prior work proved for all 1-dimensional instances does not extend to 2 dimensions. The reason is that the design space for 2-dimensional mechanisms is much richer, and the known lower bounds apply only to the more restricted class of 1-dimensional mechanisms. For example, consider a simple instance with just two agents in two dimensions. For this 2D instance, the mechanism can return a location for the facility that is not on the line that contains the two agent's location, 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 on the line), but returning a location that is not on this line also allows the designer to potentially affect the incentives of the participating agents in new and non-trivial ways that are impossible in the 1-dimensional case. Specifically, returning points that are not on the line allows us to induce previously impossible cost vectors: for a toy example, note that in a 1-dimensional instance involving two agents at distance 1 from each other, the only facility location that causes the same cost to both agents is the mid-point between them, leading to a cost vector of (0.5, 0.5). However, in 2-dimensions we can induce a cost vector of $(c, c)$ for any $c>0.5$ by just 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 will not lie; e.g., 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, depending on their reports. Although we conjecture that truthful mechanisms are always better off returning a facility on the line containing the agent's locations in the aforementioned instance, proving such a result appears to be non-trivial and, due to this additional flexibility for the mechanism in two dimensions, proving inapproximability results for this broader class of mechanisms is a harder problem and seems to require new techniques and insights.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for the time and effort they dedicated to evaluating our paper. We have provided individual responses for their questions and would be more than happy to provide additional details if any of these responses do not fully address the reviewers' concerns. Attached to this response you can find a PDF file that provides new figures that we have added to enhance the readability of some of our proofs, following the reviewer's suggestions and feedback.

Meta-review: 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.
Decision: Accept (poster)