MAC Advice for facility location mechanism design

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.

• Concern: “One concern is that I am not sure whether the MAC model is natural enough in this problem.”

  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. Another “real life” motivational example is the following:

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

  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.

• 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.”

  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.

  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:

  • 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).

  This is why we believe the resulting mechanism is interesting and non-trivial. We hope you will agree with us!

• 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.”

  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.

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.

• 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)”

  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:

  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.

  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.

• Regarding the minor comments: Thank you, we will fix all these.

• 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?”

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

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

  We are happy to add this discussion to the next version.

• 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?”

  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.

  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!

• 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?”

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

• 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?”

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

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.

• 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.”

  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:

  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.

  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.

• 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”.

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

• 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.”

  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!

  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.

• 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.”

  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.

• 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?”

  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.

  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.

  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.

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.

1. Concerns:

• 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.”

  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.

  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.

  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.

2. Questions:

   • 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)?”

     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.

   • Question: “In Theorem 2, is 𝑚𝑒𝑑1(𝑋) the cost for the optimizer of the 1-median cost function?”

     Reply: Yes, we will clarify this.

   • Question: “Theorem 4, looks like $\delta < 1/k^2$ (up to constants) is necessary. Is this a limitation?”

     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.

   • 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.”

     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.

   • Question: “It would be helpful to have a short explanation of why the coordinatewise median gets 𝑑 approximation factor.”

     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.

   • 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?”

     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.

   • Proposition: add descriptions of the algorithms and a summary table of the problem.

     Reply: We will add descriptions and a summary as suggested (also see the tables in the pdf file attached in the global response).

   • Question: “Relatedly, are there computational hardness results?”

     Reply: We don’t have any yet, but that’s a great question and we will continue to think about this.

   • 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.”

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

   • Small things: Reply: We will address these issues. (One clarification, though: the Lu et paper we refer to is from 2010, not 2020:

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

     Did you have a different paper in mind?)

I follow your point re the approximation factor. Thanks for the clarification. But if I understand correctly, the factor $3$ you show is for second-facility location, whereas the factor $4$ Lu et al. show is for the full 2-Facility Location problem? In which case the apples-to-apples comparison that should appear in line 331 should be $3.6 + O(\delta).$ Also, please add theorem and section references for the Lu result into your paper so it is clear to the reader exactly what you are citing + comparing to.

Edited to add: I see that another reviewer also had a similar confusion to me about this issue so please clarify it in the paper.

Your responses for the rest sound good! Couple points:

• I think adding $\tilde{X}$ as mentioned above would actually help greatly in clarification despite the fact that it adds notation.
• I don't see a pdf attached in the global response. Am I looking in the wrong place?
• I noticed the discussion in the related work about the abstractions for learned auxiliary inputs! I was particularly curious about the input learning-augmentation -- have there been other attempts for this kind of augmentation for related problems, e.g. clustering? If not, is studying such problems in the MAC setting interesting? If so, would suggest mentioning that in the Future Directions section!
• Re Lu 2010 -- you're right; I was looking at the wrong entry, sorry!

• Thank you for the clarification on the approximation factor -- indeed those lines were a bit confusing, and I appreciate that you will fix them in the next version.
• You interpreted "input learning-augmentation" exactly as I meant it! Apologies for the lack of clarity. Thanks for the discussion on it, and I would be excited to see future work looking at this style of "noisy" data.
• Got it, okay.

I appreciate the clarifications and trust the authors will make updates to the paper based on the discussion here. I am happy to increase my score from 6 to 8.

Edited to add: the particular reason for skipping 7 is that if indeed there is not other work that tries to model "noisy input" to this class of problems in this way, that is a significant contribution to the community. The specific problem studied here and algorithms provided are interesting, to be sure, but the novelty and sensibility of the MAC model are perhaps the more interesting contributions.