Randomized Strategic Facility Location with Predictions

Summary

The paper considers the strategic (single) facility location problem where the goal is to decide on the location of a single facility given the preferred locations {p_i} of n agents. The preferred locations p_i are private information and the goal is to design strategyproof mechanisms so that the agents reveal their true preferences. The quality of a solution is measured by its egalitarian cost, i.e., the maximum distance between any agent location (p_i) and the facility. The paper considers the problem when the mechanism has as input some predictions regarding agent's private preferences. This problem has been initially considered by Agrawal et al in EC'22 where they assume that the prediction is a single point denoting the location of the optimal facility. The paper mainly shows lower bounds on the achievable consistency / robustness in different settings. First, on a line metric, the authors show that any mechanism that is (1+delta) consistent (for 0 < delta < 0.5) must be >=(2-delta)-robust, even with strong predictions about the preferences of each agent. This trade-off is also tight and every point on this frontier can be attained by a simple mechanism that randomizes between the (1-consistent, 2-robust) mechanism of Agrawal et al and a classical 1.5-robust (and 1.5 consistent) randomized mechanism. Second, in two dimensional Euclidean metrics, the authors first provide a new lower bound of 1.11 in the classical (no predictions) setting. In the learning augmented setting, they show two other lower bounds - (i) no deterministic mechanism can have better than 2 consistency and better than 1+\sqrt(2)-robustness; (ii) no randomized mechanism can have 1-consistency and better than 2-robustness. Lastly, the authors consider a new setup where the mechanism has access to the identities of the most extreme agents, i.e, agents who incur the maximum cost in the optimal solution. In this setting, the paper shows that a variant of the centroid mechanism is 1.67-consistent and 2-robust.

Strengths

- The paper considers a very natural problem. The proposed mechanism is very accessible and easy to follow. - The paper has been well-written and is nice to read.

Weaknesses

- The paper mainly gives lower bounds in the different settings. The only positive result is obtained via running the centroid mechanism on the (predicted) extreme agents. - The proofs are terse and a bit hard to follow - for example, adding a small picture would help improve readability of many proofs (e.g. proof of Thm 2 could use a diagram illustrating the pythagoras ineq used).

Questions

- Could you add a discussion / reference for why the 1-d lower bound does not hold in 2 dimensions?

Rating

4

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

Summary

In this paper, the authors study the metric space facility location problem with machine-learned predictions. Specifically, they focus on the setting that the mechanism has predictions of every agent’s preferred location and with randomized mechanisms. The goal is to find truthful mechanisms that minimize the egalitarian social cost. The effectiveness of the algorithms are evaluated by their consistency (approximation ratio when the prediction is correct) and robustness (approximation ratio regardless of the quality of the prediction). For the single-dimensional setting, they first show that prior work with weaker predictions only on the optimal facility location are already Pareto optimal. Then, they further complete the full Pareto frontier by randomizing between the deterministic and randomized mechanisms. For the two-dimensional setting, they prove an improved lower bound of 1.11 approximate ratio for all randomized mechanisms. They also show that no deterministic mechanism can be better than 2-consistency and (1+$\sqrt{2}$)-robustness, and no randomized mechanism can be better than 1-consistency and (1+$\sqrt{2}$)-robustness. Finally, they show that a truthful randomized mechanism that only has a prediction of the identities of the most suffered agent can achieve 1.5-consistency and 2-robustness.

Strengths

This paper is nicely built on prior work of both the classic facility location problem and mechanism augmentation with machine-learned predictions, which gained much attention in recent years. The paper is mostly well written and I enjoyed reading it. The theoretical results are solid and I think would be valuable for the research community.

Weaknesses

* Several related papers [Procaccia and Tennenholtz, 2013], [Agrawal et al. 2022], [Tang et al., 2020] study both the total social cost and egalitarian social cost, but this paper only focuses on the egalitarian cost. I understand that the egalitarian cost matches well with the “extreme ID prediction” assumption in Section 4.2, but I think this paper would be much stronger with some results of the total social cost setting. * Minor comments * I was initially confused about line 83-85, as it is first claimed no deterministic mechanism can combine better than 2-consistency with 1 + $\sqrt{2}$-robustness, and then mentioned previous work achieved 1-consistency with 1 + $\sqrt{2}$-robustness. Maybe replace “combine better” with a more concrete statement, like the statement in Theorem 3. * Page 2, line 70: 2 + $\delta$ robust -> 2 - $\delta$ robust * Page 3, line 121: need a space in “design,Agrawal” * Page 5, line 230: “cause at least as much cost to the agent on $x_R$ as to the other agent” Would you explicitly point out what “the other agent” means?

Questions

* In Lemma 1, line 235 assumes the agent at $x_L$ reports a false location. Is this assumption general enough to show that no agent would misreport? Also in Lemma 1, line 238 to 248 considered two cases that $x_L < x’_L$ or $x_L > x’_L$. How about the case $x’_L > x_R$? * As mentioned above, several related papers [Procaccia and Tennenholtz, 2013], [Agrawal et al. 2022], [Tang et al., 2020] study both the total social cost and egalitarian social cost. I wonder if you have explored the total social cost objective. * Have you considered this problem in a general metric space? Are there any straightforward results?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Future directions including closing the gap between upper and lower bounds are discussed in the paper. I think there are also other interesting directions like extending the setting to general metric or consider total social cost and the objective function.

