Learning-Augmented Facility Location Mechanisms for the Envy Ratio Objective

Thank you for your insightful comments and suggestions. We respond to your questions and concerns as follows.

Q: Why the restriction to an interval needed in the setting? Why define the problem as a utility maximization problem rather than cost minimization?

A: This setting, where agents and facilities are positioned on a fixed interval of the real line, is standard in the study of utility-based facility location problems, as seen in works such as “Heterogeneous Facility Location with Limited Resources” (GEB 2023) and “Facility Location Games with Fractional Preferences” (AAAI 2018). For additional references, see the survey “Mechanism Design for Facility Location Problems: A Survey” (IJCAI 2021). Our model employs a utility-based formulation for two key reasons: (1) it aligns with established definitions of envy ratio in prior work, and (2) a distance-based envy ratio results in the nonexistence of strategyproof mechanisms with bounded approximation ratios, leading to unbounded robustness. We also discussed it in the footnote on page 3 of our paper, but we will enhance these explanations in the revised version to ensure clarity.

Q: Line 224, "By Moulin's [1980] characterization...": Could you point to the exact place in Moulin's paper?

A: The characterization by Moulin’s [1980] is presented in Proposition 2. We will specify it in the updated version of the paper.

Q: Line 312, why if $f(x, \hat{y})=0.5$ the envy ratio is the one written?

A: Recall that $x_2 - x_1 = 2\delta$. Since we are analyzing consistency, $\hat{y}$ is the optimal solution, i.e., $\hat{y}$ is the midpoint of $x_1$ and $x_2$, so we have $x_2=\hat{y} + \delta$ and $x_1=\hat{y}-\delta$. Additionally, we consider the case $x_1 < x_2 < \frac{1}{2}$, thus $x_2$ achieves the maximum utility and $x_1$ achieves the minimum utility. Under these conditions, the envy ratio when locating the facility at $\frac{1}{2}$ is given by $\frac{1-(\frac{1}{2}-x_2)}{1-(\frac{1}{2}-x_1)}.$

Q: No confidence parameter for the BAM mechanism.

A: In contrast to $\alpha$-BIM, BAM is not parameterized and thus operates independently of any parameters, including confidence parameters. We have also explored randomized mechanisms that incorporate confidence parameters, allowing users to exert control; this is detailed in the $\alpha$-Bounding Interval Randomized Mechanism (see Appendix C). As shown in Figure 4, none of these alternative mechanisms outperform BAM. Nevertheless, we agree with the reviewer that mechanisms incorporating confidence parameters are desirable, provided they maintain strong approximation guarantees.

Q: Why considering agents’ reported locations does not help the mechanism to achieve a better approximation ratio? That is, why constant mechanism?

A: We provide an intuitive example illustrating that incorporating agents’ reported locations does not improve the outcome. Suppose there is one agent located at 0 and n−1 agents located at 1. The optimal facility location is at $\frac{1}{2}​$, yielding an envy ratio of 1. However, if the mechanism depends solely on the agents’ reported locations, the facility would be placed at either 0 or 1, resulting in an unbounded envy ratio. Consequently, the approximation ratio also becomes unbounded.

Q: The techniques for achieving the consistency-robustness results are quite standard and rather straightforward, i.e., not too many novel techniques.

A: We argue that most of our techniques are novel and provide insights for future works along this line of research. Deterministic Mechanisms with Prediction. Although our deterministic mechanism shares similarities with the seminal work of Agrawal et al. [2022], our proofs diverge significantly. Unlike their maximum cost objective, which does not involve utility functions in the denominator, our envy ratio incorporates utility functions in both the numerator and denominator, resulting in a more complex analytical structure. This complexity introduces substantial challenges in handling cases involving both maximum and minimum utilities. To address these difficulties, we introduce key lemmata, such as Lemma 3.1, that streamline and simplify the overall proof process.

Randomized Mechanisms Without Prediction. We contend that both the design and analysis techniques for randomized mechanisms are novel and non-trivial. Our approximation analysis for randomized mechanisms without prediction is new and specifically tailored to the unique structure of the envy ratio objective. The progression of results from Lemma 4.1 to Theorem 4.3 reflects considerable technical effort and offers original insights to the literature.

