Learning-Augmented Facility Location Mechanisms for Envy Ratio
Authors: Haris Aziz
Yuhang Guo
Alexander Lam
Houyu Zhou
Venue: NeurIPS 2025 poster ()
Keywords: Learning Augmentation
Facility Location Game
Fairness
Envy Ratio
Mechanism Design
Primary area: theory

Abstract: The augmentation of algorithms with predictions of the optimal solution, such as from a machine-learning algorithm, has garnered significant attention in recent years, particularly in facility location problems. Moving beyond the traditional focus on utilitarian and egalitarian objectives, we design learning-augmented facility location mechanisms for the envy ratio objective, a fairness metric defined as the maximum ratio between the utilities of any two agents. For the deterministic setting, we propose a mechanism which utilizes predictions to achieve $\alpha$-consistency and $\frac{\alpha}{\alpha - 1}$-robustness for a selected parameter $\alpha \in [1,2]$, and prove its optimality. We also resolve open questions raised by Ding et al. [2020], devising a randomized mechanism without predictions to improve upon the best-known approximation ratio from $2$ to $1.8944$. Building upon these advancements, we construct a novel randomized mechanism which incorporates predictions to achieve improved performance guarantees.

Learning-Augmented Facility Location Mechanisms for Envy Ratio
Haris Aziz
Yuhang Guo UNSW Sydney
UNSW Sydney
haris wwwzeunswii..s... www.unswwwwuud..... edu
yuhang, gww.gunsww.uuu...o.om. edu.
Alexander Lam Hong Kong Polytechnic University alexander -a lam@polyu. edu. hk
Houyu Zhou'
UNSW Sydney
houyu. www.wuzww.....oo. edu. au
Abstract
The augmentation of algorithms with predictions of the optimal solution, such as from a machine-learning algorithm, has garnered significant attention in recent years, particularly in facility location problems. Moving beyond the traditional focus utilitarian and egalitarian objectives, facility location mechanisms on a line for the envy ratio objective, a fairness metric defined as the maximum ratio between the utilities of any two agents. For the deterministic setting, we propose a mechanism which utilizes predictions to achieve a-consistency and a-1 -robustness for selected parameter prove its optimality. We also resolve open questions raised by Ding et al. [2020], devising a randomized mechanism without predictions to improve upon the best- known approximation ratio from 2 to 1.8944. Building upon these advancements, we construct novel randomized mechanism which incorporates predictions to achieve improved performance guarantees.
design
[1, 2]. and
Introduction
In the uni-dimensional facility location problem, we are given of agents who are located along an interval, and are tasked with finding an idcal location to place facility. Each agent has single-peaker preferences, preferring the facility to be located as close to them possible. Due its simplicity as a continuous, single-peaked preference aggregation problem, the facility location problem has many industrial and societal applications, such as hchho//librarry/hspittl placement [Schummer and Vohra, 2002], social/economic policy selection [Dragu and Laver, 2019] and budget aggregation [Freeman al., 2021]. Among these applications, it is particularly important to achieve a fair solution, in which no agent (or subset of agents) is excessively distant from the facility. As result, this problem has been widely studied operations research, microeconomics, and theoretical computer science, with numerous papers proposing various solution concepts.
In social choice problems, common egalitarian fairness concept is to maximize the utility/well-biing of the worst-off agent, and when translated to the facility location problem, this is equivalent to the minimizing the worst-off agent's distance from the facility. This is achieved by placing the facility at the midpoint of the left- and right- most agents, but as Mulligan [1991] remarks, this solution is prone to perturbations of the extreme agent locations. Accordingly, numerous papers (e.g. [MeAllister, 1976, Marsh and Schilling, 1994]) have proposed alternative fairness objectives which provide an improved measure of the inequality within an instance.
"Corresponding Author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Our paper's focus is on the envy ratio objective, which was proposed for the facility location problem by Ding et al. [2020] and later expanded upon by Liu al. [2020]. Informally speaking. the envy ratio of an instance is defined as the largest ratio between any two agents' urilities, in which each agent's utility is equal to the difference between the length of the domain and their distance from the facilityy. Unlike the maximum distance objective, the envy ratio objective is pairwise fairees notion which additionally takes into account the relative well-being of the best-off agent. To further illustrate the difference and added nuance, consider instance with two agents, located at the extremities of the interval. When the facility is placed at the midpoint, the addition new agents near the midpoint does not affect the maximum distance, but causes the envy ratio increase, as the agents at the endpoints become envious of the agents who are located near the facility. When considering instances that correspond to a large approximation ratio, the envy ratio's 's dependence utilities creates a comparatively larger focus on instances where agents' receive low welfare from the mechanism, such when they are located at the domain endpoints. Importantly, the envy ratio objective also respects fundamental fairness principles such as the Pigou-Dalton principle [Sen, 1997] and the Rawlsian Principle [Rawls, 2017].
the agents'
Aside from fairness concerns, we typically desire a solution which is additionally strategyproof, incentivizing agents to reveal their true locations by ensuring that any misreporting is not beneficial. This is important when the agents' locations are assumed to be private information, and is the defining goal in the extensive literature approximate mechanism design [Moulin, 1980, Procaccia and Tennenholtz, 2013]. Essentially, the aim is to design strategyproof mechanisms which have a bounded approximation for some (typically utilitarian egalitarian) objective, and to compute a lower bound on the best-possible approximation by a strategyproof mechanism. For the envy ratio objective, Ding al. [2020] show that deterministic strategyproo mechanisms can achieve 2-approximation at best, and give bounds on the approximation achievable by randomized mechanisms.
In this work, we ask whether we can improve upon the best-known envy ratio approximation results by designing mechanisms which additionally utilize a prediction of the optimal facility placement (such as from a machine-leaming algorithm trained on historical data). This approach stems from the field of learning- augmented algorithms, which has seen significant interest in recent years, as the additional prediction information is leveraged to improve upon the traditional 'worst-case' approximation ratio bounds. In this context, an idcal mechanism provides an outcome which is close to the social optimum when the predictor provides accurate information (consistency), and also retains worst-case approximation guarantees when the predictor is inaccurate (robustness).
1.1 Our Results
In this paper, we apply learning augmentation to design anonymous and strategyproof mechanisms which have a bounded approximation ratio for the envy ratio objective. Our main results are as follows.
In the deterministic setting, we propose the novel a-Bounding Interval Mechanism (a-BIM), where a E [1,2] serves tunable parameter based on the confidence level of the prediction. This mechanism obtains a-consistency and a rrobustness.
o-1
2. We demonstrate the optimality of the a-BIM mechanism by showing that no deterministic, strategyproof, and anonymous mechanism can achieve (a- connisteeyy and (ي 5) robustness. We further explore fine-grained approximation ratios parameterized by the prediction error, which smoothly transition from a-consistency - -robustness as the error bound increases.
3. We next revisit open problems relating to randomized mechanisms without predictions. We first introduce class of randomized mechanisms termed (a. p) LRRM constant mechanisms, and prove
that the ( (>/5 1, -LRM constant mechanism achieves 1 + V3 ~ 1.894--aprroximation w.r.t envy ratio, which is optimal within the family of (a, p)-LRM mechanisms. Our results resolve an open question posed by Ding et al. [2020], which asked whether randomized mechanism with an approximation ratio strictly below 2 could be found.
4. We show that any randomized mechanism without predictions has an approximation ratio of at least 1.1 improving the best-known lower bound from 1.0314.
5. To address the challenging problem of devising randomized mechanisms with predictions, we propose the Bias- Mechanism (BAM), in which the probability distribution of the facility

---

depends on the deviation of location prediction ÿ from the interval midpoint 2. We demonstrate that BAM achieves (-4c² 2) -consistency and (c + 20-rbussts when E 1t 21,, and I E-consistency and f-robustness when E [0, 1), where = D 2 BAM strictly outperforms the deterministic a-BIM in terms of both consistency and robustness performance guarantees. In addition to BAM, we investigate other potential mechanisms to provide a broader perspective on the learning-augmented mechanism design. Results lacking full proofs are proven in the appendix.
1.2 Related Work
Fairness in Facility Location Mechanism Design Faimess concerns and objectives have been long-studied in facility location problems; early works in operations research (e.g., [McAllister, 1976, Marsh and Schilling, 1994, Mulligan, 1991]) discuss optimal solutions for fairesss objectives such as the Gini coefficient and the mean deviation, quantifying various inequity notions. On the other hand, the seminal paper by procaccia and Tennenholtz [2009] introduces an approximate mechanism design approach, in which they design strategyproof facility location mechanisms with a bounded approximation ratio for various objectives, including the cost/distance incurred by the worst-off agent. This measure of egalitarian fairness has a similar underlying principle as our envy ratio objective, which represents, in a multiplicative sense, the envy that the worst-off agent has for the best-off agent. This objective was introduced for the one-facility location problem by Ding et al. [2020]. and later extended to multiple facilities in the subsequent work [Liu al., 2020]. similar notion of minimax envy quantifies the envy in an additive sense (i.e., the maximum difference between any two agents' distances from the facility), and was studied by Cai et al. [2016] and Chen al. [2022]. Walsh [2025] studied Gini index in facility location mechanism design.
Other than og faimess, fairnsss objectives relating to groups of agents can be considered. For instance, Zhou et al. [2022, 2024] consider two group-fair objectives, the maximum total cost incurred by a group of agents, and the maximum average cost incurred by a group of agents. One may also consider representing group fairness via axioms that must be satisfied by 'group-fair' mechanism. For instance, distance/utility guarantees can be imposed for endogenously defined groups of agents at or near the same location, in which the magnitude of the guarantee is proportional to the size of the group [Aziz et al., 2022, Lam al., 2024, Aziz et al., 2025]. For other related work and variations of facility location problems, we refer the reader to recent survey by Chan et al. [2021].
Facility Location Mechanisms with Predictions Research on facility location mechanisms which are augmented with predictions has flourished in recent years, beginning with the paper by Agrawal et al. [2022], which studies deterministic mechanisms that take prediction of the optimal facility location as an additional imput. They provide of-botfh-oooltt style results, designing mechanisms which perform (in terms of their approximation ratio) consistently well when an accurate prediction provided, and are robust to entirely inaccurate predictions. The concept of measuring both the consistency and robustness of cerning-auggmente algorithms was first introduced by Lykouris and Vassilvitskii [2021]. and it has since been applied in numerous extensions of facility location problems. Balkanski et al. [2024] studied randomized mechanisms for the egalitarian/maximnn cost objective, whilst Chen et al. [2024] extend the domain to a continuous general metric space. For the two-facility location problem. Barak et al. [2024] design randomized mechanisms which use mostly and approximately correct (MAC) predictions of the agents' locations, supplementing the work by Xu and Lu [2022], which explores deterministic mechanism for the same problem. Aside from facility location problems, additional references, readers may refer the ALPS website [Lindermayr and Megow, 2022].
algorithms have been used for a wide variety of settings. For
2 Preliminaries
Let N = [r] be a set of agents, where each agent has a location 2; E [0, 1]. We denote the location profile of N by x = (æ1, F2, ,, .Tn) E [0, 1]" A deterministic mechanism f [0. 10" + [0, 1] takes a location profile x as input, and outputs a facility location y E [0, 1J. under which each agent i N has a utility of u(y, 2x) d(y, x;)) = yy - Ia| represents the distance between the facility and i's location. A randomized
For any L E N, denote [4] = {1,
d(y, where
Our results hold w.l.o.g. for any compact interval domain.
3

---

mechanism f :0.01 + ( 1]) maps the location profile x to probability distribution P over [0, 1], under which each agent E N has an expected utility of ((.....) -Eerrlly xz[]-
We are primarily focused with the envy ratio objective, formally defined for an instance as the ratio between the best-off and worst-off agents' utilities.?
Definition 2.1 (Envy Ratio). Given a location profile x E IR" and mechanism f. the envy ratio is
ER(S(x), = max *# xx)
For given mechanism f. we can quantify its worst-case performance (over all possible location profiles) with respect to the envy ratio objective via its approximation ratio. Definition 2.2 (Approximation Ratio). A mechanism f is said to have an approximation ratio of p
Ef(f(x)
sup x=|0,1]"
(x)))
where (PT(x) is the optimal solution which minimizes the envy ratio for any given location profile x E [0, 1j". For any specific instance x, let p(x) denote the approximation ratio of f under x.
Note that p 2 1 for all As proven by Ding et al. [2020], the OPT mechanism is the well-known midpoint mechanism which places the facility halfway between the left-most and right-most agent locations.
Lemma 2.3 (Ding et al. [2020]). Given any location profile instance x, the midpoint mechanism f(x) mid(x) = tem(() (where Im(x) == minge {zi), and rm(x) = maxie (x;}) optimizes the envy ratio objective.
Throughout the paper, our proofs focus on the case where lm(x) < rm(x) and omit the case where Im(x)= rm(x), in which any feasible facility location fxx achieves optimal envy ratio of 1,
As standard in facility location mechanism design, we assume that the agents' true locations are private information, and that the mechanism takes input the locations which are reported by the agents. Accordingly, we restrict our attention to strategyproof mechanisms, which disincentivize agents from misreporting their location.
Definition 2.4 (Strategyrroffness) mechanism f is strategyproof if for any location profile E [0, 1 we have x(f(x),x;) u(f(x_ +f), .x) for all i E N and z!..
Note that by definition, strategyproofness defined in expectation if is a randomized mechanism.
In this paper, we discuss
mechanisms, which take a prediction ÿ of the optimal additional input. We denote these mechanisms by f(x, 9). Our goal is to approximation ratio guarantees,
facility location
design strategyproof mechanisms which have boatt--fbboh-weeee performing consistently well when is perfectly accurate prediction, and also being robust to inaccurate predictions of the optimal solution. Formally, we define the two performance metrics as follows.
Definition 2.5 (7-consistency), A mechanism of is "-consistent it achieves an approximation ratio of y when given correct prediction ý OPT(x), i.e.,
ER(f(x, OPT(x)),
sup x=|0.1|-
ER(OPT(x), x)
Definition 2.6 (3-robustness). A mechanism f is B-robust if it achieves approximation ratio of B under any prediction ÿ, i.e.,
ER(S(x, x)
3 sup xE(0,11".
ER x))))
Note that the mechanism which always places the facility at the predicted location ý is 1-consistent has unbounded robustness. We also remark that a mechanism does not admit a prediction as input and is p-approximate, then it is p-consistent and p-robust in the learning-augmentee setting.
Note that a utility-base based formulation is necessary to define this objective, as distance-basse definition results in unbounded envy ratio whenever the facility coincides with an agent's location.

---

3 Deterministic Mechanisms
We begin with the deterministic setting, in which any strategyproof mechanism without predictions is known to have an approximation ratio of at least 2 (Theorem in [Ding et al., 2020]), and that this lower bound is matched by the constant-2 mechanism which always places the facility at 1. By admitting a facility location prediction as an additional input, we are able to extend the Constant- 2 mechanism to the following a-Bounding Interval Mechanism, which defines an interval based parameter a E [1, [1, and places the facility at the prediction ğ if it lies within this interval. Otherwise, the facility is placed at boundary point of this interval.
Mechanism o-- a--Bounding Interval Mechanism (a-BIM)
Input: Location profile x, facility location prediction Ù. and parameter E [1.2].
Output: Facility location f(x, 0)
1: if E [1-
1] then
2: Return fxx 4) f 9:
3: else if g E ( then
4: Return f(x. () :
5: else
6: Return f(x. 1
7:
end if
Note that the output of this mechanism ranges from f'x,, 0) ý when a 1, to f(x, ú) when a = 2, and thus its performance ranges from 1-consistency and unbounded robustness to 2-consistency and 2-robustness, As we will show, the a- a-Bounding Interval Mechanism specifically has a-consistency and - robusteesss... While we do not achieve a strict improvement over the
2-consistency and 2-robustness of the Constant- 1 mechanism, the added flexibility from the a tradeoff
parameter enables the central decision maker to choose their desired consistency-robustee depending on their confidence in the prediction accuracy. We also remark that the mechanism is additionally anonymous, meaning that the output invariant under any permutation of the agents' labelings. Before analyzing the consistency and robustness of a-BIM, we first introduce a crucial lemma which simplifies the space of location profiles which need to be considered.
Lemma 3.1. For any instance x, and a distribution of facility locations P. there always exists 2 2-agent instance x' = (Im(x), rm())) such that Ey
En(yxx) ER m
< E ER(mid(x");xx]
BR(yxx)
The proof idea is that given any instance x and for any location y P. either E [l((x), rm (x)] or y &' [lm(x), rx)), we show that the approximation ratio under x is always upper-bounded by that under x' = (Im(x), rx)).. The complete proof is relegated to Appendix A.
By Lemma 3.1, when analyzing the performance of mechanisms, only need to focus 2-agent instances. We now formally prove the consistency and robustness of a-BIM.
Theorem 3.2. a- a-BIM is anonymous, strategyproof, and satisfies a-consistency and a a
robustness.
Proof. B-BIM is trivially strategyproof and anonymous, as the output is independent of the agents' locations. We next move to the analysis of consistency and robustness. From Lemma 3.1 we only need to consider instances x = (2) with two agents where 21 < x22
(Consistency). Consider an arbitrary 2-agent instance x in which ý is accurate, i.e., y = mid(x). If mid(x) 1 [1 1, }. a-BIM trivially satisfies 1-consistency. There are two remaining cases: a
either (x)(()) = ÿ E [0, 1 - 2 or mid(x) (x) E (2. 1]. Due to symmetry, it suffices to focus on the former case, in which B-BI returns f(x 9) = 2. Since ÿ < 1 a. the maximum utility is contributed by æ22, and the minimum utility achieved by the facility location 1 1 is contributed by 21. Moreover, the utility of the agent at is at most 1. The utility of the agent at 21 is at least 1 (1 1) 1. Hence, the consistency is at most Ef (x, mid(
achieved by the facility location
7 sup
[=[0,
ER Fm(mid(x)) x)
(1 a
a.
5

---

For matching lower bound, consider an instance with 2 agents located at and 22 = =1 a² Here, Mechanism 1 places the facility at L. leading consistency of at least a. Therefore, conclude that a-BIM achieves a-consistency.
(Robustness). Consider an arbitrary 2-agent instance x, suppose the mechanism outputs Since y E [1- o'' 11, the minimum utility is least 1 and the maximum utility is at most Hence, the robustness is at most
E x).
B sup x=[o,]]" [e ER(mid(x),x
a a-1
For a corresponding lower bound, consider 2-agent instance, with the agents located at 1 and 1. The optimal facility location in this case would be 2/2 achieving envy ratio of 1. If y E [0, 10 ), then the mechanism selects - as the facility location, leading envy ratio (and therefore robustness lower bound) of
We next show that for the envy ratio objective, a-BIM obtains the best possible consistency and robustness guarantees among all strategyproof and anonymous deterministic mechanisms, establishing the optimality of the mechanism."
Theorem 3.3 (Optimality). Given any parameter (1, there is no deterministic, strategyproof, and anonymous mechanism that is (a - =)-coniistent and ( - -ro-robust with respect to envy ratio, for any & > O.
Proof. By the characterization of Moulin [1980] (Proposition 2), deterministic strategyproof and anonymous mechanism must be a phantom mechanism with n + 'constant' points/phantoms. A phantom mechanism places the facility the median of the n agent points and the n + constant points. Note that the 'phantom' locations may be a function of the prediction.
will show that all phantoms must be in [1 1 =]] in order for the robustness be - or better. To see this, suppose for contradiction that one of those phantoms (denoted by p; = f(()) is in [0, 2 Since p; only depends on J. we have that p; E [0, 1 - 1)) is fixed point for every set of locations .e...., Zn. Now consider location profile with
Observe that when (1,2), we have 1 1 < 3. Next, given any prediction
agents Pa and one agent at Under this location profile. the facility will be placed at p;. which leads to an envy ratio of p; and implies an approximation ratio of at least 1. Since p; < _. the robustness will be strictly greater than -
Next, for the same fixed j. we consider another location profile with n agents at _ and one agent at 1. The facility will be placed in the interval [1 ]] leading to a-consistency at best. Therefore, the robustness a- or better, the consistency cannot better than a, proving the result. L
consistency
2
[2,2)
1.8
1.6
1.4
1.2
2
6
10
12
robustness
Figure Trade-off between consistency and robustness under a- a-BIM
We also depict the trade-off between consistency and robustness, as determined by the parameter in Figure below. One may adjust the parameter a according to the confidence of the prediction, i.c., setting small (resp. large) when the confidence in the prediction is high (resp. low).
For 1, is trivial that mechanism with 1-consistency can achieve bounded robustness.

---

Approximation Ratio Parameterized by Prediction Error We now extend the consistency and robustness results for a-BIM obtain a refined approximation ratio parameterized by the prediction enror. Let y" denote the optimal facility location (PT(x) and 1/ denote the upper bound of the distance gap between the optimal location and prediction location, i.e., " = sup I v²1. and pa (T) be the approximation ratio for any specific a under prediction error 1/.
Theorem 3.4. Let n denote sup 1
When [1, 1+v3
the approximation ratio is
a
17 E [0, [(++1)
Pa(n)
41
1) E 2(
a-1
2
20.7
1 E g 2 2a
17 E
2n t00)
When a E (1ty6, :2, the approximation ratio is
1 E [0, la-1)²
a
2g
(T = 1
200
1 E (a-1)
11
a=
2
" E 2n +00)
Proof Sketch. Recall that a- a-BIM places the facility at ÿ when it is in the interval [1 4 4 and otherwise places it at the nearest endpoint of that interval. We obtain the approximation ratio as function of by treating these two placement regimes separately and taking the worst case in cach. When á E [1 1 L. by Lemma 3.1, we focus on the two-agent instances and analyze the worst case approximation ratio parameterized by when moving the facility from y to ÿ as 7) grows from 0 to co. Similarly, when ÿ & [1 1 a and the facility is placed at the nearest endpoint. We again consider the worst case when moving the facility from y" to the placement regimes produces single approximation ratio expressed as a piecewise function of 17, which monotonically increases from a to T as the error bound increases continuously. O
(or 4. Taking the worst case over
To better illustrate Theorem 3.4, we present the approximation ratios in Figure 2. For each fixed value of a, the approximation ratio is piecewise function, which is smooth, specifically, continuous and monotonic with respect to error bound We further observe that when the error bound < A
x 0.118, the approximation ratio achieves v5+1 1.62, which shows that a-BIM can substantially improve the ratio with a well-performed prediction model.
Approximation parameterized by under varing
As(i)
Paln) =
5
Palg)
Pal0)
2
0.1
0.2
0.3
0.4
0.5
7
Figure 2: Approximation ratio parameterized by error bound with various a values.
4 Randomized Mechanisms
In the context randomized mechanism design (without predictions) for envy ratio minimization, Ding et al. [2020] proved that any strategyproof mechanism must have approximation ratio of at
7

---

least 1.0314, and showed that an approximation ratio of 2 is achieved by the deterministic mechanism which always places the facility 2. However, they were unable construct any randomized strategyproof mechanism beyond 2-approximation. In this section, we address this gap and open problem within both the classic setting (without predictions), and mechanism design with predictions.
4.1 Without Prediction
Since remains an open question whether a randomized mechanism can achieve an approximation
ratio better than 2, we address this by introducing novel family of (a, p)-LM constant mechanisms (Algorithm 2). The mechanism inherently strategyproof and anonymous. By carefully selecting the parameters, show that there exists mechanism within this family that achieves approximation ratio approximately 1.8944.
Mechanism 2 (ax, P)-LRM Constant Mechanism
Input: Location profile
Output:
Distribution of facility locations f(x). I: With probability p: return fxx)
a;
2: With probability 2p: return f(x) 2"
3: With probability p: return f(x) +
We now compute the optimal parameters of a and which minimize the mechanism's approximation ratio. By the following lemma, we show that it suffices to restrict our attention to mechanisms with S 1. as any (a.p) (6..p)LLMMM. constant mechanism with > 1/2 will have worse approximation ratio than the deterministic mechanism which simply places the facility 1
Lemma 4.1. When 1. every (c..))LRM constant mechanism has approximation ratio of at least
Given that a S 4. we show that the optimal parameters a and p can be found by solving the following optimization problem, which concerns the mechanism's performance over 2 different location profiles.
3 + a). When a S 4' the (o""2 .P') -L.MM constant Mechanism optimizes the approximation ratio of envy ratio objective where (o".p") arg (a. (max(p(x) p(x'))
Lemma 4.2. x (z1 0, = 2)) and x' (a' = 0, z
Finally, by solving this optimization problem, we show that setting v and p leads to the optimal approximation ratio among all (a,p)-LRM constant mechanisms.
Theorem 4.3. f 1, 2 --LMM conslant mechanism is anonymous, strategyproof, and achieves approximation ratio + V5' which is optimal among all (a, p)- -LLM constant mechanisms.
2
Proof Sketch of Theorem 4.3. By Lemma 4.2, suffices to find the optimal parameters a" and p for the optimization problem (a.p) (max(p(x)) p(x')}) Specifically, we show that when a E [0, t.
by setting a v5 1, and = 2. the (>/3 - 1, 2 - mechanism achieves an approximation ratio of + 2 ~ 1.8944 while when a E [ L 4.. the optimal parameters are _ and A
2
V5
which yields an approximation ratio of 1.909. Therefore, the 5 1, - mechanism is optimal within the family of (a, p)-LMM Constant mechanisms.
With an approximation ratio of approximately 1.8944, our ( -, significantly improves upon the upper bound among mechanisms without predictions. We also further improved lower bound. Previously, Ding et al. [2020] showed that
1, ) -LRMM Constant mechanism
tighten the gap by establishing any randomized strategyproof mechanism (without predictions) has an approximation ratio at least 1.0314. We advance this lower bound by carefully selecting location profile and constructing upper bound on the facility's 's expected distance from an agent's s location, in terms of its probability to be located within certain intervals, which gives us a lower bound of 1.12579.
Theorem 4.4. Any randomized strategyproof mechanism has an approximation ratio of at least 1.12579.

---

4.2
With Prediction
Next, we extend our investigation to the paradigm of randomized mechanism design with predictions, proposing new randomized mechanism that outperforms the a-BIM. An immediate idea may be to run the (>2 1, = )-LRM constant mechanism within the a-BIM, returning the former mechanism's output when the prediction lies outside the bounding interval. However, this modification performs worse than the original a-BIM. Further details are provided in Appendix C.
To demonstrate the difficulty of this problem, consider an extreme 2-agent instance x = (x) O, .2 =)) with prediction 9 0. For any mechanism that places the facility at with positive probability, the robustness of the mechanism becomes unbounded. However, intuitively, assigning higher probability to placing the facility improves consistency. This reveals the fundamental challenge of balancing consistency and robustness. To address this, we adapt the underlying design principle of the a-BIM: the mechanism locates the facility at ğ if lies within a specified closed interval. Otherwise, the facility is placed at the boundary of that interval. This design can be viewed as a threshold mechanism, where the placement decision is based on the distance between ý and 5. By integrating this threshoid-based approach in probabilistic manner, we design our novel Bias-Aware mechanism, which we introduce as follows.
Mechanism 3 Bwas-Aware Mechanism (BAM)
Input: Location profile x, facility location prediction ý.
Output:
Facility location f(x, 9).
I: Compute bias = |
2: Compute probability p = C
3: With probability p: return fxx
4:
With probability p. return f(x, 1)
Theorem 4.5. BAM is anonymous, strategyproof and (-4c² + 2) cooosistty and + 2) robustness when c E [ z. 3 1-consistency and t-robustness when c E [0, }
Proof. BAM is immediately anonymous and strategyproof as the output independent of the agents' locations. We now consider its consistency and robustness. From Lemma 3.1, we only need to consider instances with two agents, in which the optimal envy ratio is always 1. Hence, we only need to consider the envy ratio achieved by the mechanism. Given any profile x and ÿ. without loss of generality, we assume that . < 22 and ý < 2. giving us p = ÿ and e = 2 -
(Robustness). We first consider robustness. Observe that when placing the facility at 9 (resp. 2) the minimum utility of any agent is at least - ÿ (resp. 1 as the distance from á (resp. 1) is at most y (resp. 5)). The equalities hold when x2 = 1. If < g. moving I to & will increase the maximum utility achieved by and 1.2 If 2 > } moving to 1 will increase the maximum utility achieved by and 1. Hence, only need to consider the case where I [Ø, $). in which the robustness expressed as
ER(f(x, = 1 (x) 1)
+ 0)
1
2
21)
5
1 == -
9
2
2
which reaches the maximum when xj reaches 1
(Consistency). Consider any arbitrary instance and ÿ is accurate, i.e., 9 mid(x). Let 8 حس If ÿ < 1. we have x2 < 1.
2. The envy ratio achieved by f(x, i) = 9 is and the envy ratio achieved
1-(1-ra 1-(3 (()-)8) where we have < y as 0 < x1 Σ ÿ. For consistency,
by f(x, ú) = 1-(3-11) 1-(3 0+8)*
is
1- 3 0
8)
ER(f(x,)). 9- 1+11000 (1 9)
S
9
+
9) 40) -4c 2 +2,
1 2
1
+ 8)
which reaches the maximum when 8 ÿ.

---

When ÿ > i. the envy ratio achieved by f(x,8) 9) is 1 and the envy ratio achieved by f(x, 0)
1-(8 (3- -0)
is 1- 16+
where å S i as 0 S ÿ. Hence, the consistency is
1- ( 9)) (1- -0) = 4c2 + 2c 22++1 1, 1 (6
= n. 1+ - 0)
which is maximized when å 9. Note that in this case, both consistency and robustness are monotonically increasing w.r.t. C, reaching the maximum of (2: when
Finally, we conclude that BAM satisfies (-4c² 2)-consistency and (c + 2)-robustmess when C 4. 2 4 --oosistencyy and robustnesss when c E [0. 1)-
11,
Intuitively, BAM reduces the probability that the facility is placed at ý as the distance between ÿ and the midpoint increases, in which the probability reaches 0 when ý reaches 0 or 1. This prevents the mechanism from having unbounded robustness, and improves the balance between consistency and robustness by effectively using the prediction. Figure 3 highlights that BAM ís strictly better than the deterministic a- BIM in terms of both consistency and robustness. Further discussion is provided in Appendix C. For instance, we show that if we modify BAM by replacing the output with the
v 1, } --LRM, both the consistency and robustness worsen
3.2
Robustness
3
2.8
2.6
2.3)
2.4
2.2
(1.75,2.25)
2.25)
1.2
1.4
1.6
1.8
Consistency
Figure 3: Comparison between c-BIM (red solid line) and BAM (blue dashed line). Note that, unlike a- a-BIM, the range of approximation ratios for BAM is not dependent on a chosen parameter, but rather on l 1/1
Conclusion and Discussion
In this paper, revisit the problem of facility location mechanism design problems for the envy ratio objective, through the scope of laaming-augmennationn We provide tight results by devis- ing the deterministic a-BIM, which reaches the Pareto frontier of deterministic, anonymous and strategyproof mechanisms. For randomized mechanisms without prediction, we improve upon the
best-known lower bound, and propose the 3 1, ? --LMM Constant mechanism which achieves 1. 89944-apprxximation, resolving the open question of devising mechanism with an approximation ratio better than 2. Finally, we proposed BAM, learning-augmentee outperforms a- BIM in terms of both consistency and robustness. For a-BIM, we provide a com- prehensive analysis regarding the approximation ratio parameterized by prediction error, however, regarding BAM, the randomized mechanism with prediction, unfortunately, we are unable to derive closed-form expression for approximation ratio p(n). The inherent difficulty is that when one performs a case-by case-by-case by-case analysis, each case is expressed in the form max, (.f, (1) û)}. in which the presence of f in the probability terms introduces significant complexity, especially the numerator, which includes quadratic expressions and cross terms. This prevents us from deriving an explicit form for the pypparmmeterized approximation ratio.
randomized mechanism which
For future work, exploring lower bounds for randomized mechanisms with predictions presents challenging yet meaningful task. Due to the significant differences in optimization objectives, the state-of-the-art techniques used by Balkanski et al. [2024] for learning-augmented randomized mechanisms are difficult extend to the envy ratio scenario studied in this paper. Thus, developing novel approach to establish lower bounds would be beneficial. Additionally, it is promising to apply the learning-augnnn augmented framework to other faimess notions within the literature.
10

---

Acknowledgments
This work was supported by the NSF-CSIRO grant on "Fair Sequential Collective Decision-Makinge (RG230833) and the ARC Laureate Project FL200100204 on "Trustworthy AI". The authors would like to express their gratitude to the anonymous reviewers of IJCAI 2025 and NeurIPS 2025 for their insightful and constructive feedback, which greatly helped improve this paper.
References
P. Agrawal, E. Balkanski, V. Gkatzelis, T. Ou, and X. Tan. searning-augmennn mechanism design: Leveraging predictions for facility location. In Proceedings of the 23rd ACM Conference on Economics and Computation (EC), page 497-528, 2022.
H. Aziz, A. Lam, M. Suzuki, and Walsh. Random rank: portionally fair randomized facility location mechanism. In Proceedings of the 36th International Conference on Neural Information Processing Systems (NeurIPS), pages
The one and only strategyproof and pro-
2022.
H. Aziz, A. Lam, B. E. Lee, and T. Walsh. Propotionaaity-basee fairness and strategyrroofness in the facility location problem. Journal of Mathematical Economics, 119:103 19,, 2025.
E. Balkanski, V. Gkatzelis, and G. Shahkarami. Randomized strategic facility location with predic- tions. In Proceedings of the 38th International Conference on Neural Information Processing Systems (NeurIPS), pages 35639-35664 2024.
Z. Barak, A. Gupta, and I. Talgam-Cohen. MAC advice for facility location mechanism design. In Proceedings of the 38th International Conference on Neural Information Processing Systems (NeurIPS), pages 129564-129609 2024.
Q. Cai, A. Filos-Ratsikes Ratsikas, and P. Tang. Facility location with minimax envy. In Proceedings of the 25th International Joint Conference Artificial Intelligence (IJCAI), pages 137-143, 2016.
H. Chan, A. FiltssRatsikas, B. Li, M. Li, and C. Wang. Mechanism design for facility location problems: A survey, In Proceedings of the Thirtieth International Joint Conference Artificial Intelligence (IJCAI), pages 4356-4365, 2021. Survey Track.
Q. Chen, N. Gravin, and S. Im. Strategic facility location via predictions, 2024.
X. Chen, Q. Fang, W. Liu, Y. Ding, and Q Nong. Strategyproof mechanisms for 2-facility location games with minimax envy. Journal of Combinatorial Optimization, 43(5):1628-1644, 2022.
Y. Ding, W. Liu, X. Chen, Q Fang, and Q Nong. Facility location game with envy ratio. Computers & Industrial Engineering, 148:106710 2020.
T. Dragu and M. Laver. Coalition governance with incomplete information. The Journal of Politics, 81(3):92-9936, 2019.
R. Freeman, D. M. Pennock, D. Peters, and J. W. Vaughan. Truthful aggregation of budget proposals. Journal of Economic Theory, 193: 195:105,34, 2021.
A. Lam, H. Aziz, B. Li, F. Ramezani, and T. Walsh. Proportional faimess in obnoxious facility location. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1075-1083, 2024.
A. Lindermayr and N. Megow. Alps: Algorithms with predictions, 2022. URL https:
//al i/algorithin thms w wwwhhhhheede it onss www.giithubu.... thub.io..
W. Liu, Y. Ding, X. Chen, Q. Fang, and Q Nong. Multiple facility location games with envy ratio. In Proceedings of the 14th International Conference on Algorithmic Aspects in Information and Management (AAIM), page 248-259. Springer- Springer-Verlag, 2020.
Lykouris and S. Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM, 68(4):1-25, 2021.

---

M. T. Marsh and D. A. Schilling, Equity measurement in facility location analysis: A review and framework. European Journal of Operational Research, 74(1):1-17, 1994.
D. M. McAllister. Equity and efficiency in public facility location. Geographical analysis, 8(1): 47-63, 1976.
H. Moulin. On strategy prooogyypso and single peakedness. Public Choice, 35(4))437-455, 1980.
G. F. Mulligan. Equality measures and facility location. Papers Regional Science, 70(4):345-365,
1991.
A. D. Procaccia and M. Tennenholtz. Approximate mechanism design without money, In Proceedings of the 10th ACM Conference on Electronic Commerce (EC). page 177-186, 2009.
A. D. Procaccia and M. Tennenholtz. Approximate mechanism design without money, ACM Transactions Economics and Computation, 1(4):18:1-18:26, 2013.
J. Rawls. A theory of justice. In Applied ethics, pages 21-29. Routledge, 2017.
Schummer and R. V. Vohra. Strategy-proof location network. Journal of Economic Theory, 104(2):405-428, 2002.
A. Sen. On economic inequality. Oxford university press, 1997.
T. Walsh. Equitable mechanism design for facility location. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, (IJCAI), pages 275-283, 2025.
C. Xu and Lu. Mechanism design with predictions. Proceedings of the 31st International Joint Conference Artificial Intelligence, (IJCAI), pages 571-571 2022.
H. Zhou, M. Li, and H. Chan. Strategyproof mechanisms for group-fair facility location problems. In Proceedings of the s1 International Joint Conference on Artificial Intelligence (IJCAI), pages 613-619, 2022.
H. Zhou, H. Chan, and M. Li. Altruism facility location problems. In M. Wooldridge, G. Dy, and S. Natarajan, editors. Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pages 19001,0001, 2024.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly outlines the problem setting, applications, and theoretical results of our work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The assumptions of our results are clearly outlined, and any open questions are stated where necessary.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiitiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
Justification: The assumptions stem from the problem setting, which is clearly outlined in Section 2. Any further assumptions are clearly outlined within the statement of the result, and all formal proofs are either given in the main body or in the appendix.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https: htlp:://nipg htt///nis.s..///e cc/
publ / guides/ Codeeuumm ss onoooll ollccyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips. cc/ httppscccppblip/////e. wtcp//bbccggguiioooo
CooeeeeeeSieeeeee SaddeSuuiiee ssiissiin aesionoolicyy for more details. The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
15

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: http:://neuueee /tw.rriuu...///.///.e httpppubblc/tttccccciieeeeeeelee
Answer: [Yes]
Justification: As theoretical paper which lacks experiments, the paper clearly conforms to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
The introduction implicitly outlines how our results and mechanisms can lead fairer outcomes in facility placement. We do anticipate any direct negative societal impacts of our work.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
16

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not include experiments or code.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use package should be provided. For popular datasets, papersw's thoode. com / datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
17

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
18

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The paper does not involve the use of any LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
/ / //nuurrrpsp... cc/ Conferences / 2025/ LLM) for what should or should not described.
Please refer our LLM policy (https: :
19

---

A Omitted Proofs for Section 3
A.1 Proof of Lemma 3.1
Proof. For an arbitrary location profile x (e1,..,;,,)) without loss of generality, we assume that S I Zn. Let i and ū denote the maximum and minimum agent utilities, respectively, when the facility is placed mid(x). Consequently, the optimal envy ratio can be expressed as ER(mid(xx),
For any facility location y E P. y E [21, ænI. the maximum utility is at most ū + ly mi)(x),, while the minimum utility under y is at least ly mid(x)]. Therefore, we derive the following inequality:
ER(y,)
( + (xid())))/(C - -ly mm)d()))
ER (mid((xx))
ū/ū
(ū + y mid( /))(/( (x)(
ratio is non-increasing w.r.t. ū)
ū//
ū + y mid(x))
mx)(x)))
Equality holds when all the agents are at 21 and In this case, consider new 2-agent in- stance x' = (n). Notice that both æ1 and 2n achieve the minimum utility under mid(x). i.c., uxmid(x)), 21) u(mid(xx) u. For this instance, the approximation ratio of placing the facility at y is
ER(y, x') (R(mid(x'))x)
it + by mid(x (x) 1/ū -ly mid(x')
i + Iy mid (x)))
ER(v, x)
i yy mi)(
ER(mid(x),
For the case where y & [n]. without loss of generality, assume > x. Since x2 and n, always
achieve the minimum utility under mid(x), we have d(mid(xx, x1) = d(mid(()) 2n) = 1 a.
When changing the facility location to y Fns 21 achieves the minimum utility while zn achieves the maximum utility. Specifically, uly, x1) = d(y Ø1) = (y mid(() + -1- a)) = +y+ mid(()) + while u(y, Thus, the envy ratio is
ddy, F..
(y mid (1-7)) = 2 2-2 y mid(x)
ER(y.x) x)
(2 - mid(x) - mid(s)
mid(x)
ER(mid (x), x)
ū/ū
2 y + mid(x)
ratio is non-increasing w.r.t. ū)
- + mid(x) + ū
Equality holds when all the agents located 21 and En- By considering the new instance x' (a,, it can be verified that
ER(y, x') ER(mid(x<) (x)))
2 - mid(x') -
- + mid(x') +
2 - + mid(x) ū
ER(y.x) x)
- + mid(x) + ER(mid(x), x)
In conclusion, for any location profile and distribution of facility locations P. can always construct new 2-agent instance x' = (Im(x), rx))) such that the approximation ratio of any y e under upper-bounded by the approximation ratio of y under x'. Formally,
ER(y,x)
ER(y.x) x') ER(mid (x'mid(x'),aa x')
E Eyer
< Eyer
ER CR(mid(x).xx
This completes the proof.
20

---

A.2 Proof of Theorem 3,4
Proof. When I E [1
x: 1), the a-BIM mechanism places the facility at ÿ. Without loss of generality,
assume that y" E [0. b]] (the case v" E ( 1] symmetric). Suppose the prediction error satisfies lú - y01 S We analyze the approximation ratio by cases 77. Note that for E [1, it always
holds that 1 - 2.
Case 1. E 10, 1. By Lemma 3.1, we may restrict to a two-agent instance x = (x1, .22 with
I2 = 2y r1. Since y" is optimal, the approximation ratio for placing the facility at ÿ bounded
by
(y* x1) + n
P 5
(y* z1) - "
+ 1)
(since æ 2 0, y S +
7
41
1 + 1- 21j
Case 2. 17 E ( 1 1. Here the prediction error exceeds 1 implying tighter bound on y
2' since y" 5 and E - a 1. Thus.y" S ÿ - 1) S 1/2 S 2
2' 2a
Consider any instance (x1, 2y" 111). When the facility moves from y to ÿ. the maximum utility can increase by at most 17, and the minimum utility can decrease by at most 7/. Hence,
1 (y- -1))
p
(y" xx1)
1 (1 -11)
(since 21 2 0, 8² S -n)
( - -1)
2am
1 +
a
Case 3. 1. In this regime, the approximation ratio is upper-bounded by the robustness ratio:
2a
5 a-1- This bound is tight for the instance (0, "),, where y" 20 and ÿ
Next, consider ý E [0, 2) or ÿ E (2. 1], where a-BIM places the facility the endpoint or 1. Without loss of generality, we analyze the case ý = 1
Case 1. y² S 11-1 - J. Here x2 is closer to I than 1 is. The utility of agent is at least 4, and that of
agent 2 is at most 1, yielding p S T/o a. Equality holds when y² 2 2a
1 for any 2 0.
Case 2. y² > 1 a.
1
We further distinguish subcases:
(a) If E 10, 1 - H. then y" = ÿ - 1 + S 1.4 Hence,
1
1
P (2 - (1 21-
(2(1 1 + 17) (1 2)) 1 207j
(b) nn E (1 the right) increases the ratio while maintaining y" 9 S Thus, we only need to consider 31 a g.giving
6 3,2 1. for any instance x (Iι 2y x1), moving 21 to 1-1 1 (if lies to
1- ((1 2) -1)
0
1 ((2y*
21) !))
2y -1
1 1-1 1 2n
20
<
1
1
1
where the second inequality follows from 0i
2 2y - 1. and the third from y" < 1 +7.
21

---

(c) nf > 1. the approximation ratio is bounded by a-1 which is tight for = a1:
2a. with y- 2n and 9 s for any
Combining the above, when 9 E (0,
4 ( 11, we obtain:
E
[0,
2a
0-1
1 2ar
17 E
0-1
2a
21
P Σ
1 2an
17 E
1
à
17 E 2a
+00).
1011
Finally, we combine all bounds by distinguishing two parameter ranges.
When a E [1, 1+/51 note that
a-1 2(x++1
I and that a Z
1+22 for rj S 1(
Hence:
1-2n
a
1j E [0, 2(4+1)
+ 1-2n
E 2(a+1)*
a-1
2
11
Pa
1 + a-
2an
(
11
2 2a
2a t00).
. When ( (1tv5 ,2), we obtain:
00,
(a-1)²
(a(n)
1+
2ng
E
2a
2a
11
+00).
2a
This completes the analysis of approximation ratio parameterized by prediction error bound.
B Omitted Proofs for Section 4
B.1 Proof of Lemma 4.1
Proof. For any arbitrary (0.P))LRM constant mechanism with a E (1) 1... we first consider
2-agent instance (I) 0, = 1). The approximation ratio p(x) under the instance x can be represented as
1-a 0:
1 0
p(x) = 1 (
+ (1 - 2p)
1 +p-
1 +
4- 4a
2 - 2p) +
1 - 4a
is straightforward to verify that p(x) is monotonically increasing with respect to a for 2 2) This implics that p(x) 2 2(1 2p) + - = 2(1 2pp) + 4p = 2 with equality attained when
= - In other words, as long as a > 1. the approximation of (LRM) is at least 2, regardless of the choice of parameter E [0, 11.
B.2 Proof of Lemma 4.2
Proof. Note that by Lemma 3.1, it suffices consider two-agent instances (2), Without loss of generality, we assume 0 < æh S R2 I 1. Let mid(x) = zıtza be the midpoint of the agents' locations. By symmetry, we focus on the case where mid(x) E [o, 1l (the analysis for mid(x)= []. 1] follows analogously). Let denote the utility of both agents when the facility is
22

---

placed at (x), and define å = 2 (x) as the distance between mid(x) and Consequently, we derive that 2 1/2 + 8 as u 1 - (mid(()) x1) 2 1 - mid(x) = 1 - ( 5) + 6. We
first consider the situation where a E [0, )) that is 1 2a + a. We consider the following two cases.
Case (1). 8 E [0,a]. i.e., mid(x) E 12 ax 1 For any such instance x (2), the approximation
ratio is
by
u + (a 6) u (a 5)
u u+ u + (ax + 8) 8 +
p(x) S
+ (1 2p)
(a + 6)
This bound follows from the observation that moving the facility location from mid(x) to 1 a results in maximum utility increase (decrease) of - ö, regardless of whether 21 iy is closer to mid(x). Similarly, moving the facility to 1 or + a changes an agent's 's utility by at most or a + 5, respectively.
2
2
Notice that p(x) monotonically non-increasing with respect to u and a 2 + 6, we further upper-bound the ratio by
+
2 +
26
+p- 2 + 28 +a
p(x) Sp
+ (11 2p)
+ 26
a
1+ 12
1+ 46 + 2ax
p
+ (1 - 2p) (1+ 40) + p-
1 + 40 20
20
1 + 2a 46
1 48 + 2a
S p
+ (1 - 2p) (1+ 40) + p-
1 2a
2a
(:' convexity of 1410-2a
1+2a
and 0 < 8 < o)
1 20x
= 2p
+ (1 - 2p) (1 + 40).
1 - 20x
Since p(x) is monotonically increasing with respect to and 5 E [0, al, it follows that p(x) is at most 2p- 1-2a + (1 - 2p) (1+4a) in which 8 a, i... when mid(x)
a, the approximation ratio is maximized, and the worst case falls into the instance (0, 1 - 2ax) where the inequalities become equality.
1-2a
Case (2). 8 E (a, 1) i.e., 0 S mid(x) < ax we first introduce the following claim.
Claim B.I. When (i) E [0, 1 a). for any instance x = (I1,, 32), the approximation ratio of (o.P) mechanism under x is upper-bounder by the approximation ratio under x' (0,
Proof. The proof starts by observing that for any instance x (#1, 22,,, it holds that y-zz 2 ly x2 for any y E _ a, 3. +a). That is, agent always obtains a smaller utility than agent 2. We prove this by considering the focation of 22 and each potential facility location y. If x² S y, the expression
trivially holds as x2 2 x1. Conversely, we have 12 y S y 21 as mid(x) = 21 < 2
and
y 1 a.
Let un (y) and (y( be the utilities of agent and 2 under potential facility location y E ( a, 3. + a}. As we know that un (y) S uz(y) for each y E & a, 2. 2 + a.), the approximation ratio of (a, (2,p)-LRMM mechanism is upper-bounded by
u2( 1 a)
(2(
u2 + a)
p(x) = p.
+ (1 2p)
+ p
u1 2 1 a)
"i (t)
1 5 + aa)
= p' u2( {1 a:)
u2 (22
uz(2 +a)
+ (1 - 2p)
+ +p 1 - ((} + aa) - T1
(( a) F1
1
x1
u2 [
7 ()
12 (2( (
12(5 + aa)
+ (1 2p)
+p- (9} + + - x1
= p(x).
1 (g () x
1 { x1)
23

---

With the claim in hand, we now turn our attention into the instances x = (0,x2) when mid(x) E [0. 2 aa. We divide the proof into subcases depending on the location of 22.
Sub-Case (a). 22 E [0, 1 - al. The approximation ratio is represented as
1 1 ( a x22) + (1 2p)
(
x2)
1 (1 + a 12)
p(x) = p
+p-
(1] -a)
1- 2
1- ( +a)
1+ 2a + 202
1- 1-2a- 2x2
=p 1 + 2a
+ (1 2p) (1+ 2x2) +p-
20
Here, p(x) has a derivative of
dp(x)
2p
2p
+ 2(1 - 22p
+
2 0,
dx²
+ 2a
1- 2a
as p E 10, 2] and a E [0, al This implies that p(x) is monotonically increasing with respect to 2-2-
Since 12 E [0, _/2 a]. we have that the approximation ratio of any instance x where 22 E [0, a] is maximized under the instance
(I1 0, 22 a).
Sub-Case (b). 22 E ( a. $1. We slightly modify the approximation ratio expression from sub-case (a) and get
p(x) p. - (x2 - a))
+ (1-2p) 1 ( -x2)
1- ( + ta- -x2)
+p.
- (2 0x)
- 2
(2 + a
3 2n- 2a
1 -a + 2x0
=p. 1+ 2a
+ (1 (p) (1+ 2x²) +p-
2a
Similarly, we compute the derivative of p(x) with respect 222
dp(x)
2p
2p
8pa
+ 2p) +
+ +1(1 -p))-pp) 2 0.
dr² + 2a
1 2a
1 4a²
(. E [0, 2), a 10, d)
It follows that the instance with the maximum approximation ratio has 22 = 2 i.e., x = (x1
1
0, = 2)
Sub-Case (c). 20.22 E (2:2 2 + a]. In this case, we have
1- (2= - ( a))
+ (1 - (1-2p). 1 (x2
1
1- ( + + x2)
p(x) p.
+p.
1 (1 (x)
(5 + a)
3 - 2.2 2a
1 2a + 202
=p. 1+ 2a
+ (1 2p) - (3-2rz) + p--
1 2a
The derivative is written as
dp(x)
2p 2(1 2p) +
2p
8pa
4p 2.
dr + 2a
I- 2a
4a²
Notably, when given and p. the derivative is a constant, implying that the approximation ratio is either monotonically increasing or decreasing with respect to T2. That is, for any instance this sub-case, the approximation ratio is either upper-bounded by that under (x1 0, (1) or
(x) 0, = 1/2 + +x).
Sub-Case (d). .2 (1 a, 1 2a]. The approximation ratio is computed as
1- (x2 - ( - a))
1 - (I)
(x) - (1 + a))
p(x) = p-
+ (1 2p))
+ p
- g a)
1 1- 2
( aa)
3 - 2.122 - 2xx
3 2x 2002
=p p 1 1 2a
+ (1 (1)) (3 2x²) +p.
1 2a
The derivative of p(x) w.r.t I22 is
dp(x)
2p
2p
4p
2(1 2p)
2(1 2p) S O.
dx2
1 + 2a
1
2a
4a
24

---

eitber x==
12
mid(x)
322
ta D2
+
2 +
2ax
Figure 4: Summary of Analysis when mid(x) E [0, -a]
Since p(x) is monotonically non-increasing with respect to 22 and x2 E (2 + 10,11-111 - 2a]. it follows
that (xx is upper-bounded by the approximation ratio under the instance (œ) 0, x²2 2 + a))
Figure depicts the worst instances under 4 sub-cases in Case (2).
We next observe that the approximation ratio of instance x = (x1 = 0, x2 = a) is no worse than
that instance x = (#1 = 0, T2 = 1),, and the approximation ratio of instance x = (21 0,
1 - 2a) under Case (1) is no worse than that of instance = (z1 0, = 2 + a).
By combining all aforementioned subcase discussions, we conclude that when a S G. computing the
general optimal (a, p)-LRM mechanism boils down to finding the optimal (a: p) which optimizes the
approximation ratio of envy ratio objective under instance X = (I1 = 0, Z2 2) and x = [21
0, 0, = + a.).
We next consider the remaining main case where a E 6 1 We consider three subcases depending on the position of mid(x). Since only consider mid(x) E [0, 1.. the approximation ratio p(x) is viewed as a function of u (recall u the optimal utility under mi)(x)), which is monotonically decreasing with respect to Note that
6, which implies that we only need to consider the
cases where T1 = 0. By fixing #1 = 0, we mainly consider the location of 22 as follows.
Case (1). x2 E [0, a.). The approximation ratio is represented as
1 - ( a x2)
- ( x2)
+ a T2)
p(x) p-
+ (1 22)
+p.
-a)
2/2
( +a)
1 + 2a + 20²
1 1- 2a 20²
=p + 2a
(1 2p) +1+ 2x22)
+p.
- 2a
which monotonically increasing with respect to 22, implying the worst instance this case (x1 0, = ar).
Case (2). x2 E (2 - 2 The approximation ratio is represented as
1 - [22 - ! aa)
( F2)
1- ( + a 322
p(x) =p.
+ (1- 2p)
+p.
-a)
a) 1 1 2a + 202
3 202 20
= 1 2a
+ (1 2p) (1 2x22 + +p.
1 2xx
Consequently, the derivative of p(x) over T2 is
dp(x)
2p
2p
8pa
+ 2(1 2p) +
2(1
2p) 0.
dr 1 2a
2a
4a
Therefore, the approximation ratio is upper- bounded by the instance where 2 0, 02 Case (3). 22 ( 2n.). The approximation ratio represented
1 - (x2 - ( a))
+ (1-2p)) 1 (x2
1)
1 1 (1 + a -x)2
p(x) p. - {1 (x)
+ p.
- + a
2
3 3 2r 2a
1 2a + 2x²
p 1 2a
+ (1 2p) (3-2xz) + +p.
2x
We compute the derivative of p(x) with respect to D22
dp(x)
2p
2pp + 2p
2(1
dx
1 2a
20
25

---

Case (4), 22 E (1 (1-2a, + a.. The approximation ratio is represented as
1 (1 a:)
- (x2
1 - +p. 1- + x2)
1
p(x) = p.
+ (1 (1-2p).
1 - (22 - (2 a))
-( +a)
+ 2a
- 22 2002
= p 3 20- 2a
+ (1 2p) (3222 + xp
1 2ax
Similarly, the derivative of p(x) over 22 is written as
dp(x)
2p(1 + 2ax)
2p
dæ² (3 - 2x² - 2 2(1 - 2p) + 1 2a
Notably, the derivative in Case (4) is no less than that of Case (3). It follows that if p(x) is monotonically increasing w.r.t. 22 in Case (3), then p(x) is monotonically increasing w.r.. 22 in Case (4). Conversely, if p(x) monotonically decreasing w.r.t. 22 in Case (3), p(x) could be either monotonically increasing or decreasing. This implies that the instance with worst approximation ratio is either 22 = 2 or 22 = + a.
Case (5). I2 (3 + a, 1]. Recall the definition of 8 - mid(x)), we write the approximation
ratio p(x) as function of
pxx) S p-
2 a
+11 2p): 3
+ 26
+ p
+
28 +
2
+ +0 a
2
2 - a
1
1 2a
1 46 20
=p I+ 48 2a
+ (1 2p) (1 40) +
20x
Since 22 E E + a, 1], we have å & [0, 4 - 2 Likewise, we use the same technique in Case (1)
when considering E [0. l. From the convexity of the term
1-20 1+16-20 get
2 + 4ax
1 + 20x
1 + 48 + 2ax
p(x) p. (- (1-2a) 5
(1 2p) (1+44) +p-
20
1 2a
Consider the derivative of the RHS.
dp(x)
(2+ 4
4p
4(1 2p) +
d8
(1 - 2a)²
1- 20x
+ 2
4p
3
+ 4(1 2p)
+
(:: monotonically increasing w.r.t. a E (1 D
$
1 1-
8p 0.
This implies that the RHS is monotonically increasing with respect å when 8 E 10, 1 2) Hence, p(x) is upper-bounded by the instance when = 1 3. i.c., x = (01 = 0, 12 1 + +a)
() and a [ 41. we derive that = (z) 0, = } and x' = (af = 0, 2² = 1/2 + a) are the two instances with the worst approximation ratio. Formally, when a < 4. the "p''LLLMMM constant Mechanism optimizes the approximation ratio of envy ratio objective where (a",p") = arg min (max This completes the proof.
By combining the two main cases, i.e., a E [0.
B.3 Proof of Theorem 4.3
Proof. Anonymity and strategyproofness are immediate. From Lemma 4.1 and Lemma 4.2, it suffices to only consider the two special instances (x1 0, x2 1), and x' = (œ1 0, x/2 2 + a).
Consider any arbitrary (a. p)- L)-L mechanism where E [0, }). We express the approximation ratio for instances x and x' as a function of a and as follows. The approximation ratio under x can be expressed as
1-a
a
p(x) = p.
+ (1
2p)
+p
1 g ②
1
1
1
26

---

The expression of the approximation ratio under x' slightly varies depending on the range of a. In particular, when a E [0, e can be represented as
1-2a p(x') p
1-a + (1-2p)
1
a + p
+
2
2 4a
2
=p- 1 2a
-2x) +p- 1- 22x + (1- (1-2p))
When E ( 7). for instance x', when placing the facility at 1/2 0x, I is the agent who has higher utility, Henceforth, the approximation ratio is written as
2 +
1
p(x'
=
2a
+ (1 2p) 2p)
1
+ p
2a
2
=p 2 2 4a
+ (1 (1- (2 1 2a) + 1- 2a.
Since the approximation ratio under instance x' varies with respect to the range of a. We compute the optimal parameters of a and p by considering a E [0, al and a E ( t). respectively.
Case (1), a E [0, } We show that min (. (e. max(p(x), p(x') takes an optimal value of and 2
approximately 1 + v5 = 1.8944 when a = v5
2
5"
We first consider the values of a and p which satisfy p(x) = p(x').
We have
4 4- 4a
2 4a
2
2(1 - 2p) + p.
1 4a
p-
+ 20x
+ (1 22) - -2a) + p
1 2a
Dividing both sides by 2 simplifies the expression to
2 20
2xx
1 1 1-2p + p
2p+
1- 4a = p
+ +1 2p) - (1) + 1 20.
1 20
- a - 2ap p(1 2x)2
+ p(1 + 20x
p(2 2x)
1 - 4
40²
402
- (a 20 (1 4a 2 p(1
4a + 4a² + 1 + 20
2 + 20x)
- a 40 3 2op + 80. 402p
pf8a² 2 4n²
2a) = 4a
2
p 2(4a² -2x - 1)
Note that this solution also requires 2a² - + 0 and 4a² 2a - * 0, which are achieved under a E [0, g. Substituting
Hence, we know that p(x) = p(x') when p -
2
3(1a--2a-1) into 2(1 2p) + p-
4n²
-- gives us
4-da
2 1 2 - -2 - ) + 2(4a² 22 - 1)
4a² 11
4a² 1
4 4a
8a² 4a 2 Sa² +
2a 2
4a²
4a² - 2a -
4a 2a
2a +
-4a² + 2a
which has derivative of
d 2 do
8a + 16a 2
-4a + 2a +1
(-4n2 + 2a + 1)2
This derivative is equal when -1 former value as a 2 0. Substituting
y5
2
when v5
1 R 0.118. We ignore the
v5 2
into p 2 20-1j
4n
gives 2
6.
27

---

By substitution, we have that p(x) = p(x') 1+ 88 ~ 1.8944 when _ -1 and p 5. From Lemmas B.2 and B.3, it follows that mi.. 1 pax optimality of the mechanism.
( =1 + v8 proving the
2
Case (1). a E l0: 21. With a similar method of analysis in (1), we can prove that min [0. max (nax{f(x), takes an optimal value of approximately 21 R 1.8944 when and p 11. Similarly, first consider the value of and p which satisfy p(x) p(x').
That iS.
4 4- 4a
1 22x
2
2(1 2p) + p
p-
+ (1 - (2 2xx + p- 1 2a
4a
2 4xx
It follows that
16a 4a
p 32a 4a² 28a +
Henceforth, p(x) p(x') when p 32a have
1
By substituting the p back into p(x),
2a +3
8 56a + 6
p(x) = p(x)) = 32a 4a² 28a + 3
which is monotonically increasing with respect to a E 6 1.1 Hence, by leveraging the very similar technique as in (1), we obtain that when = and p = II min p(xx)) A R 1.909.
4
By combining these two case analysis, conclude that the (25 1, --1))-LMM constant mechanism optimizes the approximation ratio at JsB R 1.8944.
Lemma B.2. 1f p(x) < 1 + v3. then p(x')= 1 v3'
Proof. We have
p(x) < +
v5
4 - 4a
2
2 4p + p
1 +
1 4a
V3
1-a
2
4p - - 4a²
> 1
55
(1 2
v5 (1 4a?)
p
4a(1 - 4a)
Note that the approximation ratio under x' can be rewritten
2 4a
2
p(x') p-
(1 2p)(2 -2a) +
+ 20
20
4a
2
= p
+ 4ax
+
+ 2 2(x
1 + 2a
1 2nx
(3 2a)
+ 2a.
(1 20x) (2a + 1)
Since p 1+2a
2- + (1 22 20)) + p. I-2a 2 0 for all 0
1/2 we can substitute
(1- 2 (1 (1=4)
px 1a(1-1a)
obtain
(1 23) (1 4a?)
8a² -2a)
p(x)= >
+ 2a
4a(1 40)
(1 22a + 1)
(1 2 22(33 2a))
+ 2a.
4cx
28

---

v5 311- Therefore, by The derivative of this expression is
d (1 (5) 2a(3 -2x)
4(4(5 + 225)a² - 2(5 + 2/5 + 3355 -
+2- 20x
do:
1 1 -4
5(1 4a
which is equal to 0 when = -5 1 or 2
3-v5 - 2 Li 2
Thus, we see that when E [0, t.. the
expression takes a minimum of 1 +
2
when a
1. Therefore, p(x') > 1 + vB
2 when
v5
p(x) ++ A8
Lemma B.3. If p(xx' < 1 + 2
then p(x) > 1+
2
V5
v5
Proof. We have
2
p(x') < 1 +
V5
83 - 2a)
2
p
22) 1)
2a
1+
V5
(2a -11 1
2
(1 4a
v5
832 2a)
Note that when a < satisfied. We therefore restrict our attention to [ v H---
V5* the RHS becomes negative and consequently, the inequality cannot be
Note that p(x) = 2 + 4p 1-1a2
-a and that 4a < when a E [2 1-ta²
(2a-1+ Jo (1-daa))
substituting p <
we have that when p(x') < 1 + v5
8a 83-(3-20)
(2ar 1 + 2 (4x - 1)
vt
p(x) > 2+
20x(3 - 20x)
The derivative of the RHS is
d
(2ar - 1 37 (4cx
4(15 4V5)a2 + (20 8/5)a a 6v5 15
2 +
da
23x(3 - 20))
10(3 - 20)
which is equal to when a the expression takes minimum of 1 + v3 when v5
vL or when a
6
9v5
We therefore see that when a E [0, d..
2
29
55
proving that p(x) v5 when
p(x')
V5
B.4 Proof of Theorem 4.4
Proof. To show the lower bound, we first consider the location profile with two agents x (r) 0.29, Z2 = 0.71). Note that for any randomized mechanism f. we have either Eges(x) II 0.29 >
0.21 or E0 l19 - 0.71|] 2 0.21.
We first consider the former case, where Ryyes()lly - 0.29]] 2 0.21. Let x' = (0, 0.71). Then we must have
Eyef(x) fly - 0.29 2 E 0.29|] 2 0.21,
otherwise agent 1 at 2 = 0.29 has an incentive to change her reported location to a/f = 0 for a better outcome, violating strategyproofness. Denote 8 = 4300
617 2 0.14, and
P1 Pr(ff(x') [0.29- - 8, 0.29 6]}
P2 : Pr(f(x') E 0.29 8) + 6, 0.58) Pa == (x') E (0.58, 1}}
29

---

Then, we have
Bye/(x)llv - 0.29 < ōp1 + 0.29p2 + 0.71pa
= = + (0.29 5)p2 + (0.71 8)p3.
Substituting Ee Fee)(ly 0.29 2 0.21 gives us
- (0.29 - 8)p2 + (0.71 8)p3 0.21.
which we can rearrange to form the inequality
P3 0.21 (0.29 8)p2
0.71
Finally, we have
ER(S(x),x)
1 1- (0.71- (0.29+)))))+))
1 - (0.71 - 0.58)
P11
+
1 - (0.29 -
1 - 0.58
0.58 8
0.87
= P1 + 0.71 - 8 0.42
25 - 0.13
15
+
0.71 - P/2
T4
28 - 0.13
15
0.21 - 8- (0.29 8)p2
+
0.71 8 P2
14
0.71
28 0.13
0.29
0.21
+ 0.71 -
P2 +
14 0.71 - 8 14 0.71
1.12579.
where in the last inequality, we substitute =
4306 so that the term in front of becomes equal to
617
zero. Note that ER(mid(x')xx' = 1, leading to our approximation ratio lower bound of 1. 1.12579.
For the remaining case where Ey Ily 0.71|] 2 0.21, we let x' (0.29, 1) and make symmetric argument.
C
Missing Details on Randomized Mechanisms with Prediction
For randomized mechanisms with prediction, by incorporating the newly devised ( -1 )-LMM constant mechanism with the learning augmentation scheme, we have the following randomized mechanism.
Mechanism 4 a-Bounding Interval Randomized Mechanism
Input: Location profile x, optimal locaiton prediction ÿ. Output: Distribution of facility location f(x, 5) I: Initialize the confidence parameter a (1, 2].
2: if [1 2: then
3: Return f(x 9) + 0:
4: else
5: Return f(x, 9) - ( - -1,
- 7-LLRMM constant mechanism with input x.
6: end if
The a- o--oundding Interval Randomized Mechanism adopts a similar approach to a-BIM. It begins by defining "trustworthy" interval associated with the predicted optimal facility location. When the prediction falls outside this interval, the mechanism employs the (>/ 1, - constant mechanism ensure the small robustness. However, next analysis shows that it achieves even worse consistency and robustness than a-BIM.
Proposition C.I. a-Bounding Interval Randomized Mechanism is strategyproof and satisfies min(1+ 12+4v0 [1 2), ( + 2x/6 + {1 2),1+ 1 2 -consisttency - -obbrussss with respect to envy ratio, where E (1,
30

---

Proof. Strategyproofness directly holds for the a- e-Boundinn Interval Randomized Mechanism. We mainly focus on the proof of the bounds of consistency and robustness.
Consistency. Consider any instance x with a correct prediction of the optimal facility location, ie., ú mid(x). If ý is within [1
J the mechanism outputs D. providing 1-consistency. Next, we consider the case where i E [0, 1 al in which the mechanism returns the output of the (v5 1, )-LLMM constant mechanism. Here, consider the following sub-cases divided by the range of the parameter a. By Lemma 3.1, it suffices to consider instances with two agents where 0 21 < x2 2(1 =
We first notice that when E 2], f.e., 2(1 ) E [2, 1), the consistency is always bounded by 1 + 3ेB since there always exists one Iwo-agent instance achieving approximation ratio of 1 + VB regardless the prediction location y. Therefore, we mainly consider two cases
2
Case (1). 2(1 -) ملاة i.e., E [1, V5 1] which implies that both Iy and 12 are on the left Henceforth, the approximation ratio is upper-bounded by
side of 3-y5 2
2 1 - 3- 2(1 )
1 1 - ( 2(1 4)
2
1-
55-1 2
2(1 - 4)
p(x)
+
5 1 3-y5
5
V5-1
2
= =1+ 12 +
5 1
a
where the equality holds when T 0 and x2 2(1 )
Case (2). 2(1 - 2)) 3-y5 i.c. E (v5 -
15,-1,11 1, The approximation ratio is upper-bounded by
2 1 12 1 - 3-v5
1 1- 2 ))
2 1
1551
2(1
)
p(x) s
2
5
1
1- 3-v3
5 1- 2
y3
2
2/5
-(5
5
5
where the equality holds when I = 0 and Ø2 = -))
Robustness. Now we consider the robustness of the mechanism. By Mechanism 1, we can see that if branch achieves قق robustness and else branch achieves robustness. Hence, the robustness 3
Next, we extend BAM by leveraging the ( 1, )-LM Mechanism, that is, with probability (1 p) running _ 1, A -LRM mechanism, rather than putting the facility at 1
Mechanism 5 Aware LRM Mechanism
Input: Location profile facility location prediction ý.
Output:
Facility location f(x, 0) 1: Compute bias = -0
2: Compute probability p- = c
3: With probability p: return
4: With probability 1 p: return V5
J -RR constant mechanism with input
We next show that Bias-Aware LRM Mechanism is worse than BAM by constructing some special instances.
Proposition C.2. Bias-Aware LRM mechanism is strategyproof and satisfies
2349v5
consistency and
v5) -robustness when [0, }1. and -
consistency,
( (4 7 5)) robustness when [t y5-11 and (3)+ 6
consistency,
(4v 775 5)) robustness when [55-1 11.
31

---

Proof. Strategyproofness directly holds for the Bias- LRM mechanism. We mainly focus on the proof of the lower bounds of consistency and robustness. Without loss of generality, we assume that ij S 2.
Consistency. By Lemma 3.1 and the proof of Theorem 4.3, only need consider instances with two agents where 0 = 21 < I 1. Note that the envy ratio achieved by is 1. The envy ratio achieved by ( 1, _ --LM is always 5+2y5 When moving 22 from location 1 to location 1
2 1, } )LLMM,, the probability of using ( v 1, 3. >-LRM will increase. Thus the expected approximation ratio will increase. Therefore, we only need to consider the case where 0- = I1 < I2 x
(the right boundary of E
2b-1 Consider any instance x with correct prediction of optimal facility
2
location G. i.e. mid(x) (x) = ÿ. We have أ I v5-1
If وة 3- 3- then v5-1 1 and the consistency is
ER(S(x,8) x),
(R(mid(x),x
2
v5-1
+
2ÿ
1
1
+ 29
2
3 3-v5
+
20
=j. (1 (1-1)
2
2
5
v5
3 v
4(3 + v5)
V5
+
2
5
which is monotonically decreasing with respect to c.
If 3- sūS 1. then [ 4 and the consistency is
ER(S(x,0) x),
ER(mid(x),
2
5 5-v5
2ÿ
1
+
2ÿ
2
3 3-v5
+ 20
= 1 (1 -g)
1
()
2
5
V5-1
5
3 /5
-88 2(23 1)c
v5 v5+6, 66
which is monotonically decreasing with respect to c.
If S 2ー-1 T then شممم 1). and the consistency is
ER(((x,0) x),
7 = ER(mid(x),x
2
5-
2ÿ
29
2
3-y5
+ 2
ÿ. 1 (1 9)
+
2
5
/5
5
3-
2
2c
1
11,
55
v5
which is monotonically increasing with respect to c.
2- 7. By using a similar analysis as Theorem 4.3 we have that the worst case satisfies 22 1. If œ g. we can show that moving this agent from x to ý will increase the expected envy ratio. To see this, the envy ratio achieved by ÿ is increasing and the envy ratio achieved by 2 --LLMM constant mechanism is increasing. If #1 3 3-v5 v5
-- Robustness. 0 S ÿ s 3-y8 then e E 25-2 11,
can also use similar analysis to show that moving this agent from 21 to v will increase the 2
expected envy ratio. Then consider 21 E [ū, 1.1 Let 5 21 ÿ. by using the similar analysis as Theorem 4.3 we can show that the approximation ratio satisfies the monotonicity with respect to
Hence, we only need compare the envy ratio between two cases (Ø. 1) and (3 1).
32

---

For case (0. 0 S 55- - 2 (CE
1
V3, 21, we have the robustness
2 vī-1 +
vB-1
+
3= .. + (1 Ø)
3
3-y5
+
2
3-
2
+ 0
4(v5 5)c² +
4(455 13) c + 421 - 53)c
34 + 89
5(v5 - (2c v5 -4)
If V < 3-v 2
(CE
2 5
2
2
-
v5), we have the robustness
1
2
v5 +ÿ +
3 5
+
B "
+ (1 !)
5
3-yL
5
2
10 ( [43 + v (2 + 4v5)c+ +33+++++1
For case (3 1). we have the robustness
B ==
1/-1
2
+
+ (1 -9
2
+1)
9
V
(4v + 7V5 + 5),
10
which is monotonically increasing with respect to c, and always larger than the robustness achieved
by (9.1). 1).
ق-V6 و S 3.40 then e E [0, v When #1 and 22 = 0, the envy ratios achieved by ý and
2
(/5-1 2
-LLM reach the maximum. Then the robustness is
2
5 + 225
B = Ú + (1 1)
5
2 V5
1 3
< + 1)e +
V5
2
which is monotonically increasing with respect to Combined with the consistency, we have that when E [0, 1). both the consistency and robustness are better than c (in this case, it is
upper-bounded by 233+9v5 -consistency and ( + Vラ )-robustness) which can be omitted.
20
We compare the consistency and robustness of all aforementioned four mechanisms, including a- a-BIM, BAM, Bounding Interval Randomized Mechanism, and Bias-Aware LRM Mechanism in Figure 5.
8
Robustness
7
6
5
4
3
1.2
1.4
1.6
1.8
2
Consistency
Figure 5: Comparison between c-BIM (red solid line), BAM (blue dashed line), a-Bounding Interval Random- ized Mechanism (green dashdotted line), and Bias-Aware LRM Mechanism (orange dotted line).
BAM clearly outperforms both B-MIM and the a-Bounding Interval Randomized Mechanism. While the Bias-Aware LRM Mechanism shares the same framework as BAM, it slightly less effective and involves greater complexity.
33


Reviews:
[{"review_id": "UXhIYn5ng6", "reviewer": "Reviewer_P6NH", "summary": "This paper studies the facility location problem for the envy ratio objective, with and without machine learning predictions. The envy ratio is a fairness metric defined as the maximum ratio of utilities between any two agents. The goal is to find anonymous and strategy proof mechanisms that have small approximation ratios. For the setting without machine learning predictions, this paper proposes a randomized algorithm $(\\alpha, p)$-LRM, which improves the approximation ratio from 2 (by Ding et al. [2020]) to 1.8944. The authors also give a lower bound example which improves the previous lowder bound of 1.0314 to 1.12579. For the setting with machine learning predictions, the authors propose a learning augmented deterministic algorithm with $\\alpha$-consistency and $\\frac{\\alpha}{\\alpha-1}$ -robustness, with $\\alpha \\in [1, 2]$, and show the optimality of this algorithm. Finally, they propose a learning augmented randomized mechanism BAM that outperforms the $\\alpha$-BIM in both consistency and robustness.", "questions": "* In Theorem 4.5, does the robustness proof work for any $c \\ in [0, \\frac{1}{2}]$? Why is the maximum robustness for $c \\ in [0, \\frac{1}{4})$ = $\\frac{7}{4}$ instead of $\\frac{9}{4}$?\n* Also for Theorem 4.5, why do you state the maximum consistency and robustness for $c\\in[0,\\frac{1}{4})$ instead of formulas with $c$ as a parameter?\n* There is still a large gap between the upper and lower bounds for the randomized mechanisms without prediction. Do you have any conjecture about what type of algorithms could improve the approximation ratio? Does it help to return more than three locations?", "limitations": "The authors discussed the limitations and future directions.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "* Strengths\n    * The paper is well-written and organized, with clearly presented and proven theorems and statements.\n    * This work appropriately builds upon prior research in facility location mechanisms for the envy ratio objective and learning-augmented algorithms. All related works are properly cited.\n    * The paper enhances the upper and lower bounds of the randomized mechanism without prediction. Additionally, it introduces novel mechanisms that offer consistency-robustness tradeoffs in the setting with machine learning predictions. The analysis and lower bound constructions are non-trivial.\n* Weaknesses\n    * A direct future direction is to reduce the gap between the upper and lower bounds for randomized mechanisms without prediction.\n\n* Minor comments\n    * Page 19, line 757. “$u(y, x_1) = 1 - d(y, x_i)$” => $x_i$ should be $x_1$\n    * Page 20, line 789 and 791. “$\\rho(\\mathbf{x})$ is monotonically non-increasing / increasing” Do you mean the upper bound of $\\rho(\\mathbf{x})$?", "was_revised": true, "final_justification": "This paper appropriately builds upon prior research in facility location mechanisms for the envy ratio objective and learning-augmented algorithms. The authors have addressed all my questions. The main remaining concern is the relatively large gap between the upper and lower bounds, but I think the problem and techniques proposed in this paper will have positive impact on the theoretical research on facility location problems.", "rebuttal": "Thank you for your insightful comments and suggestions. We respond to your questions and concerns as follows.\n\n**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?**\n\nA: 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. \n\n**Q: Any idea or conjecture of narrowing the gap for randomized mechanisms without prediction? For example, considering more than three candidate locations?**\n\nA: 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.\n\n**Q: Minor comments.**\n\nA: Thank you for pointing out the typos. We will make the corresponding edits in the revised version of our paper."}, {"review_id": "XAqcqShquG", "reviewer": "Reviewer_jQBn", "summary": "This paper studies the strategic facility location problem in a one-dimensional space. The authors consider a fairness objective, specifically the envy ratio, which is the maximum ratio between the utilities of any two agents.\n\nThey examine both deterministic and randomized settings, and they also explore the learning-augmented setting, where some prediction about the optimal outcome is available.\nIn the deterministic setting, they propose a mechanism and establish a consistency-robustness trade-off, proving its optimality.\nIn the randomized setting, they improve the best known upper and lower bounds. Moreover, they propose a mechanism with predictions in this setting.", "questions": "1- 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?\n\n2- Is there any known lower bound for the one-dimensional setting without the fixed interval constraint?\n\n3- Have you considered other prediction settings? For example, can stronger results be obtained if the predictions concern agents' locations?\n\n4- I agree with the authors that establishing a lower bound for randomized mechanisms with predictions is an interesting direction. Could you please elaborate more on the challenges involved?\n\n5- Which of your proposed mechanisms are tolerant to small prediction errors? What guarantees can you provide in terms of smoothness?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The facility location problem is a very interesting and practical problem, and I enjoyed reading this work. The quality of writing is good, and the results require significant effort to obtain. Although some of the underlying ideas (such as those in Mechanism 1 or Lemma 3.1) are drawn from previous works, the results do exhibit some novelty.\n\nMy main concern is the setting. The results are not only restricted to the line metric, but also to a fixed interval. Without a fixed interval, the constant 1/2 mechanism is not a 2-approximation and can be unbounded on an arbitrary line. The proposed mechanisms rely on this constant 1/2 mechanism, which makes the strategyproofness property relatively straightforward. I recommend that the setting be described more clearly throughout the paper, and that it also be explicitly mentioned in the abstract.", "was_revised": true, "final_justification": "This paper addresses an important and practical problem with technically interesting results and overall good writing. While some ideas build on prior work, the contributions are novel and meaningful. My main concern remains the restricted setting, specifically the reliance on a fixed interval, which limits the generality and makes some properties easier to obtain. I appreciate the authors' response and their plan to improve the presentation and include smoothness analysis. However, due to the limitations of the setting, I am not increasing my score.", "rebuttal": "Thank you for your insightful comments and suggestions. We respond to your questions and concerns as follows.\n\n**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?**\n\nA: 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. \n\n(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.\n\n(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.\n\n(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.\n\n**Q: Is there any known lower bound for the one-dimensional setting without the fixed interval constraint?**\n\nA: 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.\n\n**Q: Have you considered other prediction settings? For example, can stronger results be obtained if the predictions concern agents' locations?**\n\nA:  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.\n\n**Q: What is the challenge of establishing the lower bound for randomized mechanisms with prediction?**\n\nA: 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.\n\n**Q: Which of your proposed mechanisms are tolerant to small prediction errors? What guarantees can you provide in terms of smoothness?**\n\nA: 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.\n\nFor 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. \nWhen $\\alpha \\leq \\frac{1+\\sqrt{5}}{2}$, we have the approximation ratio \n$$\n\\rho_{\\alpha}(\\eta)=\n\\begin{cases}\n\\alpha & \\eta \\in [0, \\frac{\\alpha - 1}{2(\\alpha + 1)}]\\\\\\\\\n1 + \\frac{4\\eta}{1-2\\eta} & \\eta \\in [\\frac{\\alpha - 1}{2(\\alpha + 1)}, \\frac{1}{\\alpha}-\\frac{1}{2}]\\\\\\\\\n1 + \\frac{2\\alpha \\eta}{\\alpha - 1} & \\eta \\in [\\frac{1}{\\alpha}-\\frac{1}{2}, \\frac{1}{2\\alpha}] \\\\\\\\\n\\end{cases}\n$$\nWhen $\\alpha > \\frac{1+\\sqrt{5}}{2}$, we have the approximation ratio\n$$\n\\rho_{\\alpha}(\\eta)=\n\\begin{cases}\n\\alpha & \\eta \\in [0, \\frac{(\\alpha - 1)^2}{2\\alpha}]\\\\\\\\\n1 + \\frac{2\\alpha\\eta}{\\alpha - 1} & \\eta \\in [ \\frac{(\\alpha - 1)^2}{2\\alpha}, \\frac{1}{2\\alpha}]\\\\\\\\\n\\end{cases}\n$$\nIntuitively, 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**. \n\nFor 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)$."}, {"review_id": "JUTqABgPgo", "reviewer": "Reviewer_gHpJ", "summary": "This paper studies the design of strategyproof mechanisms for the facility location problem on the interval $[0,1]$, focusing on the envy ratio objective. The authors explore this problem within the learning-augmented framework, where the algorithm is given a potentially inaccurate prediction of the optimal facility location. The objective is to design algorithms with good consistency-robustness tradeoffs.\n\nThe paper first introduces a new deterministic mechanism called $\\alpha$-Bounding Interval Mechanism ($\\alpha$-BIM), which uses a parameter $\\alpha \\in [1,2]$ to tune the tradeoff between consistency and robustness. The authors prove that $\\alpha$-BIM achieves optimal trade-offs between these two measures for deterministic strategyproof and anonymous mechanisms.\n\nIn the randomized setting without predictions, the authors construct a randomized strategyproof mechanism that achieves an approximation ratio of $1+2/\\sqrt{5}$, improving on the previous best-known bound of 2. They also establish a lower bound of 1.1125 on the approximation ratio of any randomized mechanism, improving also upon the best known lower bound of 1.0314.\n\nFinally, they propose the Biased-Aware Mechanism (BAM) for the randomized setting with prediction, achieving a consistency-robustness tradeoff strictly better than $\\alpha$-BIM, which they proved to be optimal for deterministic algorithms.", "questions": "- Do the authors think that their algorithms have smoothness guarantees that they did not explore? Or are the algorithms brittle? (See for example \"Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search\" for the definition of brittleness). In any case, I hope the authors will provide some evidence or intuition to support their answer.\n- In the randomized setting without predictions, the gap between the upper and lower bounds is still big. Do the authors have some intuition on possible future directions to narrow it more? And if the improvement should be significant on the upper or the lower bound?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### **Strengths**\n- The problem studied is an interesting fundamental problem\n- The results of the paper cover deterministic and randomized algorithms, with and without predictions.\n- The consistency-robustness tradeoff for deterministic algorithms is tight.\n- The gap between upper and lower bounds in the randomized setting (without predictions) is narrowed by improving both the upper and lower bound, which is a very nice contribution.\n- The paper is very well written and easy to follow.\n\n### **Weaknesses**\n- In the learning-augmented framework, the authors focus on consistency and robustness, but do not study the smoothness of their algorithms, which is crucial criterion for algorithms with predictions, characterizing how the algorithm performance degrades as the prediction error increases.\n- While $\\alpha$-BIM is well-explained, there isn't much intuition on how the algorithm was designed.\n\n### **Comments**\n- In lines 85, 304 and 317, the paper states that BAM achieves a consistency of 7/4 and a robustness of 7/4. I believe this is a typo. Following the proof, the robustness achieved by BAM is 9/4, which equals 2.25 as shown in Figure 2. I trust the authors will correct this.", "was_revised": true, "final_justification": "I maintain my score of 5, as I believe the paper studies an interesting problem and proves strong results.   \nThe authors addressed my question regarding the smoothness of the deterministic algorithm. Although I am not sure of the technical details behind their smoothness claim in the rebuttal, it seems correct, and it should not be very difficult to derive.", "rebuttal": "Thank you for your insightful comments and suggestions. We respond to your questions and concerns as follows.\n\n**Q: Smoothness analysis for the proposed algorithms.**\n\nA: 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 \n$$\n\\rho_{\\alpha}(\\eta)=\n\\begin{cases}\n\\alpha & \\eta \\in [0, \\frac{\\alpha - 1}{2(\\alpha + 1)}]\\\\\\\\\n1 + \\frac{4\\eta}{1-2\\eta} & \\eta \\in [\\frac{\\alpha - 1}{2(\\alpha + 1)}, \\frac{1}{\\alpha}-\\frac{1}{2}]\\\\\\\\\n1 + \\frac{2\\alpha \\eta}{\\alpha - 1} & \\eta \\in [\\frac{1}{\\alpha}-\\frac{1}{2}, \\frac{1}{2\\alpha}] \\\\\\\\\n\\end{cases}\n$$\nWhen $\\alpha > \\frac{1+\\sqrt{5}}{2}$, we have the approximation ratio\n$$\n\\rho_{\\alpha}(\\eta)=\n\\begin{cases}\n\\alpha & \\eta \\in [0, \\frac{(\\alpha - 1)^2}{2\\alpha}]\\\\\\\\\n1 + \\frac{2\\alpha\\eta}{\\alpha - 1} & \\eta \\in [ \\frac{(\\alpha - 1)^2}{2\\alpha}, \\frac{1}{2\\alpha}]\\\\\\\\\n\\end{cases}\n$$\nFor 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.\n\nFor 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)$.\n\n**Q: Randomized mechanism without prediction, the gap between upper bound and lower bound is still big. Any intuition about possible directions to narrow it?**\n\nA: 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.\n\n**Q: Missing intuition of $\\alpha$-BIM**\n\nA: 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.\n\n**Q: Minor Typos**\n\nA: We are grateful to the reviewer for pointing out these minor typos. We will correct them in the revised version of our paper."}, {"review_id": "XIbHLl418F", "reviewer": "Reviewer_b8Qg", "summary": "This paper studies the facility location problem, where all agents are located on $[0, 1]$, and a facility is chosen to serve them. The utility of an agent is $1$ minus her distance to the facility. Agents will misreport their locations in order to maximize their utilities, and the goal is to design a strategyproof mechanism with as small envy ratio (ER) as possible, where ER is defined as the ratio between the utilitys of the best-off agent and the worst-off agent.\n\nThis paper first gives a learning-augmented anonymous deterministic mechanism that is $\\alpha$-consistent and $\\frac{\\alpha}{\\alpha - 1}$-robust for a tunable parameter $\\alpha \\in [1, 2]$. Then, it is shown that no anonymous, deterministic, and strategyproof mechanism can strictly improve this consistency-robustness trade-off.\n\nThis paper also presents an anonymous randomized mechanism with an approximation ratio of $1.8944$, which strictly improves the best known approximation ratio of $2$ in prior work for randomized mechanisms without predictions. Then, it gives a learning-augmented anonymous randomized mechanism, whose approximation ratio depends on the bias of the prediction and strictly outperforms the deterministic one.", "questions": "- Is it possible to quantify the approximation ratio of the learning augmented mechanisms in terms of the error of the prediction?\n\n- For randomized mechanisms, ex-ante strategyproofness is considered in the paper. Can similar approximation ratio guarantees be achieved when requiring ex-post strategyproofness, i.e., the mechanism is still strategyproof after fixing the randomness?\n\n- Line 236: It is claimed that the facility will be placed at $1/\\alpha$. However, it seems to me that it can also be placed at a location strictly smaller than $1/\\alpha$ since it is possible that the locations of all phantoms are strictly smaller than $1/\\alpha$. Could you address this or point out if I'm wrong?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "As both facility location and learning-augmented mechanism design have been trendy research topics, the problem considered in this paper is interesting and well-motivated. The results of this paper are complete and non-trivial, and they strictly improve those in prior work. Moreover, this paper is clearly written, and I enjoy reading it.\n\nPersonally, I find the assumption that the metric space is a line quite restricted, although this may be a common assumption in the facility location literature. While the learning-augmented mechanisms given in the paper achieve optimal or improved consistency-robustness guarantees, one complaint I have is that no smoothness guarantee is provided. Namely, it is unclear whether the mechanisms admit an improved approximation ratio compared to robustness when the prediction is only nearly perfect. This is, from my perspective, crucial in this setting since in a continuous metric space, one cannot hope to obtain a perfect prediction, rendering the consistency guarantee less useful.\n\nIn addition, for the randomized learning-augmented mechanism, although it admits desirable expected guarantees, it seems to me that these guarantees have a large variance: even when the prediction is very close to $0$ or $1$, it has a small but not negligible probability to be chosen, in which case the approximation ratio will become very large. In this sense, the deterministic mechanism is arguably more appealing.\n\nDetailed comments:\n- The assumption that the metric space is a line should be stated in the abstract as well.\n- It should be stated in the introduction that the consistency-robustness guarantee of the randomized mechanism is strictly better than that of the deterministic one since the comparison is not straightforward.\n- Line 225-226: The sentence \"This mechanism takes the...\" is hard to parse.\n- Line 264: It is better to be explicit about the dependence on $\\alpha$ in the notation $x'$.\n- Line 266: The notation $\\rho(x)$ is not defined.", "was_revised": true, "final_justification": "My main complaint, which concerns about the smoothness guarantee, has been mostly addressed. Although as Reviewer jQBn pointed out, the proof is not included in the submission so the correctness of the claim is hard to verify, it sounds quite plausible to me, and I believe it's correct. Altogether, I think this submission slightly exceeds the bar of NeurIPS, as reflected in my score raise.", "rebuttal": "Thank you for your insightful comments and suggestions. We respond to your questions and concerns as follows.\n\n**Q: Quantify the approximation ratio in terms of the prediction error.**\n\nA: 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.\n\nFor 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. \nWhen $\\alpha \\leq \\frac{1+\\sqrt{5}}{2}$, we have the approximation ratio \n$$\n\\rho_{\\alpha}(\\eta)=\n\\begin{cases}\n\\alpha & \\eta \\in [0, \\frac{\\alpha - 1}{2(\\alpha + 1)}]\\\\\\\\\n1 + \\frac{4\\eta}{1-2\\eta} & \\eta \\in [\\frac{\\alpha - 1}{2(\\alpha + 1)}, \\frac{1}{\\alpha}-\\frac{1}{2}]\\\\\\\\\n1 + \\frac{2\\alpha \\eta}{\\alpha - 1} & \\eta \\in [\\frac{1}{\\alpha}-\\frac{1}{2}, \\frac{1}{2\\alpha}] \\\\\\\\\n\\end{cases}\n$$\nWhen $\\alpha > \\frac{1+\\sqrt{5}}{2}$, we have the approximation ratio\n$$\n\\rho_{\\alpha}(\\eta)=\n\\begin{cases}\n\\alpha & \\eta \\in [0, \\frac{(\\alpha - 1)^2}{2\\alpha}]\\\\\\\\\n1 + \\frac{2\\alpha\\eta}{\\alpha - 1} & \\eta \\in [ \\frac{(\\alpha - 1)^2}{2\\alpha}, \\frac{1}{2\\alpha}]\\\\\\\\\n\\end{cases}\n$$\nIntuitively, 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.** \n\nFor 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)$.\n\n**Q: Ex-post strategyproofness guarantee for randomized mechanisms.**\n\nA: It is worth noting that our randomized mechanism is constructed from three deterministic constant mechanisms, each of which directly satisfies ex-post strategyproofness.\n\n**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}$.**\n\nA: 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.\n\n**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.**\n\nA: 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.\n\n**Q: Minor comments.**\n\nA: We are grateful to the reviewer for pointing out these minor typos. We will correct them in the revised version of our paper."}, {"review_id": "VAgqDmEr7P", "reviewer": "Reviewer_Lmi3", "summary": "This paper studies a learning-augmented version of the facilitation location mechanism design problem: a variant with the ratio envy ratio objective, which is the max ratio of utilities of any two agents.\n\nFor deterministic mechanisms: they give a $(\\alpha,\\frac{\\alpha}{\\alpha-1})$ consistency-robustness tradeoff.\n\nFor randomized mechanisms:\n\nFor the setting without predictions,\nthey  show an improvement in the upper bound (from $2$ to approximately $1.89$) and in the lower bound (from approximately $1.03$ to approximately $1.11$).\n\nFor the setting with predictions, they propose the BAM randomized mechanism that gets $(-4c^2 + 2, c+2)$-consistency-robustness trade-off for $c \\in [0.25,0.5]$ and $(\\frac{7}{4}, \\frac{7}{4})$ for $c \\in [0,0.25)$, where $c$ is the deviation from the interval midpoint $\\hat{y}$. They investigate other\n potential mechanisms as well.\n\nIn the paper they give 3 mechanisms $BIM$, $LRM$ and $BAM$:\nThe $BIM$ mechanism is essentially a one dimensional predetermined hard-coded bounding-box mechanism, which chooses the prediction if it is inside the box or the closest box endpoint otherwise. The $LRM$ mechanism roughly returns the hard-coded middle point of the assumed segment or a random point in a constant distance from it. The $BAM$ mechanism returns the middle or the prediction according to a coin-flip determined by the distance between the prediction and the middle point.", "questions": "* Why is the restriction to an interval needed in the setting? I am aware that Ding [2020] also have this assumption. Are there any results for the general setting (locations are some real numbers)?\n\n* What is the motivation for defining the problem (again, as Ding [2020]) as a utility maximization problem rather than a cost minimization one? \n    Do the mechanisms fail otherwise?\n\n* Line 224: \"By Moulin's [1980] characterization...\": Could you point to the exact place in Moulin's paper?\n\n* Line 312: Could you add why an explanation for why if $f(x,\\hat{y}) = 0.5$ the envy ratio is the one written?\n\nSmall possible fixes:\n* Line 293: I would replace \"To summarize\" with \"To demonstrate\".\n* Line 310: I would change the order to: Let $\\delta = \\frac{x_2 - x_1}{2}$ rather than the other way around.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n* This work improves the best known lower and upper bounds on the approximation ratio obtained by random strategyproof mechanisms: The upper bound is improved from $2$ to $\\approx 1.89$ and the lower bound is improved from $1.03$ to $\\approx 1.126$.\n\n* The paper provides consistency-robustness tradeoffs for their mechanism.\n    \n* It is interesting that more can be done without using the agent reported locations. \n\n* The prediction settings results demonstrate a reasonable smooth consistency-robustness tradeoff. The randomized algorithm achieves a better trade-off than the deterministic one.\n\n* I did not find any errors in the proofs.\n\nWeaknesses:\n* Usually, the main challenge in mechanism design is to ensure strategyproofness (or some variant of it).\n    In mechanism design with predictions, usually the challenge is to try and make use of the input together with the predictions to come up with a strategy-proof mechanism with a good approximation ratio.\n\n* All given mechanisms, $BIM$, $LRM$ and $BAM$, are trivially strategyproof and anonymous as they do not use the input (reported by the agents) at all, but only the prediction. This reduces the problem from a mechanism design problem to the much simpler problem of approximating the midpoint of a sub-segment of a given known segment, where the sub-segment is not known.\nI would encourage the authors to try and make use of the input reported by the agents as well. If the input does not help, specifying this would also benefit the paper.\n\n* The techniques for achieving the consistency-robustness results are quite standard and rather straightforward: The $\\alpha$-BIM mechanism is very similar to the minimum bounding box mechanism of Agrawal et al. 2022 (except it is even simpler as it does not use the agent locations but only hard-coded box-constraints). The control over the consistency-robustness trade-off boils down to deciding on the box endpoints. The BAM mechanism returns the prediction w.p. $p$ and the \"hard-coded\" segment midpoint otherwise, interpolating between $p=1$ (deterministically choosing the prediction) and $p=0$ (deterministically choosing the midpoint).\n\n* A smaller weakness: Often in algorithms with predictions a confidence parameter is available to choose, roughly translating how much the algorithm/mechanism user trusts the predictions. In BAM there is no confidence parameter. The mechanism user can not control the exact location on the consistency-robustness tradeoff lines presented in Figure 2. We note this is not true for the $\\alpha$-BAM mechanism.", "was_revised": true, "final_justification": "The techniques used to achieve the consistency–robustness results are fairly standard and relatively straightforward.\n\nAll proposed mechanisms—$BIM$, $LRM$, and $BAM$—are trivially strategyproof and anonymous, as they rely solely on the prediction and not on any input reported by the agents. This effectively reduces the problem from a mechanism design setting to the much simpler task of approximating the midpoint of a sub-segment of a known segment, where the sub-segment itself is unknown.\n\nIn my view, this is the paper’s main weakness and the primary reason why my score remains at borderline accept rather than higher.", "rebuttal": "Thank you for your insightful comments and suggestions. We respond to your questions and concerns as follows.\n\n**Q: Why the restriction to an interval needed in the setting? Why define the problem as a utility maximization problem rather than cost minimization?**\n\nA: 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.\n\n**Q: Line 224, \"By Moulin's [1980] characterization...\": Could you point to the exact place in Moulin's paper?**\n\nA: The characterization by Moulin’s [1980] is presented in Proposition 2. We will specify it in the updated version of the paper.\n\n**Q: Line 312, why if $f(x, \\hat{y})=0.5$ the envy ratio is the one written?**\n\nA: 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)}.$$\n\n**Q: No confidence parameter for the BAM mechanism.**\n\nA: 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.\n\n**Q: Why considering agents’ reported locations does not help the mechanism to achieve a better approximation ratio? That is, why constant mechanism?**\n\nA: 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.\n\n**Q: The techniques for achieving the consistency-robustness results are quite standard and rather straightforward, i.e., not too many novel techniques.**\n\nA: We argue that most of our techniques are novel and provide insights for future works along this line of research. \n**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.\n\n**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.\n\n**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. \n\nWe 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.\n\n**Q: Minor Comments.**\n\nA: We are grateful to the reviewer for pointing out these minor typos. We will correct them in the revised version of our paper."}]

Author rebuttal:

Meta-review: The paper studies strategyproof mechanisms for facility location games, focusing on the envy ratio objective, in the learning-augmented framework.  The authors present improved upper and lower bounds in a number of settings.  The reviewers find the results meaningful and nontrivial.  The main concern is the fairly restricted setting, which ultimately is not considered a disqualifying weakness.  We encourage the authors to further improve the paper based on the constructive comments.
Decision: Accept (poster)