Mechanism Design With Predictions for Obnoxious Facility Location

The theory of algorithms with predictions [1, 2, 3] is, without a doubt, one of the most exciting recent research directions in algorithmics: when supplemented by a (correct) predictor, often based on machine learning, the newly-developed algorithms are capable of outcompeting their worst-case classical counterparts. A desirable feature of such algorithms is, of course, to perform comparably to the (worst-case) algorithms when the predictors are really bad. This requirement often results [2] in tradeoffs between two measures of algorithm performance, robustness and consistency. A significant amount of subsequent research has followed, summarized by the algorithms with predictions webpage [3]. Recently, the idea of augmenting algorithms by predictions has been adapted to the game-theoretic setting of mechanism design [4, 5, 6, 7]: indeed, strategyproof mechanisms often yield solutions that are only approximately optimal [8]. On the other hand, if the designer has access to a predictor for the desired outcome it could conceivably take advantage of this information by creating mechanisms that lead to an improved approximation ratio, compared to their existing (worst-case) counterparts. Tradeoffs between robustness and consistency similar to the ones from [2] apply to this setting as well.