MAC Advice for Facility Location Mechanism Design

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

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

Questions

No question.

Rating

4

Confidence

3

Soundness

4

Presentation

2

Contribution

2

Limitations

N.A.

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.

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). The 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). I did not find any errors in the proofs, which were technically sound. The approximation ratios achieved by the algorithms improve on existing results under reasonable conditions (though this is achieved with the help of predictions). The 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) Minor comments: Question 1: “despite large” -> “despite a large” Line 74: add a comma -> “using agent reports, it is…” Line 299: add a comma after the approximation ratio expression Line 358: “sine”-> “since” The references in lines 55-57, 84-86, 194 should be \citep instead of \citet Theorem 9 begins with “For a for a” Definition 13 could be written slightly more formally: instead of “the goal is”, the authors could write something like “the objective is”

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

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

N.A.

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

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

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?

Rating

5

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

N/a

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.

Strengths

- defines MAC predictions in a sensible way - uses results from robust statistics to show that MAC predictions can be used for the original problem - provides results for a handful of relevant versions of the problem - 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.

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)? - In Theorem 2, is $med_1(X)$ the cost for the optimizer of the 1-median cost function? - Theorem 4, looks like $\delta < 1/k^2$ (up to constants) is necessary. Is this a limitation? - 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. - It would be helpful to have a short explanation of why the coordinatewise median gets $\sqrt{d}$ approximation factor. - 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? - 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. - 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. - Relatedly, are there computational hardness results? - 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. Small things: - I believe lines 222-224 need to be moved to before Definition 6 - Please add a definition of “strategyproof” - line 332, I believe the citation year should be 2020

Rating

8

Confidence

3

Soundness

4

Presentation

4

Contribution

3

Limitations

theorem statements detail the settings in which they apply, so the scope of the theoretical results are well-addressed.