Learning-Augmented Strategyproof Mechanisms for Two-Facility Location

In learning-augmented mechanism design for two-facility location, we examine strategyproof mechanisms that, given access to predictions, elicit facility location preferences of the agents truthfully and determine two facility locations on the line that approximately minimize the utilitarian social cost, defined as the sum of agents' distances to their closest facilities. Because the predictions may be inaccurate, we evaluate the mechanisms' performance in terms of their consistency and robustness, which are the approximation guarantees on the utilitarian social cost when the prediction is correct and when the prediction is arbitrary, respectively. We consider two types of predictions, namely the locations of an optimal pair of facilities and the preferred location of each agent, and investigate the consistency and robustness of strategyproof mechanisms with access to each of the two prediction types. For deterministic strategyproof mechanisms, we characterize the optimal consistency-robustness trade-off for each prediction type and provide mechanisms that attain the trade-off exactly. Predictions of optimal facility locations cannot improve upon the optimal prediction-free approximation ratio, whereas predictions of agent preferences yields a nontrivial trade-off. For randomized mechanisms, we provide mechanisms that establish upper bounds on the consistency-robustness trade-off for each prediction type, and complement them with a uniform lower bound.