MAC Advice for facility location mechanism design
Authors: Zohar Barak
Anupam Gupta
Inbal Talgam-Cohen
Venue: NeurIPS 2024 poster (2024)
Keywords: Algorithms with Predictions
MAC Predictions
Facility Location
Discrete Optimization
Primary area: algorithmic_game_theory
TL;DR: We define a notion of Mostly Approximately Correct predictions, and use them to get better strategyproof mechanisms for facility location.

Abstract: Algorithms with predictions are gaining traction across various domains, as a way to surpass traditional worst-case bounds through (machine-learned) advice. We study the canonical problem of $k$-facility location mechanism design,
where the $n$ agents are strategic and might misreport their locations. We receive a prediction for each agent's location, and these predictions are crucially allowed to be only "mostly" and "approximately" correct (MAC for short): a $\delta$-fraction of the predicted locations are allowed to be arbitrarily incorrect, and the remainder of the predictions are required to be correct up to an $\varepsilon$-error. Moreover, we make no assumption on the independence of the errors.
Can such "flawed" predictions allow us to beat the current best bounds for strategyproof
facility location?

We show how natural robustness of the $1$-median (also known as the geometric median) of a set of points leads to an algorithm for single-facility location with MAC predictions. We extend our results to a natural "balanced" variant of the $k$-facility case, and show that without balancedness, robustness completely breaks down even for $k=2$ facilities on a line. As our main result, for this "unbalanced" setting we devise a truthful random mechanism, which outperforms the best known mechanism (with no predictions) by Lu et al.~[2010]. En route, we introduce the problem of "second" facility location, in which the first facility location is already fixed. Our robustness findings may be of independent interest, as quantitative versions of classic breakdown-point results in robust statistics.

MAC Advice for Facility Location Mechanism Design
Zohar Barak
Anupam Gupta
School of Computer Science
New York University and Google Research anupam gaangggggeuee. edu
Tel Aviv University
zoharbarakCmail. bau.ac...
Inbal Talgam-Cohen School of Computer Science
Tel Aviv University
inbaltalgaam@gmail. com
Abstract
Algorithms with predictions are gaining traction across various domains, as a way to surpass traditional worst-case bounds through (machine-learned) advice. We study the canonical problem of k-facility location mechanism design, where the n agents are strategic and might misreport their locations. We receive a prediction for each agent's 's location, and these predictions are crucially allowed to be only "mostly" and "approximately" correct (MAC for short): a 8-fraction of the predicted locations are allowed to be arbitrarily incorrect, and the remainder the predictions are required to be correct up to E-error. Moreover, we make no assumption on the independence the errors. Can such "flawed" predictions allow us to beat the current best bounds for strategyproof facility location?
We show how natural robustness of the 1-median (also known the geometric median) of a set of points leads to an algorithm for natural "balanced" variant of the
location with
MAC predictions. We extend results k-facility case, and show that without balancedness, robustness completely breaks down even for k = 2 facilities on line. As our main result, for this "unbalancedd" setting we devise a truthful random mechanism, which outperforms the best known mechanism (with no predictions) by Lu al. [2010]. En route, we introduce the problem of "second" facility location, in which the first facility location is already fixed. Our robustness findings may be of independent interest, as quantitative versions of classic breakdown-pon point results in robust statistics.
Introduction
Algorithms with predictions is popular field of study in recent years within the paradigm of beyond the worst case analysis algorithms - see Mitzenmacher and Vassilvitskii (2022) for comprehensive survey, Motivated by developments in machine learning, this area assumes that algorithms can access predictions regarding the input or solution, thus leveraging predictability in typical computational problems. Recently, Agrawal et al. (2022) and Xu and Lu 2022) proposed to study predictions in the context of mechanism design, where they have the potential to transform existing designs by adding information about agents' private knowledge (see Balkanski et al. (2023a)).
Our focus in this work is on the canonical problem of facility location. The (utilitarian) k-facility location problem is as follows: Consider multi-set of points X C IRd and & facility locations; the cost of point x E X is the minimum distance between x and any of the l locations. The goal is to compute & locations that minimize the utilitarian cost, which is the total cost of points in X. In the context of mechanism design, the points X are the privately- known true locations of strategic agents,
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