Summary

The paper revisits the strategic facility location problem, focusing on the role of randomization in designing truthful mechanisms enhanced by machine-learned predictions. The authors build on a recent framework that refines worst-case results by incorporating potentially incorrect predictions about agents' true locations. They aim to achieve both strong consistency, which provides optimal guarantees when predictions are accurate, and near-optimal robustness, ensuring acceptable performance even with inaccurate predictions. The paper specifically investigates the power and limitations of randomization within this context, analyzing the best achievable approximation guarantees concerning the egalitarian (max) social cost measure on one- and two-dimensional Euclidean spaces. For the single-dimensional version, the paper shows that even with the strongest possible prediction, any $1+\delta$ consistent randomized truthful mechanism can be no better than $2+\delta$-robust. This implies that the previously proposed mechanisms by Procaccia and Tennenholtz, and Agrawal et al. are both Pareto optimal. They further show that this trade-off can be achieved. For the two-dimensional version of the problem, the authors provide a lower bound of 1.11 for all randomized mechanisms, and further show that no deterministic mechanism can combine better than 2-consistency with $1+ \sqrt{2}$​-robustness, and no randomized mechanism can combine 1-consistency with better than 2-robustness. Additionally, they present a truthful randomized mechanism that achieves 1.5 consistency and 2 robustness.

Strengths

+) The paper gives pretty good results for one- and two-dimensional strategic facility locations. In particular, the paper provides a complete characterization of Parato optimal mechanisms for the one-dimensional setting. +) The writing is pretty good. +) The consideration of various prediction settings may enrich the mechanism with prediction literature.

Weaknesses

Some of the technical writing is unclear. I will list some in the following sections. - Lemma 1 should quantify $\alpha$ and $\beta$. Theorem 3 should quantify $\epsilon$

Questions

Major: I do not follow the proof of Lemma 1. In particular, is the OnlyM mechanism at line 248 well defined? The distribution needs the knowledge of $x_L$, which is not part of the input. Minor: - What is formal definition of OnlyM mechanisms? Given report $\mathbf{x}$, and prediction $*$, if $x_L = \min \mathbf{x}$ and $x_R = \max \mathbf{x}$, $supp(M(\mathbf{x}, *)) = \{x_L, x_R, M\}$ - Does Lemma 1 require the original randomized mechanism to be truthful?

Rating

5

Confidence

2

Soundness

2

Presentation

3

Contribution

3

Limitations

Yes

Summary

The authors study the problem of designing incentive-compatible mechanisms for the facility location game, in particular a learning-augmented variant of ABGOT22 where an oracle returns (potentially inaccurate) predictions about optimal solutions. The paper focuses on considering when predictions are available for the preferences of individual participants/which participants are extremal. In the 1d setting, the authors show that randomizing between known algorithms is already optimal---allowing predictions about individual preferences cannot result in a mechanism that dominates prior algorithms which depend at most only on optimal facility predictions. In the 2d setting, the authors show that a slight improvement over state-of-art is possible by only assuming prediction access to identification of extremal agents; the authors also provide a few factoids e.g. minor improvement in approximation ratio lower bound for the general (non learning-augmented) setting.

Strengths

The paper's results are novel, cleanly presented, and indeed strictly improve upon several bounds in literature. The results on the line are not particularly surprising---e.g. Theorem 1 is just a short proof-by-contradiction given the reduction of Lemma 1 which seems to be largely implied by PT13---but are well-written and an accessible warmup to the plane results, which appear to be the main contributions of the paper. In terms of the results on the plane, although Theorem 6 also is not particularly surprising---circles have three degrees of freedom and one should expect mechanisms to really only depend on the reports of extremal agents, which on a plane should always be about three in practice---verifying the result is still non-trivial and the paper gives a clean exposition and proof. The paper also benefits from a collection of various observations; for example, the lower bound of Theorem 2 seems to just be a short note that PT13's 1d lower bound can be easily lifted to 2d. Overall the paper is also very well written and gentle.

Weaknesses

I only have minor notes on polishing the writing. Theorem 5 can make more explicit that an assumption is being made on the number of extreme agents---it was a bit confusing when initially skimming the paper. It would also be helpful to clarify if Lemma 1 is novel; from my reading it's just an consequence of the linearity of in-expectation honesty and seems to be implied by PT13---if this is correct, it would be helpful to note in the text. Also, L372-L377 were a bit difficult to understand without drawing it out graphically by hand; perhaps a diagram would help readability.

Questions

See weaknesses section.

Rating

7

Confidence

2

Soundness

4

Presentation

4

Contribution

3

Limitations

Yes the authors have addressed any negative societal impacts.

Response

I appreciate the clarifications and look forward to the revisions. I also appreciate the clarifications regarding Lemma 1---I didn't actually feel that the proof was too compressed but agree that it could be clarified (the diagram is nice). I maintain my positive review otherwise.

Lemma 1

Thank you for your clarification. I understand the final ``mechanism'' in Line 251 does not output $x_L$. However, do the weights of the convex combination (probabilities) depend on $x_L$ as they need to be set to maintain the same cost for the agent at $x_L$?