Randomized Mechanisms With Prediction. Our proposed Biased-Aware Mechanism (BAM) introduces a fundamentally new approach: the placement probability dynamically adjusts based on the prediction bias, defined as the distance between the predicted location and the midpoint $\frac{1}{2}$​. In contrast, existing literature typically employs fixed probabilities to combine different deterministic mechanisms. We also presented similar mechanisms in the appendix, but their performance is significantly inferior to that of BAM. The key intuition of BAM is that when the prediction is near the endpoints of the interval, robustness requires the mechanism to drastically reduce the probability of placing the facility at the predicted location. This strategy avoids an unbounded approximation ratio in cases where the prediction is inaccurate. This idea is central to achieving the $\frac{7}{4}$-consistency result without significantly sacrificing robustness.

We believe that our mechanism design and analytical techniques for the randomized setting provide novel contributions and offer valuable insights for future research in this area.

Q: Minor Comments.

A: We are grateful to the reviewer for pointing out these minor typos. We will correct them in the revised version of our paper.

I thank the authors for their response.

Followup:

A: This setting, where agents and facilities are positioned on a fixed interval of the real line, is standard in the study of utility-based facility location problems, as seen in works such as ... Our model employs a utility-based formulation for two key reasons: (1) it aligns with established definitions of envy ratio in prior work, and (2) a distance-based envy ratio results in the nonexistence of strategyproof mechanisms with bounded approximation ratios, leading to unbounded robustness. We also discussed it in the footnote on page 3 of our paper, but we will enhance these explanations in the revised version to ensure clarity.

Thank you for the helpful references. As other reviewers have noted, the assumption that agents lie on a fixed interval plays a critical role in shaping the problem and the complexity of its solutions. Adding the reference helps.

A: We argue that most of our techniques are novel and provide insights for future works along this line of research. Deterministic Mechanisms with Prediction. Although our deterministic mechanism shares similarities with the seminal work of Agrawal et al. [2022], our proofs diverge significantly. Unlike their maximum cost objective, which does not involve utility functions in the denominator, our envy ratio incorporates utility functions in both the numerator and denominator, resulting in a more complex analytical structure. This complexity introduces substantial challenges in handling cases involving both maximum and minimum utilities. To address these difficulties, we introduce key lemmata, such as Lemma 3.1, that streamline and simplify the overall proof process. Randomized Mechanisms Without Prediction. We contend that both the design and analysis techniques for randomized mechanisms are novel and non-trivial. Our approximation analysis for randomized mechanisms without prediction is new and specifically tailored to the unique structure of the envy ratio objective. The progression of results from Lemma 4.1 to Theorem 4.3 reflects considerable technical effort and offers original insights to the literature.

While your response addresses the complexity of the analysis and the technical steps in the proofs, it does not fully address the concern regarding the novelty of the mechanism itself—particularly how the predictions are combined with standard mechanisms.

For example, Lemma 3.1 reduces the analysis to two-agent instances, but this simplification is fairly direct given that envy is only affected by extreme points. As for Theorem 4.3, the mechanism's strategyproofness and anonymity follow almost immediately, since the agents' reports are unused. There is no intricate incentive-alignment technique involved.

The approximation analysis, though careful, appears to follow standard techniques for analyzing multivariate rational functions. While it’s true that incorporating utility functions in both numerator and denominator complicates the expressions, this structure arguably detracts from the simplicity and interpretability of the model. It remains unclear whether the analysis techniques are general or tailored to this particular objective.

A: We provide an intuitive example illustrating that incorporating agents’ reported locations does not improve the outcome. Suppose there is one agent located at 0 and n−1 agents located at 1. The optimal facility location is at 0.5, yielding an envy ratio of 1. However, if the mechanism depends solely on the agents’ reported locations, the facility would be placed at either 0 or 1, resulting in an unbounded envy ratio. Consequently, the approximation ratio also becomes unbounded.

This example shows that selecting only from reported locations can lead to arbitrarily bad outcomes. However, it does not rule out the possibility that using agent reports—together with predictions—could enable better approximation ratios. The example supports the limitations of restricted mechanisms, but not necessarily the impossibility of leveraging agent data more generally.

