Procurement Auctions with Predictions: Improved Frugality for Facility Location
Authors: Eric Balkanski
Nicholas DeFilippis
Vasilis Gkatzelis
Xizhi Tan
Venue: NeurIPS 2025 poster ()
Keywords: Algorithm with predictions
Uncapacited facility locations
mechanism design
Primary area: theory

Abstract: We study the problem of designing procurement auctions for the strategic uncapacitated facility location problem: a company needs to procure a set of facility locations in order to serve its customers and each facility location is owned by a strategic agent. Each owner has a private cost for providing access to their facility (e.g., renting it or selling it to the company) and needs to be compensated accordingly. The goal is to design truthful auctions that decide which facilities the company should procure and how much to pay the corresponding owners, aiming to minimize the total cost, i.e., the monetary cost paid to the owners and the connection cost suffered by the customers (their distance to the nearest facility). We evaluate the performance of these auctions using the \emph{frugality ratio}.


We first analyze the performance of the classic VCG auction in this context and prove that its frugality ratio is exactly $3$. We then leverage the learning-augmented framework and design auctions that are augmented with predictions regarding the owners' private costs. Specifically, we propose a family of learning-augmented auctions that achieve significant payment reductions when the predictions are accurate, leading to much better frugality ratios. At the same time, we demonstrate that these auctions remain robust even if the predictions are arbitrarily inaccurate, and maintain reasonable frugality ratios even under adversarially chosen predictions. We finally provide a family of ``error-tolerant'' auctions that maintain improved frugality ratios even if the predictions are only approximately accurate, and we provide upper bounds on their frugality ratio as a function of the prediction error.

