Procurement Auctions with Predictions: Improved Frugality for Facility Location
Eric Balkanski, Nicholas DeFilippis, Vasilis Gkatzelis, Xizhi Tan
We study the problem of designing procurement auctions for the strategic uncapacitated facility location problem: an agency needs to procure a set of facility locations in order to open new facilities for its customers. The owner of each location has a private cost for providing access to that facility (e.g., renting it or selling it) and needs to be compensated accordingly. The goal is to design auctions that decide where to open the facilities and how much to pay the corresponding owners, aiming to minimize the total cost, i.e., the opening cost paid to the owners and the total distance between the customers and the opened facilities. 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 owner's true opening costs. Specifically, we propose a family of learning-augmented auctions that achieve significant payment reductions, leading to much better frugality ratios, when the predictions are accurate. 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 inaccurate predictions. We then extend this result to provide a family of ``error-tolerant'' auctions that perform well even if the prediction is approximately accurate, and we provide bounds regarding their frugality ratio as a function of the prediction error.