Randomized Mechanisms With Prediction. Our proposed Biased-Aware Mechanism (BAM) introduces a fundamentally new approach: the placement probability dynamically adjusts based on the prediction bias, defined as the distance between the predicted location and the midpoint . In contrast, existing literature typically employs fixed probabilities to combine different deterministic mechanisms. ...

I agree that dynamically adjusting placement probabilities based on the bias between the predicted and standard solutions is an elegant idea.

Thank you for your insightful comments and suggestions. We respond to your questions and concerns as follows.

Q: Quantify the approximation ratio in terms of the prediction error.

A: Thank you for raising the issue regarding smoothness analysis. We initially derived results for the approximation ratio with respect to prediction error. However, we chose not to include them in the main text, as their analysis is sufficiently complex and the results are less intuitive than the (consistency, robustness) framework. In the revised version, we will incorporate these results, or at least include a related discussion, to provide insights for interested readers.

For the deterministic mechanism with prediction, $\alpha$-BIM, let $\eta$ be the prediction error. Notice that the mechanism $\alpha$-BIM is parameterized by $\alpha$, We have the following approximation ratio result. When $\alpha \leq \frac{1+\sqrt{5}}{2}$, we have the approximation ratio

When $\alpha > \frac{1+\sqrt{5}}{2}$, we have the approximation ratio

Intuitively, Assume that we know the prediction model has an error smaller than $\frac{\sqrt{5}}{2} - 1\approx 0.118$, then we have the approximation ratio of $\frac{\sqrt{5}+1}{2}\approx 1.62$. This implies that when we have a good prediction model with bounded small error, we can significantly improve the approximation ratio from 2 to 1.62 by our proposed $\alpha$-BIM.

For the randomized mechanism, unfortunately, providing an explicit expression for $\rho_{\alpha}(\eta)$ is indeed difficult, and we outline the reasons below. Similar to the smooth analysis of deterministic mechanisms, the randomized one also involves case-by-case examination based on the ranges of $\hat{y}$ and $\eta$. Each case is expressed in the form $\max_j { f_j(\eta, \hat{y}) }$. However, unlike deterministic mechanisms, the presence of $\hat{y}$ in the probability terms introduces significant complexity. Specifically, the numerator of most $f_j(\eta, \hat{y})$ terms includes quadratic expressions like $\hat{y}^2$ and cross terms like $\hat{y} \cdot \eta$, while the denominator involves both $\hat{y}$ and $\eta$. This inherent complexity prevents us from deriving a closed-form expression for $\rho_{\alpha}(\eta)$.

Q: Ex-post strategyproofness guarantee for randomized mechanisms.

A: It is worth noting that our randomized mechanism is constructed from three deterministic constant mechanisms, each of which directly satisfies ex-post strategyproofness.

Q: Line 236, the lower bound proof of the deterministic mechanism with prediction. The facility can be placed at a location strictly smaller than $\frac{1}{\alpha}$.

A: Yes, you are correct. It should say that the facility must be placed in $[1-\frac{1}{\alpha},\frac{1}{\alpha}]$. This still leads to alpha-consistency at best, so the correctness of the proof is unchanged here. Thank you for spotting this error, we will fix it in the updated version of the paper.

Q: (Weakness) For the randomized mechanism with prediction. It is still possible to have a bad approximation ratio when prediction lies closely to 0 or 1.

A: The dynamic probability approach achieves a low expected approximation ratio, as illustrated in Figure 2, particularly when the prediction lies near 0 or 1. This effectively mitigates the large envy ratio that would result from placing the facility exactly at the predicted location (mentioned by the reviewer), which is a key feature of our Biased-Aware Mechanism (BAM). Specifically, when the prediction is close to the endpoints of the interval, the mechanism significantly reduces the probability of placing the facility at the predicted location to maintain robustness. This reduction is crucial to avoid an unbounded approximation ratio in cases where the prediction is inaccurate.

Q: Minor comments.

A: We are grateful to the reviewer for pointing out these minor typos. We will correct them in the revised version of our paper.

