Procurement Auctions with Predictions: Improved Frugality for Facility Location

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:

• Regarding the techniques and comparison to Mechanism Design with Predictions literature

Personalized 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.

[Xu and Lu IJCAI ‘22] Chenyang Xu, Pinyan Lu. Mechanism Design with Predictions 2022

[Balkanski, Gkatzelis, Tan ITCS ‘23] Eric Balkanski, Vasilis Gkatzelis, Xizhi Tan. Strategyproof Scheduling with Predictions 2023

[Berger et al. EC ‘24] Ben Berger, Michal Feldman, Vasilis Gkatzelis, Xizhi Tan. Learning-Augmented Metric Distortion via (p,q)-Veto Core 2024

[Balkanski et al. EC ‘24] Eric Balkanski, Vasilis Gkatzelis, Xizhi Tan, Cherlin Zhu. Online Mechanism Design with Predictions 2024

[Christodoulou, Sgouritsa, Vlachos NeurIPS ‘24] George Christodoulou, Alkmini Sgouritsa, Ioannis Vlachos. Mechanism design augmented with output advice 2024

• Regarding lower bounds

Although 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.

• 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?

Thank 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:

• When $\eta < \lambda$: The ratio is at most $\lambda^2 + \epsilon$, and in most sub-cases, it improves to $\lambda + 2\epsilon$ or better.
• When $\eta \ge \lambda$: The ratio is bounded by $\max\{5, 3 + 2/\epsilon\}$, matching the robustness guarantee of the simpler Auction 1.

We provide a proof sketch for this additional result below.

Proof Sketch

Let the facility with the mispredicted cost be $f$.

Case 1: $f$ is not in OPT and is overpredicted.

Since $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$.

Case 2: $f$ is not in OPT and is underpredicted.

• If $\hat{OPT} = OPT$: The analysis from Case 1 applies, yielding a $\lambda + \epsilon$ ratio.
• If $\hat{OPT} \neq OPT$: This must be because the underpredicted cost made $f$ attractive enough to be included in $\hat{OPT}$.
  • If $\eta \le \lambda$, the analysis from the paper gives a bound of $\lambda + 2\epsilon$.
  • 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\}$.

Case 3: $f$ is in OPT and is overpredicted.

• 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$.
• 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$.

Case 4: $f$ is in OPT and is underpredicted.

• If $\hat{OPT} = OPT$:
  • If $\eta \le \lambda$, whole-solution scaling applies, and the analysis from Case 1 gives a $\lambda + \epsilon$ ratio.
  • If $\eta \ge \lambda$, per-facility scaling is triggered, bounding the ratio by $\max\{5, 3 + 2/\epsilon\}$.
• If $\hat{OPT} \neq OPT$: The analysis is identical to the second sub-case of Case 2.

I thank the authors for their response.

I trust that the minor issues—such as the definition and use of $U_{l,f}$ , which was raised by multiple reviewers—will be addressed in the revised version of the paper.

• On the techniques and comparison to the Mechanism Design with Predictions literature:

I agree that the performance analysis in your setting is more involved than in Xu and Lu 2022, and appreciate the clarification.

• On lower bounds:

Thank you for the detailed explanation. I found this aspect interesting and suggest briefly including the key insight (perhaps in 2–3 sentences) in the main text, with full details deferred to the appendix.

• On robustness to a single erroneous prediction:

I may not have phrased my question clearly. What I meant is: suppose it is promised that exactly one facility cost prediction may be arbitrarily incorrect (unbounded error), while all others are perfectly accurate. Under such an error model, can the ErrorTolerant auction still provide any meaningful performance guarantee?

Thank you for carefully reviewing our paper and providing constructive feedback. We address your questions below:

• Regarding the use of the frugal solution as the benchmark

Thank 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.

Maybe 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.

[1] Aaron Archer, Éva Tardos. Frugal path mechanisms, 2002

[2] Kunal Talwar. The Price of Truth: Frugality in Truthful Mechanisms, 2003

[3] Anna R. Karlin, David Kempe, Tami Tamir. Beyond VCG: Frugality of Truthful Mechanisms, 2005

• Regarding the coin flip between posting the predictions and using VCG

It 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$.

For 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.

In 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.

• 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

We 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.

• Computation complexity of Auction 1 and integer program formulation

Although 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.

We 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,

Specifically, 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:

$\sum_{l \in \hat{OPT}} (1 - y_l) + \sum_{l \notin \hat{OPT}} y_l \ge 1$

This 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.

Finally, the threshold payment of each facility in the output set can be computed by running a UFL integer program without the facility.

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.

• OPT, a central object in the definition of the frugality ratio, is used before being clearly defined

This 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)$.

• Key concepts, such as the VCG auction, are not properly defined when first introduced

The 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

• The notation for the auction mechanism is used inconsistently throughout the paper with varying input sets

The 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.

Does this address the reviewers’ concerns, or is there some other inconsistency that they have in mind?

• 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.

When 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.

On 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.

• Regarding computational considerations

Although 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)

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.

• Regarding the learning-augmented model and its comparison to Bayesian models

Both 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.