and the mechanism receives location reports (see Chan et al. (2021) for a recent survey). Facility location mechanism design with predictions has been studied by Agrawal et al. (2022); ; Xu and Lu (2022) We diverge from previous work by assuming prediction for each point that is, the advice X" consists of a prediction xy for every 24 E X. Importantly, our measure of prediction error allows for very large errors (outliers) for a d-fraction of points (hence we call it the "mostly approximately correct" model). Our work shows how to get improved bounds despite these large errors, and can thus be of interest beyond facility location.
Standard worst-case prediction error. In the majority of the literature, the goal of (algorithm or mechanism) design with predictions centers around two seemingly conffiiiinnn properties: robustness to erroneous predictions, and consistency with predictions that are non erroneous. fairly common way of achieving both consistency and robustness is interpolating between the approaches of com- pletely following the predictions, and applying the best worst-case algorithm while disregarding the predictions. An ideal design is one that gracefully transitions as the prediction error increases from optimal performance when the prediction is correct, to the best-known worst-case performance (Lykouris and Vassilvitskii 2021; Purohit et al. 2018 Agrawal et al. 2022). By definition, achieving such graceful degradation hinges on how the prediction error is measured.
The most common measure of prediction error is arguably the distance between the predicted and actual values. If X {ai...., .n. contains the actual values and X' = ........ 2n, is the prediction, the error is defined as 17 (p(X X'), where fp represents either the & norm (t) = E; [t,/) or the &o norm (f (t) max; [t This is "worst case" measure of prediction error, since a single deviation in one of the entries can significantly inflate the error. Prediction errors measured this way appear in the context of ski rental Purohit et al. (2088),) online caching [ykouris] and Vassilvitskij (2021) Rohatgi (2020). the secretary problem Antoniadis et al. (2020). single-item auctions Xu and Lu| (2022), and many other problems. In what follows, we address this type of prediction error as the "worst case" error model.
Motivation for alternative measure. We demonstrate the need for an alternative measure of prediction eπтоr combined with new algorithmss through the following k-facility location instance, in which a single error causes the optimal solution for prediction X' to perform badly for the actual dataset X
Example 1 (Sensitivity of 2-facility location on a line). Let = 2, and assume the n agents' actual locations X are divided evenly between O and I the real line. Let X' be the prediction, with all coordinates predicted accurately except for a single coordinate i, which is predicted erroneously to be located x², M >> While the optimal solution for X is place the k: 2 facilities at O and 1 for a total cost of zero, in the optimal solution for X' one of the facilities moves to M. This solution performs badly for X- the approximation ratio compared to the optimal solution is unbounded.
Predictions
Real
n/2
n/2-1
1
n/2
n/2
1
M
0
Figure I: Illustration of Example D the predictions X' are on the left side and the real points X are on the right side. The triangles are the optimal facility locations for the points. A single bad prediction translates into an unbounded "worst case" error and approximation ratio.
In many MI contexts, it is very possible that small fraction of points have a large "worst case" prediction error - even excellent predictors may err on a certain fraction of the dataset. This motivates alternative measures of prediction accuracy. Concretely, we ask:
Question 1. For 2-facility location on line (as in Example 7 can we design a mechanism that uses agent reports get a good solution despite a large "worst case" prediction error?
We answer this question positively, proving that, using agent reports, it is possible to design resilient mechanisms against adversarial "worst case" errors. The main take-away is that predictions can still
I Predicctions have also been studied for online non-strategic version of facility location - see Appendix Simillarly, bad performance persists for any algorithm that does not get location reports from the agents.

---

be valuable despite high "worst case" prediction error, if the fraction of such grossly-erroneous points small. In other words, high "worst case" prediction error may not always justify "throwing out" the predictions and settling for the best worst-case guarantee (although it is currently standard in design with predictions). Our new error model and results thus suggest a new pathway for effectively utilizing predictive advice in strategic settings, despite significant uncertainties in the predictions.
2
Overview of Contributions
2.1
Our Model
We introduce MAC predictions where MAC stands for Mostly Approximately Correct. This formula- tion captures the essential features of some closely related previous models, c.g., the model (Azar et al. 2022) formulated for online metric problems, and the PMAC model of (Balcan and Harvey 2018 formulated in the context of learning submodular functions. A vector of predictions X" is MAC 8) with respect to dataset X if at least (1 - 5))-factiion (i.e., most) of the predictions are approximately correct up an additive E-error. Intuitively, if we do not think it is likely that most of our predictions will be close to being correct -we would typically refrain from relying on them in pecision-making processes. Throughout, ö [0, 0.5) is assumed to be small (but can still be constant). Crucially, when a prediction is not approximately correct (i.e., it belongs to the d-fraction of incorrect predictions). the error is allowed to be arbitrarily large. Also, the 5-fraction of wrong predictions is allowed to be arbitrary among all possible subsets of that size (there is no assumption of independence). We show that despite their adversarial nature, and the fact that the prediction error is unbounded, such predictions can be used, in combination with strategic reports, to produce a solution with better cost compared to the best no-prediction solution.
The MAC prediction model is suitable for capturing errors from a variety of sources including ML- generated predictions, data that accommodates changes over time, data corrupted by a malicious user, and expert advice (see Appendix for more details). The accuracy parameters e, 8 of the MAC model can also be viewed as confidence parameters. The use of confidence parameters is prevalent in the algorithms with predictions literature (see, e.g.. Agrawal et al. (022)). Arguably, e, 8 are highly explainable compared to most confidence measures in the literature, and it is also quite natural to estimate them from data.
2.2 Our Results
We design both deterministic and randomized strategyproof anonymous mechanisms for facility location problems, with MAC predictions of the n agent locations. A preliminary simplifying observation is that in the context of facility location, it suffices to consider mostly-correct (i.e., MAC(O, 5)) predictions, since handling a nonzero approximation parameter & follows directly (see Appendix C
Randomized mechanism design. As our main technical result, for 2-facility location on a line we design a randomized mechanism that guarantees an expected approximation ratio of 3.6 + O(8) (see Algorithm 4 and Theorem 99) For sufficiently small (but still constant) 8, this improves upon the best-known no-prediction expected guarantee of 4 by Lu et al. (2010). (The mechanism of Lu et al. (2010) works for any metric space.) This result provides a positive answer to Question [ justifying the take-away that predictions with high "worst case" error are useful. We give brief description of the mechanism in Section 2.3 Note that 2- facility location on line was also studied by Procaccial and Tennenholtz (2013). and they provided a deterministic mechanism with an (n 2) approximation ratio, which is tight (Lu et al. 2010; Fotakis and Tzamos, 2014).
Deterministic mechanism design. For single-facility location in R2, we design a mechanism that 46
guarantees an approximation ratio of ming1 + 1-26 vd) (see Algorithm | and Theorem 5). For sufficiently small (but still constant) 6, this improves upon the no-prediction guarantee of v by Mein (2019), which is tight for d = 2. For 3-balanced k-facility location with constant 1 (in any metric space), which a natural extension of facility location where at least a 3-fraction of the n points must be assigned to each of the & facilities (for cost-sharing or load boad-balancing reasons), we design simple strategyproof mechanism which guarantees an approximation ratio of c + O [ where c is constant (see Algorithm 7 and Theorem
1
For sufficiently small (but still constant) ö, this greatly
3

---

improves upon the best-known no co-prediction guarantee of n/2 - by Aziz et al. (2020) (we remark that Aziz et al. (2020) study a variant called capacitated, which our result apples)
While we have not optimized the constants, our conceptual contribution is in showing that even if the worst case error of the predictions is unbounded, it can still provide useful information for improving the performance of facility location mechanisms when coupled with strategic reports. In other words, the MAC model allows achieving robustness outliers while still beating the no-prediction performance. Our single-facility result demonstrates how the accuracy parameter of the model, 6, can serve as a trust parameter which has natural explainability. Another interesting feature of our results is that utilizing MAC predictions seems to suggest richer family of mechanisms than standard interpolations of ino-predcction" and "complete trust" in the predictions.
Below we give a summary of the results in tables.
Deterministic Mechanism Design Best known "no predictions" approximation ratio
Problem
Approximation ratio ob-
tained using MAC predic- tions
Single facility location in 12d Vd
1 0(8)
3-balanced facilities in Rd Linear (O(n))*
A constant depending on 6,
Table Deterministic Mechanism Design.
*The linear appoximation ratio is of Aziz et al. (2020) for the capacitated facility location variant where there is an additional constraint of maximum cluster size. 'he 3-balanced variant of the problem was not studied without predictions, but is comparable to the capacitated variant, since minimum cluster size (as in the balanced variant) implies a maximum cluster size (and for 2, maximum cluster size implies minimum cluster size as well).
Random Mechanism Design Best known "no predictions" approximation ratio
Problem
Approximation ratio ob-
tained using MAC predic- tions
2 facility location on line
4
3.6 + O())
Table 2: Random Mechanism Design
2.3 Our Techniques and Roadmap
We break the problem into two natural conceptual steps. First, we establish what can be done by just using the predictions this requires us to show some stability properties of algorithms for k-medians. For some problems, such as the single facility location, we show that using only the predictions is enough to get good approximation ratio. For other problems, such 2-facility location, it is not enough, and thus we need to include the input in the computation. For this purpose, we show how to choose the first facility by just using the predictions, and way choose the second facility by taking the first facility and the input into account. Then, we show how the interplay between these parts allows us get better approximation. Let us now give few more details for these steps.
Robust statistics and the robustness of the geometric median and k-medians. We first develop quantitative versions of classic results in robust statisties on breakdown points, which may be of possible independent interest. Consider a location estimator, a function that gets n points in a metric space and returns k locations. Its breakdown point is the proportion ó of adversarially modiifee points it can handle before returning an arbitrarily far result from the original estimator. is the mean has breakdown point of 5 = 1/n (consider changing one point an arbitrarily large value) and that the median is robust with a breakdown point of = 1/2. However, the notion of breakdown point is qualitative, and does not reveal the relation between the fraction 5 of modified points, and how much the estimator changes. In Section 5 we fill this gap by defining measures of robustness (distance robustness (Definition 99) and approximation robustness (Definition 10). Next, show robustness properties of the median and its generalizations, showing that the cost of the geometric median
that
3- E-balanced means every cluster is of size at least Gn, and hence most (k 1)9r.

---

behaves smoothly as the fraction of modified points increases. These smooth robustness results prove crucial obtaining improved mechanisms for facility locations using predictions. Moreover, the robustness guarantees have interesting interpretations in the context of robust statistics and robust clustering in machine learning, and might also be of independent interest as explained in Appendix D
Second facility location. In Section 6.2.1 1 we introduce the second facility location problem. It is often the case that facilities are created incrementally and not all at once. Hence, is natural to ask how can we design a mechanism for choosing the location of a second facility (say second hospital) given an existing first one. We show that the random proportional choice (second step) used in the proportional mechanism by Lu et al. (2010) achieves a (tight) approximation ratio of 3 for the line metric, improving over the factor of in the general case for the second facility location problem.
The Robust Half Technique: Beyond interpolation. We generate half of the solution (the first facility location) from the predictions, and use the result together with the input (agent reports) to generate the other half of the solution (the second facility location). To generate the first half of the solution, we define and analyze robust location estimator we name BIG- BNGG-CLSTER--ON CEETER (which turns out to be a non-trivial task); Hence the name: "Robust Half". To generate the second half of the solution from the input (given the first half) we define and analyze the second facility location on the line problem. Finally, to combine the results we consider two cases: the input either induces a balanced clustering or an unbalanced clustering. We utilize the robustness results (both for balanced k-medians and for Big- CeCusle----eeteeeee Our mechanism differs from many existing designs which interpolate between the two approaches of trusting the predictions and using the no-predictions algorithm.
to show that in both cases we get good approximation ratio.
3 Related Work
Facility location mechanism design with predictions. In the "worst case" error model, Agrawal et al. (2022) show a mechanism for single-facility location on the real plane TR22. Their prediction consists of a single value representing advice for where to locate the facility, Given a trust parameter e [0, 1]. their mechanism guarantees an approximation ratio of at most 22 if the prediction is perfect, and 2/c++2 in the worst case. In theory, we could reduce the MAC model to the one studied by Agrrwal et al. (2022), by setting their single prediction to be the geometric median of the MAC predictions. Then c can be determined according to 8. However, knowing ō and the 8-robustness of 1-Median, we can directly choose either the no-pre predictions mechanism the predictions' 1-Median, rather than interpolating between these two solutions.
Mechanism design for the 2-facility location on the line with predictions is studied by Xu and Lu (2022), where the predictions are for the locations of the agents. While they do not define an error parameter, their deterministic mechanism is in line with the "worst case" prediction error model: it achieves an approximation ratio of 2 if the predictions are perfect, and 2n if they are arbitrarily bad.
Two-facility location on a line mechanism design without predictions. In the setting of no- predictions, the best strategyproof deterministic anonymous mechanism achieves a tight approxima- tion ratio of n 2 Procaccia and Tennenholtz (2013): Fotakis and Tzamos (2014). In comparison, in our MAC model under the additional assumption that the number of agents assigned to each facility in the optimal solution is of minimum size 2(5n). the deterministic mechanism in Algorithm achieves a constant approximation ratio. Under no further assumption, our randomized mechanism in Algorithm g achievess constant expected approximation ratio for small ö.
Additional related work is deferred Appendix A
4 Formal Definitions
Let (V, d) be a metric space and ks n. E N. The input to the facility location problem is a multi-set X =
{x V". We are also given a prediction, which is another multi-set X' = (=f.... ., 2n) E V". The distance between a point u and a multi-set W is d(u, W) = min w d(u, w). The Hausdorff distance between multi-sets U. W E V is
du (U, == max[max d(u, W), max d(w, U}}, NEU
WEW
that is, the maximum distance between a point in multi-set and the other multi-set.
5

---

Definition 1. Fix E 2 O. For x. E V, we say x' is an e-correct prediction of x if d(z,z²) S otherwise we say it is E-incorrect.
Definition 2. The (e, neighbboooo of multi-set X E V is defined to be all predictions X' E V such that H [n]] x4 is an s-incorrect prediction of mi3 S..
The (0, neeghhbooooo of X is often just referred as the r-neighborhood of X.
Definition (Mostly Approximately Correct (MAc) Predictions). Fix E 2 0, E [0, 0.5). The point set X' is an (e, 8)-M prediction for X if X' belongs the (E, 6, -eighhoohooodd (nidiiX)-neighhoohhoodd of X.
Definition& 4 (Location Estimator). For k E N, fufucttion f(X): V + V is called a location estimator.
Some common examples of location estimators with for points on the real line are the minimum, maximum, mean, and median; for general metric spaces, k-means and k-medians are well-studied examples (k-means is similar to k-medians with squared distances). For k = 1 and V IR the k-medians solution is also called the GEOMETRIC- -MDIAN which is generalization of the median to higher dimensions. different such median generalization is the COORDINATE- WISE- MEDIAN: Definition 5. For a multi-set of n point X C Rd: COORDINATE- WIDEMMEIAN := (4,....,ua La) where where 1 is the median of the multi-set of the thth coordinates of X for all j [d].
Definition 6 (k-medians cost function). Given multi-sets X E V", F E Vk, the k-medians cost function is
medg(X, Σ dd,,
DEX In the context of the facility location problem, this function is also known as the social cost function or the utilitarian goal function.
The k-medians problem takes as input multi-set X E V and outputs multi-set F that minimizes this cost function. The minimizer P** E V the problem is called the k-Medians solution. k-Medians can be viewed as a location estimator of X that optimizes the k-medians objective function:
Definition 7 (Center-Induced Partitions). collection of centers F = [f...... f&] S V induces partition 6 = .C Ck) of the dataset X C2 C {x E X d(x, fi) S d(x, f,) This partition is called the clustering of X induced by F. This partition (or clustering) is 3-balanced if [k).
[C]] 2 X for all
Note that a collection '6 need not be unique, since points in X can "choose" between any of their closest centers in F.
Definition 8 (3- (3-balanced k-median). The 3-balanced k-medians problem takes dataset X E V as input, and outputs centers F Vk along with an induced 3-balanced partition '6 of X: the goal is minimize the cost function med,, F) = Σvex d(x,F).
This problem is similar to the lower-bounded k-meddan problem where want to output F (Ji,..., Sx} E V as well as a partition [Cr,..., Ct } of X such that |C,| 2 X) in order to minimize Erec, d(xr,, fi) (see Han al. (2020), Wu et al. (2022)). ). A significant difference between that definition and ours is that we require the particion to be induced by F (in the sense of Definition 7 which is not required by lower-bounded k-median.
5 S 6-Robustness of Location Estimators
In this section we define notions of robustness with respect to changing d-fraction of the points (hence referred to as 6-robustness) and analyze the 5-robustness of 1-Median and k-Medians. These results will be very useful for the mechanism design for facility location with predictions. We consider two robustness notions for location estimators: The first notion measures the movement in the solution (as measured by the Hausdorff distance), and the second measures the change in an objective function applied to the solution.
Definition 9 (Distance Robustness). Let 2 0, 8 E (0,0.5). For location estimators f. f. V Vk we say that f is (p. robbancce-obbss with respect to f for any X v and any X' in the 6| neighborhood of X.
dh (I(X). s

---

If f. we say that is (p.3))dittance-robuus
In the next definition, cost function is evaluated for the same dataset X E V with respect to two different solutions f(X) and f(x').
Definition 10 (Approximation Robustness). Let 2 1, e 00,0.5) and let F V x + Rzo be cost measure. For location estimators J, f. V - Vk. we say that is (7. ap-aapproiimaiioo-rhaae
solution for cost function F with respect to f ifr any X E v and any X' in the 6|X neiighhhoooo of X,
F(X, S
xxX(())(( F(X.J(X))
(2)
Is= f. we say that f is (7,8))-pprroen -ppproximmation--oiis solution for F. If Eq. 2 only holds for datasets E y for some restricted to instances y
V we say that f is (7,6) ( pappaappoammaioonubaaae solution for F
We give the the following d-robustness results. For the 1-Median:
me),(X) (
Theorem 2. For < 1/2, the 1-Median location estimator is ((1-28) [X] ,6) -iisaanc--
robust, where med1 (X) is the optimal cost of the geometric median, that is: med1(X) = Ex.x d(r;; GEOMETRIC-MEDIAN(T))
16 Corollary 3. For 8 1/2, the 1-Median estimator is (1 1-28 6) approxxmmatioon for med1-
Recall Example from Section In this example, choice of achieves a good (bounded) approximation for the 2-medians problem on both X and X'. Given this negative example, turn balanced version of k-medians for which are able give robustness guarantee. The following theorem shows that computing the best "slightly less balanced" solution on the predictions has cost (on the original dataset X) that is close the optimal one.
centers simultaneously
Theorem 4. Let 2k + 2. Consider the algorithm B that computes the optimal (b 1 1)l-balanced k-medians solution on its imput. For any instance X & V of the bö-balanced k-medians problem with optimal solution G, let X' E 4 belong the 6-neighborhood of X. The algorithm B, when given X', returns solution H such that
2k
du (n H)
Σ ZEX
d(x, G).
8|X| (b - 2 - -2k)
Moreover, the k-medians cost med, (X, H) S (1+ b-2-2k balanced partition "6 of X.
4k
med G), and H induces a (b (b-2)6-
For a fixed value of k. this theorem gives solution H ihat (0-2))-balanced and also (1+0(1/)) 6)- approximation-robus with respect to the best bó-balanced solution.
Missing proof's are provided in Appendix E The intuition behind the proofs in this section is that since
most points (1 d) are shared between the actual instances and the predictions, any cost-minimizing solution for the predictions will be close (in terms of Hausdorff distance) to the cost-minimizing solution for the real points, thus resulting in a similar cost as implied by Lemma [0 Appendix
6 Mechanism Design for Facility Location with MAC Predictions
6.1 Warmup: Deterministic Mechanism Design for Facility Location
In this section we show how design deterministic mechanisms for facility location problems that utilize the MAC predictions to get better approximation guarantees. We do so by utilizing the 5-robustness results from Section 5 In the mechanism design setting, there are n agents with (true) locations X = {x; mechanism has access to location reports by the strategic agents, and also to X' (./....,, x which are the MAC(E. 5) predictions of the true locations X. The mechanism only has access to the reported locations
[n]] E I where d is the dimension of the facility location problem. The
(X) and the predictions (X'). For any strategyproof mechanism, the reported
locations will be the same as real ones (X X)) as illustrated in Fig.

---

Real
Reported
Predicted
There are three sets of points: The real locations X (black), the reported locations X (yellow), and the predicted locations X'bblu). The algorithm can only access X, X'. For any strategyproof mechanism, the yellow and black points overlap.
Figure 2:
As explained in Appendix C for the sake of the analysis we assume that = 0. All proofs can be found at Appendix F
For the single facility location problem (A: = 1): In this setting we assume 6 (or an upper bound
value) is known and thus we can simply check in advance if 1 + 1-26 S v or not, and use the algorithm that guarantees us the best approximation ratio.
48
Algorithm 1: Best- Beet-CChhie--innt---allliLLLLLL.
(1 + 1-28 Vd)
48
then return GEOMETRIC-MEDIAN(X"
else return COORDINATE- WISE- (ESS-MEDIAN(();
See Appendix F2 for clarification the computation of the geometric median.
Theorem 5. Algorithm is strategyproof and gets an approximation ratio of min
48 +
vd).
1-26
Supporting the weaker setting of high probability (only w.p. 1 o(3n)) MAC predictions: In Appendix F.3 we show how to achieve the same approximation ratio as in Theorem 5
For the & facility location problem: In similar way to the single facility, ministic mechanism for the & facility location problem with predictions, under some balancedness condition (see Appendix G The balancedness condition roughly translates minimum cluster size in the optimal solution. The resulting approximation ratio is bounded by 1 + 5-2-28 constant that depends on the minimum cluster size and 8.
also get deter-
4k
where b is
6.2 Randomized Mechanism Design for 2-Facility Location on a Line
We consider the 2-facility- locatton problem, where the metric is given by the real line R. Formally, our metric is over the point set V IR with d(x, y) = x - y/. There are n agents with locations the real line X {z)...... ... }. and the cost of solution G' /2 is med, G) are unknown, but we
Σx,x d(x; G)- In the mechanism-design setting, the agent locations are given (a) MAC predictions X' for these locations, as well as (b) the agents' reports for their locations. Unlike in the 3-balanced problem variation, we do assume the balancedness of the optimal solution, but handle the unconstrained case where the optimal solution might induce either balanced unbalanced clustering of X. In this section, present strategy-prodd radnom mechanism with a small (expected) approximation ratio.
Before doing so, solve two other problems. After we solve those in Sections 6.2.1 and 6.2.2 use the solutions in our mechanism for the 2-facility-location on line problem in Scction 6.2.3
6.2.1 The Second Facility Location Problem
First, we define another independent mechanism design problem (the second facility location) for which we show a randomized mechanism. We later use to solve the 2-facility-locaal location problem.
Definition 11 (Second Facility Location). Given metric space (V, d), dataset X E V", and a single facility hy V, the goal to find another facility hyr to minimize the 2-medians cost medg (X, (hs,,r)) hr)))

---

We consider the following random mechanism for the facility location on the line problem proposed by Lu al. (2010).
which is the second step of the
Algorithm 2: STCoND-PROPORTTONNN-MCCCAAAAA
(X, hs)
a, < d(z,, hs);
Pick h E X such that Pr[h = = 2/20
Lemma 6. SICOMD-FROOORTONNJ-MEEEEEEEE
is strategyproof for any metric space.
Theorem 7 (Second Facility Results). Let V =
TR. Fix any dataset X and first facility {gs). : For any second facility 9i e V; let (S, I") be partition of the dataset induced by F {gs, 97 The expected cost of SECOND-PROPORTIONNAL MEEALANSS given X and gs is:
E[med2 (X, {gs: gr }) s med] (S, {gs}) + med, (T, {9r1),
(3)
where gr is the second facility location chosen by SECOND- PWO.PPPPPPPPTTTVAAAAEEEEEEEE
We defer the proof' of Lemma 6 and Theorem 7 to Appendix [
See Remark 29 for tight example.
The algorithm prioritizes farther locations (belonging to agents who pay more if their location is not chosen) over agents that are near the first facility. The intuition for the ptrategyproofness is that if the agent deviates to different location, might be chosen with higher probability, but the agent will also pay more. The largest technical difference in the analysis from Lu et al. (010) is our introducing of a more delicate analysis for the line metric. We stress, however, that the better approximation ratio of 3 (rather than the ratio of 4 Lf et al. (2100) is due to the different nature of the problem both algorithms
(rather then the more delicate analysis) explanation for why the similar approach works better for the second facility problem is that the first facility fixed and so we do not have to pay the cost of "ggesssig it" done in Lu al. (2010).
tight for the line metric. One intuitive
6.2.2 The R-Robustness of the Big Cluster Center
Our randomized mechanism uses the predictions to estimate one facility, and randomly chooses the second facility. For this purpose, we come up with an algorithm to "estimate" the first facility location. We formally define what it means to "estimate" one of the two facilities, and then we quantify the distance and approximation robustness of the estimator. This is the last piece of the puzzle that we need for our randomized mechanism. The idea here is that even though Example shows we cannot simply compute the optimal solution, most of the predictions are correct and contain useful information: We can still get good estimation for one of the two centers of the optimal solution. In this section, we show an algorithm (location estimator), BIG-CLUSTER MIN-CLLUSERRCEETERR of the center of the bigger cluster center out of the two clusters induced by 2-Medians.
CENTER, that "estimates"
Definition 12 (BIG-CLLUSTER-COSSS
For any X = (II,.... Fn) E V let F be its optimal 2-median, and let '6 '6(X, F) be the induced clustering. Let BIG-CLUSTER (X) be the cluster in clustering '6 with at least Ix\/2 points (if both clusters have the same size BIG- BIG-CLUSTER(XX can be the one containing 1.). For E V, define
BIG- MIG-CLUTTER- COST(X,t) CLUSTER-COST(X. == med, (BIG-CLUSTER(X))))
Definition 13 (Big Cluster Location Problem). Given points X E V", the objective is to find point E V to minimize the cost function BIG-CLUSTER- COSERRCCOT((X))
We specifically focus on the line metric, and only consider X E instances where the clustering induced by 2-Medians( X) are bó-unbalanced for some (some constants) b > 1, 8 E [0, 1/2).
Algorithm 3: BEIO-CCLUSTER-CENTTEE
(hr., (R)) = (b- - 1)5 -BLAANED 2 2-MEDIAN(X);
L'= (2; X d((,,, h2) S ((2,,hR))
R' = S\L' L':
Return by if LE [R| and lgg otherwise;
'For any clustering induced by any 2 points in space, there is always one bigger cluster (that is, the cluster that contains at least half the points).

---

Theorem 8. Let y be the collection of all datasets in I. for which the optimal 2-medians induces no bó-balanced clusterings. Then for small enough (constant) 6. Algorithm BIG- FLLUSTR-CENNTEE is (1.8 + O ppy=pppoximmaionnoooe for the cost function instances y
CLJUTERR-COST restricted to
The intuition for the proof of Theorem 8 is that one cluster has big portion of the points, and most of them also appear in the predictions. Thus, in the cost minimizing solution computed on the predictions, there must be a big center "near" these points (since any solution far away from these points would result in a higher cost). The analysis is close to tight (see Remark 25 in Appendix H).
6.2.3 The 2-Facility Location Algorithm
Our randomized algorithm below first uses the CELUSTER-CENTEER procedure on the predictions to approximate the "big" cluster center, and then uses the PROIONOOPPOOORIOONAA-MMM
to approximate the second cluster center using only the agents' reports. (We set b E R>1 such that
the approximation robustness in Theorem Saarremmequall equuls 1.2.) The proof is at Appendix D
Algorithm 4: Robus--aaff-Meccanism/// X')
h BIG-CLUSTER- CELUSSTTER-CNTER(XX CENTER(X' b, 6) h1);
h2 = POI----POORRTTA--MMCIIIIIII Return (h1, h2):
Theorem 9. For a small enough (but still constant) 8: Algorithm 4 is strategyproof and has an expected approximation ratio of 3.6 + O()).
The proof uses most of the tools we came up with so far, and it considers two main scenarios: when clustering is bó-balanced and when it is unbalanced. In both cases, by leveraging the 8-robustness and the (randomized) strategic placement of the second
of 1 -meddian, 2-medians, big-cluster-cent facility, the mechanism ensures that the solution approaches the optimal cost.
Conclusion and Future Directions
We explore strategyproof facility location within our introduced MAC predictions error model. Our model integrates the trust level into the error model, handles outliers, and leads to new mechanism designs (that do not seem to be an interpolation between completely trusting the predictions and resorting a "no-predictions" method). To analyze our designs, we utilize distance and approximation robustness notions established in Section
An immediate question arising from our results is whether there is a deterministic mechanism with MAC predictions for 2-facility location on line that yields a constant approximation. Another avenue for future research is improving the approximation ratio by randomized mechanisms for this problem. One promising strategy entails refining the selection process for the first facility in [ which can lead to a superior approximation ratio. Our current mechanisms treat the multi-sets of predictions and reported values as independent entities; an intriguing direction for further investigation is to devise mechanisms that capitalize on the matching between predictions and agent-reported values, potentially yielding more accurate approximation ratio. Lastly, exploring the application of the MAC model to problems beyond mechanism design for facility location may yield insights into the efficacy of such predictions in diverse contexts.
Acknowledgements
We are grateful to Batya Berzack for comments earlier draft of the paper, and to Haim Kaplan, Michal Feldman, Amos Fiat and Yossi Azar for discussions about a previous version of the model. We would like to thank the NeurIPS 2024 anonymous reviewers for their comments on this paper. This work is funded by the European Union (ERC grant No. 101077862, project: ALGGOCOTTRACT. Pl: Inbal Yalgam-Cohen), a Google Research Scholar award, the Israel Science Foundation (ISF grant No. 3331/24), the Binational Science Foundation (BSF grant No. 2021680), and the National Science Foundation (NSF grant Nos.
and CCF-2006953).
10

---

References
Gagan Aggarwal, Rina Panigrahy, Tomás Feder, Dilys Thomas, Krishnaram Kenthapadi, Samir Khuller, and An Zhu. 2010. Achieving anonymity via clustering. ACM Transactions on Algorithms (TALG) 6, 3 (2010), 1-19.
Akanksha Agrawal, Tanmay Inamdar, Saket Saurabh, and Jie Xue. 2023, Clustering what matters: Optimal approximation for clustering with outliers. Journal of Artificial Intelligence Research 78 (2023), 143-166.
Priyank Agrawal, Eric Balkanski, Vasilis Gkatzelis, Tingting Ou, and Xizhi Tan. 2022. Learning- augmented mechanism design: Leveraging predictions for facility location. In Proceedings of the 23rd ACM Conference on Economics and Computation, 497-528.
Matteo Almanza, Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi, and Giuseppe Re. 2021. Online facility location with multiple advice. Advances in Neural Information Processing Systems 34 (2021), 4661-4673.
Idan Amir, Idan Attias, Tomer Koren, Yishay Mansour, and Roi Livni. 2020. Prediction with corrupted expert advice. Advances in Neural Information Processing Systems 33 (2020), 14315-14325
Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. 2021. A regression approach to learning-augmentt online algorithms. Advances in Neural Information Processing Systems 34 (2021), 00504-30517.
Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. 2022. Online algorithms with multiple predictions. In International Conference Machine Learning. PMLR, 582-598.
Keerti Anand, Rong Ge. and Debmalya Panigrahi. 2020. Customizing ML predictions for online algorithms. In International Conference on Machine Learning. PMLR, 303-313.
Antonios Antoniadis, Themis Goulcakis. Pieter Kleer, and Pavel Kolev. 2020. Secretary and online matching problems with machine learned advice. Advances in Neural Information Processing Systems 33 (2020), 7933-7944.
Yossi Azar, Debmalya Panigrahi, and Noam Touitou. 2022. Online graph algorithms with predictions. In Proceedings of the 2022 Anmual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 35-66.
Yossi Azar, Debmalya Panigrahi, and Noam Touitou. 2023. Discrete-Smoothness in Online Algo- rithms with Predictions. seirth-seventh Conference on Neural Information Processing Systems.
Haris Aziz, Hau Chan, Barton Lee, Bo Li, and Toby Walsh. 2020. Facility location problem with Algorithmic and mechanism design perspectives. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 34. 1806-1813.
capacity constraints:
Maria-Florina Balcan, Siddharth Prasad, and Tuomas Sandholm. 2023. Bicriteria Multidimensional Mechanism Design with Side Information. CoRR 2tbb//202.112344 (2023). https://doi.onn org/ 10. 40.48550/ARXIV 2302. 14234 arXiv:2302. 14234
Maria-Florina Balcan and Nicholas JA Harvey, 2018. Submodular functions: Learnability, structure, and optimization. SIAM Compur. 47, 3 703-754.
Eric Balkanski, Vasilis Gkatzelis, and Xizhi Tan. 2023a. Mechanism Design with Predictions: An Annotated Reading List. SIGecom Exchanges 21, (2023), 54-57.
Eric Balkanski, Vasilis Gkatzelis, and Xizhi Tan. 2023b. Strategyproof Scheduling with Predictions.
In 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, Januury 10-13, 2023, MIT, Cumbridge, Massachusetts, USA (LIPles, Vol. 251), Yael Tauman Kalai (Ed.). Schloss Dagstuhl- Leibniz-7entrum für Informatik, 11:1-11:22, https:/ //doi. org/10. 4230/LIPICS
ITCS. 111

---

Eric Balkanski, Vasilis Gkatzelis, Xizhi Tan, and Cherlin Zhu. 2023c. Online Mechanism Design with Predictions. CoRR abs/2310.02879 (2023). htttp:://di..oo
40450/555500 2310. 02879
arXiv:2310.02879
Amir Beck and Shoham Sabach. 2015. Weiszfeld's method: Old and new results. Journal of Optimization Theory and Applications 164 (2015), 1-40.
Ben Berger, Michal Feldman, Vasilis Gkatzelis, and Xizhi Tan. 2023. Optimal Metric Distortion with Predictions. CoRR abs/2307.07499 (2023). hntpp:://dol 1t..g/10.885500 ARXIVV 20.. 07495 arXiv:2307.07495
Giulia Bernardini, Alexander Lindermayr, Alberto Marcheti--Spaccamel Nicole Megow, Leen Stougie, and Michelle Sweering. 2022. A universal error measure for input predictions applied to online graph problems. Advances Neural Information Processing Systems 35 (2022), 3178- 3190.
Anup Bhattacharya, Dishant Goyal, and Ragesh Jaiswal. 2020. Hardness of Approximation of Euclidean k-Median. arXiv preprini arXiv:2011.00 1.0422/ (2020).
Hau Chan, Aris Ratsikas,,,, Bo Li, Minming Li, and Chenhao Wang. 2021. Mechanism Design for Facility Location Problems: A Survey. In Proceedings of the Thirtieth International Joint Confer- ence on Artificial Intelligence, IJCAI-21, Zhi-Hua Zhou (Ed.). International Joint Conferences on Artificial Intelligence Organization, 4356-4365.
https://doi... org/ 24963/ijcai.........///.. 2021/
596 Survey Track.
Moses Charikar, Samir Khuller, David M Mount, and Giri Narasimhan. 2001. Algorithms for facility location problems with outliers. In SODA, Vol. 1. Citeseer, 642-651.
Michael B Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, and Aaron Sidford. 2016. Geometric median in nearly linear time. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing. 9-21.
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian, and Nikos Zarifis. 2021. Learning online algorithms with distributional advice. In International Conference Machine Learning.
PMLR, 2687-2696.
Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. 2021. Secretaries with advice. In Proceedings of the 22nd ACM Conference on Economics and Computation. 409-429.
Ulrich Eckhardt. 1980. Weber's 's problem and Weiszfeld's algorithm in general spaces. Mathematical Programming 18 (1980), 186-196.
Yuval Emek, Yuval Gil, Maciej Pacut, and Stefan Schmid. 2023. Online Algorithms with Randomly Infused Advice. arXiv preprint arXiv:2302. 0536666000666. (2023).
Dimitris Fotakis, Evangelia Gergatsouli, Themis Gouleakis, and Nikolas Patris. 2021. Learning augmented online facility location. arXiv preprint arXiv:2107.08221 (2021).
Dimitris Fotakis and Christos Tzamos. 2014. On the power of deterministic mechanisms for facility location games. ACM Transactions on Economics and Computation (TEECC) 2, 4 (2014), 1-37.
Vasilis Gkatzelis, Kostas Kollias, Alkmini Sgouritsa, and Xizhi Tan. 2022. Improved Price of Anarchy via Predictions. In EC '22: The 23rd ACM Conference on Economics and Computation. 529-557.
Sumit Goel and Wade Hann-Caruthers 2023, Optimality of the coordinate-wist median mechanism for strategyproof facility location in two dimensions. Social Choice and Welfare 61, (2023),
11-34.
Anupam Gupta. Debmalya Panigrahi, Bernardo Subercaseaux, and Kevin Sun. 2022. Augmenting Online Algorithms with epsilon Accurate Predictions. Advances in neural information processing systems (2022).
Lu Han, Chunlin Hao, Chenchen Wu, and Zhenning Zhang. 2020. Approximation algorithms for the lower-bounded k-median and its generalizations. International Computing and Combinatorics Conference. Springer, 627-639.
12

---

Gabriel Istrate and Cosmin Bonchis. 2022. Mechanism Design With Predictions for Obnoxious Facility Location. CoRR abs/2212.09521 (2022). https:///oo.orr/100 ARX5000/AXIII 09521 arXiv:2212.09521
/4555/5..0000110044454/5//22 2212
Shaofeng H-C Jiang, Erzhi Liu, You Lyu, Zhihao Gavin Tang, and Yubo Zhang. 2021a. Online facility location with predictions. arXiv preprint arXiv:2/ (2021).
Zhihao Jiang, Pinyan Lu, Zhihao Gavin Tang, and Yuhao Zhang. 2021b. Online selection problems against constrained adversary. In International Conference Machine Learning. PMLR, 5002- 5012.
Misha Khodak, Aaria-Florina F Balcan, Ameet Talwalkar, and Sergei Vassilvitskii. 2022. Learning predictions for algorithms with predictions. Advances in Neural Information Processing Systems 35 (2022), 3542-3555
Akshay Krishnamurthy, Thodoris Lykouris, and Chara Podimata. 2020. Corrupted Multidimensional Binary Search: Learning in the Presence of Irrational Agents, CoRR abs/2002. 11650 (2020). arXiv:2002.1 1650
https:/ arxiv. wtggabs///aa 2002. 11650
Ravishankar Krishnaswamy, Shi Li, and Sai Sandeep. 2018. Constant approximation for k-median and k-means with outliers via iterative rounding. In Proceedings of the 50th annual ACM SIGACT symposium on theory of computing. 646-659.
Kevin A. Lai, Anup B. Rao, and Santosh Vempala. 2016. Agnostic Estimation of Mean and [cs.DS]
Covariance,
Thomas Lavastida, Benjamin Moseley, R Ravi, and Chenyang Xu. 2020. Learnable and instance- robust predictions for online matching, flows and load balancing. arXiv preprint arXiv:201 /. 1.73 (2020).
Hendrik Lopuhaa and Peter Rousseeuw. 1991. Breakdown points of affine equivariant estimators of multivariate location and covariance matrices. The Annals of Statistics (1991), 229-248.
Pinyan Lu, Xiaorui Sun, Yajun Wang, and Zeyuan Allen Zhu, 2010. Asymptotically optimal strategy- proof mechanisms for two-facility games. In Proceedings of the 11th ACM conference on Electronic commerce. 315-324.
Pinyan Lu, Yajun Wang, and Yuan Zhou. 2009. Tighter bounds for facility games. In Internet and Network Economics: 5th International Workshop. WINE 2009, Rome, Italy, December 14-18, 2009. Proceedings 5. Springer, 137-148.
Thodoris Lykouris, Vahab S. Mirrokni, and Renato Paes Leme. 2018. Stochastic bandits robust to http://arxiv.org org/
adversarial corruptions. CoRR 0as//883.0093. (2018). Abs/1803.09333
Thodoris Lykouris and Sergei Vassilvitskii. 2021. Competitive caching with machine learned advice. Journal of the ACM (JACM) 68, (2021), 1-25.
Nimrod Megiddo and Kenneth Supowit. 1984. On the complexity of some common geometric location problems. SIAM journal on computing 13, (1984), 182-196.
Reshef Meir. 2019. Strategyproof facility location for three agents on circle. In International symposium on algorithmic game theory. Springer, 18-33.
Michael Mitzenmacher and Sergei Vassilvitskii. 2022. Algorithms with predictions. Commun. ACM 65, 7 (2022), 33-35. httts::/doi.
1145/3528087
Ariel D Procaccia and Moshe Tennenholtz. 2013. Approximate mechanism design without money. ACM Transactions on Economics and Computation (TEAC) 1, (2013), 1-26.
Manish Purohit, Zoya Svitkina, and Ravi Kumar. 2018. Improving online algorithms via MI.
predictions. Advances in Neural Information Processing Systems 31 (2018).
13

---

Dhruv Rohatgi. 2020. Near-optimat bounds for online caching with machine learned advice. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1834-1845.
Bo Sun, Jerry Huang, Nicolas Christianson, Mohammad Hajiesmaili, and Adam Wierman. 2023. Online Algorithms with (2023).
Predictions. arXiv preprint arXiv:2310.11558
Xiaoliang Wu, Feng Shi, Yutian Guo, Zhen Zhang, Junyu Huang, and Jianxin Wang. 2022. An approx- imation algorithm for lower-bounded k-median with constant factor. Science China Information Sciences 63, 4 (2022), 140601.
Chenyang Xu and Pinyan Lu. 2022. Mechanism Design with Predictions. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, Lud De Raedt (Ed.). International Joint Conferences on Artificial Intelligence Organization, 571-577. https 7/doi. org/ 10. 24923/294221 19963/ijcai. 2022/81 Main Track.
Chenyang Xu and Benjamin Moseley. 2022. Learning-augmented algorithms for online steiner tree. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 36. 8744-8752.
Emmanouil Zampetakis and Fred Zhang. 2023. Bayesian Prrategy-Prood Facility Location via Robust Estimation. In International Conference Artificial Intelligence and Statistics. PMLR, 1196-4206
14

---

Organization of the Appendices
Appendix A
contains more related work.
Appendix contains more examples for sources of MAC predictions.
Appendix contains the explanation for the effect of >> 0.
Appendix
D
contains interpretation of the established robust statisties ô-robustness results.
Appendix contains the proofs for Section
Appendix and Appendix Contain proofs and supplementary material for Section 6.1
Appendix Appendix and Appendix Sappendixxconaaii contain the missing proofs for section Section 6.2 (for the analysis of Algorithm "Robust Half" mechanism). Namely:
Appendix contains the proof for Algorithm
2 properties: Lemma 6 Theorem
Appendix H contains the proof of Theorem
Appendix contains the proof of Theorem
15

---

A Additional Related Work
Models of prediction accuracy. Azar ct al. (2022) study online graph algorithms with notion of error they call metric error with outliess, applied to problems where the predictions are locations in metric space. The error parameters of this model are D and A roughly, D is the minimum cost matching between the predictions and the actual locations, where A outliers may be excluded from the matching. These parameters are similar to the (c, parameters of the MAC model. They then give a general framework for solving online graph problems in their model. Interestingly, their matching cost D captures a notion of average error, whereas we focus on individual error; while our results can be extended to fit within their model, it would be interesting to investigate a version of MAC where captures some notion of average error.
Gkatzelis et al. ) generalize the outlier model of Azarr et al. (2022) and apply it to improve the price of anarchy of cost-sharing mechanisms. Xu and Moseley (2022) study online Steiner tree problems with predictions where the error parameter is the number of erroneous predictions. Bernardini et al. (2022) introduce model named the "cover error model" that generalizes the model of Azar et al. 2022) to achieve more precision for online problems.
Gupta et al. 2022) study predictions that are incorrect independently with probability 8. Their work focuses on online algorithms rather than mechanism design. Our model is related to their model since independent errors imply MAC predictions w.h.p. by Chernoff. The MAC model is more general in the sense that it does not assume independence of erroncous predictions. [mme et al. (2023) also consider a similar model to the one of Gupta et al. (2022), assuming access to predictions that are correct with some probability or contain random bits otherwise. Dütting et al. (202T) consider a signaling scheme advice model for the secretary, which for binary ML-advice roughly translates into measures of accuracy of the signals (named recall and specificity).
Jiang et al. 2021b) consider a prediction guaranteed to be inside prediction interval. While their error model is closer to the "worst case" error model, their motivation is confidence intervals from statistics, where it is reasonable to assume that confidence interval is achieved with probability 1 - 8 for some å [0, 1). Sun et al. (023) consider an approach for "uncertainty quantified" prediction. One class of predictions they focus on, the "probabilistic interval prediction", can also be seen as a a confidence interval, as in the motivation of Jiang et al. (2021b). Like our MAC model, they "model in" the amount of trust in the advice. [Sun et al. (2023) focus on settings where the algorithm receives a single prediction (such as the ski rental problem). They use online learning for tuning the trust parameters, and introduce regret minimization analysis for learning the trust parameter online (over many instances of the same problem). The MAC model addresses problems that necessitate the quantification of uncertainty for multiple predictions simultaneously within the same input instance, such as in the k-facility location problem.
Mechanism design for facility location problems without predictions.
Mechanism design for the single facility location problem. In the single facility location in Rd problem, the task is to return single facility minimizing the social cost function. For the case of no- predictions, Meir (2019) shows a deterministic strategyproof mechanism that gets an approximation ratio of v which is optimal for d Goel and Hann- Jaant-Cauthhers (2023)). The optimal deterministic strategyproof mechanism is computing the COORDINATE- -EEE-MEAIANN of the points. In short, the vd ratio follows from the fact that COORDINATE- WISE-MEDIL is the optimal solution is the optimal solution w.r.t the 11 norm, which is at most sqrt(d) times 12 norm. The goal of introducing predictions is to get something better than vd in this context.
Mechanism design for the two facility location on the line. In this variant the goal is to return two facilities to minimize the social cost, where all points lie on the real line R. We want find strategyproof mechanism that given the agent reported locations returns the two locations for facilities in R. s.t. the social cost is minimal. A deterministic n 2 approximation ratio mechanism (called the "Two Extremes" mechanism) was given by Procaccia and Tennenholiz (2013), and lower bound of 2 by Fotakis and Tzamos 2014). A randomized strategyproof mechanism with an expected approximation
n/2 was given by Lu et al. (2100) which was later improved to (the tight) lower bound
ratio was given by [u et al. (2010) (which also works for any metric space), while the currently
best known lower bound for random mechanisms (Lu et al. (2009) is 1.045.
16

---

k-facility location. For & > 2. Fotakis and Tzamos (204)) show that there is no deterministic anonymous strategyproof mechanism with a bounded approximation ratio for k-facility location on the line for the general case (not just balanced) for any k 2 3, even for simple instances with k: + agents. Moreover, they show that there do not exist any deterministic strategyproof mechanisms with a bounded approximation ratio for 2- 2-Facility Location on more general metric spaces, which is true even for simple instances with 3 agents located in a star.
Mechanism design for the capacitated facility location is a variant of the problem studied by Aziz ct al. 2020) where each facility has a maximum capacity, limiting the number of points that can be assigned to it. For the utilitarian cost function, they have shown a '/2 approximation ratio.
Robust & medians and facility location. The robustness of the (offline non non-strategic) l medians and k facility location has been studied under different variations. As Example [ demonstrates, it not possible to get any bounded approximation ratio for the optimal solution. The approach of Charikar et al. (00T) to look at different variants of the problems with less restrictive objectives. In one variant they consider, the problem is to place facilities so as to minimize the service cost to any subset of facilities size at least p for some parameter p. Another variant they consider allows denial of service for some of the clients with the additional cost of some penalty for each such denied client. For work in these kind of models see Krishnaswamy et al. [2018;; Agrawal et al. (2023).
Other models of advice/predictions. In the recent literature of algorithms with predictions there are existing other models for algorithms with predictions which are different from the models already discussed. We now mention some of them.
Some other MI. advice is to focus on values that are learned via classical PAC learnability and focus on the learnability and analysis of sample complexity bounds. The assumption is that there is some distribution generating the input for the algorithm. Then the approach is to learn the distribution in terms of classic supervised learning. This kind of modeling is detailed in Annnd et al. 2020))
Lavastida et al. (2020) Anand et al. (202T).
Diakonikolas et al. (202I) assumes that the advice is not given deterministically, but that they can access the distributions of the inputs and sample from these: they consider access to the instances of interest, and the goal is to learn a competitive algorithm given access i..dd samples. They provide sample complexity bounds for the underlying learning tasks.
Online variants of the facility location problem with different notions of prediction were studied
e.g. by AAlmanza et al. (202T), Fooaaiis et al. (202T): Jiang et al. (2021a); : Azar et all (2022); Gupta et al.) (2022): : Azar al. (2023) ; Anand et al. (2022). The online setting of the problem differs significantly from our mechanism design setting: the real points arrive in sequence where each time an irrevocable decision must be made by the online algorithm (unlike the mechanism design setting where all the input is given to the mechanism at once, but is reported by strategic agents).
Learning the trust parameter. In the context of online algorithms with prediction, Khodak et al. (0022). show that the confidence parameter can be estimated under certain conditions via online learning. [Sun et al. (2023) also have online learning analysis to estimate their different type of confidence parameter.
Other algorithmic game theory with prediction work Istrate and Bonchis (2022) study mechanism design with predictions for obnoxious facility location where agents prefer to be as far possible from the facilities. Research in algorithmic game theory incorporating predictions, beyond the previously discussed work, has been explored by Balkanski et al. (2023b ch; Berger et al. (202)); Balcan et al. (2023).
Models outside of algorithms with predictions literature. One way to view the MAC model is to view the predictions as data with with corruptions. Designing algorithms to try and handle the corruptions was studied before. Multi-Arm-Bann
with corruptions is such a setting (Lykouris et al.
(2018): Krishnamurthy et al. (2020); Amir et al. (2020).
Zampetakis and Zhang (0033) propose the use of robust statistical estimators for strotegyproof mechanism design in a Bayesian setting. They show how to use location estimator which is robust to corrupting å fraction of the data drawn from some known distribution, to get a strotegyproof mechanism for the same location problem. This is conceptually very similar to our result for the
17

---

single facility case. Since there is no robust estimator for the two-facility problem, their approach cannot apply without making Bayesian assumptions: nonetheless, in our work we show how to use predictions and agent reports to get improvements on the worst-case approximation guarantees.
B
MAC Prediction Sources
The MAC prediction model is suitable for capturing errors from a variety of sources, mainly:
Machine learning. In practice, useful ML models produce predictions which are mostly accurate, and the accuracy parameters e, 6 can be estimated through testing. For example, we often have a predictor with the guarantee that each prediction (independently) will be E-correct with probability at least 5. Thus, through concentration bounds such as Chernoff, with high probability the number of predictions which are s-incorrect is at most se 8n. This was the motivation in Balcan and Harvey (2018). Gupta et al. (2022) also consider independent predictions, each correct w.p. ó. Note that unlike this example, the MAC model does not require that the predictor's errors are independent (and in that sense is generalization, having weaker assumption).
Data with corruptions. In a setting in which the algorithm's input itself might contain errors, we can treat the corrupted input as a prediction of the true input and apply the MAC model. Corruptions can be result of adversarial changes to the algorithm's 's input, e.g., in a malicious attempt to affect the output - in which case the adversary may change only a 6-fraction of the input to avoid getting caught. Corruptions can also capture outliers in the data, e.g., as result of rare but arbitrary measurement errors. This was the motivation in Azar et al.] (2022). As another example, the input data may have been collected at certain point in time, while the ground truth continues to evolve - in the context of facility location, a population census may form the prediction, with errors occurring since a small fraction of the population has relocated since being surveyed.
Experts advice. The data also originate from expert advice, where experts usually correct, but can be significantly inaccurate when they are wrong.
C
Supporting Small E >> 0 Values
Throughout the analysis assume that O, meaning each prediction is either wrong, or exactly correct. As we predict values in space (such as real values) it is hard to expect exact precision in the predictions. Thus, we can weaken this assumption by allowing prediction to be "correct" if it is e-accurate for some small E > 0 value. Consider, for example, the scenario where we want to locate hospital close to where people live where the locations are the house addresses. An "approximately correct" prediction that equals to the location of the house next door to the actual house of a person would be a reasonable prediction but would result in small 0. The prediction (and the cost) is almost the same, but it is not exactly right.
Consider, for example, the case of the single facility location problem. The effect of E the approximation ratio is bounded by an additive term of at most En, simply because each of the n points "conttibutes" another additive term. If en is small in comparison to OPT, or equivalently, E is small compared to OPT/n then the effect on the approximation ratio will be small; also, simply means that every agent pays at most more average. On the other hand, if is big in comparison to OPT/n, then we have no chance to compute a good solution. Indeed, OPT/a is the average deviation of the points from their true geometric median, which be viewed notion of the variance of the input; this is a measure of the "scale" of the cost of the problem, and a noise level above this value swamps the signal in the data.
We drop the e from the calculations to avoid "dragging" the additive e-dependent term along each result.
D Robust Statistics and Clustering Results Interpretation
In Section 2.3 we've mentioned how the 5-robustness notion generalizes the breakdown point notion from robust statistics. The existing literature does have quantitative approach, but mostly for specific
18

---

distributions or for distributions under some constraints, and mostly for mean and covariance robust estimation. For example, Lai al. (2016) shows that the distance between the mean of a Gaussian distribution in Red from the geometric median ()(Vd)) dd). In section Section 5 we give the definitions of 6-robustness, to consider the robust estimation of general location estimators (such as the mean, median and their generalizations) for data chosen adversarially (thus fitting any distribution, with no further assumption). Then, we use these to study the robustness of the median and its generalizations to adversarial corruptions.
we show that 1-Median (also known as the geometric median) has a dis- tance robustness of (1) MAD(X) where (5(1) is a small 6-dependent constant, and MAD stands for Mean Average Deviation, a known notion of variance defined as MAD(X) := Ex,xx d(x;, GROMETRIC MEDRIIC An interpretation of our result is that given a small the robustness of the geometric median depends on the MAD of the points, and the quantification of this relation is given by Theorem 2 and Corollary 3 When we calculate the (geometric) median we often want single point representing the dataset. The geometric median represents the dataset the sense that it is the point closest to the dataset points. Intuitively, for data with high MAD (or variance), there is no single point that represents it in a good way. Consider the examples in Fig.
In Appendix
E.1
High MAD example
Low MAD example
n/2
n/2
Figure 3: Illustration of instances with different MAD; In the LHS example, MAD is very high unlike RHS where MAD = O.
On the left example (high MAD example) half the points and half the points at no single point can represent the data in good way any point returned would misrepresent half the data. In the second example (low MAD example) all points are co-located at O. In this case MAD = and so the geometric median (at 0) represents the dataset in the best possible way - it equals to every point in the dataset. So the interpretation sense that it still returns good representation of the dataset: point that gets representation of the dataset, which is almost as good as the real "best" representation of the dataset.
the results here is that the geometric median is robust in the
In Appendix E.2 we show that for l >> 1 there is hope for robustness of k-mmedians We thus turn to 3-balanced k-medians, which are medians that induce clusters of size at least ,3,, where n is the total number of points (see Definition 77. Clustering with the additional constraint of minimum cluster size has applications such as data privacy (Aggarwal et al. (2010), ) or clustering with a minimum/maximan cluster size (capacitated variation). The robustness of 3-balanced k-medians implies that balanced clustering algorithms can be robust to adversarial corruptions, outliers or missing values.
In our context, we show the usefulness of these 6-robustness results for all of the mechanisms for the MAC predictions settings.
E 6-Robustness of the Median and Its Generalizations: Proofs and More Details
First, we show a lemma connecting the distance robustness to the approximation robustness notions, in the context of k-Medians.
Lemma 10. Consider location estimators f.f: V + V that satisfy the following two properties:
1. For any X E V and X' in the 8|X| leighhhogooo of X, medg (X', F(X')) S medg ( f(X)):
2. i (p, distanccee-osl with respect to f-
Then i a (1+
med, -uppormmmmimssssnnnnbbuuus solution for = medy with respect to f.
28
19

---

Proof. Let n = X let A == [n] 2; 2 be the indices where X, X are the same, and :: [m] A be the remaining indices. Define G f(X) and H f(X'). Using this notation can write med (x, [(x')) as
Σ d( H) Σ d(1) H) +
E(d(x; H) d(a': H))
iEB
Ed G)+ Σ (d(x H) d(rk, H))
(4)
iEB
Σ [(
(d(x), G) E(
d(z;, G)) + Σ
(d(2,, d(z': H))
iEB
iEB
medg (x, (x)) +
Σ
(d(a), G) d( H))
Σ
(d(r;, H) d(a; G)), (5)
iEB
SEB
where uses the first assumption of the theorem.
We claim that each of the differences in Eq. (5) is at most drr(G, H). Indeed, for any E V. let
its closest points in and H be and h respectively. Then d(x, 9) d(x, h) I d(g, h) by the triangle inequality, and this is at most the Hausdorff distance; the case of d(x, h) - d(x, 9) is identical.
Therefore.
med, f(X')) & med, (X. + 2| du (G,
Finally, using the definition of (p. 6) disstaace- implies that du (G, H) is at most p. The fact that [B] S [| completes the proof.
Now, move onto proving the robustness of 1-Median (which is GEOMETRIC-MEDIAL for Eucledian space).
E.1 The 5-Robustness of 1-Median
In this section, quantify the distance robustness (and hence approximation robustness, by Lemma [0] of the I-median location estimator. We show that changing any 8-fraction of a dataset X where 8 1/2 can move the 1-Median by only T-28 times the average cost of point in the optimal 5
solution of X. Hence, this changes the total 1-Median cost by only a 1 + O factor.
This is captured by Theorem 2
Corollary
E.1. Proof of Theorem 2
.......,,,n,> = fr' E V where X' is in the 8| neighbooood of X. Let n = [X]. let A lie E [n] x; = x/} be the indices where X, X' are the same,
Proof. Let X
and B = [n] \ A be the remaining indices. Let arg min med, (X', (w}). follows that Eienn d(z), m²) Eiejn d(z/, m). Using the triangle inequality and the fact that x² = x; for all i E A, we get that
arg min med, (X, (v)) and m'
Σ (d(m', m) - ((m,x,)) + V (d(z), m) - m)) KEA
S Σ d(r,,m) m) + - d(a m)
sEA
iEB
d(m', m) (IA) BB] S 2
d(z,, m)) 2 Σ
d(z;, m) = med, (X).
iEA
[E(m]
Since [B] S 8n and [A| + B n, we get d(m', m) S
2 med; (X).
(1-26)m
The quantity med,(X) [X
is called the mean absolute deviation and can be viewed as a notion of variance.
Hence, Theorem essentially says that since 8 1/2, the 1-Median only changes by Os(1) (1) (a
constant depending on ô) times the mean absolute deviation.
To get Corollary we simply substituting the distance parameter of 1-26
2 med,(X) (X)
[X]
into Lemma I0
20

---

ErrolaarBssayy that if X' is obtained by perturbing a 8-fraction of the points in X, then the geometric 48 j-apprxximately optimal solution for the original point set X (with median of X' is a (1 + I-26
respect to the 1-Median cost objective). This result can be viewed as quantitative version of a classical result of Lopuhaa and Rousseeuw (1991), which shows that the breakdown point for the geometric median is 1/2. This gives us an understanding not only of the fraction of perturbations required to "break" the estimator (i.e., make it arbitrarily far from the real location), but also of the deterioration in the estimation before breaking it. The quality of estimation as a function of ō is captured by our result of p T-26 estimation.
2 (X), showing that smaller d corresponds to better
We conclude the discussion of 5-robustness of the 1-Median with two remarks:
1. Results similar to Theorem 2 hold even for the case where X' is obtained by adding or removing points; in fact, the approximation factors can be improved slightly (the proof is almost the same).
2. The quantitative bounds are tight; consider the example where X comprises of (0.5-8)r points at O, and (0.5 + 6)n 1 points at 1 and X' is obtained from X by moving on points from 0. A calculation shows that this case approximation robustness of the 16
geometric median is + I-25 O ())
E,2 The d-Robustness of 3-Ralanced k-Medians
Proof of Theorem
Proof. The claimed algorithm B is simple: compute the optimal (b - 1)6-balanced k-medians solution on X'. Since X admits a b6-balanced solution G = {.h..... J. and X' differs from X in only X| points, this solution G is ballnneeee for X'. Now let H (hi..... ., h be (b - 115o-)bllnnee balanceed k-medians solution of least cost for X' computed by B: this means
d(d,H)
Σ d(z',G).
#' F'
x'EX'
Let (C ..... C/}. be the balanced partition of X' induced by H. Similarly, since X is in the o-neighborhood of X', the centers in И induce a (b ballanced partition of the original dataset X: call this EH (Ci...., Ck). Finally, let Eo [Ci,-.. ... C2} be the bö-balanced partition of X induced by G. Recall that n = [ define
OPT : med, (X,d) = Σ
d(z, G) Σ
Σ
d(I, and
xEX
i=1 xE
ALG
Σ xEX
d(z, Σ
ΣΣ j=1xEC,
Σ d(z,hz).
We now want to prove that max; d(gi, H) and max, d(hj, ; G) are both small. To show the former, fix any and let C be the cluster corresponding gi- Since the clustering is bo-balanced, |C > bön. By averaging, there exists some cluster Cj E E6 such that |C n nCC 2 bōn/k; choose this j. and consider the corresponding center hy E H. Now
d(g, H) < Ky) (4)
Σ zecinG,
[d(x - d(a, 1y)1
S
ALG + OPT
C
bōn/k
where (+) uses the triangle inequality. A similar argument shows:
ALG+OPT
d(h,, G) < (b 2)ôn/k
Hence the Hausdorff distance between the two solutions is du dn H) & Lemma 10 with this bound on the Hausdorff distance, we get
ALG+OPT (b-2)6n/K"
Using
ALG < OPT + 2ôn dy (G, H) < 0PT+ ALG OOT
(b - 2)
21

---

Simplifying, we get ALG < (1
4k
JOPT. and that dy dx H) S
2k 6-2-2k 2k
OPT
as claimed.
6-2-2k
6n
F Proofs and Additional Analysis for Section 6.1
E. Proof of Theorem 5
48 approximation ratio: Proof. By Corollary 3 computing the 1-Median on X' results in a + 1-26
this is because the metric space is RR, and hence the 1-Modian is in fact the geometric median (which is also known as the spatial median, L1 median or Fermat point). Since the geometric median computation depends solely on the predictions is strategyproof. Thus, by the the strategyproofness of COORDINATE- BRRADDNATEWWIS---EEE WISE-MEDIAN and by the fact that the decision of which mechanism to use does not depend on the reported locations, Algorithm is strategyproof. Due to the vd approximation
vd) approximation ratio COORDINATE- WISE-MEDIAN (Mein (2119), we get min (1 + I 1-26
46
ratio for Algorithm
I
F.2 Remark on Computing the Geometric Median
For general dimensions d and number points n, there no known formula or algorithm to find the geometric median exactly. However, since the problem is a convex optimization problem, there are optimization algorithms that find solutions with arbitrary precision efficiently. By using such an optimization algorithm we get an additional factor of E' >> where E' is arbitrarily small. For more information on efficiently computing the geometric median, see Eckhardt (9800) Beck and Sabach (2015) Cohen et al. (2016).
F.3 Combined Strategy for High Probability MAC(s,
In this section we show how we can use both the predictions and the reports of the agents to gain good performance even in the case of MAC(E, 8) only in high probability.
The MAC(E, 8) model requires that at most a fraction of the points have error more than e: one can extend this to the setting where this requirement holds only with high probability. For instance, consider the setting where the number of prediction errors can be larger than fraction with probability at most o(2/n). In this case the computed geometric median might be arbitrarily far away with this small probability, and hence the expected approximation ratio for our mechanism would be unbounded. To avoid this problem, we can use the agent reports. Intuitively the agents have the incentive to make sure that the returned facility location is not infinitely far away from them.
One way to do this is by using the MIN- MIN-BOUNDING- Box mechanism. introduced by (Agrawal et al. 2022, Mechanism 2) for the egalitarian cost function for d' 2; The mechanism naturally extends to any d 2 1 (Algorithm 6). The mechanism calculates the minimum bounding box B containing all the input points; then, given single prediction o, it returns the point E closest to o. We show in Appendix that that the approximation ratio of the generalized MIN- HIN-BOUNDING-A Box mechanism for the utilitarian cost function (med,) O(n).
Therefore, by composing MIN- MIN-BOUNDING-BE Box with Algorithm we get strategyproof mechanism which has an approximation ratio of min 1 1- vd) with high probability, and has an ((n) approximation ratio with probability o(/n)): this gives an expected approximation ratio of at most min 1- + o(1). The form of the resulting mechanism is simple:
48
Algorithm 5: Bounded Best- Chees-hhhhcc--Sggll-Fllllttt--l
Input: 8 E [o, 1) and X, XX' C [2d where X reported by strategic agents and X' contains the MAC predictions for X"
Output: The facility location in R
return HHIN-BOUNDING. Box Best Sess-CChhoie-Sngl--eilllleee X', 5))
22

---

F.4 Generalized Minimum Bounding Box Mechanism
In this section we properly define the generalized MIN-BOUNDINGGEE Box mechanism and prove that for points in R (for any d 2 1) it has tight approximation ratio of ((n) for the med, cost function. For any y E Rd let [wl, denote the j'th coordinate of y.
Algorithm 6: MIN-BOUNDING-BOX
Input: C 1RR E R²
Output: A facility location in d which is inside the minimum bounding box of X
for j E [d] do
of MINMAxP(((r))))....... (z)
return d'
Algorithmm computes, for each coordinate j, the closest point oj that inside the minimum closed interval that contains all of the jhtj j'th coordinates of the points of (which what MINMAXP does, see Mechanism 1 of Agaawal al. (2022)). Let us now prove an approximation ratio for the med, cost.
Theorem 11. Algorithm i is strategyproof and has a light O()) approximation rutio for the med cost function.
Proof. Let us assume, w.l.o.g, that the geometric median g is at = Let B be the minimum bounding box of X. Formally:
B y E Fdd Vj e [d] : My E [minag[n]] [ædly [a) [m,]]]}- Let h be the point returned by
Algorithm for X C Rd, o E IRd (thus must be inside of B). Let aj be the side length of the box
B in each coordinate. As usual, we denote OPT to be the cost of the optimal solution and ALG the cost of the algorithm.
2
OPT
|zi||
2 Σ
Σ
([x:l))²=
Σ
((xgla)²
iEim)
iE(n] jEd
SE(d]
iE(n)
jE(d]
(.))
OPT 2
h 2
/all-
(6)
21
2
(+) is due to the fact that for any j E [d] there is some x, s.t. |[x,]] 2 since otherwise we would get that the j'th side length is smaller than az..
(**) explanation: It is known property the geometric median that lies inside the convex hull of the points. Thus, lies inside B (since the convex hull of the points lies inside the bounding box of the points). So by the fact that h E we get that Ihy h2 hh 9j S layl-
Finally:
triangle inequality
Eg.
ALG
Σ |1, blll iE(n]
E1 #E|m]
|||l
OPT 2n OPT O(n) OPT.
We deduce that Algorithm 6 has an approximation ratio of at most O(z).
To that the result is tight, consider the instance where X is the multi-set of n points where 1 points are at a = (-1,... -1) E IRd and one point is at = (1...., E Rd. Let o The optimal solution puts the facility at a and has a cost OPT = d(a, b) = 2 Algorithm 6 returns
b and therefore the cost of the algorithm is ALG = (n 1) -d(a, b) (n 1) 2/d.
Overall we get: OPT
(n-1)-2vv
((n).
2vd
The strategyproofness of the mechanism similar to the one proof given by Agrawal et al. (022)) for the egalitarian cost function.
23

---

One could wonder why use the minimum bounding box rather than the convex hull of the points. After all, the convex hull is always contained in the minimum bounding box, and always contains the geometric median. Unfortunately, such mechanism is not strategyproof:
Remark 12. The mechanism obtained by replacing the minimam bounding box in Algorithm with the convex hull is not strategyproof. The example showing this is for d = 2: Given X {(-0.5, 0). (0.5. 0), (0, 1)}. computation shows that the agent at (0,1) can lower its cost by reporting (1/2, 1).
We can further generalize the mechanism for k facilities by simply using Algorithm for each facility independently.
G A Deterministic Mechanism for Balanced k-Facility Location in General Metric Spaces
For B E 00, 11, the 3-balanced k-facility location problem considers agents with locations X {zI...., InJ C V. Each agent reports a location to the mechanism, and the goal is to return multi-set H = (h1,.... ................................ ,ha) containing points from V that minimizes med& (X, H),, such that the clustering induced by I is 3-balanced (according to Definition 7
For small enough 6, by choosing b F/a the balancedness condition translates into a minimum cluster size of bō. Hence, we can utilize the d-robustness results of (b - 1) BALAANCDD k -MEDIAN (Theorem 4) to immediately obtain the deterministic mechanism in Algorithm 7 with the following guarantee:
Theorem 13. Algorithm is deterministic strategyproof mechanism with constant (k-dependent) approximation ratio of at most
4k:
+
b 2 2k
Algorithm 7: Balanced-k -acilkFtyy X', b. 6)
Input: X, X' C V. and 6 > 1, 8 [0, 0.5) where X' are the MAC predictions for X Output: The l facility locations V
return (b 1)8 BALANCED A: -MEDIAN(X')
We do not specify how (b 1)6 -BLLANCED i MEDIAN is implemented. If all points lie on the real line, then there exists ((n*) )-tme algorithm for it (computing the minimum cost of all (?) options).
In Euclidean spaces of dimensions greater than one, the k-medians problem (and its balanced lower bounded variant) is classified as NP-hard Megiddo and Supowit (1984); Bhattacharya et al. (2020)
necessitating the use of approximation algorithms. Any approximation algorithm with approximation ratio e can be applied, incurring an additional multiplicative cost factor of c. This approach allows for practical solutions within the constraints of computational complexity, ensuring that achieve near-optimal placements of facilities even in high-dimensional contexts. The effect e values and handling the case of high probability MAC predictions is similar to the single facility location results.
still
H Full Proof of BIG-CLUSTER -ENERRR 5-Approximation Robustness
In this section we show that Algorithm 3 indeedd has "good" approximatioonrooustii for unbalanced clusters by providing the full proof for Theorem g
Proof. Let == (OL, In) be the 2 - median solution, where L = {á d(z;, S d(r; gR)) and R [n] L. W.L..g 9L 9R.
We have slight abuse of notation throughout for the sake of not introducing more variables, referring to L,, R as multisets of points and sometimes as the sets of indices of the points in X.
We assume that the clusters are bsfunbbaancce. That is, at least one of the clusters L., R are of size less than bôn. W.l.o.g [R] < bôn and so [ > (1 (1-10 b8)n.
24

---

We also assume that å is small enough s.t. bó < and so [L] >
3n 1
Let H = (hz, hR) = (6 1)6 2ellanced-2MMeiinnn 2-Medians(X)) (as in the first line of Algorithm 3) W.l.o.g hy S hg.
Let L', R be the multi-set of the elements closest dy and hR the remaining. So L' d(2,, hz) S d(z,, hx)) and R' = [m]
Let A = {i [n] x; 2t} the shared points between X, X' (the "correct" predictions), and B = [x] A the remaining.
Let m 2. be the middle point between IL and JR. Let m' AoR be the middle point 2
between h, and hR. By the definition of m: All points of L lie to the left of m and all points of R lie to the right m. Similarly, all points L' lie to the left of m' and all points of to the right of mn'.
We begin by proving the following simple lemma:
Lemma 14. Let C R (for some N) be a multi-set of points. For any 3 10, S ler M = (m1.... m&) = 3 balanced
median(S), s.t. S S are the disjoint clusters induced by my.- my of S. Then for all E [k]: m, the 1 median of S,
Proof. Consider the implementation of balanced - median which is obtained by taking the cost-minimizing balanced partition into k B balanced clusters. That is, the implementation considers all of the partitions of S into l 3 balanced clusters and then computes the location that minimizes the center of each cluster S;. For each such center S,, the minimizing location is (by definition) 1 median(S.)) Thus, the implementation always returns points that are the - median of their clusters.
We divide the proof into cases as follows (also illustrated in Fig.
Case : h4 S IL and hR 9R-
Case h1 9r. and hn S gn-
Case 11, 2 gr. and hn 2 gn.
Case hr. S gr. and hR gR.
Cases are similar and have short proofs. The hard case Case (4).
Predictions X'
hy
hR
Predictions X'
P.g.
hgg
Real X
9R
Real
91.
9R
Case
Cass 3
Prodictions
hg
lig
Predictions X'
by
li
Real
91.
Real X
91. Case
ON
Cuac
Figure Illustration of the 4 cases. On the top of each case drawing we have the "esti- ppredc""preddctee" locations H, computed on X'. On the bottom we have the "real" locations, G, computed on X.
Case 1: hy, I gr. and hR 2 DR- In this case we can image the two centers moving away from one another. That is, gr. "moves to the left" hr. and gn "moves the right" to hR--
m m then T.' contains all of the points Ln A. and Ln A) 2 [T] 8n 2 n (b + 1)8n. Thus, for small enough 8: (b + 1)ôn > z and thus the algorithm returns fz. From Corollary
25

---

we get an approximation-robustie of + (b6)) = 1 (()) (since L' is obtained from L by change or add of at most (b+ + 1) elements).
Otherwise, m' < m. The number of elements to the right gR in R is since it is the median of R (by Lemma 14).
IR]
Since ha In then the number of elements to the right of hn in R' is most [R]
|B]
[ + ön.
hg is the median of R' (by Lemma 14) and thus [A*] - 2( 2 + ôn) = [R] 26n I (6+ (6+2) 2)ón. Thus again by Corollary 3 we get approximation--rousieee
of + (()).
Case 2: hr 2 9L and hg S gR- In this case we can image the two centers moving towards one another. That is, 9r. "moves to the right" to ht, and gR "moves to the left" to hR.
If m' 2 then L' contains all of L n A plus at most (b + 1)8n points and thus just like the previous case we get (from the I-median approximation robustness) a axproxiimation-robustttoo
of 1 + O()).
Otherwise m' < m. By Lemma [4 we know that hy is the median of L' and that 9L is the median of L. Since hy Z 9L. there are at least [L| ön points in L' to the left of h1- Thus:
1 2 2( ( dn) 2 |1| 2ôn 2 (1 - (b + 2)d)n, and we can utilize Corollary 3 again to get the desired.
Case 3: 1y 2 gr and RR 2 gR. this case we can image both centers "moving to the right".. In this case, m' bette 2 m.
Just like in the previous case: L' contains all of Ln A plus at most (b (6+ 1)on points and thus (from
I-median approximation robustness) a appoxiiaation-robuunnss of 1 + O()).
Case 4: hy S gL and hn S gn- this case we can image both centers "moving to the left".
By the definition of m': m' thz
2
Until now we had an approximation-rouuttees case, as for this one we will get 1.8 + O()) approximation result. Since we also have a lower bound of R: 1.667 + (2)) we get that this is indeed "strictly" the hard case.
result of + O This case is the most difficult
If hR 2 m then the number of elements in X to its right is at most [R] and thus the number of elements its right on X' is most [R] ōn. Since hgg median of Ht' must be the case that |281| < 2( + ôn) I 2(6 + 1)6n = ((8) n. Thus LL' = [t'| 2 (1 0(8))n and therefore: (a) The algorithm returns hg (since L'l / and (b) From the 1 median robustness (Corollary 3
we get the required 1 + (6)) pxproximatiion-roustnnn
Thus, let us assume that fgz m.
We first handle the case where m' 2 gr. and then we will show a reduction from the case m' > gr. to this one.
H.1 Sub-case: m' 2 9L
Since m' is the middle point between hy and hy we get that: m' h2 = hR m' but m' h2
m' - gL + 9L - h2 2 91 - hy and so: - -h I hR - m'. But hR - m' I hn IL and therefore:
gL hy S hR IL.
We introduce the following notations (also see Fig. 5 First, we denote the left and right parts of L', Rt, L, R:
Let (i 4 h1) L'\ L'
Let R' = E R'
R', = R'' R'r.
Let = [i L x 5. = =b L1.
= ii R 2 5 R, R Ri.
26

---

Next, we denote the partition of L into 4 disjoint multi-sets S,T, U. V by the 3 points h., m' hn- I; h fi E S, m'), U {i L SUT. xz S hnl-
So S fi == ii E I. i IESUTUT.
Let m" = S1. the be the middle point between 9L and hg- W.l.ogg we assume that m" > m' (otherwise the proof is similar). We define Ui, U, to be the as follows: U2 = {i x S m"). U, = U Uz-
Finally, we introduce the notion of e-approximately-equal : Definition 14. For any a. b, a E R:
b a
V
R
Li
1
R4
R
Prodictions
X'
1
hR
91
UR
Real
0/
U
7 U
L,
Figure 5: Illustration of case (4) where m' 2 9t. On the top we have h1, hn. computed on the "predicted" locations X". On the bottom have the IL.9R. 9n. the 2-Medians of the "real" locations X. I' and are the disjoint partitions of X' into two multi-sets of points: those closer to h2 and those closer hR (respectively). Similarly L and R the disjoint multi-sets of gL. 9R. L't, L', are the disjoint partitions of L' into two multi-sets: all points to the left of f1, and all points to the right of hR. In similar manner R', L, We can also see S, T. U, V which is the disjoint partition of L determined by the points h m ha- Finally, we have Uj and U, which are the left and right parts of U.
partitioned into their left and right parts (R's 1, Rt' ry Lis Le, Rí, R.).
27

---

For every M S X we define оPТM to be the cost that the optimal solution (G) pays for the multi-set of points M. That is: OPTM == med2 (M, G) (we sometimes use this notation where M S [rx] in which case OPTMs is slight abuse of notation for OPT (2.liEM)).
Let B, 7 E [0, 1] the ratio between 5 [V] and [1.. That is: B == 181//21 and y == 11/
Claim 15.
med1 (L,) OPTs OPTrL + OPPT, + (gr. -11)(111(1(111 -23))
Proof.
medi((,,11)
[2
hy Σ hL Ij
Σ 34 hL
iEL
NETOUUV
Σ iES
9L. Li (g hr)
Σ
9r. + |T Tol(gr h1)
VETTL
Σ
I2 9L ([T L,
18 + (V) hL)
jE(UUNAJUUU
( OPTs - OPTTLL: + OPTL, + + hL 2151)
= OPTs - OPPTLL + +PPT, + (9L - (2) - 23)).
(+) triangle inequality
(**) due to the fact that L, T UUUU and | |S| + U V + [T].
If the algorithm returns h2 then we want to show that med, med](L,h1) - (1.8 + O())) med, modi(L, gt).
From Claim 15 we get the following equivalent condition:
med, h1) = (1.8 + ((6))PPT, >
OPT's - OPTTL. + OPT., + (9L - h1)( - 23) S (1.8
(gL - -h - 23)) & 0.80PTs + 2.80PTML + 0.8OPT, +0())PPT;
(gL - h1) 0.80PTs 2.80PTTLL, + 0.80PT, + 0())PPT [L[ 23)
Thus, all we have to do is find the above bound for gr. - hr, Indeed we will show that this is the case. We start by proving few claims that will help us bound gr. h
Claim 16. (B + L) ((ón) L
Proof. Since h is the median of L'. and the points in S U T differ from those in L' by at most (ōnn), we get that [T'] ((ôn) B14]. Similarly, since hg is the median of H' and since [R] = |4]:
|U] O((n)) (7 L)] + n. By using the fact that L = S + T + U0 + [V] we get:
| R O(6n) B|L| + 8141 + (7 L| + n L
2(B + 7) ||| 2 ((ón) 2|[
(8 L ((6))
|L|
n 2
Claim 17.
(ØL hL)1 S OPTs.
(9)
Proof.
4z,E5: Sh
OPTs Σ
9L
2
9L
h2
|5](91 hz)-
iES
ie5
28

---

Claim 18.
-hR - 9u) & 20PTu.
(10)
Proof.
Vr:EU.: 2:2m"
[rr
OPTu, Σ
r2 9L
Σ m" |U.l(m" -9L)
(hx 9L).
2
iEU.
EE
where the last equality is due to the fact that m" is the middle point between gr. and hR.
Thus we get:
(ha 9L)lUa1 & 20PTu.
Claim 19.
- (a--9)lVV &
10--VVIVSPPPP OPTV.
(11)
Proof.
Vo,EV: 2,2nn
OPTv Σ Tj 9L
2
Σ hR gr. = =V[(hn -rt)).
NEV
Consider the clustering induced by H' [gL, hg) If this clustering is unbalanced then Algorithm returns hy since LiD is contained the left cluster and since LNA| 2 Y -ôn - ((n)) it must be that the right cluster the smaller one. And the left cluster has at least n- (6-1)66))) 1jón n (ôn) elements and thus it is obtained from L by modifying or dropping at mots (ôn)) elements and thus the algorithm returns h2 and like before get a (1 0(ō), 5) approximation-robusinn
Otherwise, the clustering induced by H' is balanced, and we get the following claim:
Claim 20. (hx - ([U( ((n)) 2(0PTT + OPTu;)
Proof. For convenience, for any multi-set of the real points A C X we denote M C X' to be the multi-set of the estimated points X' that correspond to the same partition of the real line M. So
we define the following multi- sett: L, = {af E X' z S 91), L, {a] X' L x S m), R', x E m/. Ú; = (2) E R' o S m"). - R', x4 m"). The reason we use this notation is that we have an inequality in terms of the points X' and we want later move on the inequality in terms of the points in X. This notation will help us see the connection between the points in X' and the points in X. Each such M, M contain the same points up to at most ôn points.
= T L',, Ú R' =
By definition of H know that med2 (X', H)) S med2(X) (X' for any T (41,6) R² that induces a (b - 1)o-balanced clustering of X'. Therefore, med2 (X', H) S med2(X', hR),
By the definition of medg:
Σ
hy 21+ EE
- hL
Σ ha 2 Σ x hR S
MELL'
2,EL'
Z/ER'
Z/ER'
Σ gr. - x +
Σ
J/ - gr. + Σ
hR 1/4 + Σ x/ hR-
afESu(Tn(a)
rfE(TnL.)u0f
tEE
Z,ER
Which implies:
Σ
hr. x +
Σ
x hr +
Σ hn - x/j
E'll'
x/eR'
Σ
gr. x +
x/ - 91. + Σ hR - 2/c
(12)
rfESu(tn(,))
rfE(fnL.))
x!EU,
29

---

Let us observe LHS:
Σ h2 - 2/z + E
d 11-h1 1y -
Σ
hR 2/4
KE
E/ER'1
= =|1i1(1e 9L) +
Σ
9L o +
x 9L + 111r - hL) + R-
g2) +
Σ
9L -
x
d'El'r
Σ gT.
Σ
d/ gr. + |Ri(bR - gr.) + Σ
g1. -1.
"EER'
Σ 9L
x +
IL
|0]( - -91)
Σ IL x²¹
x/ES
E/ET
Σ gr. - d' +
Σ
J gt. +
E
14 - gr. + [k( - gr.)+ + Σ 91. - d'p
x/Eš
So by plugging this in
we get:
Σ 9t.
1 +
Σ
d - gr.
Σ
2/ g1. + +1[(nR gr) + Σ 9t. x/j
Σ
9L - x +
Σ
d' - 9L + Σ hR - =zy.
(ESUU(Nti
x <<E(TNL,))U;
&GEU
1Ū1(hR - (L) +
Σ
9L - x 2
Σ 9L
-L - x + Σ
x - 9L + Σ
hR- x
&EE
NEEnLL
xfEU;
tEU,
=2 Σ
9L H + Σ
9L + [ū,( (L) + Σ 9L x =
ofETnia
deth
#/Et,
[illhn (L) 2
Σ
9L o + Σ x - DL.
(13)
zEENLL
xtEU;
By the definition of f, T: in fa and T La differ by at most on elements, and for any a4 E fnntn fu: x hr. Similarly U, and U/ differ by most on elements and for any x Uj: x mm"
By plugging this in the above
13 we get:
((U)) - 8nn - (1) S (0 - -9L)
2 Σ 9L 9L-X, x4 -28n(gL 124 +2 Σ z:Eti
x; -9 + =28n(m" 9L).
Which implies:
(hn --)) S 2(OPTToL, + OPT;,) + 8n(((gr - h1.) + +(mm" - g1. + (hR g1.))
Since m" 9L (hR-922/2 (by the definition of m²) and from Eq. we get:
Mbn-9t)UA S 2(PPTmL, + OP7
gt.)
(hR - (U)) O(5n)) < 2(OPT + OPTú;).
(14)
Now are ready to bound gL hL-
30

---

Lemma 21. If the algorithm returns 1y then:
(9L- - -h)) +.88 + 0.80PT + +000OPP
[L (
Proof. By Claim 17
Claim
18
Claim
20
Claim 19 and the fact that gr. hr, S hR gr. we get the
following four inequalities:
(gl - kr) _ 20PTu,
hc)( 0(ón)) s 2(0PTTL + +PPT))
(gr. ln.) 20PTv,
(9.. - h,.)2 S 20PTs.
By summing the above inequalities:
(gr. - (2 + |0| 2 ((6)) < 2 OPTnt, + +PPT + +OPT)
hr. S (OPTss + OPTTLL + OPTr + +PTv)
2(1 23)
(15)
(1 (1223)
2 10 2 -O(En)
Since [L'|] L'rl get that [T| on |S| 3 and so
2|5s + U| + 2| (δn)
|1] ((nn)
(IS) [V))
[V]) [S] -((6)
[2] + ( - -O(ôn)
Clain 10
+ L
3 (66)
2
2| B| -(6n)
Where (+) is due to: |L| = |S| +
T + 0 + Vl. V = 1S1 3|1
By plugging this inequality into Eq. 15
9L - h1 (OPTs + OPT + OPT. OPTv)
2(1 - 21) L
(16)
2.3
2 3
O(nn)
We will bound the second term in RHS. First, we know that [L] ((8n) n and thus:
2|[| - 2(1- - L
2(1 - (3) O(8n))
2(1 - 28)
< 3n (ôn)
(1 0(0)
O(nn)
3
We denote: /(9)
2(1 2(1-
-
Since the algorithm returns hy we deduce that [L' > 2. Thus, L'rl, |1 2. But S and L', differ
by most on elements, and |S] 2 8n. Since [S] B L and L S n we get: In 4 8n which implies
Also obviously 8 < 0.5 since hr < gr by the definition of S. So : 12
8, 1 R is well defined function. We find its maximum:
f((3) = 2 3 - (1-1)33(
+1 -3+ 28
-4
0.
-32
8)2
2 3)
So gets its maximum at the left boundary where 9 1 8:
31

---

11 5) 2
+ 26
4
+ 0(8))
7
By plugging the above into Eq. 16 we get:
(OPTs + +PTT +
gr. - hr, 5
- -
What we have shown that if the algorithm returns hr we done. the algorithm returns hR can similarly show that in this case mcd](L, ha) I (1.8 + ( med, (Z, 91).
H.1.1
Handling the Case where the Algorithm Returns hR In this case the cost med, (g) will be:
Claim 22.
med; (L, hR) OPT's OPTTLL -0Phh000000000000007 (7)) -9t).
Proof.
med1 hI,)R)
Σ
hn Fi + Σ Jt hR
iESUTUU
Σ
(hn (1) (gL xzi) Σ
(x: 91) - (hn g1.
iESUTUU
ieV
OPTs + OPTTL -OPTTLL OPT. - OPTv + (1S) + [2] | 91)
| +V|==41 OPTs + OPTTNL - -OPT - OPT, + OPT, + [ - 2 - 9L)
OPTs + -P
- -PTT OPTv + (lZ((1 27)) gr.).
To get med (L, hR) < (1.8+0(0) medi gI, we need to show (by the above claim) the following lemma:
Lemma 23. If the algorithu returns hy then:
(hR 9L) < +
+ OPTmL + OPTV)+ +
(1-2
Proof. We begin by showing the following claim:
Claim 24.
|S|
(hR 95)) S (hR gL)]ss OPTs + OPTT.
[U]
Proof. lgg 91 m' hy = (m' - (1) (ØL - hτ) and so OL hy = (hR (1) - (m' 91).
Together with Claim we get:
(hR 9L)]S| S OPTS [5](m' gL).
(17)
Also, OPT. Eiev gr E seU m² g1. 10 gr.) which implies
OPTo
m' OL
(18)
|0]
By Eq. 17 and Eq. 18 we get the desired inequality.
32

---

From Claim 24
Claim 18
Claim 20 Claim 19
get the following four inequalities:
(hR 91)2 - 20PT's +2 OPTo.
U
(hn Uu) v 20PTu..
(hR - - 0(ón)) < 2(0PTT + OPTo))
(hR - 9L)2 & 20PTv,
By summing these inequalities:
OPTs OPTU OPTTOL + OPTV + 2|5 OPTs
ge)=s) + |V] + 2|V| O(ôn))
<
2(1 27)
(1-27)]1
(19)
Since the algorithm returns bg must be the case that [R*| 2 3 and so |R'|l 2 n which means that [U] 2 i Ön. This also means that [L' s z and thus similarly |S| S + ôn. So together:
S
m + 2ôn
2 <
7 En = 2 2
U
By plugging this back into Eq. (99) we get:
OPTs (3+ (3+0()))PTT + OPTTOL +PTTy
(hn - (0) [1) 2| ((n))
<
2(1 1-2)
(1-27)14
(20)
Since [L/1]
[',r get that IT| ~0 |S| and so
S| - |0| - 2|V| - ((6)
10] 2 O(ōn)
= 10 [V]) + IV - O(6m)
(1+)))11- - ((6n)
Where (+) due to: = | [V. 7/4/.
Let us use this fact in Eq. 20 and get:
OPTs + (3 + 0()))OPTT + OPTTLL + OPTV (1 [L]
(2 (1 - -((n)))()))
(1-2>)14) 21-211141 )
ha 9L S
(21)
The second term RHS is (up to 1 (8) factor): h(?)) = = 149
Let find bound or h.
Since [ y:
V R ((6)) Rt', 4
and since R < bōn: T = [V 2 bôn. We deduce:
y 2 1 - 0()). The nominator is decreasing in y and the denominator is increasing in y and thus
1
the maximum is received on the left end point: = 1 0(6). The maximum value of is thus: 2 -0(6))
2 = + 0(5).
So found bound for the RHS of Eq. (1 and therefore:
OPTSs + 12 OPT + OPPTLL + $ OPT 00))PT,
ha S
(1 2y) L
33

---

H.2 Sub-case: m' < 9L-
To handle this sub-case we use reduction the previous sub-case and show that we pay another multiplicative factor of at most + O6)). We show a bound of med1 (hz. L) in case the algorithm returns hg. In the case the algorithm returns h bound for med1 (hR, L) is achieved similarly.
Let بL = m'. For any multi-set of points M C L let OPTM ΣiEM 22 - 9L
L'
L
R
R
Predictions
7I
hg
96
91
Real X
9R
U
Ur
T
4
1r
L
R
Figure 6: Illustration of case (4) where m' < 9L. On the top we have the "estimated" locations hy, hR, computed on X'. On the bottom we have the "real" locations. IL 9R. computed on X. L', R', L'i, L',, R',, R',, S, U, V, Uú, U, are all the same as before. The difference is that m' is now to the left of gL.
34

---

By the exact same analysis of the case where m 2 9L. now we have that m' 2 9r and thus, just like before, 9L h2 OPTs+OPTT++ +OPT....
(1-28) L
But OPTs OPT = OPTs +PP (0L -00-mm]a (0s= (T) and OPTL, OPTL, (g1
m' L-rl-
So together we have:
4OPTs + OPTT (gr. - "01.-m)((55) [T]) + OPT,, + + - ml m(U IV])
gt. - h1
(22)
U1l H 5
- L
1 OPTL, (91 m (-1s) [T) 10 (VD)
(23)
(1 (1-231) 23)
Since LL' a must be the case that |S] [T] マ/ ôn since otherwise there would be strictly
less than elements in [L' For this reason also [U] + [
So 11| [7] + U0| IV S ón. By plugging this in Eq. (2) we get:
4 (OPTss + OPT, OPTL, + (OL - m')( (1 (1-28)
JL h1 <
5
Note that gr. h4. gT. - gr. + gr. - h1. = gr. hr, - (gr. - gT.) (gr. (1.)
(gr. - -m().
By plugging this in the above we get:
(OPTs + OPT, 10 gg m m')
- h4 S
(1-28)
Note that OPT, = = 24 342EEer
ΣiET 9L - m' so 9L m < OPTr
OPTSs + OPT + 2.50PT 5n
fT. - 1-
(1-28)
OPTs + OPT, + OPTL + 20PT 8n n/2-on
5
(1-
4 +1 (1100P77+PPPT)))
(24)
T
and so we get the desired bound (due the equivalent condition stated in Eq. (8)
We conclude with a final remark:
Remark 25. Algorithm 3 does not have (c,ō) approximation robusiness for any
1.667.
This lower bound is obtained by observing the following instance: Let = >> 0 be a small enough value, X RD where n/2 points are at x
n/4 points are one point at M > n. Now let X' be obtained from X by moving the point at x M to = -. Calculation shows that the above instance leads a 5 approximation ratio.
-0.5 - E, "/4 points
and
3
I Second Facility Location: SECONO-PROPRRIONN--MECHAAA
Proofs
In this section we show the strategyproofness and the expected approximation ratio of Algorithm
35

---

Proof of Lemma 6 We follow the proof of (Lu et al. 2010 Thm 4.1). In the proof they show that given that the first facility at 2g for any from X by agent i deviating from to z4 the expected cost of agent i only increases by deviating to xI.. The proof does not depend at all on the location the first facility. Since the first facility is
|nl, then for any X' =<< z X_; that gained
entirely independent of the agent reported values, then the above implies that the choice of the second facility is also strategy proof.
The proof is similar in structure the one given by Lu al. (2010) for the IiportionalMMecaniiit the main difference is careful (and tight) analysis of Lemma 27 for the real line which leads to an approximation ratio at most rather than 4.
Proof of Theorem 7
Let G == J.). S = {i x E X, d(z., S d(a;, and T = [n] \ S.
For any M S X let OPTM medy(M, G). So OPTs med; (S.gs), OPTr med1 (T, gr) and thus OPT = med2(XX,)) = OPTs + OPTr.
Let H = (gs, h) be the algorithms solution for the problem, and ATGG = med2 X, H). We denote A. ALGT to be (S, H), med2(T H) respectively, so that ATG ALGs + AL.T and therefore E[ALG]] = B[ALGs] + [B[AGGT).
Since ALGs S med (S. OPTs, we get that E[ALGs] S OPTs, and we only need find bound for E[ALGT].
E[ALG,]= = Σ
E[ALGr h Pr(h =
(25)
EE mg
Σ GT
B[ALGr| h x.. x.)) Σ E[ALGT h= xr=::Pr(h-- 2.) SET
(26)
In the summation above the first term is the expected cost due to choosing the second facility to be location in S and the second term is the expected cost due to choosing the second facility to be location in We will bound each one individually.
For all i E [n] let = d(z,, gs), =
Eginle and 6, = ((I),TT). So Eies as = OPTs.
Eier d OPT and CiE(n] P: 1. For each j,j E [m] let di,j d(z),
Lemma 26. EiES E[ALGT h = x.] = xx) S OPTs
Proof.
B[ALGr h n. Pr(h = xz)) = Σ Σ
min (a,, dutt)
iES
iES NET
ΣIET dt E at
Σ
P4 Σ iES
S Σ
0; OPTs
Eeegos 0g
SES
KET
iES
Where inequality (+) is gained by ignoring the second facility.
Lemma 27. Σier E[ALGr h = Pr(h x4) s 30РT,
Proof. Let D = d(ga.
Σ E[ALGT = x. sr
Σl
Σ
minfap 2(() Pb
E
iET
VET
triongle inoquality
min az, by + bi
Σ b Σ
minfar (e be, be)
iET
NET
iET
IET
GET
Σ
min(a: be, bit
Pi
Pi
IET
ieT
JET
36

---

pi
+
Σ
minfa:
be,bi) bib
b, Eje(n] aj
ve
ieT
NET
ai bi
Σ
minfa - be. bit
Σ ]jE(m] az
iET
JET
We bound each of these terms individually by OPTr, and thus get the desired bound. The first term bound:
Σ
Σ
be
Pi
=
Σ IET
bt
Σ 'ET
ps S
OPTT
(27)
KET
LET
The second term bound:
Σ
minfae - be,bib b,,bit
Σ a0 - b1 -1)
8; Σ EnE(n) 41)
[jE(n] aj
YET
IET
iET
NET
bi
Σ
Σ VET
b: = OPTT
ΣjE(m) aj
ier
KEeT
The third term bound:
Σ
Σ
minfa:
bebbit
be, bib
ai - bi " EEE(n aj
bi
0: - bi Σ aj
0g bi
Σ |||n [n] aj (28)
KT
VET
iET
KET
SET
We finish the third term bound by showing the following claim Claim 28.
b; Σ aj
ITb:
OPTr
EE
Proof. Let Ta be the part of T closer to as and Tb be the other part T.
So T, TT S d(x,, 9r)), and Tb = T \ Ta- Since the points are all on the line
metric:
For all E Ta: 0; digs, xz) d(gs, gr) b; D b.
For all E Tg: a; = d(gs, x;) = d(gs, 9r) + b, = D + bi.
Let us use these facts in Eq. 28 to get:
bi
D- b, bi
D+ b; - bi Σ aj
T by
|T|b
|T|b
Ejem as
ΣjE(n aj
SE
TET.
iET.
D
2/T') Σier, 6,2
ITID -PPPPPPTT- 2/TT) Eier, 6,²
Σb, by
=
Σje(n aj
ΣSE(n) aj
Σje(n) Oj
NET
T -OD-OPT,--- - )2 (++)
- OPT
2 (OPTT.)
-PPT
(29)
Ejen) Oj
TT OPTT -OPTT.
(+) is due QM AM inequality since
CiET, b,)²
Σ TET.
0 2 >
2 (OPTr.) )
Tal
[T]
37

---

(++) explanation
Σ 9 Σ
Jj +
Σ 02
Σ djj = OPTs+ Σ
D bb DDb + Σ
D bj
jE(n]
JES
jET.
JETb
JET.
JELb
= OPTss + D
OPTR
OPTT. 2 I
OPTT, OPTT.
We now show that
(OPTT.)
T - OPTT
TID+OPT, -OPT S
Indeed, OT 2 O. then D OOPT. -OPT,, 2 D and thus:
- 2 (r.Tr, )
ITD 2 (OPTr.)
T
OPT.
1.
T OPTT.
D
T
Otherwise OPTr. - OPPT. > and thus:
OPTr. OPTT, = OPT, OPTr. + OPTI, <0OPTI.
(OPTT. -OPT OPPT S 2OPTT,
= 90P 20PT,, 3 20 -
TD 21D-2(PPH) (OPTr.)
2(OPTT.)
T OPTT, -PP =1
OPTT. - OPTT S OPTr
OPT
T + OPTr.
T OPTz -OPTr.
So from Eq. 22 Σier [Tbb
Esenn
SPPT..
To summarize:
Σier E[ALG] h = x. Pr(h 24) S
30РТT.
From plugging Lemma 26
Lemma 27 into Eq. 26
we get:
E [[AGG] < 20PT's + 30PT 30PT.
Remark 29, The upper bound of in the analysis of Theorem is tight.
To show tightness, consider an instance with n points on the real line: n/2 points at x. 0, f/2 1 points at x 1, and single point at 2. Assume the given first facility is at 0. The optimal solution puts the second facility at and pays the cost of On the other hand E[ALG]
2-2 2 3 2/2-1 R 3.
#/24
Proof of Theorem
Proof. The proofegysroofness is due the fact that the first facility is chosen based only using the predictions, and the second facility choice is strategyproof due to Lemma 6
Let G (gL, 9R) be the optimal cluster centers for X, and let L, R be the respective corresponding clusters. We consider two cases: when this optimal clustering is b8- balanced, and when it is not; in both cases show that the algorithm achieves low expected cost. Let H (hı, h2) be the solution returned by Algorithm 4
The first case is when (L, R) is a bó-balanced clustering of X. In this case claim that
E meddg (X, H)] < (3.6 O())) medg G).
38

---

Indeed, let T = (f1. tR) be the two centers of the (b 1)6-balanced 2-medians algorithm on X'. Since G induces a bó-balanced clustering, Theorem and our choice of b ensures that
med2(X, 7) 1.2 me).
Since Algorithm returns one of the centers of the (b - 1)0-bblanceed 2-medians algorithm on X" h1, let assume w.l.o.g. that
returns h1 L1 Let (X XR) and
(XL, X/r) be the clusterings of X and X' induced by T' = {tL, (R). From Theorem 7
Elmed2(X, ()] E (X, (1z, h2))] 2 2 medi (X (r) + 3 medi (XR, median(XR) (X))
2 2 med, tL) + 3(1 O()) medj (XR, fR)
$ (3 + (6)) med2(X, T) & (3.6 + (()) (X, G),
where the inequality (+) uses the fact that X and X differ on at most X points, and hence
can sue (1 O(6), 8) approximation-robuttnee of 1-Median from Corollary
Now for the other case: suppose (L, R.) is b6-unbaladced clustering. Theorem implies that either medı h1) & (1.8 + 0()) med1 (L, (1) or med, (R, h1) & (1.8+ + 0(6) med RR ga). W.l.o.g.
consider the first option. Then from Theorem
E(mod2(XX X, H)) - 2 med, (Z, h2) + med, (R,
s 2((1.8 O())) med, (T,, g1)) + med, (R, S (3.6 0()))PPT.
Combining the cases completes the proof.
39

---

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]
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: See Section where list possible directions to improve what we have done in this work, and directions for future work.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results 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]
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
6. Experimental Setting/ettails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
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]
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:p/ppp...aaooo....oppaapaaaa
Answer: [Yes]
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: It is theoretic paper discussing beyond worst case analysis algorithms with predictions.
40

---

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]
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
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 participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
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]
41


Reviews:
[{"review_id": "lEcyXraYry", "reviewer": "Reviewer_HjD5", "summary": "This paper studies a learning-augmented version of the facilitation location mechanism design problem. In particular, the authors consider a model for predictions they call “mostly approximately correct” in which most points have an estimate close to the true value and a small fraction can be arbitrarily wrong. In the paper, they first recap that the standard statistics are indeed robust with respect to distance and approximation. Then, they apply these results to solve 1-facility location in $\\mathbb{R}^d$ and 2-facility location on a line. The latter they do by breaking the problem down into picking the location of the second facility conditioned on the first one being fixed (which is solved by Lu et al. 2020) and separately estimating a good location for the first one.", "questions": "- Why have definitions 9 and 10 been defined in generality for a pair of location estimators $f, \\hat{f}$ that might be the same? It seems like they are only used in the case where \\hat{f} = f, so why not just define them that way to begin with (which is perhaps more familiar to the audience anyway)?\n- In Theorem 2, is $med_1(X)$ the cost for the optimizer of the 1-median cost function? \n- Theorem 4, looks like $\\delta < 1/k^2$ (up to constants) is necessary. Is this a limitation?\n- I would have found it clearer to define a third set $\\tilde{X}$ (which may be dependent on time if the mechanism is iterative) that represents the reported locations of the agents. Then, strategyproofness is just saying that $\\tilde{X} = X.$ That way, it is clear the algorithm gets the _reported_ locations (which confused me at first), but the strategyproof property of the mechanism means agents have no reason to deviate from the truth. \n- It would be helpful to have a short explanation of why the coordinatewise median gets $\\sqrt{d}$ approximation factor.\n- In lines 294-295, what is the randomness over? Is it randomness over the state of the world? So with probability, e.g., 1/n^2, all of the points could be bad?\n- Generally, it would be helpful as a reader to receive some prose descriptions of the algorithms, why they work, and the results as they are presented in technical detail.\n- it would be helpful to have a summary table of the problem with different values of k, d and with/without randomization, with/without MAC advice (your results) for at-a-glance parsing the strengths of your paper.\n- Relatedly, are there computational hardness results? \n- Can you please briefly comment on other abstractions people have used for learned auxiliary inputs to an algorithm? And how MAC is similar / different to them? The nature of the prediction in [Agrawal 2022] is quite different.\n\nSmall things:\n- I believe lines 222-224 need to be moved to before Definition 6\n- Please add a definition of “strategyproof”\n- line 332, I believe the citation year should be 2020", "limitations": "theorem statements detail the settings in which they apply, so the scope of the theoretical results are well-addressed.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- defines MAC predictions in a sensible way\n- uses results from robust statistics to show that MAC predictions can be used for the original problem\n- provides results for a handful of relevant versions of the problem\n- they claim results show that the problem strictly benefits from having this kind of MAC advice, demonstrating a separation between what can be done without the advice and what can be done with it. If this is true, this is a great strength of the paper.", "weaknesses": "I am unsure if I quite believe the claim that the problem strictly benefits from having this kind of MAC advice for the following reason. It seems in line 331-2 that the better approximation factor comes from analyzing the algorithm in a more restricted metric space, not from having access to the MAC advice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed and helpful feedback! We are glad that the reviewer appreciated many aspects of our work. We respond to your comments and questions below. If our response to the suspected concern is satisfactory, we would greatly appreciate it if you would consider raising your score.\n1. **Concerns**:\n* **Concern**: “It seems in line 331-2 that the better approximation factor comes from analyzing the algorithm in a more restricted metric space, not from having access to the MAC advice.”\n\n    **Reply**: The approximation ratio of $4$ for the algorithm of Lu et al. (2010) [1] is in fact **tight for the line metric space**. (See Section 4.3 of their paper showing a lower bound of 4 for the performance of their algorithm for points on the line.) So the access to the MAC advice is indeed crucial for improving the approximation (to $3.6 + O(\\delta)$) for this tight case.\n\n    Thus our result does separate between what can currently be done with/without advice, and we thank you for noting this is a strength of our paper.\n\n\n    Our results show that MAC predictions are useful for other problems too (like the single facility case, and the balanced k-facilities), and we hope that these will be useful for other settings --- including the approximation for two-facility location on more general metrics --- in the near future.\n2. **Questions**:\n    * **Question**: “Why have definitions 9 and 10 been defined in generality for a pair of location estimators  $f,\\hat{f}$  that might be the same? It seems like they are only used in the case where $\\hat{f} = f$, so why not just define them that way to begin with (which is perhaps more familiar to the audience anyway)?” \n\n        **Reply**: In Theorem 4 we use different  $f,\\hat{f}$, which is why we defined it that way. If the reviewer thinks it is too confusing, we are open to changing that.\n\n    * **Question**: “In Theorem 2, is  𝑚𝑒𝑑1(𝑋)  the cost for the optimizer of the 1-median cost function?”\n\n        **Reply**: Yes, we will clarify this.\n    * **Question**: “Theorem 4, looks like  $\\delta < 1/k^2$  (up to constants) is necessary. Is this a limitation?”\n\n        **Reply**: This is an interesting direction, we don’t think getting delta larger than $1/k^2$ is a barrier in general, but we don’t have better bounds yet.\n    * **Question**: “I would have found it clearer to define a third set $\\tilde{X}$  (which may be dependent on time if the mechanism is iterative) that represents the reported locations of the agents. Then, strategyproofness is just saying that  $\\tilde{X}=X$.  That way, it is clear the algorithm gets the reported locations (which confused me at first), but the strategyproof property of the mechanism means agents have no reason to deviate from the truth.”\n\n        **Reply**: We considered that option, but worried that it would add more notation to the paper. We can definitely add a sentence clarifying this point.\n    * **Question**: “It would be helpful to have a short explanation of why the coordinatewise median gets 𝑑 approximation factor.”\n\n        **Reply**: We will add this. In short it is because the coordinatewise median is the optimal solution w.r.t the L1 norm, which is at most sqrt(d) times L2 norm.\n    * **Question**: “In lines 294-295, what is the randomness over? Is it randomness over the state of the world? So with probability, e.g., $1/n^2$, all of the points could be bad?”\n\n        **Reply**: Both your statements are correct. In essence, this captures a PAC-style setting, where there is a small probability (e.g. $1/n^2$) that all points could be bad. We hedge against this by using the $O(n)$-approximate Min-Bounding-Box mechanism in this (low-probability) bad event, as we explain in appendix F.3.\n    * **Proposition**: add descriptions of the algorithms and a summary table of the problem.\n\n        **Reply**: We will add descriptions and a summary as suggested (also see the tables in the pdf file attached in the global response).\n    * **Question**: “Relatedly, are there computational hardness results?”\n\n        **Reply**: We don’t have any yet, but that’s a great question and we will continue to think about this.\n    * **Question**: “Can you please briefly comment on other abstractions people have used for learned auxiliary inputs to an algorithm? And how MAC is similar / different to them? The nature of the prediction in [Agrawal 2022] is quite different.”\n\n        **Reply**: We have a comparison of related abstractions people use for learned auxiliary inputs in the related work section 3 (lines 179-191), the model section (lines 83-103), as well as Appendix A (lines 558-591), but let us comment here on the most related work. \n        The predictions in [Agrawal 2022] (and relatedly [Xu&Lu 2022]) are indeed quite different: they predict only the optimal facility location(s) for facility location, for one and two facilities respectively. Unlike these works (and many others), we don’t predict the optimal *solution* to the problem, but instead predict the *input*. Moreover, their measure of the prediction error is the distance between the predicted solution and the real one, while our measure is the fraction of errors, regardless of how bad each error is. This allows us to capture the property that some predictions may be arbitrarily bad (outliers), but most of the predictions are good — this fine-grained notion is difficult to achieve using a single prediction.\n    * **Small things**: **Reply**: We will address these issues. (One clarification, though: the Lu et paper we refer to is from 2010,  not 2020:\n\n      [1] Pinyan Lu, Xiaorui Sun, Yajun Wang, and Zeyuan Allen Zhu. 2010. Asymptotically optimal strategy proof mechanisms for two-facility games. In Proceedings of the 11th ACM conference on Electronic commerce. 315–324.\n\n      Did you have a different paper in mind?)", "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": "6bRKxVqrrd", "reviewer": "Reviewer_JMjQ", "summary": "This work considers facility location mechanism design in the presence of (pretty good) advice on locations. In this setting, agents report their locations to impact the places facilities are installed or built. In this model, the designer has access to advice that is Mostly and Approximately Correct, a notion introduced by this work whereby at least $1-\\delta$ of the advice is approximately correct with additive error at most $\\epsilon$.\n\nThe authors show that they can use that advice to beat the theoretical results without advice. In particular, for 2 facility location on a line, they can achieve approximation ratio of $3.6 + O (\\delta)$, a significant improvement over the best known without advice. \n\nThe algorithm for merging the advice and reports is a simple combination of the two: first, use the advice to place the first facility, then use the agent reports to place the second facility. The analysis is quite related to some analysis from Lu et al 2010 for facility location in metric spaces without advice, but they are able to improve the analysis since they are on the line.", "questions": "Relative to the work without predictions, there is the requirement that the number of agents assigned to each facility is at least a minimum value. How sensitive is this? Can this be dropped or is there a tight upper bound?", "limitations": "N/a", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This work presents a general model, MAC,  for advice that would seem to be useful in many other situations. In particular the model includes a small chance of arbitrarily bad advice. \n\nThe presented algorithm details how to use that advice in order to improve on the classic 2-facility location on a line problem.", "weaknesses": "While the MAC notion is a clean one that would seem to be a good vehicle for exploring advice, the additive error here plays a minimal role - the authors immediately drop the $\\epsilon$ everywhere... \"we drop the $\\epsilon$ from the calculations to avoid \"dragging\" the additive $\\epsilon$-dependent term along each result\". As a result of that... is it really better to include it in the first place if you're going to ignore it? Or better to say that the advice is mostly correct and then describe how behavior scales with the additive error? It feels overall like a simpler notion from literature could have been used for advice if the additive error wasn't going to play any sort of role in the analysis.\n\nThe underlying approach - while beneficial that it is simple, is a little dependent on the fact that it is somewhat easy to split this problem into two: the first facility location, and the second facility location. The approach and analysis for the second facility location draws very heavily on prior work from Lu et al (2010), and is able to improve on that primarily because of the restriction to real line rather than metric. \n\nRelative to prior work, this work assumes a prediction for each agent. This helps quite a bit in minimizing error, as the use of medians and clustering can mitigate the risk of some outliers. As a result, I wouldn't say that the impact is an improvement on an existing result, but more of a change in the type of error and prediction.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback! We are glad that the reviewer appreciated some aspects of our work like its usefulness in many situations. We respond to your comments and questions below. If our response is satisfactory, we would greatly appreciate it if you would consider raising your score.\n* **Concern**: “While the MAC notion is a clean one that would seem to be a good vehicle for exploring advice, the additive error here plays a minimal role - the authors immediately drop the  𝜖  everywhere... \"we drop the 𝜖  from the calculations to avoid \"dragging\" the additive 𝜖-dependent term along each result\". As a result of that... is it really better to include it in the first place if you're going to ignore it? Or better to say that the advice is mostly correct and then describe how behavior scales with the additive error? It feels overall like a simpler notion from literature could have been used for advice if the additive error wasn't going to play any sort of role in the analysis.” \n\n    **Reply**: We agree it is an option to drop 𝜖 for much of this work (and call it Mostly Correct Predictions), but we see the following advantages in keeping it:\n\n    1. We wanted to present a general/flexible model that would be useful for problems beyond those considered here. To the best of our knowledge, mechanism design subject to our definition of MAC predictions has not been studied even for the 𝜖=0 case, so we could not revert to existing notions from the literature. Moreover, we anticipate that the case of non-zero 𝜖 may be interesting in other settings, and we wanted to present a comprehensive model to the community.\n\n    2. We think that in many instances of facility location it might be unrealistic to expect perfect predictions (𝜖=0), but is realistic to expect a small 𝜖. This notion emphasizes that this is not a problem, and is handled just as well by the model.\n\n* **Concern**: “while beneficial that it is simple, is a little dependent on the fact that it is somewhat easy to split this problem into two: the first facility location, and the second facility location”. \n\n    **Reply**: While our Robust Half technique approach does proceed in two stages, the stages delicately complement each other, rather than being independent. The first stage for choosing the first facility via Big-Cluster-Center using the robust statistics results we developed in Appendices F and H, has different guarantees for balanced and unbalanced instances. The second stage chooses the second facility using both the predictions (by using the first facility) and the input (reported locations). Finally, it is only the characterization we develop for balanced vs unbalanced optimal clustering cases that allows us to show that the two stages together return a good solution, as in the proof of Theorem 9 (Appendix J).\n* **Concern**:  “The approach and analysis for the second facility location draws very heavily on prior work from Lu et al (2010), and is able to improve on that primarily because of the restriction to real line rather than metric.” \n\n    **Reply**: The approximation ratio of 4 for the algorithm of Lu et al. is in fact **tight for the line metric space** (see Section 4.3 of their paper showing a lower bound of 4 for the performance of their algorithm for points on the line). So the access to the MAC advice is crucial for improving the approximation (to $3.6 + O(\\delta)$) for this tight case. Thus our result separates between what can currently be done with/without advice!\n\n    Our results show that MAC predictions are useful for other problems too (like the single facility, and the balanced k-facilities), and we hope they will be useful for other settings --- including the approximation for two-facility location on more general metrics --- in the near future.\n * **Concern**: “Relative to prior work, this work assumes a prediction for each agent. This helps quite a bit in minimizing error, as the use of medians and clustering can mitigate the risk of some outliers. As a result, I wouldn't say that the impact is an improvement on an existing result, but more of a change in the type of error and prediction.”\n\n    **Reply**: We completely agree: we get an improvement over the “no predictions” setting, but in relation to the previous models, the MAC model is incomparable. That said, it presents a different and useful (and also important, we believe) perspective: by allowing a delta fraction of the predictions to be arbitrarily bad, it is robust to outliers, and gives a finer-grained control over the kinds of errors that may arise in applications. \n* **Question**: “Relative to the work without predictions, there is the requirement that the number of agents assigned to each facility is at least a minimum value. How sensitive is this? Can this be dropped or is there a tight upper bound?”\n\n    **Reply**: To avoid any possible misunderstanding, let us emphasize that our main results do not require that the number of agents assigned to each facility is at least a minimum value. The only results with this requirement are Theorem 4/Theorem 13 on the balanced k-facility location (for k>1) with predictions.\n\n    About the sensitivity: The bounds we know on the sensitivity are in Theorem 13 (line 898, Appendix G). At a high level, this says that our approximations improve as we consider more balanced solutions. Moreover, we cannot remove the balancedness assumption for this type of mechanism as Example 1 (lines 63-68) shows. We do not have a bound in the general case.\n\n    Finally, we note that the balanced setting is closely related to the capacitated variant of the problem — studied without predictions by Aziz et al. (2020) who showed a linear (O(n)) approximation ratio for k=2. For k=2 the minimum cluster size setting implies a maximum size (capacitated) and vice versa; therefore, Theorem 13 can be viewed as an improvement of the capacitated variant via MAC predictions to a constant approximation ratio.", "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": "Y2Fcah1q6O", "reviewer": "Reviewer_4KnM", "summary": "The authors study variants of the facility location problem from a mechanism design perspective, in which the mechanism receives predictions on the agents' locations. A percentage of the predictions may have an unbounded error, whilst the remainder of the predictions can be incorrect up to a certain bound. This is in contrast to most existing work on facility location with predictions, in which the designer is given predictions for the optimal facility placements.  Specifically, the paper looks at the single facility location problem in multiple dimensions, and the 2-facility location problem on a line, designing strategyproof mechanisms with bounded approximation ratios.", "questions": "Could the authors give some precise examples on how the algorithms’ approximation ratios would change for both small and large epsilon>0? If my understanding is correct, would each approximation ratio have an additive epsilon*n term for small epsilon, and be unbounded for large epsilon?\nWould “winner-imposing mechanisms” such as from the paper “Winner-Imposing Strategyproof Mechanisms for Multiple Facility Location Games” by Fotakis and Tzamos (2013) be applicable in this setting? If so, could this concept be used to extend the “second-proportional mechanism” to multiple facilities?\nRegarding the phrase “While we have not optimized the constants,…” on line 129, specifically which constants are being referred to here? And can the authors comment on how much room there is for improvement?\nAre the existing deterministic mechanisms for the 2-facility location problem with predictions (in the paper by Xu and Lu (2022)) immediately applicable in this setting?", "limitations": "N.A.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is written and structured very well, and I had almost no issues with understanding the paper. I found very few typos or grammatical errors (see Minor comments).\nThe setting is novel, well-motivated, and is applicable to a wide range of researchers (as the paper is relevant to the fields of both machine learning and computational social choice/mechanism design).\nI did not find any errors in the proofs, which were technically sound.\nThe approximation ratios achieved by the algorithms improve on existing results under reasonable conditions (though this is achieved with the help of predictions).\nThe use of the Big-Cluster-Center mechanism and its analysis is quite interesting.", "weaknesses": "My main concern is on the omission of the epsilon term throughout the paper and slightly vague discussion in the appendix, which is a bit suspicious. This could be improved by being more precise with the effect of epsilon on the results. (see the first question)\nMinor comments:\nQuestion 1: “despite large” -> “despite a large”\nLine 74: add a comma -> “using agent reports, it is…”\nLine 299: add a comma after the approximation ratio expression\nLine 358: “sine”-> “since”\nThe references in lines 55-57, 84-86, 194 should be \\citep instead of \\citet\nTheorem 9 begins with “For a for a”\nDefinition 13 could be written slightly more formally: instead of “the goal is”, the authors could write something like “the objective is”", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback! We are glad that the reviewer appreciated many aspects of our work. In what follows, we attempt to address the remaining concern and questions. \n* **Concern**: “My main concern is on the omission of the epsilon term throughout the paper and slightly vague discussion in the appendix, which is a bit suspicious. This could be improved by being more precise with the effect of epsilon on the results. (see the first question)”\n\n    **Reply**: In the reply to the first question later in this rebuttal, we explain the mixed-additive-and-multiplicative nature of the cost that we get by introducing epsilon, showing why it is in fact reasonable to not include it in the calculation. We note that while we considered dropping epsilon from this work (and calling it Mostly Correct Predictions), we ultimately decided to keep it for the following reasons:\n\n    1. We wanted to present a general/flexible model that would be useful for problems beyond those considered here. To the best of our knowledge, mechanism design subject to our definition of MAC predictions has not been studied even for the epsilon=0 case, so we could not revert to existing notions from the literature. Moreover, we anticipate that the case of non-zero epsilon may be interesting in other settings, and we wanted to present a comprehensive model to the community.\n\n    2. We think that in many instances of facility location it might be unrealistic to expect perfect predictions (𝜖=0), but is realistic to expect a small 𝜖. This notion emphasizes that this is not a problem, and is handled just as well by the model.\n\n* **Regarding the minor comments**: Thank you, we will fix all these. \n* **Question**: “Could the authors give some precise examples on how the algorithms’ approximation ratios would change for both small and large epsilon>0? If my understanding is correct, would each approximation ratio have an additive epsilon*n term for small epsilon, and be unbounded for large epsilon?” \n\n\n    **Reply**: Since the cost increases additively by at most 𝜖*n for all values, we would get a mixed-additive-and-multiplicative result in this setting. Hence, as 𝜖 gets large compared to OPT/n (i.e., large compared to the average optimal cost for each client), our approximation would indeed be unbounded. In this case, one can say that the predictions are not worth using, since the noise (the additive error in the predictions) is more than the signal (the average cost for clients).\n\n    * *For instance*, consider the (degenerate) single facility location problem with n input agents, all located on the real line at x=0, and all MAC predictions are x=𝜖. Our mechanism would return x=𝜖 as the location for the facility. The mechanism’s cost is 𝜖*n while the optimal cost is 0, resulting in an unbounded approximation ratio. While each agent only pays an 𝜖 more, the (purely multiplicative) approximation ratio does not capture the fact that this is still a good solution for a small 𝜖. This kind of example can be extended to k facilities.\n\n\n    We are happy to add this discussion to the next version.\n* **Question**: “Would “winner-imposing mechanisms” such as from the paper “Winner-Imposing Strategyproof Mechanisms for Multiple Facility Location Games” by Fotakis and Tzamos (2013) be applicable in this setting? If so, could this concept be used to extend the “second-proportional mechanism” to multiple facilities?” \n\n    **Reply**: This is a very interesting question. As Fotakis and Tzamos (2013) point out, giving the mechanism power to force agents to only use a single facility does indeed improve the approximation ratio to a k-dependent constant. Without this additional power, the problem is harder: for $k=3$ they get a linear $(n-1)$ approximation ratio.\n\n    We focused on the problem without this additional power, but we believe it likely that utilizing this additional power can yield better approximation ratios with MAC predictions as well. One promising strategy could be to use the matching between predictions and agent-reported values (as we mention in lines 383-385). This way, it might be possible to force an agent to only use a facility near its predicted value if the reported value is close to the predicted value. This will be a great future direction!\n* **Question**: “Regarding the phrase “While we have not optimized the constants,…” on line 129, specifically which constants are being referred to here? And can the authors comment on how much room there is for improvement?” \n\n\n    **Reply** We refer mostly to the constants in Theorems 4 and Theorem 13. It is tight asymptotically in terms of the balancedness constant b: given a constant $k$, the approximation ratio of our mechanism is $1 + \\Omega(1/b)$ (we have such an example for $k=2$ which we omitted from the paper). There is room for improvement here for large values of $k$, specifically in extending the theorem to larger values of $\\delta$.\n\n* **Question**: “Are the existing deterministic mechanisms for the 2-facility location problem with predictions (in the paper by Xu and Lu (2022)) immediately applicable in this setting?” \n\n    **Reply**: Indeed, we can use the optimal solution for the predicted points as the predicted centers, and then use the mechanism of Xu and Lu (2022). However,\n    the instance from Example 1 shows that even a single outlier can cause the predicted solution’s optimum to be very bad and thus their mechanism will also perform poorly given this prediction.", "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": "VrfvIjBCpr", "reviewer": "Reviewer_8TXK", "summary": "This paper studied facility location games with mostly approximately correct (MAC) predictions. In this setting, there are n agents in a metric space, and k facilities to be located in that space. The cost of each agent is defined as the minimum distance from the facilities to their location. Each agent location is private, and the mechanism designer can predict the agent locations. In a MAC prediction, there are two parts of data: some (more than half) are approximately correct up to an additive error, and the others are arbitrary. The goal is to approximately minimize the total cost of all agents while eliciting truthfulness, given the predictions.\n\n-For a 2-facility location on a line space, they designed a randomized mechanism that guarantees an expected approximation ratio of 3.6+, which is better than the result which is derived from the no-prediction setting.\n\n-For single-facility location in a more general metric space, they designed a deterministic mechanism which is better than the result which is derived from the no-prediction setting when the part of arbitrary prediction is small.\n\n-They also studied k-facility location in a general metric space where at least a fraction of the agents must be assigned to each of the k-facilities. A truthful mechanism with a constant approximation ratio is presented.", "questions": "No question.", "limitations": "N.A.", "rating": 4, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "Overall, this is an interesting and new topic with a few papers having studied facility location with prediction. The leverage of the prediction helps to improve the approximation ratio when we deal with multiple facilities and multi-dimensional space.", "weaknesses": "One concern is that I am not sure whether the MAC model is natural enough in this problem. I find the mechanisms designed in this paper are not very interesting in the sense that the predictions are exploited in a very heavy way. For most of the mechanisms, they go like this: if some conditions are satisfied, the mechanism uses the predictions with the agents’ reports completely ignored; otherwise, the predictions are ignored and traditional facility location mechanisms are used. This makes me feel that the mechanisms are artificial, and I also feel like the conceptual contribution of this paper is incremental due to this.\n\nMoreover, the structure of the paper can be improved. The model proposed is quite general while many special cases are studied. For example, there are many settings such as single/2/k facilities, deterministic/randomized mechanisms, and line/general spaces. It would be better to give a table to tell which combinations are addressed and which are not.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. We respond to your comments and questions below. If our response is satisfactory, we would greatly appreciate it if you would consider raising your score.\n * **Concern**: “One concern is that I am not sure whether the MAC model is natural enough in this problem.”\n\n    **Reply**:  We would like to try and demonstrate that the MAC model is quite natural as a way to capture predictions for facility location mechanism design problems. For example, in such problems, historical data can give predicted locations for each of the agents, which we can then use (along with agent reports) to get better mechanisms.\n    Another “real life” motivational example is the following:\n    * *Example*: A large tech company (such as Google or Apple) wants to set up a facility (such as a physical store or data center) as close as possible to its users' home location in some city. They can predict home locations of people via a learning algorithm, trained on features such as GPS data, which WiFi hotspots they are connected to, which stores they often buy at (via wallet application data), and more. When a prediction is correct, it might be close to correct (approximately correct), e.g., due to GPS location not being accurate so the neighboring house location might be predicted rather than the real one. Also, it might be the case that a prediction is far from being correct (such as faulty GPS data, or a place of work being identified as a place of living). For most people, the features contain enough information to approximately predict their home location.\n\n    Please also see the discussion in the introduction section (lines 41-80) for why this kind of model is needed to support handling the important issue of outliers, and the discussion in appendix B laying out more potential sources for such MAC predictions.\n\n* **Concern**: “I find the mechanisms designed in this paper are not very interesting in the sense that the predictions are exploited in a very heavy way. For most of the mechanisms, they go like this: if some conditions are satisfied, the mechanism uses the predictions with the agents’ reports completely ignored; otherwise, the predictions are ignored and traditional facility location mechanisms are used. This makes me feel that the mechanisms are artificial, and I also feel like the conceptual contribution of this paper is incremental due to this.”\n\n    **Reply**: The mechanisms that only use predictions (and ignore the agent reports) are the ones in the “warm up” Section 6.1: these results are to develop our tools and build towards the main results.\n\n    The main technical core of the paper is in Section 6.2, which incorporates both the predictions and the input (agent-reported locations) in quite a non-trivial way. Indeed, we strongly believe it goes beyond the common approach of interpolating between the best “no predictions” algorithm and the approach of completely trusting the predictions: \n    * The first stage for choosing the first facility via Big-Cluster-Center using the robust statistics results we developed in Appendices F and H, has different guarantees for balanced and unbalanced instances. \n    * The second stage chooses the second facility using both the predictions (by using the first facility) and the input (reported locations). \n    * Finally, it is only the characterization we develop for balanced vs unbalanced optimal clustering cases that allows us to show that the two stages together return a good solution, as in the proof of Theorem 9 (Appendix J).\n\n    This is why we believe the resulting mechanism is interesting and non-trivial. We hope you will agree with us!\n * **Concern**: “Moreover, the structure of the paper can be improved. The model proposed is quite general while many special cases are studied. For example, there are many settings such as single/2/k facilities, deterministic/randomized mechanisms, and line/general spaces. It would be better to give a table to tell which combinations are addressed and which are not.” \n\n    **Reply**: One contribution of the paper is to introduce the new model which is general, and to show how it can be used to achieve beyond worst-case analysis in several examples (of facility location mechanism design). We thank the reviewer for suggesting a table for the results and we completely agree it will make things clearer. We intend to add it to the next version.", "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 the reviewers for taking the time to carefully read our work and for their valuable feedback.

We reply to specific points of each reviewer separately.

Meta-review: This paper provides a new prediction model for algorithms with predictions called MAC advice where a fraction of the predictions can be arbitrarily wrong and the other predictions must be approximately correct. The authors study this new model in the context of facility location mechanism design. This new MAC advice model is interesting and well-motivated. It might be of broader interest and lead to follow-up work that uses this model for other problems
Decision: Accept (poster)