Thank you for your insightful comments and suggestions. We respond to your questions and concerns as follows.

Q: Smoothness analysis for the proposed algorithms.

A: Thank you for raising the issue regarding smoothness analysis. We argue that the $\alpha$-BIM satisfies smoothness as the approximation ratio is a continuous and monotonic function of the prediction error. The supporting evidence is as follows. Let $\eta$ be the prediction error. Notice that the mechanism $\alpha$-BIM is parameterized by $\alpha$, We have the following approximation ratio result. When $\alpha \leq \frac{1+\sqrt{5}}{2}$, we have the approximation ratio

When $\alpha > \frac{1+\sqrt{5}}{2}$, we have the approximation ratio

For both piecewise functions, we have verified that they are continuous and monotonically increasing with respect to the prediction error. Therefore, we argue that $\alpha$-BIM is smooth with respect to the prediction error. In the revised version, we will incorporate these results, or at least include a related discussion, to provide insights for interested readers.

For the randomized mechanism, we currently do not have a clear understanding of its smoothness, as deriving an explicit expression for $\rho_{\alpha}(\eta)$ is indeed challenging, and we outline the reasons below. Similar to the smooth analysis of deterministic mechanisms, the randomized one also involves case-by-case examination based on the ranges of $\hat{y}$ and $\eta$. Each case is expressed in the form $\max_j { f_j(\eta, \hat{y}) }$. However, unlike deterministic mechanisms, the presence of $\hat{y}$ in the probability terms introduces significant complexity. Specifically, the numerator of most $f_j(\eta, \hat{y})$ terms includes quadratic expressions like $\hat{y}^2$ and cross terms like $\hat{y} \cdot \eta$, while the denominator involves both $\hat{y}$ and $\eta$. This inherent complexity prevents us from deriving a closed-form expression for $\rho_{\alpha}(\eta)$.

Q: Randomized mechanism without prediction, the gap between upper bound and lower bound is still big. Any intuition about possible directions to narrow it?

A: At this stage, we do not have a concrete conjecture regarding how to further narrow the approximation gap for randomized mechanisms. However, we believe that simply extending the support of the mechanism to include more candidate locations with positive probability may not be a promising direction. This intuition is grounded in prior work on facility location problems, where a widely adopted and effective strategy involves selecting three representative points, typically from the left, center, and right of the domain. This approach, exemplified by the well-known LRM mechanism, has been shown to achieve strong approximation guarantees.Our own randomized mechanism without prediction builds upon this three-point idea and successfully breaks the approximation barrier of 2. Moreover, as demonstrated in Theorem 4.3, even optimizing over three candidate locations requires substantial technical effort. Extending the support to more than three locations would likely increase this complexity without yielding clear benefits and may even degrade performance. These considerations reinforce our skepticism about the effectiveness of mechanisms with broader support within the current framework. Therefore, we believe that the most promising direction for future research lies in developing an entirely new framework for randomized mechanism design.

Q: Missing intuition of $\alpha$-BIM

A: Thank you for your suggestion. We will incorporate an explanation of the intuition behind the design of $\alpha$-BIM in the revised version of our paper. The key idea is that placing the facility at the predicted location $\hat{y}$ ensures $1$-consistency. However, when $\hat{y}$ approaches the endpoints of the interval (i.e., near $0$ or $1$), this choice becomes increasingly risky in the presence of prediction errors, leading to poor robustness. To address this issue, $\alpha$-BIM is designed to balance consistency and robustness by adopting alternative placement strategies when $\hat{y}$ deviates sufficiently far from the center of the interval. This trade-off helps mitigate the impact of erroneous predictions near the boundaries.

Q: Minor Typos

A: We are grateful to the reviewer for pointing out these minor typos. We will correct them in the revised version of our paper.

Thank you for your insightful comments and suggestions. We respond to your questions and concerns as follows.

Q: Which techniques or ideas from your paper could potentially extend to more general settings, such as those without the fixed interval constraint or in higher dimensions?

