Randomized Strategic Facility Location with Predictions

Thank you for your helpful comments and suggestions.

• Reviewer: "The paper mainly gives lower bounds in the different settings. The only positive result is obtained via running the centroid mechanism on the (predicted) extreme agents."

Response: Although many of our results take the form of impossibility results, we do prove that all these lower bounds are tight, i.e., achievable by truthful mechanisms. These tight bounds provide a complete picture for a natural problem, they fully capture the power and limitations of learning-augmented mechanisms in this setting, and they can be very useful information for designers, even beyond their theoretical value.

• Reviewer: "adding a small picture would help improve readability of many proofs"

Response: We agree with the reviewer and we have now enhanced our paper with additional figures: we have added one figure in Section 3 to clarify the proof of Lemma 1, and two figures in Section 4 to make the proofs of Theorem 2 and Theorem 6 easier to follow. You can find these three figures in the PDF file that we uploaded in the general response.

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

Response: This was, indeed, quite surprising for us as well when we first realized it, and it appears like no prior work has made this interesting observation. To provide more intuition regarding this fact, we have now added the following paragraph before Theorem 2. Thank you for the suggestion.

Since the problem of designing good facility location mechanisms in 2-dimensions is ``harder'' than the 1-dimensional one, it may seem counter-intuitive at first, but the lower bound that prior work proved for all 1-dimensional instances does not extend to 2 dimensions. The reason is that the design space for 2-dimensional mechanisms is much richer, and the known lower bounds apply only to the more restricted class of 1-dimensional mechanisms. For example, consider a simple instance with just two agents in two dimensions. For this 2D instance, the mechanism can return a location for the facility that is not on the line that contains the two agent's location, which it, of course, cannot do in one dimension. Note that, in terms of social cost alone, returning such a location is always Pareto dominated by returning an appropriate location on the line (e.g., its projection on the line), but returning a location that is not on this line also allows the designer to potentially affect the incentives of the participating agents in new and non-trivial ways that are impossible in the 1-dimensional case. Specifically, returning points that are not on the line allows us to induce previously impossible cost vectors: for a toy example, note that in a 1-dimensional instance involving two agents at distance 1 from each other, the only facility location that causes the same cost to both agents is the mid-point between them, leading to a cost vector of (0.5, 0.5). However, in 2-dimensions we can induce a cost vector of $(c, c)$ for any $c>0.5$ by just returning the appropriate point on the interval's perpendicular bisector. This additional flexibility could potentially provide the designer with novel ways to ensure that the agents will not lie; e.g., the classic technique of "money burning", used to achieve incentive compatibility without monetary payments, heavily depends on the designer's ability to penalize and reward agents, depending on their reports. Although we conjecture that truthful mechanisms are always better off returning a facility on the line containing the agent's locations in the aforementioned instance, proving such a result appears to be non-trivial and, due to this additional flexibility for the mechanism in two dimensions, proving inapproximability results for this broader class of mechanisms is a harder problem and seems to require new techniques and insights.

Dear reviewer hDFx,

Thank you once again for your helpful comments and suggestions. As the discussion period is coming to an end soon, it appears like you still maintain a negative score with high confidence, so we were wondering whether our responses did not address all of your concerns, and whether you would like us to provide any additional support for our submission while we still can.

Thank you for your helpful comments and suggestions.

• Reviewer: Minor comments.

Response: We agree with all the suggested changes and have applied all of them. Regarding the first comment, we have edited the statement as follows:

We then turn to mechanisms augmented with the strongest predictions and show that no such deterministic mechanism can simultaneously guarantee better than $2$-consistency and better than $1 + \sqrt{2}$-robust, and no randomized one can simultaneously guarantee $1$-consistency and better than $2$-robustness.

• Reviewer: "In Lemma 1, line 235 assumes the agent at $x_L$ reports a false location. Is this assumption general enough to show that no agent would misreport? Also in Lemma 1, line 238 to 248 considered two cases that $x_L < x'_L$ or $x_L > x'_L$. How about the case $x_L'> x_R$?"

Response: Yes, the analysis of Lemma 1 does imply that neither one of the two agents would misreport. Note that while we focus on the potential misreporting of $x_L$, we could directly apply symmetric arguments for the potential misreporting of the other agent. Furthermore, while we analyze the incentives of the agent located at $x_L$, we do not need to make any assumption regarding the report of the other agent, i.e., we do not need to assume that the other agent reports truthfully. Therefore, the analysis proves that an agent has no incentive to misreport, irrespective of what the other agent reports. Finally, the argument that we provide for the case that $x'_L > x_L$ (i.e., that "the cost of the agent is the same across the two mechanisms'') also applies if $x_L'> x_R$. Specifically, the only thing that this argument uses is that the points that are affected by the lie are all on on the same side of $x_L$ (in this case all the points that are affected have coordinates greater than $x_L$). As a result, the cost of the agent located at $x_L$ is uniquely determined by the expected coordinate value of these points (the ones that lie on its right), and the two mechanisms yield the same expected coordinate value for these points.

