MAC Advice for facility location mechanism design

Algorithms with predictions are gaining traction across various domains, as a way to surpass traditional worst-case bounds through (machine-learned) advice. We study the canonical problem of k -facility location mechanism design,where the n agents are strategic and might misreport their locations. We receive a prediction for each agent's location, and these predictions are crucially allowed to be only "mostly" and "approximately" correct (MAC for short): a \delta -fraction of the predicted locations are allowed to be arbitrarily incorrect, and the remainder of the predictions are required to be correct up to an \varepsilon -error. Moreover, we make no assumption on the independence of the errors.Can such "flawed" predictions allow us to beat the current best bounds for strategyprooffacility location?We show how natural robustness of the 1 -median (also known as the geometric median) of a set of points leads to an algorithm for single-facility location with MAC predictions. We extend our results to a natural "balanced" variant of the k -facility case, and show that without balancedness, robustness completely breaks down even for k 2 facilities on a line. As our main result, for this "unbalanced" setting we devise a truthful random mechanism, which outperforms the best known mechanism (with no predictions) by Lu et al. [2010].