A: We first clarify that the fixed interval assumption is necessary for our problem setting as it ensures that the utility function remains non-negative and well-defined. Studying higher-dimensional settings is out of scope for our current work, as there is no existing literature that examines envy ratio (without prediction) in high-dimensional facility location problems. Nevertheless, we briefly discuss potential extensions below.

(1). For deterministic mechanisms, a natural extension from one-dimensional to higher-dimensional settings involves placing the facility at the centroid of a bounded space, generalizing the interval assumption used in one dimension. However, identifying the centroid in an arbitrary bounded space presents significant challenges due to its geometric complexity. Even in a more specific setting, such as a ball, extending the $\alpha$-BIM mechanism is non-trivial, as the boundaries in higher dimensions extend beyond the two points ($1-1/\alpha$ and $1/\alpha$) used in one dimension, requiring a careful redefinition of the mechanism to account for multidimensional geometry. Overall, we agree that this is an interesting but challenging direction for future work.

(2). For randomized mechanisms without prediction, the extension is also challenging. The key difficulty lies in the fact that the LRM approach, relying on three representative points, is not directly applicable in higher dimensions, and more support points would likely be required.

(3). With prediction, our proposed $\alpha$-BIM mechanism can, in principle, be extended by considering a bounded subspace. The core idea behind BAM remains applicable: to ensure robustness, the probability of placing the facility at the predicted location should decrease sharply when the prediction is near the boundary of the space. However, it is evident that determining the appropriate probability distribution and analyzing consistency and robustness in this setting pose substantial challenges.

Q: Is there any known lower bound for the one-dimensional setting without the fixed interval constraint?

A: We clarify that the fixed interval constraint is essential for properly defining each agent’s utility. Moreover, for the envy ratio objective, a utility-based formulation is necessary. If a distance-based definition were used instead, the envy ratio would become unbounded whenever the facility is located at an agent’s position.

Q: Have you considered other prediction settings? For example, can stronger results be obtained if the predictions concern agents' locations?

A: For deterministic mechanisms with prediction, we establish tight bounds under the assumption of optimal location prediction. Since the optimal location can be computed directly from agents’ reported predictions, this implies that access to an optimal predictor is sufficient for the design of effective deterministic mechanisms. For randomized mechanisms, Lemma 3.1 shows that the analysis of the envy ratio approximation can be reduced to two-agent instances. This insight suggests that incorporating predictions about the positions of the leftmost and rightmost agents could potentially yield stronger approximation guarantees by more fine-grained analysis. However, investigating such extensions is beyond the scope of the current paper and represents an interesting direction for future research.

Q: What is the challenge of establishing the lower bound for randomized mechanisms with prediction?

A: Thank you for your question. We would like to highlight the difficulty of establishing lower bounds for randomized mechanisms with predictions under our objective. For classical objectives such as social cost and maximum cost, the paper “Randomized Strategic Facility Location with Predictions” successfully derives lower bounds by elegantly characterizing all mechanisms within a class called “ONLYM mechanisms,” and then proving bounds specific to that class. Motivated by their approach, we attempted to develop a similar characterization tailored to our setting. However, we encountered significant obstacles in identifying a corresponding class of mechanisms suitable for our objective. Unlike social cost or maximum cost, their objective function is linear, while ours is not. In particular, our objective can be seen as a multiplicative ratio, with the numerator involving a maximum utility function and the denominator involving a minimum utility function, which introduces significant analytical complexity. This structure makes precise characterization challenging, as it requires identifying the agents responsible for the maximum and minimum utilities and accounting for how these agents may change when the facility’s location is adjusted.

Q: Which of your proposed mechanisms are tolerant to small prediction errors? What guarantees can you provide in terms of smoothness?

A: Thank you for raising the issue regarding smoothness analysis. We initially derived results for the approximation ratio with respect to prediction error. However, we chose not to include them in the main text, as their analysis is sufficiently complex and the results are less intuitive than the (consistency, robustness) framework. In the revised version, we will incorporate these results, or at least include a related discussion, to provide insights for interested readers.

For the deterministic mechanism with prediction, $\alpha$-BIM, let $\eta$ be the prediction error. Notice that the mechanism $\alpha$-BIM is parameterized by $\alpha$, We have the following approximation ratio result. When $\alpha \leq \frac{1+\sqrt{5}}{2}$, we have the approximation ratio