Although our analysis is correct and the mechanism is well-defined, we agree with the reviewer that the writing is somewhat confusing (e.g., not being clear enough regarding the distinction between reported locations and true locations), so we plan to revisit the part of the proof that discusses truthfulness and add more details. In the meantime, we would be more than happy to provide the reviewer with any additional details to convince them that there is no issue with the proof (e.g., we would be happy to provide a completely rewritten version of the proof).

• Reviewer: "I wonder if you have explored the total social cost objective."

Response: We believe that exploring this problem with total social cost is a very interesting direction.

We know that the median mechanism gives the optimum solution in one dimension. Therefore, there is no need for prediction in the line metric. The coordinate-wise median achieves a $\sqrt{2}$ approximation in the Euclidean plane metric, and Agrawal et al. (2022) studied this problem with predictions in the deterministic setting.

Since there are no known randomized mechanisms that strictly improve the total social cost over the best-known deterministic mechanisms, we decided to focus solely on egalitarian social cost (for which there are more studies beyond the line metric, such as Alon et al. (2010), who studied truthful mechanisms on circles and trees with egalitarian social cost) and explore randomized mechanisms with several prediction settings.

Moreover, we believe that for any learning-augmented problem, studying different prediction settings (ideally all possible settings) and establishing different bounds (ideally tight) is important and currently missing from the literature.

• Reviewer: "Have you considered this problem in a general metric space?"

Response: We believe that exploring this problem in more general metrics is also a very interesting direction. However, we are still a few steps away from addressing it.

Currently, there are no tight results in the randomized setting, even in the Euclidean plane. When no tight bounds are available, it is unclear whether an improvement with predictions is due to the power of predictions alone or if it is also possible without predictions.

The main challenge is the lack of characterization for randomized mechanisms, both in the Euclidean plane and in more general metric spaces. Although we could not find a characterization for randomized mechanisms in the Euclidean plane or make our results (with or without predictions) tight, we have made progress toward this goal.

Moreover, we believe that some of our techniques can be extended to more general metrics. For instance, with more complicated arguments, we could modify our Centroid Mechanism on Extreme Agents for Euclidean space to achieve better than 2-consistency and 2-robustness.

Thank you for your helpful comments and suggestions.

• Reviewer: Lemma 1 should quantify $\alpha$ and $\beta$. Theorem 3 should quantify $\epsilon$.

Response: Thank you for pointing this out. We have now quantified all these parameters and we provide the reworded statements below. Furthermore, we took this opportunity to change $\epsilon$ to $\delta$ in the statements of Theorem 3 and Theorem 4 to be consistent with our notation in Section 3.

Lemma 1 (Reworded). For any problem instance involving two agents with reported locations $\mathbf{x} = \langle x_L, x_R \rangle$ on the line, and any randomized mechanism that is truthful in expectation and achieves $\alpha$-consistency and $\beta$-robustness for some $1 \leq \alpha \leq \beta$ over this class of instances, there exists a randomized $OnlyM$ mechanism that is truthful in expectation and achieves the same consistency and robustness guarantees.

Theorem 3 (Reworded). For any $\delta > 0$, there is no deterministic truthful mechanism that is $(2-\delta)$-consistent and $(1+\sqrt{2}-\delta)$-robust, even if it is provided with full predictions $\hat{\mathbf{x}}$ (the location of each agent).

Theorem 4 (Reworded). For any $\delta > 0$, there is no randomized mechanism that is truthful in expectation, $1$-consistent, and $(2 - \delta)$-robust, even for two-agent instances and even if it is provided with full predictions $\hat{\mathbf{x}}$ (the location of each agent). This is tight, i.e., there exists a randomized mechanism that is truthful in expectation, $1$-consistent, and $2$-robust for two-agent instances.

• Reviewer: "is the OnlyM mechanism at line $248$ well defined? The distribution needs the knowledge of $x_L$, which is not part of the input."

Response: The line that the reviewer is referring to is actually not proposing a mechanism. The mechanism that is being analyzed throughout the proof is the one already defined in the second paragraph of the proof. The argument here starts with the distribution that the original mechanism, f, would output if the agent were to report $x'_L < x_L$. Then, it modifies this distribution to get one that yields the same cost for the agent at $x_L$ but only outputs no locations in $(x'_L, M')$ other than $x_L$ and $M$. It is this distribution that Line 248 describes and the reviewer is correct that a mechanism could not guarantee this, as it would require knowledge of $x_L$, which is private. However, this "intermediate" distribution is then further modified, starting at Line 251, to yield a probability distribution which never returns any outcomes in $(x'_L, M')$. It is this final distribution that is equivalent to the output of the mechanism defined in the second paragraph of the proof if it were provided with input $x'_L$ and $x_R$. Note that this mechanism does not need to know $x_L$, so it is a valid mechanism. Due to space limitations, we have to really compress this part of the proof, which makes it harder to read, but we will make sure to dedicate a bit more space to it in the next revision. We would also be more than happy to clarify this proof further, or even provide a fully rewritten version of the proof, if this would help convince the reviewer that there is no correctness issue here.