Procurement Auctions with Predictions: Improved Frugality for Facility Location
Eric Balkanski
Nicholas DeFilippis New York University mad9961@nyus edu
Columbia University eb32248columbia. edu
Vasilis Gkatzelis Drexel University, Archimedes, Athena R.C., Greece giatz@drexel.eem
Xizhi Tan"
Stanford University xizhi@stanford. edu
Abstract
We study the problem of designing procurement auctions for the strategic unca- pacitated facility location problem: a company needs to procure a of facility locations in order to serve its customers and each facility location is owned by strategic agent. Each owner has a private cost for providing access their fa- cility (e.g., renting it or selling it to the company) and needs to be compensated accordingly. The goal is design truthful auctions that decide which facilities the company should procure and how much to pay the corresponding owners, aiming to minimize the total cost, i... the monetary cost paid the owners and the connection cost suffered by the customers (their distance to the nearest facility). We evaluate the performance these auctions using the frugality ratio.
We first analyze the performance of the classic VCG auction in this context and prove that its frugality ratio is exactly 3. We then leverage the learning-augee augmented framework and design auctions that are augmented with predictions regarding the owners' private costs. Specifically, we propose family of learning saaming-augmenter auctions that achieve significant payment reductions when the predictions are accurate, leading much better frugality ratios. At the same time, demonstrate that these auctions remain robust even if the predictions are arbitrarily inaccurate, and maintain reasonable frugality ratios even under adversarially chosen predictions. We finally provide a family of "error-tolerant" auctions that maintain improved frugality ratios if the predictions are only approximately accurate, and we provide upper bounds on their frugality ratio as a function of the prediction error.
Introduction
When government agencies, retail chains, or banking institutions need to open new facilities or branches to better serve their customers, they face challenging optimization problem: they want customers to be close as possible to a facility, but opening new facilities can be very costly, and the cost can vary significantly by location. Deciding which locations to open therefore requires balancing the customers' connection costs (their distance to the nearest facility) against the facilities' opening costs. This optimization problem known as the uncapacitated facility location (UFL) problem and it has received lot of attention in prior work (e.g.. [14, 21, 29, 36, 36, 40, 471).
However, the vast majority of this prior work assumes that the designer has full information regarding both the connection and the opening costs, which is often unrealistic in practice. For example, each location may be owned by different strategic agent who would need to be appropriately compensated
This work done while the author PhD student Drexel University
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

for the agency to open facility there. Negotiating this compensation (i.e., the opening cost) is itself strategic problem: the owner wishes maximize it, while the agency wishes to minimize it. This additional obstacle is captured by the strategic UFL. problem, where the opening cost of each location private information held by the agent who own [3. 19, 35, 48].
From the agency's 's perspective, rather than negotiating compensation separately with each owner, a more effective approach is to run procurement auction. This encourages competition, leading to more efficient and cost-effective outcomes, which is one primary reason why the US government routinely uses procurement auctions [44]. To prevent manipulation, prior work on strategic UFL has focused on designing truthful auctions that incentivize agents to reveal their true opening costs [3, 19, 35, 48). Our work continues in this direction.
Evaluating the performance of a procurement auction is complicated by the lack of a suitable benchmark. If there is little competition, the agency may have to pay higher compensation, whereas greater competition can reduce costs. The frugality literature [4, 48) addresses this by proposing the cost of the "second-best" solution as a benchmark (see Section 2). When this second-best cost is much higher than the optimum, the instance resembles a monopoly, and the agency must pay more. Conversely, if the second-best is close the optimum, well-designed auction can leverage competition for better outcomes. The frugality ratio quantifies how closely the auction's cost approaches this benchmark, and our main technical results are new frugality ratio bounds.
Despite its appeal, most prior work in frugal mechanism design is restricted to the adversarial framework, analyzing the auctions' performance under worst-case instances and assuming they have no information regarding the private costs. While this provides robust guarantees, it can be overly pessimistic, especially in practice, where agencies often have access predictions regarding opening costs, derived from historical data, expert estimates, or data-driven models. This naturally raises the question: can we design mechanisms that exploit such predictions to improve frugality, while still remaining robust if the predictions turn out to be inaccurate?
Motivated by this, our work leverages the learning- augginnnnd framework, which has recently spurred significant research on "algorithms with predictions" " [37, 42], and more recently, on the design of truthful auctions and mechanisms augmented with predictions [1, 49]. In this framework, the designer is given an unreliable prediction (potentially from machine learning or historical data), and the goal is achieve improved guarantees when the prediction is accurate (consistency), while maintaining strong guarantees even when the prediction is arbitrarily inaccurate (robustness).
1.1 Our Results
Our first result is a tight analysis of the frugality ratio of the classic truthful VCG auction (without predictions) for the strategic UFL problem. Prior to this result, the best known upper bound was 4 by Talwar [48], and there were known lower bounds. Using tighter analysis and matching lower bound, we prove that its frugality ratio is exactly 3.
Then, rather than assuming that the auction has no information regarding the private opening cost og at each location f, we consider learning-aueen augmented auctions that are provided with a prediction óg regarding this cost. Crucially, this prediction is unreliable and can be arbitrarily inaccurate.
Our second result a new truthful procurement auction that takes parameter e (0, 2] as input and guarantees frugality ratio of 1 + whenever the prediction is accurate (the consisiency guarantee), while simultaneously guaranteeing frugality ratio of at most max (5, + 2). irrespective of how inaccurate the prediction may be (the robusiness guarantee). Note that choosing a small constant allows us to guarantee a near-optimal frugality (arbitrarily close to 1) when the prediction is accurate, while simultancously guaranteeing constant frugality even for adversarially chosen predictions. To achieve this guarantee, our sarning-auggment scaled using the predictions. Specifically, if the opening cost reported by the owner at some location l is exceeds the prediction òg, then it is scaled up even higher, reducing their chance of being selected. When the prediction is accurate, this limits the agents' ability to manipulate, leading to reduced costs.
auction uses the VCG mechanism on input that is
For our third result, we design a learning-augment first define the prediction error as = maxzer. max (ōz/ fe/ oz/ oz/or), i.e., the largest ratio between the predicted opening cost and the actual opening cost. Our auction is then provided with an error tolerance parameter, À >> 1, input (as well as the parameter E (0, 2)), and as long as the error 77 of
procurement auction that "error tolerant." We

---

the prediction is at most X. it guarantees a frugality ratio of 1y(1 + X) + 2c. Even if the error exceeds the error tolerance threshold, i.e., 7) >> X, the frugality ratio is at most max 2x* + 3X², 3 - 3
1.2 Related Work
The strategic UFL problem was first studied by Archer and Tardos [3], who analyzed the structure of truthful mechanisms for this problem. The frugality of truthful mechanisms for the strategic UFL problem was studied by Talwar [48], who showed that the VCG auction has a frugality ratio of at most 4. Chen al. [19] considered different social cost objectives for the special case where the facility locations coincide with the locations of the agents (i.e., each agent has a "dual-role" as a customer facility operator). Chen et al. [19] and Li et al. [35] also considered the budget-feasible version of this problem, where the overall payment cannot exceed budget. For related work on the non-strategic version of the UFL problem, see Appendix A.
The study of frugal mechanism design is motivated by the challenge of minimizing unnecessary overpayment while preserving truthfulness in procurement auctions and combinatorial team selection problems. This perspective has been applied across a variety of classic optimization settings. In network design, Archer and Tardos [4] and Talwar [48] initiated the investigation for path auctions, demonstrating that VCG mechanisms can incur large overpayments and establishing tight frugality bounds under the frugal solution benchmark. For coverage problems such as vertex cover and set cover, Elkind et al. [24] and subsequent works developed truthful mechanisms with frugality ratios that depend on structural parameters like graph degree or spectral properties, and also provided matching lower bounds in several cases. Frugality in k-flow and cut problems has also been explored, with mechanisms achieving constant-competitive frugality ratios relative to various benchmarks, including both disjoint-alterman alternative and equilibrium- based definitions [17, 33, 34). In some settings, such as matroid and spanning tree auctions, VCG mechanisms are provably frugal, achieving optimal or near-optimal frugality ratios [33, 48).
The design of Marning-augmentte
mechanisms for settings involving strategic agents was initiated by Agrawal et al. [1] and Xu and Lu [49]. This line of work spans strategic facility location [1, 8, 12, 18. 31, 46, 49], strategic scheduling [7. 20, 49], auction design [9, 15, 16. 28, 38, 41, 49], bicriteria mechanism design for welfare and revenue trade-offss [6], graph problems with private input [22], distortion [13, 25], and equilibrium analysis [27. 32). The work most closely related this paper is [49], which studied frugal mechanism design with predictions in the context of path auctions. See Appendix A for more extensive discussion on the line of work on algorithms with predictions.
2 Preliminaries
In the Uncapacitated Facility Location (UFL) problem, there is set U of users and set L of facilities. Each facility f has an opening cost og. Each user E and facility & E L have connection cost d(u,, f). The connection costs are assumed to form a metric space, i.e., d(x, y) is defined for any x, E U L and satisfies d(x,, x) = O, d(x,, v) 2 0 (non-negativity), d(x;, ((xx.)) y) = d(y, x) (symmetry), and d(x z) < d(æ,, y) + d(y, =) (triangle inequality) for all x. y. = E U U L. The cost of connecting a user u E U to a set of facilities C L is minees d(u, E). i.e., it is its distance to its closest facility in S. Given facilities S L, say that user is assigned to facility e if & arg minges d(u, E).
The total connection cost incurred by a set of facilities S C L is
d(U,
Σ min d(u, E), EES
NeU
and its total cost c(S) is the sum of its opening cost and total connection cost, i.e.,
c(S)
Σ oo + d(U,S). EES
The goal is to open set of facilities S C L that minimizes the total cost. Given U, d, and (ot)EEL. the optimal facility set is OPT(U, o, d) = arg minss c(S).
Strategic UFL. In the strategic version of the UFL problem, each facility E L is owned by strategic agent and its opening cost oR is private (the connection costs are public information). An auction M(U b, d) for strategic UFL takes input the set of users U and the connection costs d,
3

---

and it asks the owner of each location & E L to report an opening cost by (which we refer to bid), leading to a bid vector (b.) For simplicity, we write MMbb and OPT(o) when and d are clear from context. We also use b to refer to the vector of all bids excluding by. We say that a facility misreports its reported cost is not true cost, i.e., # og- The output (S. p) of
an auction consists of set S S I. of facilities to open and payment to each facility & E S for opening. The utility of a facility from output (S, p)
Pt oe
i S
ue(S, p)
otherwise
An auction is truthfful it is a dominant strategy for every facility i to report its true opening cost, i.., by og, irrespective of what the other facilities report. That is, for every or, by, b b-e, U,d,
ue(Mior,,rr b-t)) 2 we(M((E,, b-t))-
An auction M for UFL is monotone if for any facility E L and any bid profile b of the other facilities, the probability that é E S, where S is the facilities chosen by MMbr, b-z), z). is non-increasing in its bid by. In angge-parameter environments such as strategic UFL., Myerson's Lemma characterizes truthful auctions:
Lemma 2.1 (Myerson's Lemma). An auction is truthful if and only if it is monotone. For any monotone auction, there exists a unique payment rule that ensures truthfulness, which can be computed explicitly.
Frugality and Efficiency. The total cost incurred by an auction for outputting (S,p) is the sum of the payments and the total connection cost, i.e.,
p(S, p)
Σ pr + d(U,
EES
The frugal facility set is the second- best solution, i.e.,
o( arg min SCLAOPT(UOO..)
c(S).
The efficiency of an auction is evaluated by its frugality ratio, which is the worst-case ratio between its total cost and the cost of the frugal solution:
frugality(M) = max p(M(U,,, o.))
U.o.d cl (F
Cearning-Augmentt Framework. In the cammming--ggmeeeedd setting, the auction is given predic- tions about the opening costs We evaluate the performance of M using two metrics.
Consistency:
The frugality ratio when the predictions are accurate (ō = o): p(M(U, o, 6 d,, max U.o.d c(F(U.o,
co
Robustness:
The frugality ratio when the predictions can be arbitrarily wrong:
(,,(U,,,d,)) c(F(U,o))
(M
max U,o,d.6
Tight Frugality Bounds for the -ickrey- Auction
Our first main result establishes improved frugality ratio of 3 for the VCG auction, which start by describing in the context of the strategic UFL problem.
The VCG auction. Given instance (U, o. d) of UFL, the set of facilities opened by the VCG auction is the optimal facility set OPT(o). The VCG payment, also called threshold payment, to each opened facility e OPT(o) is
Pe c(PPT(x0, c()))

---

i.e., it is the difference between the total cost of the optimal solution when facility é is infeasible (op 2o) and when is free (o, = 0). This payment can be alternatively defined as
Pt max b 2 0 é OPT(6,
i.., the largest bid that facility l can declare and remain in the optimal set OPT selected by VCG. Theorem 3.1. The frugality ratio of the VCG auction for the metric uncapacitated fuciliy location problem is exactly 3.
We first argue an upper bound of 3. At a high level, the proof bounds the total cost incurred by the VCG auction by (1) bounding the payments by twice the total cost of the frugal solution and (2) observing that the total connection cost of the optimal solution is bounded by its own total cost, which is in turn bounded by the total cost of the frugal solution. Combining these two facts immediately yields 3-approximation. The payment bound is achieved by "rerouting" argument: for each facility in the optimal set, we show how to reassign its users to other facilities, either within the optimal set itself or to those in the frugal solution, thereby upper-bounding its threshold payment by the corresponding rerouting cost.
Proof of Theorem 3.1. Let OPT and F be the optimal and frugal solutions. We denote by Ue C U the users assigned to facility according to OPT. We first note that for any set of facilities O₂ S L {E) that does not contain facility l, we must have
Pe
Σ d(u,f) NEU:
S
Σ os
E min d(u, f'),
(1)
PED
FEO,
REU;
otherwise Og would have a smaller total cost than OPT when facility é reports opening cost pt, which would imply pe > max 2 0: (PT(b,o-4) and would contradict the alternative definition of VCG.
The central part of the proof consists of defining some alternative solution O₂ and to reassign and reroute the users in Ug to facilities in O₂ to bound Enev, min d(u, f'). To define O, and this reassignment, we first need to introduce some notation. For each pair (E E OPT, f E F), we let in the optimal solution OPT and to f in the frugal solution
U S U be the set of users assigned F. For each f E F, let OPT, = {E E OPT |Wr.l > 0} and x(({) be the ranking of E OPT, among all other facilliies in , in terms of the size of |Ve,yl, where ties are broken arbitrarily but consistently. This definition implies that 10) E 0PT, is the facility with the jth smallest non-negative 5 and we thus have 0 < 102, *ay) S ... S IU
20 A(IOPT, D.gl
We define the alternate solution be O2 OPT u E F (f( = |0PT, In this solution, facility is removed from OPT and the facilities f E F such that [Ve,rl is largest among { (Ue are added. We then define mapping I OPT, + OPT, U{} that reassigns users in Ue,f that are assigned to facility l according to OPT to a new facility in OPT UL}}. This reassignment
defined as
o7 (x)(0))
if (() < 0PT
(f(
if xf) = |OTT,
In words, (E) maps facility l the facility ranked immediately after with respect to f: if is ranked last, then T (f) = Since UJ-EOPT, Ue, = Ut, we have that
Σ NEU
min d(u, S'eo
Σ f:PEOPT,
min d(Ue,, Σ d(Ue,,,Ty()).
ree:
F:FEOPT,
Next, if (c) < |OPTyl, then [Ue,r S (0)) by the definition of T.. Thus, combined with the triangle inequality, we get that if xf(()) < / I, then
S Σ d(Ur.,, +
+ (11)(
(3)
fiCEOPT,
Informally, this last inequality corresponds to rerouting the users in U2,5 to (f) by going through f and then (0. This rerouting is the key component of this proof, see Figure for an illustration.
5

---

Facility L
Facility T (t)
Ut.
Uni(ON
Facility f
Figure 1: Illustration of how users in U are rerouted to facility x y Each color (and line pattern) denotes the path taken by distinct user u E Ut.f- The total connection-cost along each set of colored edges gives an upper bound on the payment to facility for serving that subset of users.
We obtain that
((OPT)
Σ
Pt +
E d(u,e)
by def. of p
ŁEOPT
uEUr
of
Σ
min d(u, f*)
by (1)
P'eOc
БCOPT
of Σ d(Ues,
by (2)
ЕDOPT
(1=y(()=[
1:EEOPT
Σ JEF
of + Σ a(Ur,,,=((())
RDOPT
1OPT , 1-1
Σ
of + (U,;
Σ (U ==1
+
SEF
Of + U (U27"(OPTT))))))))
SEF
Σ
(d(U (d(U,, (., d(f. ,
+ d(U d(Un))((H))) (j + 1)))
by (3)
Σ SEF
Of + Σ
(d(Ue,,))) + d(F.Ue,)) [(U,,)
BEUPT,
Eo oof +2 Σ Σ d(U....))
Σ E EEDP F:REOPT,
Σ
+d(Ue.,,
fEr
JEF tEOPT,
< c(F) + c(OPT)
We show that this upper bound of 3 is tight for VCG by providing a simple tree-metric instance. Due to space limitations, we defer its analysis to Appendix B.
D

---

4 Leaniing-Aumeented Frugal Auction
We now consider the strategic UFL, problem within the auction has access to potentially inaccurate predictions about the true opening costs of the facilities. Specifically, for each facility& E L, a prediction Og is provided for its true opening cost og. Our objective is to leverage this unreliable information to design truthful auctions that minimize the frugality ratio while remaining robust against inaccurate predictions.
framework, where the
To achieve this, we propose PREDICTEDLIMITS, described in Auction 1. This auction first identifies the optimal solution based the predicted costs, denoted by OPT. then modifies the cost function by scaling the actual opening costs of facilities in OPT when their true costs exceed the predicted opening costs. Finally, the auction selects the solution that minimizes this scaled cost function. We note that,
Auction I: PREDICTEDLIMITS
Input: Set of clients U. set of facilities L, parameter predicted opening costs òr for all & E L Output: Selected facility subset S and threshold payments for each facility & E 5"
Compute DPT t arg minsgr (d(U, S) EiEs 0z); Define the modified cost function for any subset S C
oE if OPT and or > o
de(S)
O2,
otherwise
Compute:
S" + arg min d(u,))+ +
CES
return S* and threshold payments for each S"
achieve the claimed results, our auction only needs access to the membership of the predicted optimal solution OPT and to the opening costs of those facilities. We show that PREDICTEDLIMITS can achieve near-optimal consistency (arbitrarily close while still maintaining competitive robustness.
Theorem 4.1. Given any E [0,2] as inpul, PREDICTEDLIMITS is truthful, (1 + -cconsssstnn, and max (5, 3 + 2) -robust.
At first glance, this auction may seem counterintuitive and differs from existing mechanisms that also use predictions to scale costs (c.g, [7, 49]). Instead of scaling down the opening costs of facilities in the predicted optimal solution, set that would normally be favored for minimizing the overall social cost, the auction scales these costs upwards, making the predicted optimal solution less appealing. The primary rationale for this upward scaling restrict the potential overbidding the bidder can claim while remaining in the optimal solution, which leads to a high threshold price. By amplifying any over-reported opening costs over the predicted ones, the auction gains tighter control over facility payments, which can lead to lower frugality ratio when the predictions are accurate.
Importantly, the scaling applied by auction is solution-dependent rather than deeeedt--eeeedent. Specifically, the opening cost scaling is activated only when evaluating the predicted optimal solution OPT as complete set. For any other subset, the opening costs of individual facilities remain unscaled. This distinction is crucial for our robustness analysis, as it ensures that the adverse effects of inaccurate predictions confined to the evaluation of the single predicted optimal solution, leaving alternative solutions unaffected. We defer the truthfulness proof to Appendix C. We first provide the consistency analysis of Auction PREdICTED LIMITS. We then provide the robustness guarantee of the auction, which holds regardless of the quality of the predictions.
Lemma 4.2. Given any E [0, 2] as impul, PREDICTEDLIMITS achieves a consistency of +
Proof. Recall that consistency analysis assumes the predictions are correct, i.e., ôN facilities L E L. By the definition of Auction 1, if predictions are accurate, the condition oN > for l E OPT (which equals OPT here) is never met. Therefore, no costs are scaled, and the auction selects the true optimal solution, i.e., S = OPT. We adopt the same definitions of OPT, and x ( as the analysis of VCG (proof of Theorem 3.1).
for all
7

---

We now provide an upper bound for the payment Pe to the agent controlling facility E OPT. Similarly VCG, we will upper-boume bound the payment by considering the cost of rerouting. The difference that when the reported bid exceeds òz, the scaling would apply. Formally, for any set of facilities Oe C L, (e) not containing
2 Pt
Σ d(u,)) S NEU?
Σ
of
E min d(u,f) NEUE
(4)
f'E
O'EOROPP
Note that the scaling affects only the opening costs of the facilities in OPT. Hence the right-hand side of (4) remains unchanged for all (f, f) pairs relative to the VCG analysis, as it represents cost of alternative solutions not involving f's potentially scaled cost. Therefore, the bounds from Equations (2) and (3) continue to hold. Following the same steps as in the VCG proof (Theorem 3.1), we obtain:
d(U..: )UUAS)))
Σ
Σ
dun
Σ
os +2
E
E E d(Ue,,))) REOPT I:
Pt +
ÉDOPT
dEU,
/EF
/EF LEOPT,
2
Σ PE
S
Eo, of +
Σ d(Ue),))
Σ pe Se
SЕOPT
JEF
JEP EEOPT,
ビCOPT
Together with the fact that the connection cost of the optimal solution is at most c(F), we conclude that the total auction cost EtcOpt Pt + d(U, OPT) most (1 +e c(F).
We now move on to the robustness analysis. We begin with the simpler case in which the auction still outputs the optimal solution the instance, i.e., OPT, All missing proofs the section can be found in Appendix C.2.
Lemma 4.3. Given any instance (U, o, d) and any S 2, let OPT and F be the optimal solution and frugal solution, respectively. If auction I outputs S OPT, then we have:
Σ pe d(U,)*) (1+2 EES
2
Σ
or + d(U,F)
The proof is deferred to Appendix C.2.1. We now address the case where scaling alters the output set, i.c., S* * OPT. This case particularly challenging because S may contain facilities belonging to both the frugal solution and the optimal solution, making it difficult bound the payment. To tackle this, we need a different accounting argument than the ones used for the VCG and consistency analyses. Specifically,
will analyze payments for facilities in the output solution S differently, based on whether they are part of the frugal solution F. We begin by establishing bound for payments fon-frugal facilities in S (i.e., those in S \ F)) with the following lemma.
Lemma 4.4. Given any instance (U, o, d), and any S 2, let OPT and F be the optimal solution and frugal solution, respectively. Let S* + OPT be the output of Auction 1, and let S F. Then:
Σ Pe Σ ot Fd. EES
The proof is deferred Appendix C.2.2. Then, we bound the payment the output solution that is also part of the frugal solution.
Lemma 4.5, Given any instance (U, o, d), and any e S 2, let OPT and F be the optimal solution and frugal solution, respectively. Let S" + OPT be the output of Auction and S S* F. Then:
Σ pt max (.2)) FEST
Σ of
Fot+d(1s d(U,F)
Proof. The approach considers rerouting users currently assigned to a facility f E S! back to their corresponding facility & the true optimal solution OPT. This facility j E OPT might not be included in the output set S", and if OPT OPT, its opening cost of might be effectively scaled

---

upwards to of in the auction's 's payment calculation if it was under under-predicted (or > oτ). The analysis mirrors the VCG structure but with the roles of the chosen solution (51) and the alternative (OPT)
flipped. Define Ue, U. and Tf( as in the proof of Theorem 3.1, replacing OPT with St. Define / = { S
5 0}.
Case The optimal facility & 55 By the same rerouting argument as VCG, inequalites (2) and (3) hold with OPT replaced by 5 and the opening cost replaced by the scaled opening cost.
Case 2: The optimal facility e E S" Here, users Uz.e can be rerouted directly to e within the output set S so the cost associated with rerouting users U, denoted obeys
Σ d(u, & d(U
PE
DEU
This bound is better than inequalities (2) and (3) from Case 1.
Summing all agents E 5t and assuming the worst-case where every cost gets scaled get:
Pe + Σ d(u,))
-
Σ
PE P Σ d(u,e) Net!e
RES!
NEVE
EEOP FES!
)
Σ EOPP
Of +2 Σ d(Ue,)))) dU
+E
E
d(Ue.),))
EESt
ZEOPT f:tEOPTy
Σ
Of +2 2 Σ Σ d(UE.,)))
<
LEST
EEOPT
EEOP JES!
Pe S max (2 (2.2 c(F) max (2:2)
Σ o0 D LEEF
By combining Lemma 4.3, Lemma 4.4, and Lemma 4.5, get the robustness of Auction PREDICT- EDLIMITS. The proof is deferred to Appendix C.2.3. Lemma 4.6. Given any E [0,2] as input, PREDICTEDLIMITS achieves a robustness of
max (5, 3 + 2).
The Error-Tolerant Scaled VCG
Auction PREDICTEDLIMIT achieves (1 + e)-consistency in its frugality ratio when provided with perfect predictions of opening costs, and maintains max (5, ro-buuustessss guarantee in adver- sarial scenarios. These existing bounds, however, capture only the extremes prediction quality. In this section, we extend the auction from the previous section to achieve an improved frugality ratio, only for accurate predictions but also for approximately accurate predictions, thereby offering more granular performance characterization.
We denote the prediction error as 17 2 where 7j defined as the largest ratio between the predicted opening cost and the actual opening cost, i.c.,
Ōe O2 dz
max max EEL
The auction, ERRORTOLERANT. formally defined in Auction 2, extends PREDICTEDLIMITS by incorporating error-tolerance parameter À 0. Recall that the original auction selects the predicted-optimal facility set OėT and, whenever a facility's 's true opening cost exceeds its prediction, inflates that cost by factor of 2/c; otherwise. leaves opening costs unchanged.
designed to preserve this behavior not only under exact predictions but also when predictions are accurate up to a factor of X, with one key enhancement. To ensure that OėT remains the chosen set under low prediction error, we replace the overscaling threshold òr with À ór. In addition, if every facility in OPT reports true cost below this new threshold, we apply uniform
ERRORTOLEERNE

---

Auction 2: ERRORTOLERANT
Input: Clients U. facilities L, predicted oR for all & parameter S 2, error-tolerance À Output: Chosen facilities S" and threshold payments each / e S*
OPT < arg minsgr. (d( + Eees 6r);
ve E OPT, or S Xoς then
x2 [(U.S) + EES
Σ oc).
S OPT,
Define (x
d(U,S) + Σ
ol,
otherwise.
ees
else
1 o2,
DPT and oe > Aoe;
Define each and $ d{(
o2:
otherwise,
and (x d(U, S)
+
Σ
oe(S))
EES
+ min cx (S). sgr.
return S" and threshold payments for each E S"
down-scaling to the entire solution cost (both opening and connection costs). This extra adjustment guarantees that, when the prediction error is at most X, the auction outputs OPT. Aside from these two modifications, ERRORTOLERANT follows PREDICTEDLIMITS exactly. achieves an approximation guarantee of (1 + X) + 2. when 1) S X, and maintains frugality bound of max 3
for arbitrary error 1).
Theorem 5.1. Auction ERRORTOLERANT is truthful, and given parameters E (0, 2] and À > 1, it
achieves the following frugality ratio, where n is the error of the prediction:
711 + A) 2e,
is S X
max 22a 322,
?
Due to space limitations, we defer the analysis Appendix E.
6 Conclusion and Open Problems
In this work, we studied the design of frugal procurement auctions for the strategic uncapacitated facility location problem. We first established tight frugality ratio of 3 for the classic VCG auction. Prior to our work, the best known upper bound for VCG was 4 [48] and there was no known lower bound. We then considered the problem in the provided with predictions regarding the costs of the facilities. We designed a novel truthful auction that achieves frugality ratio of + when the predictions are accurate, while maintaining constant- faattont-facto robustness guarantee even when the predictions are arbitrarily wrong.
framework where the auction
Although the focus of our work is on the information-theoreti limitations of truthful auctions, note that our proposed mechanisms can formulated as integer programs (IPs). Please see Appendix for the IP implementation.
Our work leaves several exciting directions open. In the classic setting, while we show that VCG's frugality ratio is exactly 3, the optimal frugality ratio achievable by a truthful auction remains unknown. An important question is whether VCG is optimal, if another design can achieve better frugality ratio. Thus, establishing a tight lower bound for this problem is a key next setting, an open problem to determine the optimal trade-off
step. In the between consistency and robustness, thereby characterizing the Pareto-optimal frontier. Furthermore, exploring more nuanced definitions of prediction error beyond magnitude- such as the number of mispredictions or the recent "mostly and approximately correct" (MAC) framework [12]-is promising direction. Analyzing mechanisms under such models could lead to auctions that degrade more gracefully given imperfect, yet informative, predictions.
10

---

Acknowledgments and Disclosure of Funding
Eric Balkanski was supported by NSF grants CCF-2210501 and IIS-2147361. Nicholas DeFilippis was supported by NSF Graduate Research Fellowship under Grant No. DGE-2039655, Vasilis Gkatzelis and Xizhi Tan were supported by NSF CAREER award CCF-2047907 and NSF grant CCF-2210502, Any opinion, findings, and conclusions recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.
References
[1] P. Agrawal, F. Balkanski, V. Gkatzelis, T. Ou, and X. Tan. Learning-augmenttr mechanism design: Leveraging predictions for facility location. Math. Oper. Res., 4964)2266-2251,, 2024. doi: 10. (011287/MMOR.20022.000
URL https: /twii//oiio/o org 10. 1287 /oorr 2022. 0225.
[2] A. Antoniadis, T. Gouleakis, P. Kleer, and P. Kolev. Secretary and online matching problems with machine learned advice. Discret. Optim., 48(Part 2):100778, 2023. 20233.
[3] A. Archer and É. Tardos. Truthful mechanisms for one-parameter agents. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 482-491. IEEE Computer Society, 2001.
[4] A. Archer and É. Tardos. Frugal path mechanisms. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 991-999. SIAM, 2002.
[5] Y. Azar, D. Panigrahi, and Touitou. Online graph algorithms with predictions. Proceedings of the Thirty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2022.
[6] M.-F. Balcan, S. Prasad, and T. Sandholm. Bicriteria multidimensional mechanism design with side information. In Proceedings of the 37th International Conference Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2024. Curran Associates Inc.
[7] E. Balkanski, V. Gkatzelis, and X. Tan. Strategyproof scheduling with predictions. In Y. T. Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, volume 251 of LIPles, pages 11:1-11:22. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2023.
[8] E. Balkanski, Gkatzelis, and G. Shahkarami. Randomized strategic facility location with predictions. In A. Globersons, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. M. Tomezak, and C. Zhang, editors, Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024. NeurIPS 2024, Vancouver. BC, Canada, December 10 15, 2024, 2024.
[9] E. Balkanski, V. Gkatzelis, X. Tan, and Zhu. Online mechanism design with predictions. In D. Bergemann, R. Kleinberg, and D. Sabán, editors, Proceedings of the 25th ACM Conference on Economics and Computation, EC 2024, New Haven, CT, USA, July 8-11, 2024, page 1184. ACM, 2024.
[10] É. Bamas, A. Maggiori, and O. Svensson. The primal-dual method for learning augmented algorithms. In Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[11] S. Banerjee, V. Gkatzelis, A. Gorokh, and B. Jin. Online nash social welfare maximization with predictions. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022. SIAM, 2022.
[12] Z. Barak, A. Gupta, and I. Talgam-Cohen. Mac advice for facility location mechanism design. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang, editors, Advances Neural Information Processing Systems, volume 37, pages 129564-1222 -296444 Curran Associates, Inc., 2024.

---

[13] B. Berger, M. Feldman, V. Gkatzelis, and X. Tan. soaming-augmented metric distortion via (p. q)-veto core. D. Bergemann, R. Kleinberg, and D. Sabán, editors, Proceedings of the 25th ACM Conference on Economics and Computation, EC 2024, New Haven, CT, USA, July 8-1 1-11, 2024, page 984. ACM, 2024.
[14] J. Byrka and K. I. Aardal. An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM J. Comput. 2966)2212-22311, 2010. doi: 10.1 10.1137/070708901. URL hwwphhttss::..oooooo 10. 1137/07707088111
[15] I. Caragiannis and G. Kalantzis. Randomized learnin--augmetted auctions with revenue guarantees. arXiv preprint 1rXiv:2401.13384, 2024.
[16] I. Caragiannis and G. Kalantzis. Mechanisms for selling an item among strategic bidder and profiled agent. arXiv preprint arXiv:2502.12313, 2025.
[17] N. Chen, E. Elkind, N. Gravin, and S. Petrov. Frugal mechanism design via spectral techniques. In 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 755-764. IEEE, 2010.
[18] Q. Chen, N. Gravin, and S. Im. Strategic facility location via predictions. arXiv preprint arXiv:2410.07497, 2024.
[19] X. Chen, M. Li, C. Wang, C. Wang, M. Zhang, and Y. Zhao. Mechanisms for fuai-itle- location games: Truthfulness and approximability. Theor. Comput. Sci., 932:69-83, 2022.
[20] G. Christodoulou, A. Sgouritsa, and I. Vlachos. Mechanism design augmented with output advice. Advances in Neural Information Processing Systems, 37:41934 2024.
[21] A. Chudak and D. B. Shmoys. Improved approximation algorithms for the uncapacitated facil- ity location problem. SIAM Comput., 33(1):1-25, 2003, doi: 10.1137/50007559970445577774 URL https://doi. org/ httg//...137//00000 01011177//00077337770057774
[22] R. Colini-Baldeschi, Klumper, G. Schäfer, and A. Tsikiridis. To trust or not trust: Assignment mechanisms with predictions in the private graph model. In Proceedings of the 25th ACM Conference on Economics and Computation, pages 1134-1154, 2024.
[23] Dütting, S. Lattanzi, R. Paes Leme, and S. Vassilvitskii. Secretaries with advice. Mathematics of Operations Research, 49(2):856-879, 2024. doi: 10. 10.12877/moor 1384. URL https: / //doi. org/ 11tgg/10.000 1287 / 2023 1384.
[24] E. Elkind, L. A. Goldberg, and P. Goldberg. Frugality ratios and improved truthful mechanisms for vertex cover auctions. Proceedings of the 8th ACM Conference on Electronic Commerce (EC), pages 336-345, 2007.
[25] A. Filos-Ratsikas, G. Kalantzis, and A. A. Voudouris. Utilitarian distortion with predic- tions. In Proceedings of the 26th ACM Conference Economics and Computation, EC '25, page 254-271, New York, NY, USA, 2025. Association for Computing Machinery. ISBN 9798400719431.
[26] K. Fujii and Y. Yoshida. The secretary problem with predictions. Mathematics of Operations Research, 49(2): 1241-1222 2024. doi: 10. 10.11877/mor.222220003. URL https://doi.org 10. 10r7/moor
[27] V. Gkatzelis, K. Kollias, A. Sgouritsa, and X. Tan. Improved price of anarchy via predictions. In Proceedings of the 23rd ACM Conference on Economics and Compulation, pages 529-557, 2022.
[28] V. Gkatzelis, D. Schoepflin, and X. Tan. Clock auctions augmented with unreliable advice. In Y. Azar and D. Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 2629-28 2255. SIAM, 2025.
12

---

[29] S. Guha and S. Khuller.
Greedy strikes back: Improved facility location algorithms. Journal of Algorithms, 31(1):228-24) 248, 1999. ISSN 0196-6774. doi: https://doi.or/// 10. 1006/jagm.19%% 1998.0993. URI. wwt.h:tsp/t/tttteee /ttp//...cenneerretttttt wttp://wwe..oeeccccc//aatttttaae com//scciemcce/attccll//pt $0196677498909932.
[30] S. Im, Kumar, M. M. Qaem, and M. Purohit. Online knapsack with frequency predictions. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 2733-2745 2021.
[31] G. Istrate and C. Bonchis. Mechanism design with predictions for obnoxious facility location. CoRR, abs/2212.09521, 2022.
[32] G. Istrate, C. Bonchis, and V. Bogdan. Equilibria in multiagent online problems with predictions. CoRR, abs/2405.1 1873, 2024.
[33] A. R. Karlin, Kempe, and T. Tamir. Beyond veg. Frugality of truthful mechanisms. 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 615-624. IEEE, 2005.
[34] D. Kempe, M. Salek, and Moore. Frugal and truthful mechanisms for vertex covers, flows, and cuts. In S1st Anmual IEEE Symposium on Foundations of Computer Science (FOCS), pages 745-754. IEEE, 2010.
[35] M. Li, C. Wang, and M. Zhang. Budget feasible mechanisms for facility location games with strategic facilities. Auton. Agents Multi Agent Syst. 36(2):35, 2022.
[36] S. Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf. Comput., 222:45-58. 2013. doi: 10.1016/111.200121100000. URL https://doi. org/10.
1016/j. ic.. 2012. 01. 00.
[37] A. Lindermayr and N. Megow.
Alps, 2024.
URL https://
algorithms-aeee temttthsssts wetttprpeiiiionsss www.riiiiiiionn............ github.io/.
[38] P. Lu, Z. Wan. and J. Zhang. Competitive auctions with imperfect predictions. In Proceedings of the 25th ACM Conference on Economics and Computation, pages 1155-1183, 2024.
[39] T. Lykouris and S. Vassilvtskii. Competitive caching with machine learned advice. In Interna- tional Conference on Machine Learning, pages 3296-3305. PMLR, 2018.
[40] M. Mahdian, Ye, and Zhang. Approximation algorithms for metric facility location problems. SIAM J. Comput., 36(2):411-332 2006. doi: 10.1 101113//0009759704433366 URL https://doi. org/10. 1137 11117//000977337743333777
[41] A. M. Medina and S. Vassilvitskii. Revenue optimization with approximate bid predictions. In
I. Guyon, U. von Luxburg, S. Bengio, H. M. Wallach, R. Fergus, S. V. N. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 1858-1866, 2017. URL
neur ips.ipis.. htpps.cc/ppaae hccppappe//01///////// /hassh/ 8aa47996ttabboaaee133aaaaaa//aa http:///a...aaaaaaaaaaaaaaaaaaa. Awstract....... hhtml. html.
[42] M. Mitzenmachhr and S. Vassilvitskii. Algorithms with predictions. In T. Roughgarden, editor, Beyond the Worst-Case Analysis of Algorithms, page 146-662. Cambridge University Press, 2021. doi: 00.0017/978110867433..3333
[43] M. Mitzenmacher and S. Vassilvitskii. Algorithms with predictions. Commun. ACM, 65(7): 33-35, 2022.
[44] U. G. A. Office. Reverse auctions. [accessed March 2025].
http://ww...g//prottttt///aaaae 2024.
[45] M. Purohit, Z. Svitkina, and R. Kumar. Improving online algorithms via ML predictions. In Advances in Neural Information Processing Systems 31: Annual Conference Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 9684-9689999 9693, 2018.
13

---

[46] Y. Shi and Z. Xue. Prediction-augmenntc mechanism design for weighted facility location. arxiv preprint arXiv:2507.06559, 2025.
[47] D. B. Shmoys, E. TTIdos, and K. Aardal. Approximation algorithms for facility location problems (extended abstract). In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC "97, page 265-274, New York, NY, USA, 1997. Association for Computing Machinery. ISBN 089791 18866 doi: 10.1 145115555333... 10.1145/258333.256666 258600.
URL https:
/ //doi. wrg/10..../.oooooo.oo.... 1145/258523 258600.
[48] K. Talwar. The price of truth: Frugality in truthful mechanisms. In Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 608-619. Springer, 2003.
[49] C. Xu and P. Lu. Mechanism design with predictions. L. D. Raedt, editor, Proceedings of the Thirty-Fite First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, pages 571-577. ijcai.org, 2022.
A Extended Related Work
Algorithms with Predictions. In recent years, the Btarning-augmenter framework has become a leading paradigm for algorithm design and analysis. For an overview of its early developments, see [43], and for a comprehensive, up-to-date survey, consult [37]. By incorporating (potentially imperfect) predictions, this framework overcomes the limitations of classical worst-case analyses. Indeed, over the past five years, hundreds of papers have revisited core algorithmic problems through this lens, with prominent examples including online paging [39], scheduling [45], covering and coopsacck-onntraieeed optimization [10, 30), Nash social welfare maximization [11], variations of the secretary problem [2, 23, 26), and a variety of graph-basee based challenges [5].
The metric Uncapacitated Facility Location (UFL) problem is a fundamental NP-hard op- timization problem, widely studied due to its theoretical significance and practical relevance in operations research and algorithmic game theory. Early foundational results established the APX- hardness of the problem, showing that it cannot be approximated within a factor better than 1.463 unless P NP [29]. The first constant-faae factor approximation was provided by Shmoys al. [47], who achieved a ratio of approximately 3.16. Subsequent improvements significantly narrowed the approximation gap, with notable progress by Chudak and Shmoys [21] 1.736 and Mahdian et al. [40] to 1.22-approximation via sophisticated finear-rrogrammigg techniques. Byrka and Aardal [14] later improved this bound state-of-the- algorithm, due to Li [36], achieves an approximation ratio of 1.488, leaving a small gap relative to the known hardness bound.
UFL.
1.00-aprrxximation using novel bifactor algorithm The current
B Tightness of the Frugality Bound for VCG
We now show that the frugality ratio of 3 for VCG is tight by exhibiting the following instance. Theorem B.1. The frugality ratio of VCG auction is at least 3 in the worst case (as [L] + co), the frugality ratio approaches 3.
1 even for tree metrics. Hence,
6
Proof. Consider the tree metric defined by facilities L (lo. ..., (x]. users = {u)..... Uu }. and edges E {[e, Ui } } Uf(,, fo)) (see Figure B for an illustration). Facility lo has an opening cost Ot, = 2 and the other facilities have an opening cost of O. The distance of from the central facility to any other facility é is 2 and d(e, Eg) for all pairs of distinct i, 0. Finally, we have one user in the midway of & and to-
For the given instance, the optimal solution OPT(U, o, d) is open all of the peripheral facilities & (f,,...,(y) for a total cost of k. Consequently, the frugal solution FUU, = {66} is to open the central facility for total cost of k 2.
Now consider the payment made by VCG. Note that for E (1,..., k). the opening cost of & og oc (and the other opening costs do not change), then user i4 must connect either to the central
14

---

0
0
Figure 2: Illustration of the lower bound instance where each square represents a facility location with its opening cost, and the circles represent users.
facility tu (which has opening cost 2) or to another peripheral facility (which increases the connection cost of u, by 2), the solution OPT( (o,, o-1) is either {fo} or {f1..... .......,---- ..-1, fit1..... lx and c(OPT oo, o-1)) = + 2. Thus, for each peripheral facility with E {l,..., ........]......... the VCG payment is
= c(OPT(2o, o-1)) - c(OPT(O, o-i)))))))))))))) (k: + 2)
Therefore, the total payments by the VCG auction to the facilities OPT(U, o) = (4..... lx) that it selects is 2k which, combined with total user connection costs of k; leads to total cost of 3k. Therefore, the frugality ratio for this instance
3k c(F(U,,)) o))
3(Il) -1
3(L + 1) 6)
3
k+2
|L| +|+1
L +1
L +1
C Missing Proofs from Section 4
C.1 Truthfulness of PREDICTEDLIMITS
We first prove that the auction is truthful. By Myerson's Lemma (Lemma 2.1), it suffices prove the monotonicity of the allocation rule.
Lemma C.1. For any < 2, the PREDICTEDLIMITS auction truthful.
Proof. We show that the allocation rule of Auction is monotone, and then invoke Myerson's 's lemma to conclude truthfulness.
Fix facility E L, and hold constant the true opening costs c_, of all other facilities as well as all predictions& It suffices to prove that if belongs the winning set when reports cost 0, then it still belongs to the winning set when it reports any lower cost S a.
Recall that the auction uses the modified cost function
( Ct. if = OėT and cr > Ct cr.
<(S)
otherwise.
We slightly abuse notation and use (S a) and (S to denote the scaled cost when facility i reports a and b, respectively. Since lowering E' reported cost can only (weakly) decrease its scaled cost in every candidate set, and since the event "S = OPT" depends only on the prediction, not on the reported bid, we have
d((),)) S (((sa) for all S.
Se be the winning set when ? bids o, and let Se be the winning set when it instead bids b keeping everything else fixed. 5' S* then & E S' immediately. Otherwise the only cost that changed is d so in order for the auction to switch to a different optimal set S', must still include Hence in all cases & remains selected, proving monotonicity. Finally by Myerson's 's lemma, monotone allocation rule induces truthful payments, so the auction is truthful.
D
15

---

C.2 Missing Proofs from Section 4
C.2.1 Proof of Lemma 4.3
Proof. By definition of the auction, at most one subset, OPT, can have its costs scaled. Therefore, suffices to consider the relationship between OPT and OPT (the true optimal solution). We also note that since c S 2, any set that is scaled can only increase its total cost relative other solutions. The proof structure closely follows the VCG analysis. The main idea is to handle the two cases depending on whether the predicted optimal set OPT matches the true optimal set OPT.
OPT * OPT. In this case, the true optimum OPT was not the set subject to potential scaling, Since S OPT the output, OPT must remain the optimal solution even in the modified (potentially scaled) instance. We apply the same VCG analysis structure as in Theorem 3. and Lemma 4.2.
Case one:
Define y and (t(() as Theorem 3.1. The bounds from (2) and (3) hold, so we get
Pt
d(Ue, f:EEaPT,
S Σ of(F) +2 Σ E d(Ues,))+
Σ E
d(Ue.s,
REOPT
SEF
fer BEOPTy
REOPT f:REOPT,
S
Of + 2d(U,
Σ E
d(Ue.F!!)
EEF
BEOPT S:REOPT
Of 2d(U,F)+ +
Eor+
2 +
o0 0 Σ FEF
(5)
where the second inequality assumes the worst case for df((F, (F), which occurs if F = OPT and the opening costs of facilities in were under-predicted. The third inequality uses the fact that the connection cost of the true optimal solution is weakly less than the total cost of the frugal solution.
Case two: OPT OPT. and we have:
Since S
OPT, the consistency analysis from Lemma 4.2 applies directly,
Σ p Σ Σ
Σ +o d(U, F)
ÆEOPT
#EUPT F:CEOPT,
The lemma statement follows by taking the maximum of the bounds from the cases
C.2.2 Proof of Lemma 4.4
Proof. The proof is very similar to the VCG analysis, replacing the facilities in the optimal solution with the facilities in S 5* \ F. In addition, also need to consider the case where the corresponding frugal facility f is included in S*, which turns out to be an casier case for bounding rerouting costs.
Consider the case where S* * OPT. First, we note that OPT = OPT, otherwise OPT would be output since scaling solution only makes it worse. Therefore, both 5 and F unscaled. Let S 5" F..
Define Ug, Ue,-- 2 (E) and π (f) as Theorem 3.1, but replacing OPT with If E S*, then rerouting users from é E S to f is bounded by just connecting the users to f. Therefore, in the worst case, all facilities f are not S*. Then, inequalities (2) and (3) hold when replacing OPT with S. Therefore, our total payment is bounded by
Σ pe Σ d(u.e) EES
+2 Zo
+ Σ
a(UL))s)
+ +ΣΣ a(Ue,s,)
NEUe
FEF
JEF BES,
EES FiEES,
Σ
[2((U,, +oy +
Σ
d(Ue,), E).
FEF
LES fREE,
16

---

Cancelling the total connection cost term Eles Eueu, d(u,t)= = :xiEs Exiess, d(Ue,,,) .) from both sides:
Σ
Pt S
[2(UU
-
Σ LEF
or F)(
EES
SEF
C.2.3 Proof of Lemma 4.6
Consider any instance (U, o, d) and any 6 S 2. Let OPT and be the optimal solution and frugal solution of the given instance. Let S be the output of Auction 1.
Proof.
Case one: S = ОPT. St = OPT, by Lemma 4.3 we have:
Σ LES-
pt + d(U,5)) < (2+1)
Σ or + 3d(U, EEF
Case two: S* # OPT. We now consider the case where S * OPT. First, note that the connection cost of 5 is weakly less than or equal to the total cost of any solution K, including the frugal solution F. We have:
d(U < Σ + = Σ ddU,
(6)
REF
EEF
where the equality is due the fact that OPT is the solution that is scaled, by the fact that S * OPT.
Let S S" \ F and S S* n F. Putting together Lemma 4.4 and Lemma 4.5, we get:
Σ Pe d(U,S*) - AES*
Σ Pt + Σ Pe d(U,S")
BEST
Og + 2d(U,F) + Σ Pt d(UUS*")
(by Lem. 4.4)
EEF
BEST
$ max
3, - +1
2
Σ
+ max
4, (4222) d(U, F) + d(U,S*)
REF
(by Lem. 4.5)
2
5, (.2+3)
S max
- +
Σ
o0 + max
d(U, F)
(by (6)
Taking the worst case the two scenarios we get that
Σ
Pt - d(U,S*) & max (5. 5, - +3)
Σ
ot + d(U,F))
Lier
D Proof of Theorem 4.1
Proof of Theorem 4.1. Auction PREDICTEDLIMIT truthful by Lemma C.I, (1 + consisttt by Lemma 4.2, and max (5, 2 3)r-bouust by Lemma 4.6.
[
E Missing Proofs from Section 5
E.1 Truthfulness of ERRORTOLERANT
We first prove the truthfulness Auction ERRORTOLERANT. The proof is very similar to Theo- rem C.I.
Lemma E.1. For any S 2, the PREDICTEDLIMITS auction is Truthful.
Proof. We show that the allocation rule of Auction 2 is monotone.
17

---

Fix a facility E L, and o-; of all other facilities as well as all predictions 6. Let l's reported cost be a 2 O, and suppose that when bids a the auction selects S We must show that instead reports any lower cost b S it remains selected.
Denote by ex (S; =) the total cost of set S under report & {a, b). according Auction Note that in either branch (the "whole-solution downscaling" or the "per-facility inflation"), lowering f's cost from to b weakly decreases its contribution to (S) for every S. We consider two cases:
Case 1: Whole-solution downscaling applies at report That is,
v E OPT, oe S Xôe under a. Since b S a, the same test holds at b, so the auction remains in the downscaling branch. In that branch
x ((U,S) + Dr S =
(x 2)
d(U, Eres oz,
otherwise,
and reducing it cost from a to b multiplies its term by at most b/a S every candidate set. Hence (S; b) < (5; a) for all S
Since solution that got a reduced cost must contain L, any new minimizer S must still contain É.
Case 2: Per-facility inflation applies at report Then there is some l' OPT with of Xōg
under x = a. Two subcases arise:
ê & OPT. Lowering its bid does not affect the branch test, we stay in the inflation branch. But in that branch each facility's scaled cost (whether inflated by 2/c or not) is nondecreasing function of its report, so the argument from the original auction applies verbatim to show monotonicity.
if E OPT. Then > Xog but b & Xog, so at = b the auction flips into the downscaling branch. In that branch it will choose OPT (since uniformly downscale its cost), and OPT э l. Thus l remains selected.
In all cases, lowering ''s bid can only weakly decrease its cost in every candidate set including it, and any switch of the minimizer continues to include é. Therefore the allocation rule is monotone, and by Myerson's 's lemma the resulting payments make the auction truthful.
E.2 Performance analysis for ERRORTOLERANT
We now provide the performance as a function of the error and the error tolerance parameter A.
E.2.1 Performance when 1) S A
We first consider the case where 1) S. X, we start by showing the claim that OPT is always outputted when 17 I A. The result of this case summarized in Lemma E.8. We first show that under the condition 77 S A, the prediction optimal is always returned.
Lemma E.2. nn S X, then Auction 2 always selects OPT; that is, S OPr.
We now provide upper bound of the connection cost of the output solution.
Proof. Let
E(S) = d(U,S) + Σ dz:
EES
be the predicted total cost. First note that since
S X, we have 0r S λo for all & the auction will set
(S) X ((PT),
OPT,
C(S),
S o OPT.
Since OPT minimizes the predicted cost,
e(DPT) < ((S) AS C L.
(7)
18

---

By S À we have - oo for all E OPT, so
c(OPT) Σ d(u, DPT) +
Σ or Ed(u, d(u, DPT) + A Σ de A((OPT)
#EOPT
#oOPT
On the other hand, since òe S noz for all l, we get
((S) = Σ S( + Eoe S Ed S) + 11 Σ or =
EES
u
LES
Combining the above incquality with (7) we have,
c(OPT) < Xe(S) < cT) = x2
CO(T)) S c(S) = cx S Cx(s),
AA o OPT.
Since the auction output the set that minimizr cx, therefore have S = OPT.
Observation E.3, For any set S + OPT, let ((5) = d(U,S) + Eres Ôg, we have
((S) S (s(s))
Proof. 1) S X implies oe S Aog for every L, so
ē(S) = S) +
Σ δe S d(, + n Σ ot = ((((
Σor
EES
LES
EES
We now provide an upper bound of the connection cost of the output solution.
Lemma E.4. In S X, then for any S C L,
d (U, OPr) & (d(U,S) + Eor)
EES
Proof. Since d (U,OPT) < ((PTT), combining with the fact that OPT minimizes é, we have gives d (U, DPT) a(DPT) s a(S) s n(((U,))
Σ
08
EES
where the last inequality is by Observation E.3.
We now move on upper bound the payment the facilities in the output solution, i.c., OРT. In particular, we will partition OPT based on the threshold they applied, and whether it is member of F, the true frugal solution. We first analyze the low-threshold facilities.
Lemma E.5. Under the condition 7) X, let S
{e OPT: pt Xoτ}. Then
Σ & Ane(F). EES
where F is the frugal solution.
Proof. Since Pt
S oo for every L E S1
Σ Pc
de
< Σ dz < (((PPT) & X²(F), & An
RESL
LEST
εEOPT
where the last inequality is by Observation E.3.
Lemma E.6. Assume 1) S X, and lei
$2
[EE OPT: > Xor, $ F}.
Then
Σ De S cc(F), 8E
where F is the frugal solution.
19

---

Proof. We follow the rerouting argument of Lemma 4.4, with the additional fact that when the reported bid is more than λog, the opening cost is scaled up. specialized to the output OPT.
Define U and f (f) as in Theorem 3.1, but replacing OPT with S If f E S", then the cost of rerouting users from 5² to f is bounded by just connecting the users to f. Therefore, in the worst case, all facilities f F not in S Then, inequalities (2) and (3) hold when replacing OPT with S. For & E S payments are scaled by 2 Following a similar argument as Lemma 4.4, our total payment is bounded by
2
Σ Pe Σ FES
E S:tES]
d(Ue),))) Σ
2 Σ
d(UL,f,)+
Σ
d(UE)))))
BES
FEF
LES
[ES)
Σ
f( + oo]
+
Σ Σ RES?
d(Ue,,.
fEP
f:tEs
Cancelling the total connection cost term Etes E Eirest d(Ue,, E) from both sides gives
2
Σ
DE
[ , +oy1
EES
SEF
we therefore get
Σ DE S Σ
Σ (c
of +
EES2
fEF
fEF
Lemma E.7. Under the condition 1) S X, let
S3
{lE OPT: Pt > Xoe, E F}.
Then
Σ p S ((PP). BESS
Proof. For E $ E F and > Xdg. An argument analogous to Lemma 4.5 shows that inflating the opening cost of any facility in the frugal solution beyond its predicted cost by up to a 2/e factor bounds its threshold payment by times the cost of the true optimum. Hence ExEsa Pe S e c(OPT).
Lemma E.8. Assume 7 S X Let F be the frugal solution, and let S and {peltes- be the output of Auction 2. Then
d(U,s*) Σm pe I (n)(1 + X) x) c(F).
EES
Proof. By Lemma E.2, under 1) S the auction selects S OРT. We partition the payments over OPT into three parts S", 52, 53 as in LemmasE.5, Lemma E.6 and Lemma E.7. since c(OPT) < c(F). Summing connection cost and all payments gives
d(U,s*)
Σ pr d(U,OPT) EE
Σ Pe +
Σ pc
+
Σ Pt FESS
FES
$ n (((() + Σ PE +
Σ PE + Σ
Pe
(by Lem. E.4)
EE
EES
tE
s nc(F) + Xnc(F) +
Σ Pt
+
Σ Pe
(by Lem. E.5)
LES
tEg
s nc(F + Xnc(F) + ec(F)) + Σ Pt
(by Lem. E.6)
łES
s nc(F) + Xnc(F) + +cc(F) + (c(F)
(by Lem. E.7)
(n(1 2) 2c) .c(F).
20

---

E.2.2 Performance for general error 77
We now analyze performance for arbitrary 77 by breaking the proof into two dimensions: (a) which scaling rule the auction applies: either inole--souttion downscaling or per-facility inflation- andionn-nddd (b) which set is ultimately selected. In each of the resulting subcases, we separately bound the connection cost and the total payment using rerouting arguments and the appropriate scaling factor; combining these four analyses yields the unified frugality guarantee stated in Lemma E.11. We start by consider the case where whole-solution scaling applied and the OPT outputed.
Lemma E.9. Let S be the oulput of Auction 2, S OPT, for any OPT,
d dU,,5" v X² c(S).
Proof. By the scaling scehem of the auction we have (U, & (0FT)) combining with the fact that Sth minimizes C22 we have gives
SU) & X² 22 cx(") S 2² ex()) & X2 cc))
where the last inequality is since OPT.
Lemma E.10. Let 5" be the output of Auction 2. 1f =OPT and the whole-solation-scaling is applied, then
Σn
P S (2X* c(F))
EES
Proof. We follow the rerouting argument of Lemma 4.4. Partition OPT into
S* F and s -OPT F.
Define U and (E( as Theorem 3.1 but replace OPT with S*
Since the auction applics a 1/X² down-scaling to DPT, no profitable deviation implics
1
pt
Σ d(Ue.,, s
Σ
Tif
(8)
X2
for each E where re, is the cost to reroute Ut, to (
By the standard charging argument,
ETes S Σ d(Ue, of + Σ d(Ue.,,
(9)
KES
RES,
LES₁
Summing (8) over all E S and then using (9) together with Lemma E.9 f) d(U,F) yields
Σp. Ps s 2c(F)+ (1 (1-
Σ Σ d(Ue,,.) S 2c(F) + (2-1))ck dFF)
2
EES
EES j'tES
Hence
En ÉES
Pc S (A* + x2))
The case St gives the even better bound Te, S d(Ue,,+ f f), so it cannot increase the total.
Applying the identical rerouting argument to 5 (with F replaced by OPT) yields the same upper bound (X+ + ()). Summing over both parts,
Σ Σ DEP E FES-
PE S (2X* + 2x²) c(F).
BES
FES!
Lemma E.11. The Auction achieves frugality ratio
max{ 2x* + 3X2, 3 2]
21

---

Proof. The auction uses exactly one of two branches:
(i) Whole-solution downscaling:
Cx(5) X (
S OPT
d(U,s) +EEE
S OPT.
(ii) Per-facility inflation:
Cx(S) d(U,S) + Σ d()))
EES
where d5(5) 00 if OРT and or λog, and d5(5) or otherwise.
Case 1: Whole-solution downscaling applies.
Case 1.1: If the auction still outputs S = OPT, then by Lemma E.9,
d(U. I X² c(F).
Combined with Lemma E.10, which gives Etes Pe S (2X* + 2X²) c(F), we obtain
d(U,s*) Σ pe $ (2X* + 3x c(F) EES
Case 1.2: Otherwise S* + OPT. In this subcase, OPT was downscaled but not chosen, and all other candidate sets remain unscaled. Thus from the winners' perspective the outcome is no worse than standard VCG, so
d(U,5") + Σ pe I 3c(F)-
EES
Case 2: Per-facility inflation applies. In this branch the analysis of Section 4.3 carries over unchanged: the exact triggering condition (or > ôg vs. of > Aoτ) does not affect the worst-case bound. By the robustness proof of Theorem 4.1,
d(U,S*) + Σ Pe s max 5, 3+ 2 c(F).
Taking the maximum over all branches and subeases yields
max 2x + 32?, 5, 3 3+ ? = max 2x* 322, 3 ? c(F).
Putting findings together gives up the performance ERRORTOLERANT.
Proof of Theorem 5.1. If S X, by Lemma E,8 have the first statement and Lemma E.11 proves the other bound, for arbitrary 7) values.
F Computational Complexity
The standard IP formulation for UFL uses binary variables oy E {0, 1) to denote whether facility f E L is opened and variables Vue E [0, 1] for assigning user u E U to facility f.
The implementation of Auction 1 proceeds follows:
1. Determine the Predicted Optimal Set: First, we solve classic UFL integer program using the predicted opening costs, {oeJeEL. to find the predicted optimal set, OPT.
2. Find the Best Alternative Solution: After identifying OPT, its modified cost according to the auction rules is calculated directly. To find the best alternative, we solve second UFL
22

---

integer program using the the opening costs, foeteez. A linear constraint is added to this IP to make the set OPT an infeasible solution:
Σ 2e I0PTT -1
ΣЕOPT
This inequality ensures that least one facility from the set OPT remains unopened, allowing the IP to find the optimal solution among all other feasible sets.
3. Select the Winning Set: The auction's 's final output, S is determined by comparing the modified cost of OPT with the cost of the best alternative solution found in the previous step. The with the lower cost chosen.
4. Compute Payments: Finally, for each facility & in the winning set S its threshold payment is computed. This done by solving one additional UFL integer program per winning facility to find the critical cost at which that facility would no longer be part of the optimal solution.
23

---

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: Our primary claims are establishing tight bound for the VCG mechanism frugality ratio the incapacitated facility location problem, and introduce a prediction- enhanced mechanism that achieves good consistency and robustness guarantees. Both of these claims are achieved in the paper and proven in Sections and respectively.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
It is fine 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: we have clearly stated our mathematical model and the assumptions we make about the model, including the metric space, types of predictions and explicitly explained that the results hold under the given model.
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 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 (e.g.. independence assumptions, noiseless settings, model well-specification, 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 a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect 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-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency 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 fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren'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 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?
Answer: [Yes]
Justification: The main goal of the paper is to prove claims about the frugality ratio of several mechanisms for the incapacitated facility location. Therefore, all theorems and lemmas provided in the paper are stated with appropriate assumptions and justified with complete proof.
Guidelines:
The answer NA means that the paper does not 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 proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to 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
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 of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper does not include experiments. All results are entirely theoretical.
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 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 make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed 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 are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS 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 reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
25

---

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
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
The paper does not include any experiments, nor does use on data or code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
mublic/guide Bttee//iide///oeeuubiiee (CodeSummissionf oonoooooooy)) for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurlPS code and data submission guidelines (https: //n /nips. htips.cc/puble http:/pulllcgdddde httpe//guideeeoeeeeuubiieseeeeee (oode@uumisssiooooool...
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. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is 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 a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be 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 emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
26

---

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.)
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 one 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 figures symmetric error bars that would yield results that are out 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
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
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 runs as well 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 in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /tt///eursp.../ cttpppp.cccpppppppeccppe
Answer: [Yes]
Justification: The authors have reviewed the Code of Ethics and concluded that the research conforms with all guidelines listed.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS 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., there a special consid- eration due to laws 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: [NA]
The paper presents purely theoretical results (e.g.. mathematical theorems and performance bounds) without proposing deployable systems, datasets, or algorithms. Consequently, we do not anticipate any direct positive or negative societal impacts that warrant further discussion.
Justification:
27

---

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 or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate to point 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 a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as 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 or 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
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 use models or data.
Guidelines:
The answer NA means that the paper poses 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
Question:
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?
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
28

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com comddataees has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it 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/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an 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 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 to the NeurlPS Code of Ethics, 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 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 an equivalent approval/review based on 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 crowdsoureing nor research with human subjects.
29

---

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 NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if 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.
Question:
Answer: [NA]
Justification:
The paper does not use L.Mss.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should not be described.
30


Reviews:
[{"review_id": "U334j5DKXS", "reviewer": "Reviewer_Efkg", "summary": "This paper studies the strategic uncapacitated facility location problem (UFL). In UFL, an agency wants to procure a set of facilities among a set of potential locations to provide service to its users. Each facility location comes with an individual cost. The goal is to choose a set of facility locations that minimizes the sum of the distances from users to facilities and the total payment to the facility owners.\n\nIn strategic UFL, each facility owner has a private cost, and the agency does not know these private values. Instead, it runs an incentive-compatible auction to determine which locations to procure and how much to pay. In the literature, there has been some work on analyzing the worst-case guarantees of IC auctions, comparing them to the total cost when the location costs are public. More formally, the benchmark is the frugality ratio, which is the worst-case ratio between the total cost of a truthful auction and the cost of the second-best solution when the agency knows the true costs.\n\nThe first result of the paper is a tight analysis of the frugality ratio for the VCG auction. Previously, the best known upper bound for VCG was 4. This work improves it to 3, with a matching lower bound instance.\n\nThe second contribution is that while most previous works focus only on worst-case guarantees, this paper designs and analyzes new auction frameworks that take into account predictions on the cost of each location. These mechanisms not only perform well when the predictions are accurate, but also retain worst-case guarantees when the predictions are wrong.", "questions": "The notation $U_{\\ell, f}$ is not defined. Is it the set of users that are assigned to $\\ell$ in OPT and assigned to $f$ when the facility set is F?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1.The problem is well-motivated, and the authors provide a tight analysis of the VCG auction, improving upon previous results in the literature.\n2. The paper goes beyond traditional worst-case analysis. It designs algorithms that achieve strong guarantees when given accurate predictions, while still providing baseline performance guarantees even when the predictions are completely inaccurate.\n\nWeaknesses:\n1. The presentation can be improved—some proofs are hard to follow, with a missing definition that makes them difficult to parse.\n2. The model is somewhat limited: it focuses on the case where the agency has accurate predictions for the cost of each location. It would be more interesting to consider Bayesian models, where the true costs are drawn from known prior distributions.", "was_revised": true, "final_justification": "I recommend acceptance of this submission. Though the presentation could use some additional work, I believe the paper addresses an interesting and important problem and would be valuable to this venue.", "rebuttal": "Thank you for carefully evaluating our paper and for providing us with constructive feedback. We apologize for omitting the definition of $U_{\\ell, f}$, which is exactly the one you mentioned. We have updated the submission to include this definition. We briefly address you comment regarding the Bayesian model below.\n\n* **Regarding the learning-augmented model and its comparison to Bayesian models**\n\nBoth the Bayesian model and the learning-augmented model are part of the same broader literature, aiming to move beyond worst-case analysis, however there are important differences between the two. The most important among them is that in the learning-augmented model the quality of the predictions is unknown and they can actually be arbitrarily inaccurate (this is in contrast to the reviewer's claim that the learning-augmented model \"focuses on the case where the agency has accurate predictions\"). On the other hand, the Bayesian model actually assumes that the distributions that the agency is provided with are (perfectly) accurate, and the algorithms and mechanisms are then evaluated in expectation over that randomness. In settings where such accurate distributional information is easy to extract, we agree that the Bayesian models are quite interesting and relevant. However, in settings where such information may be harder to gather and the predictions of the machine learning algorithms are less dependable, we believe that the learning-augmented model is more relevant. Another signal regarding the significance of the learning-augmented model is the fact that more than 250 papers have focused on this model during the last 5 years according to the \"Algorithms with Predictions\" github."}, {"review_id": "R5jYoMNivx", "reviewer": "Reviewer_xSdS", "summary": "The paper studies procurement auctions for the strategic uncapacitated facility location (UFL) problem, where facilities are owned by strategic agents with private opening costs. The goal is to open facilities and determine payments to minimize total cost, balancing opening and user connection costs. The authors evaluate auction performance using the frugality ratio, which compares auction cost to a “second-best” benchmark. They first show that the classical VCG auction has a tight frugality ratio of 3. Then, they introduce learning-augmented auctions that use potentially inaccurate cost predictions to significantly reduce payments when predictions are accurate, while still maintaining bounded frugality under adversarial errors. They also propose an error-tolerant auction variant that adapts to approximately accurate predictions, achieving improved frugality guarantees as a function of prediction error.", "questions": "Just wondering if the authors have thought about this comment:\n\n**Furthermore, the prediction-augmented algorithm may have limited practical applicability, as it penalizes certain agents by scaling up their costs based on potentially inaccurate predictions. The design appears somewhat single-minded, focusing narrowly on optimizing a specific objective (i.e., frugality) while overlooking broader consequences of the mechanism, such as fairness or unintended distortions in participation incentives.**\n\nAnd if they have done some simulations to see how biases in prediction can hurt some of the players?", "limitations": "See my earlier comments.", "rating": 2, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 1, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\nThe paper addresses an important and timely problem---the design of procurement auctions for strategic uncapacitated facility location---by exploring how predictive information can improve frugality in mechanism design.\n\n**Weaknesses:**\nThe paper is poorly written and lacks clarity in both exposition and notation. Key concepts, such as the VCG auction, are not properly defined when first introduced. The proofs are difficult to follow, partly due to inconsistent and undefined notation. For example, the term $U_{\\ell, f}$ appears in key arguments without any formal definition, and the notation for the auction mechanism $\\mathcal{M}$ is used inconsistently throughout the paper with varying input sets, without acknowledgment. Similarly, $\\mathsf{OPT}$, a central object in the definition of the frugality ratio, is used before being clearly defined. Additionally, the motivation for focusing on the VCG auction and for using the frugality ratio as the primary performance metric is not clearly justified. \n\nFurthermore, the prediction-augmented algorithm may have limited practical applicability, as it penalizes certain agents by scaling up their costs based on potentially inaccurate predictions. The design appears somewhat single-minded, focusing narrowly on optimizing a specific objective (i.e., frugality) while overlooking broader consequences of the mechanism, such as fairness or unintended distortions in participation incentives.\n\nFinally, the paper completely overlooks the computational aspects of the optimization problems involved in the proposed mechanisms. These problems are often NP-hard, and the paper provides no discussion on tractability or practical solvability.\n\n\nThese are just some example problems. The paper has some potential. But, in its current form, it is not ready for publication.", "was_revised": true, "final_justification": "I am not fully convinced by the authors' response regarding the following\n\n> Furthermore, the prediction-augmented algorithm may have limited practical applicability, as it penalizes certain agents by scaling up their costs based on potentially inaccurate predictions. The design appears somewhat single-minded, focusing narrowly on optimizing a specific objective (i.e., frugality) while overlooking broader consequences of the mechanism, such as fairness or unintended distortions in participation incentives.\n\nFurthermore, the exposition needs some additional work; the paper is not well written.", "rebuttal": "Thank you for carefully reviewing our paper and providing constructive feedback. We apologize for omitting the definition of  $U_{\\ell, f}$, which denotes the set of users assigned to $\\ell$ in OPT and to $f$ in the frugal solution $F$. We understand that this omission (which, unsurprisingly, all the reviewers pointed out) may have made it harder to parse the proofs. We also agree that there is some room for improvement in the writing, but we believe that these issues are easy to address (e.g., by just adding the definition of $U_{\\ell, f}$) and, as we point out in the rest of the rebuttal, some of the reviewer’s concerns are actually already addressed in the initial submission. We therefore believe that the overall assessment of our submission is somewhat harsh, and we would be happy to use the discussion period as an opportunity to convince the reviewer that this is the case, and that we can address all of their concerns in the next revision of the paper.\n\n\n* **OPT, a central object in the definition of the frugality ratio, is used before being clearly defined** \n\nThis is actually not accurate. The first time that OPT is used is on line 129 where it is defined both in words as the optimal facility set as well as with a formal mathematical definition as $\\arg\\min_{S \\subseteq L} c(S)$.\n\n\n* **Key concepts, such as the VCG auction, are not properly defined when first introduced**\n\nThe formal definition of the VCG auction is at the bottom of page 4, at the very beginning of Section 3, right after the preliminaries. If the reviewer prefers that we add a pointer to its definition when the VCG mechanism is first mentioned in the introduction, we would be happy to do so. If there are other key concepts that are not properly defined when first introduced, we would appreciate it if the reviewer could provide us with additional examples\n\n\n* **The notation for the auction mechanism is used inconsistently throughout the paper with varying input sets** \n\nThe mechanism notation is introduced at the bottom of page 3 and in its full generality it takes as input the tuple $(U,b,d)$. One line after its first definition, we also state that we often just provide $(b)$ as its input when $U$ and $d$ are clear from context. Then, at the top of page 4, we define truthfulness and point out that whenever a mechanism is truthful, it is a dominant strategy for bidders to submit the truth, so that $b=o$. As a result, since the whole paper is restricted to truthful mechanisms, we can also directly use $o$ instead of $b$ as the input of the mechanism.\n\nDoes this address the reviewers’ concerns, or is there some other inconsistency that they have in mind?\n\n\n* **The design appears somewhat single-minded, focusing narrowly on optimizing a specific objective (i.e., frugality) while overlooking broader consequences of the mechanism, such as fairness or unintended distortions in participation incentives.** \n\nWhen designing procurement auctions, the most obvious and natural objective to optimize is the cost of the buyer who will be using this auction. This is analogous to the design of (forward) auctions, where the seller running the auction aims to maximize revenue. As a result, it is a central goal in the mechanism design literature to minimize cost and maximize revenue when designing such auctions. We agree with the reviewer that an important secondary objective would be to understand the extent to which the buyer’s cost can be optimized subject to fairness constraints. In fact, although we have not conducted any simulations regarding such fairness considerations, our mechanisms always guarantee individual rationality (i.e., they ensure that no bidder will ever receive a payment less than the cost that they report), which is a classic form of a participation incentive in mechanism design. Note, however, that in the setting that we consider even the primary objective of cost minimization was previously not well understood, so this is the most natural first goal. \n\nOn a related note, we noticed that the reviewer flagged our submission for major ethical concerns, based on potential discrimination, bias, and fairness issues. To draw an analogy, the same concerns that the reviewer is raising here would directly apply to the classic (Nobel award winning) work of Myerson on the design of revenue-optimal auctions. Specifically, this work shows that the optimal auction for maximizing revenue when the value of each bidder is drawn from a distribution is to post bidder-specific posted prices, which is precisely the type of concern that the reviewer is raising. Although we would be happy to add a discussion regarding fairness considerations, including the participation incentives discussed below, we believe it is unreasonable for the reviewer to use this as grounds for rejection.\n\t\n\n* **Regarding computational considerations**\n\nAlthough the focus of our submission is on the information limitations of truthful (learning-augmented) auctions can be implemented using integer programming (see our response to Reviewer ENCf for more details)"}, {"review_id": "1i0VnX8558", "reviewer": "Reviewer_ENCf", "summary": "The authors study a procurement version of the strategic facility location problem where facilities report their operating costs, and a central planner decides on which facilities to open to minimize operating costs plus the costs of serving a fixed set of users. The planner has access to predictions about the facilities' operating costs. The work contributes to a recent active line of study on mechanism design with predictions, so it is a timely contribution. The main performance metric is the frugality ratio, which compares a mechanisms cost to the cost of the second-best solution. The authors first improve a result on the frugality ratio of VCG (establishing a tight result), then present a mechanism attaining (1+eps)-consistency and max(5, 3+2/eps)-robustness, and then present a error-tolerant mechanism with consistency and robustness ratios depending on the accuracy of the cost predictions.\n\n(Prior work on strategic facility location assumes strategic agents who can misreport their true locations. The present work considers agents with fixed locations, and the facilities are the strategic entities that need to report their operating costs.)", "questions": "What is the equivalent notion of frugality for a forward auction (1 seller, many buyers)? Why not just compare directly to OPT instead---that seems like a stronger benchmark and is what the literature on learning-augmented mechanism design (e.g. Xu and Lu [IJCAI'22], Balcan et al. [NeurIPS'23]) has typically focused on. My guess is that this is a feature specific to the facility-location/procurement setting, but some clarification would be helpful.\n\nRelated to the above, if one receives perfect predictions of the opening costs, isn't it possible to obtain cost = OPT while remaining truthful? (In contrast to the weaker result presented here that achieves a frugality ratio of 1.) Along that vein, consider the randomized mechanism that w.p. p trusts the predictions completely and implements OPT by paying each facility exactly the predicted cost, and w.p. 1-p discards the predictions and uses VCG. The consistency (I'm not sure about robustness) of this mechanism can be compared directly to OPT instead of the second-best. Where does this fit into the picture with the mechanisms in the present work?\n\nI am a bit confused about the explanation in lines 211-213. The authors say that scaling up under-estimated costs is to deter overbidding. My understanding is that incentive compatibility has nothing to do with the predictions/the facilities do not see the predictions. Could the authors clarify?\n\nWhat is the computational complexity of Auction 1? Vanilla facility location can at least be solved efficiently in practice via integer programming---is there a concise integer programming formulation for Auction 1?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths\n-------------------\n\nI think the problem and model studied are nice. Frankly, I think the model studied here is a more meaningful reflection of real-world procurement than anything modeled by prior work on strategic facility location :)\n\nThe improvement to the old result of Talwar on VCG's frugality ratio is a nice standalone contribution as well.\n\nThe paper is well written.\n\nWeaknesses\n-------------------\n\nThe robustness guarantees seem a bit weak since regardless of epsilon the frugality ratio is >= 5 which is worse than the VCG benchmark. Some result showing tightness would be nice here.\n\nI know that frugality is a standard notion and has been studied before, but its motivation is a bit unclear to me. A sentence or two giving the intuition behind why the second best solution is the right measure would be helpful. To me it seems like a needless weakening of the strongest benchmark which is OPT.\n\nIt would be nice to include a few lines of intuitive description of how Theorem 5.1 is proved in the main body.", "was_revised": true, "final_justification": "I am in favor of accepting the paper since its contributions are substantial and technically interesting. (Also, I think that the ethics issue that was raised is a nonissue and should not work against this paper.)", "rebuttal": "Thank you for carefully reviewing our paper and providing constructive feedback. We address your questions below:\n\n* **Regarding the use of the frugal solution as the benchmark**\n\nThank you for raising this point. The OPT benchmark is indeed stronger, but it is actually easy to verify that it is impossible to approximate. In fact, this impossibility is exactly what motivated the literature on frugality (starting with [1,2,3]), which introduced the frugal solution as a more appropriate benchmark. Therefore, this benchmark is not specific to facility location but, rather, the benchmark used in all of this literature on procurement auctions. Regarding the two papers that the reviewer referred to, note that Xu and Lu [IJCAI ‘22] do, in fact, also use this benchmark for their procurement auctions, while the Balcan et al. [NeurIPS ‘23] paper does not study procurement auctions.\n\nMaybe the simplest example to verify this inapproximability of OPT is to consider the case of just two sellers that provide the same service (e.g., in our case these could be two sellers that both have the same distance from every customer), so we need to procure the services of just one of them. If one of these sellers has a much higher cost than the other, then OPT would buy from the cheaper of the two at the cheaper cost, but this is impossible to approximate the payment in a truthful way in a setting without priors. This simple example captures the much more general fact that whenever the optimal solution is much better than the competition (resembling a “monopoly”), it is impossible to approximate it. We do briefly discuss this in the paragraph starting in line 43, but we agree that we would be happy to emphasize this further in the next revision. Also, we would be open to providing a short formal proof of the claim above if the reviewer believes this would make the need for the alternative benchmark more obvious.\n\n[1] Aaron Archer, Éva Tardos. Frugal path mechanisms, 2002\n\n[2] Kunal Talwar. The Price of Truth: Frugality in Truthful Mechanisms, 2003\n\n[3] Anna R. Karlin, David Kempe, Tami Tamir. Beyond VCG: Frugality of Truthful Mechanisms, 2005\n\n\n* **Regarding the coin flip between posting the predictions and using VCG**\n\nIt is indeed true that if we knew we had perfect predictions regarding the opening costs, we could even achieve solutions with optimal cost (e.g., by identifying the optimal sellers based on these predictions and posting a take-it-or-leave-it price equal to their predicted cost). However, what is very important to emphasize here is that the predictions can actually be arbitrarily inaccurate (which is a key feature of the learning-augmented model), so this would lead to *unbounded robustness, even if we did that with very small probability $p$*. \n\nFor example, consider the same simple instance that we discussed above: there are just two facilities, $A$ and $B$, where $A$ is OPT and $B$ is arbitrarily more costly than $A$. If the prediction regarding the cost of $A$ is even slightly higher than the true cost, then $A$ would reject the take-it-or-leave-it price, and the only feasible solution would be to buy the arbitrarily more expensive facility $B$. Note that this can readily be generalized to hold even if the mechanism is more conservative and posts a price (slightly) higher than the prediction, aiming to approximate OPT rather than achieve it exactly. Thus, even if we use VCG with the remaining probability of $1-p$, the expected payment can still be unbounded across the two cases, leading to unbounded robustness.\n\nIn general, it is not difficult to achieve good consistency alone (even relative to the OPT benchmark) or good robustness alone (relative to the frugal benchmark). The true challenge (which is the focus of our submission) is to simultaneously achieve good robustness and consistency, without any knowledge regarding the prediction quality.\n\n* **I am a bit confused about the explanation in lines 211-213. The authors say that scaling up under-estimated costs is to deter overbidding**\n\nWe agree that the use of the word \"overbidding\" in that context can be confusing and we would be happy to update  the wording accordingly.  Note that the threshold prices that are implied by Myerson's lemma, and which are used by all truthful mechanisms in single-parameter settings (like ours) effectively pay each bidder an amount equal to the \"best lie\" that they could report by overbidding and remaining a winner. One way to interpret this is that the mechanism pays the bidders the best amount they could earn by strategically overbidding so that they will not lie. As a result, if a mechanism chooses an allocation where some bidder has a lot of room to overbid and remain a winner, this directly implies that the amount that this bidder will have to be paid is high.\n\n\n* **Computation complexity of Auction 1 and integer program formulation**\n\nAlthough the focus of our submission is on the information limitations of truthful (learning-augmented) auctions, Auction 1 can indeed be implemented using integer programming (details provided below). We would be happy to include this in the next revision if the reviewer thinks it would add value.\n\nWe can first solve a classic Uncapacitated Facility Location (UFL) integer program using the *predicted* opening costs to determine the predicted optimal set, $\\hat{OPT}$. Once $\\hat{OPT}$ is identified, its total modified cost can be calculated directly by scaling up the true cost of any of its facilities that were under-predicted. Subsequently, a second UFL integer program is solved using the *true* opening costs, but with an added linear constraint that explicitly rules out $\\hat{OPT}$ as a feasible solution, \n\nSpecifically, if $y_l$ is the binary variable that equals 1 if facility $l$ is opened and 0 otherwise, the constraint that rules out $\\hat{OPT}$ can be written as:\n\n$\\sum_{l \\in \\hat{OPT}} (1 - y_l) + \\sum_{l \\notin \\hat{OPT}} y_l \\ge 1$\n\nThis allows the integer program to find the optimal solution amongst all feasible sets *excluding* $\\hat{OPT}$, thereby finding the best alternative outcome. The final output of the auction is then determined by comparing the modified cost of $\\hat{OPT}$ with the cost of the best alternative solution; the set with the lower cost is chosen.\n\nFinally, the threshold payment of each facility in the output set can be computed by running a UFL integer program without the facility."}, {"review_id": "3tjwkIpTVK", "reviewer": "Reviewer_cHUk", "summary": "This work examines a variant of the learning-augmented facility location auction problem, where each facility must be explicitly rented or purchased to be utilized. This introduces incentives not for the facility users—as in prior work—but also for the facility owners. The main performance metric studied is the *frugality ratio*.\n\n**Key results**:\n\n- Without predictions: The classic VCG auction is shown to achieve a frugality ratio of exactly **3**.\n\n- With predictions:\n  1. An auction that guarantees a $(1+\\varepsilon, \\max\\{5, \\frac{2}{\\varepsilon}\\})$ consistency-robustness trade-off.\n  2. A smoother alternative trade-off is also given:\n     - If $(\\eta \\le \\lambda)$, the frugality is bounded by $\\eta(1+\\lambda) + 2\\varepsilon$.\n     - Otherwise, the bound becomes $\\max $ {$\\{ 2\\lambda^4 + 3\\lambda^2, \\ 3 + \\frac{2}{\\varepsilon} \\}$ }.\n\n     where $\\varepsilon \\in (0,2]$ and $\\lambda > 1$ are tunable parameters.", "questions": "* Are there negative results about strategic UFL for the approximation ratio objective? The paper would benefit from listing impossibilities or hardness result of achieving a constant approximation ratio (with and without predictions).\n\n\n* In line 169 $U_{l,f}$ is used even though it was not defined anywhere. From the context, it seems like $U_{l,f}$ is defined to be the set of users that are connected to both facilities $l \\in OPT$ in the optimal solution and to $f \\in F$ in the frugal solution. Is this true? \n\n* You have shown a lower bound of $3$ for the tree metric for the frugal ratio. Are you aware if the results are different for a Euclidean metric space (the real line, the plane, $R^d$ Eucledian space)?\n\n* In Appendix B: line 457 states \"Figure B\" but the caption says \"Figure 2\". Please choose one of these (probably 2). Also in the same line, I think the edges should be $(l_i,u_i)$ instead of $(l,u_i)$. Line 458: \"distance of from\" - remove the \"of\". Line 459: $d(l,l_j)$ should be $d(l_i, l_j)$. The same goes for the end of the sentence.\n\n* Putting the ErrorTolerant auction in the paper body rather than the appendix (in the version where there are $\\ge$ 10 pages to the paper body rather than $9$) might be a good idea.\n\n* What happens if there's one erroneous facility cost prediction (say one predicted cost is far from the actual cost) but all the rest are not? Does the ErrorTolerant auction get any guarantee? It is fine if it is unknown to you.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n* The VCG no-predictions frugal analysis is simple (elegant), yet tight.\n\n* The paper achieves  consistency-robustness results for the settings with predictions. The Error Tolerant Scaled VCG auction allows smooth consistency-robust results with tunable parameters $\\lambda$, $\\varepsilon$.\n\nWeaknesses:\n\n* The problem is not about strategic facility location as much as it is about auctions. That is, the users are not strategic and all of their locations are known (the user locations only affect the cost of each solution). This reduces to an auction where the auction designer attempts to buy/rent the facility locations from the owners. Hence, the standard techniques of VCG and Myersons lemma apply. In terms of the combination with predictions, the techniques seem similar to the ones given for auctions with predictions by Xu and Lu 2022 - the $\\lambda$ parameter seems (roughly) to play the role of the $\\gamma$ parameter of Xu and Lu 2022 (their Theorem 2,5).\n\n* The PredictedLimits auction is really only useful if the optimal solution is exactly correct, which seems unrealistic (a problem which the \"ErrorTolerant\" auction attempts to solve).\n\n* While the last (\"ErrorTolerant\") auction is more robust to small errors than the PredictedLimits one, its performance of the Error Tolerant auction only seems to work well for very good predictions. $\\lambda$ seems to roughly be the user's estimate of $\\eta$. Say the auctioneer chooses a reasonable estimate - that the worst of all predictions is off by 50 percent ($\\lambda = 1.5$). And say that in reality $\\eta = 1.2$ (the worse prediction is off by 20 percent). Then the algorithm will get a frugality of $3$ which is what the VCG auction without predictions achieves. On the other hand, the robustness guarantees are not really small either ($16.875$ for $\\lambda = 1.5$).\nNote that also the $\\varepsilon$ parameter must be small enough to allow the $\\eta(1+\\lambda)+2\\varepsilon$ term be smaller than $0.5$ to allow any better than $3$ result in the best-case, but this results in a large robustness guarantee. Say for example, the user chooses reasonable $\\varepsilon = \\frac{1}{3}$ and $\\lambda = 1.15$. So the robustness is $9$ (high), but, the consistency is around $3$ for reasonable error of $\\eta = 1.1$, which is again what we would get with the no-predictions regime.\n**To summarize this point**: it seems hard to choose reasonable $\\lambda,\\varepsilon$ parameters that will make the given auction with predictions more attractive than the no-predictions one.", "was_revised": true, "final_justification": "In the rebuttal the authors convinced me their analysis techniques are different enough even though the VCG mechanism is used. Together with a few other smaller points addressed, I've decided to raise my score.\n\nThe main concern remaining is that it seems hard to choose reasonable $\\lambda,\\varepsilon$ parameters that will make the given auction with predictions more attractive than the no-predictions one.\n\nReading the other reviews I was not convinced there is an ethical concern. In terms of fairness, this is a different metric that is studied in algorithmic game theory, and often fairness and other metrics (such as social welfare or revenue) do not go hand in hand and it is ok. Some work consider obtaining both at the same time, but this is not the focus of this work.", "rebuttal": "Thank you for carefully reviewing our paper and providing constructive feedback. We apologize for omitting the definition of  $U_{\\ell, f}$, which is the set of users assigned to $\\ell$ in OPT and to $f$ in the frugal solution $F$. We will make sure to address this point, along with other minor issues in the next revision of the paper. We address your questions below:\n\n* **Regarding the techniques and comparison to Mechanism Design with Predictions literature**\n\nPersonalized scaling is a widely used approach for leveraging predictions, as seen in [Xu and Lu IJCAI ‘22] and many others, including [Balkanski, Gkatzelis, Tan ITCS ‘23], [Berger et al. EC ‘24], [Balkanski et al. EC ‘24], and [Christodoulou, Sgouritsa, Vlachos NeurIPS ‘24]. The key distinction between our mechanism and all these scaling-based methods is that our scaling is solution-based rather than facility-based. Specifically, we only scale the facilities in $\\hat{OPT}$ when they are part of the predicted optimal solution; all other facilities, as well as those in $\\hat{OPT}$ when considered in other solutions, are not scaled. This design avoids unnecessary distortion from inaccurate predictions. We experimented with direct scaling approaches similar to prior work but could not achieve constant robustness. Furthermore, our setting differs from that of Xu and Lu, who, to our knowledge, are the only other procurement-focused work in this line: their objective is payment only, whereas ours also includes connection cost, which can change in complex, non-smooth ways as the solution changes. This makes performance analysis significantly more challenging in our setting.\n\n[Xu and Lu IJCAI ‘22]  Chenyang Xu, Pinyan Lu.  Mechanism Design with Predictions 2022\n\n[Balkanski, Gkatzelis, Tan ITCS ‘23] Eric Balkanski, Vasilis Gkatzelis, Xizhi Tan. Strategyproof Scheduling with Predictions 2023\n\n[Berger et al. EC ‘24] Ben Berger, Michal Feldman, Vasilis Gkatzelis, Xizhi Tan. Learning-Augmented Metric Distortion via (p,q)-Veto Core 2024\n\n[Balkanski et al. EC ‘24] Eric Balkanski, Vasilis Gkatzelis, Xizhi Tan, Cherlin Zhu. Online Mechanism Design with Predictions 2024\n\n[Christodoulou, Sgouritsa, Vlachos NeurIPS ‘24] George Christodoulou, Alkmini Sgouritsa, Ioannis Vlachos. Mechanism design augmented with output advice 2024\n\n* **Regarding lower bounds**\n\nAlthough we are not aware of any general lower bounds for the frugality ratio of all truthful mechanisms, we do actually have additional lower bounds for the VCG mechanisms in interesting classes of metric spaces which we did not include in the submission. Specifically, for the line metric, a similar construction that led to the lower bound of 3 for general metrics (with twists on the edge weights) yields a lower bound of 5/3 for the VCG auction (in fact, we can also show that this bound is tight for the line). Also, for $d$-dimensional Euclidean spaces with $d \\ge 2$, a similar construction with optimized weights  provides a lower bound of $2d-\\frac{(2d-1)(4d^{2}-1)}{4d^{2}-2d+1+2\\sqrt{5d^{2}-2d}}$. This value is approximately 1.857 for $d=2$ and converges to $\\sqrt{5} \\approx 2.236$ as $d$ approaches infinity. We would be happy to include this results in the paper if the reviewer believes that they add significant value.\n\n* **What happens if there's one erroneous facility cost prediction (say one predicted cost is far from the actual cost) but all the rest are not? Does the ErrorTolerant auction get any guarantee?**\n\nThank you for raising this interesting question! We considered this question and we can show that when only one facility cost is mispredicted, the ErrorTolerant auction actually achieves much better guarantees than the general bound. In particular, if $\\eta$ is the ratio of the single misprediction, the improved frugality ratios are:\n\n* When $\\eta < \\lambda$: The ratio is at most **$\\lambda^2 + \\epsilon$**, and in most sub-cases, it improves to $\\lambda + 2\\epsilon$ or better.\n* When $\\eta \\ge \\lambda$: The ratio is bounded by **$\\max\\{5, 3 + 2/\\epsilon\\}$**, matching the robustness guarantee of the simpler Auction 1.\n\nWe provide a proof sketch for this additional result below.\n\n**Proof Sketch**\n\nLet the facility with the mispredicted cost be $f$.\n\n*Case 1:* $f$ is not in OPT and is overpredicted.\n\nSince $f$ was not in the true OPT and is now even less attractive, the predicted optimal set remains the true optimal set ($\\hat{OPT} = OPT$). The whole-solution scaling rule applies, and OPT is selected. The analysis is much stronger than the general case because every facility in the chosen solution has a perfect prediction, which tightens the bounds from Lemmas D4, D5, and D6 to give a frugality ratio of $\\lambda + \\epsilon$.\n\n*Case 2:* $f$ is not in OPT and is underpredicted.\n* If $\\hat{OPT} = OPT$: The analysis from Case 1 applies, yielding a $\\lambda + \\epsilon$ ratio.\n* If $\\hat{OPT} \\neq OPT$: This must be because the underpredicted cost made $f$ attractive enough to be included in $\\hat{OPT}$.\n    - If $\\eta \\le \\lambda$, the analysis from the paper gives a bound of $\\lambda + 2\\epsilon$.\n    - If $\\eta \\ge \\lambda$, the per-facility scaling rule is triggered. As shown in Lemma D11, this bounds the frugality ratio by $\\max\\{5, 3 + 2/\\epsilon\\}$.\n\n\n*Case 3:* $f$ is in OPT and is overpredicted.\n* If $\\hat{OPT} = OPT$: The whole-solution scaling is applied, and OPT is returned. A more careful analysis similar to Lemma D10, but accounting for only one misprediction, gives a frugal ratio of $\\lambda^2 + \\epsilon$.\n* If $\\hat{OPT} \\neq OPT$: This means f was priced out of the predicted solution. The $\\hat{OPT}$ set contains only correctly predicted facilities. Whole-solution scaling applies to $\\hat{OPT}$, and the resulting bound is $\\lambda + 2\\epsilon$.\n\n*Case 4:* $f$ is in OPT and is underpredicted.\n* If $\\hat{OPT} = OPT$:\n    - If $\\eta \\le \\lambda$, whole-solution scaling applies, and the analysis from Case 1 gives a $\\lambda + \\epsilon$ ratio.\n    - If $\\eta \\ge \\lambda$, per-facility scaling is triggered, bounding the ratio by $\\max\\{5, 3 + 2/\\epsilon\\}$.\n* If $\\hat{OPT} \\neq OPT$: The analysis is identical to the second sub-case of Case 2."}]

Author rebuttal:

Meta-review: This paper studies the strategic uncapacitated facility location problem (UFL). The first result of the paper is a tight analysis of the frugality ratio for the VCG auction. Previously, the best known upper bound for VCG was 4. This work improves it to 3, with a matching lower bound instance. The second contribution is that while most previous works focus only on worst-case guarantees, this paper designs and analyzes new auction frameworks that take into account predictions on the cost of each location. These mechanisms not only perform well when the predictions are accurate, but also retain worst-case guarantees when the predictions are wrong.

The rebuttal appears to be able to address the main issues about presentation. I also suggest the authors to add some word about the complexity of the ILP algorithm. Anyway these issue are very minor. On the other side the paper concerns a well-studied problem, and presents tight and relevant results. Hence, we here support acceptance of this paper.
Decision: Accept (poster)