When $\alpha > \frac{1+\sqrt{5}}{2}$, we have the approximation ratio

Intuitively, Assume that we know the prediction model has an error smaller than $\frac{\sqrt{5}}{2} - 1\approx 0.118$, then we have the approximation ratio of $\frac{\sqrt{5}+1}{2}\approx 1.62$. This implies that when we have a good prediction model with bounded small error. We can significantly improve the approximation ratio from 2 to 1.62 by our proposed $\alpha$-BIM.

For the randomized mechanism, unfortunately, providing an explicit expression for $\rho_{\alpha}(\eta)$ is indeed difficult, and we outline the reasons below. Similar to the smooth analysis of deterministic mechanisms, the randomized one also involves case-by-case examination based on the ranges of $\hat{y}$ and $\eta$. Each case is expressed in the form $\max_j { f_j(\eta, \hat{y}) }$. However, unlike deterministic mechanisms, the presence of $\hat{y}$ in the probability terms introduces significant complexity. Specifically, the numerator of most $f_j(\eta, \hat{y})$ terms includes quadratic expressions like $\hat{y}^2$ and cross terms like $\hat{y} \cdot \eta$, while the denominator involves both $\hat{y}$ and $\eta$. This inherent complexity prevents us from deriving a closed-form expression for $\rho_{\alpha}(\eta)$.

Thank you for your insightful comments and suggestions. We respond to your questions and concerns as follows.

Q: The typo of the robustness in Theorem 4.5. Why state the maximum consistency and robustness for $c\in [0, \frac{1}{4})$ instead of formulas with $c$ as a parameter?

A: Thank you for pointing out the typo in Theorem 4.5. We acknowledge that it is a typo and the correct value should be $\frac{9}{4}$ rather than $\frac{7}{4}$. This aligns with our Case 1 analysis, which is continuous, as thoroughly detailed in the proof and illustrated in Figure 2, representing the worst-case scenario. We will make the correction in the revised version of the paper. Secondly, we clarify that in BAM, $c$ is not an input parameter. When $c\in [0,\frac{1}{4})$, BAM achieves $\frac{7}{4}$- consistency and $\frac{9}{4}$-robustness as these values correspond to the worst-case ratios derived from our consistency and robustness analysis. For $c\in [\frac{1}{4}, \frac{1}{2})$, we express the performance of BAM as $(-4c^2+2)$-consistency and $(c+2)$-robustness. This is because in this range, the worst cases for consistency and robustness are no longer directly comparable, and the trade-off between the two defines a Pareto frontier. As $c$ increases from $\frac{1}{4}$ to $\frac{1}{2}$,the performance of BAM smoothly transitions from $1$-consistency and $\frac{5}{2}$-robustness to $\frac{7}{4}$-consistency and $\frac{9}{4}$-robustness.

Q: Any idea or conjecture of narrowing the gap for randomized mechanisms without prediction? For example, considering more than three candidate locations?

A: We consider that developing a novel framework for randomized mechanisms, distinct from the one presented in this work, offers greater potential and appeal than increasing the number of candidate locations within the existing framework, though we do not have a concrete conjecture on what the new framework might entail. This intuition is grounded in prior work on facility location problems, where a widely adopted and effective strategy involves selecting three representative points, typically from the left, center, and right of the domain. This approach, exemplified by the well-known LRM mechanism, has been shown to achieve strong approximation guarantees.Our own randomized mechanism without prediction builds upon this three-point idea and successfully breaks the approximation barrier of 2. Moreover, as demonstrated in Theorem 4.3, even optimizing over three candidate locations requires substantial technical effort. Extending the support to more than three locations would likely increase this complexity without yielding clear benefits and may even degrade performance. These considerations reinforce our skepticism about the effectiveness of mechanisms with broader support within the current framework. Therefore, we believe that the most promising direction for future research lies in developing an entirely new framework for randomized mechanism design.

Q: Minor comments.

A: Thank you for pointing out the typos. We will make the corresponding edits in the revised version of our paper.