• Reviewer: " Does Lemma 1 require the original randomized mechanism to be truthful?"

Response: Yes, the original randomized mechanism is required to be truthful and we have updated the statement of the Lemma 1 to mention this explicitly (see the reworded lemma statement in our first response, above).

• Reviewer: What is formal definition of $OnlyM$ mechanisms? Given report $x$, and prediction $*$, $supp (M(x, *)) = x_L, x_R, M$

Response: No, the support of $OnlyM$ mechanisms can also include any point outside the $[x_L, x_R]$ interval. The only restriction is that their support within $(x_L, x_R)$ is just $M$ (see Line 203). To make this part clearer, we will include the following formal definition:

Definition ($OnlyM$ mechanisms) A mechanism $f$ is an $OnlyM$ mechanism if $P[f(\mathbf{x}) \in (x_L, x_R) \setminus \{M\}] = 0$, where $x_L$ is the leftmost reported location, $x_R$ is the rightmost report location, and $M = (x_L + x_R)/2$ is the midpoint of the two.

Furthermore, to make the reduction of Lemma 1 easier to follow, we have added a figure. You can find it as Figure 1 in the PDF file that we uploaded in the general response.

I see. The intermediate construction confuses me. Alternatively, you may use the convexity argument of the distance function. Thank you for your clarification. I do not have further questions.

Thank you for your helpful comments and suggestions. We actually think that our 1-dimensional results are quite significant on their own and much more than a warm-up for the two-dimensional ones. We provide some justification for this fact in response to the reviewer's question below.

• Reviewer: "It would also be helpful to clarify if Lemma 1 is novel; from my reading it's just an consequence of the linearity of in-expectation honesty and seems to be implied by PT13---if this is correct, it would be helpful to note in the text."

Response: Lemma 1 is, indeed, novel, and we do not see how it could be implied by any argument in PT13. To maintain the robustness, consistency, and truthfulness guarantees throughout this reduction, we do make use of linearity of expectation, however, there is much more to this proof than that. Specifically, note that there can be an infinite number of ways to rearrange the probability that a mechanism assigns to outcomes in $(x_L, x_R)$ to get an OnlyM mechanism without affecting the expected cost of the two agents located at $x_L$ and $x_R$. For example, we could first replace the outcomes in $(x_L, x_R)$ with a single outcome whose coordinate corresponds to the expected coordinate of these outcomes, and then express this single outcome as a convex combination of $M$, $x_L$, and $x_R$ (and there can many such convex combinations). However, maintaining the robustness and consistency guarantees limits the ways in which we can do that, and the particular way in which we rearrange the probability is really crucial for us to maintain the very delicate truthfulness property. The part of our argument that really leverages this subtlety starts at Line 244, and it argues that if the agent located at $x_L$ were to lie and report a location further away from the other agent (i.e., $x'_L < x_L$), then the amount of probability that the modified mechanism would assign to $x'_L$ instead of $x_L$ would penalize the agent for the lie more than any benefit that the agent could get from this lie.

Although this is one of the more technical parts of the proof, we had to really compress it in order to fit the results within the page limit, but we would be happy to emphasize this part of the proof much more in the next revision of the paper and to explain how some alternative approaches would fail to maintain truthfulness, robustness, or consistency.

Furthermore, to make the reduction of Lemma 1 easier to follow, we have added a figure. You can find it as Figure 1 in the PDF file that we uploaded in the general response.

• Reviewer:"Theorem 5 can make more explicit that an assumption is being made on the number of extreme agents---it was a bit confusing when initially skimming the paper."

Response: We agree with the reviewer. We will rephrase the statement to more clearly emphasize this assumption, as follows:

Theorem 5 (Reworded). Consider any instance that has only two extreme agents, i.e., $k = 2.$ Then, given predictions $\hat{\mathbf{e}} = \langle e_1, e_2 \rangle$ regarding the IDs of the two extreme agents, there exists a randomized mechanism that is truthful in expectation and achieves $1.5$ consistency and $2$ robustness for any number of agents.

• Reviewer:"Also, L372-L377 were a bit difficult to understand without drawing it out graphically by hand; perhaps a diagram would help readability."

Response: We agree with the reviewer. We added a figure to make the proof of Theorem $6$ easier to follow. You can find it as Figure 3 in the PDF file that we uploaded in the general response.