Parsimonious Predictions for Strategyproof Scheduling

We consider the problem of scheduling mjobs on nunrelated strategic machines to minimize the maximum load of any machine. As the machines are strategic they may misreport processing times to minimize their own load. The pioneering work of Nisan and Ronen gave an n-approximate deterministic strategyproof mechanism for this setting, and this was recently shown to be best possible by the breakthrough results of Christodoulou et al. This large approxation guarantee begs the question: how can we avoid these large worst-case results. In this work, we use the powerful framework of algorithms with (machine-learned) predictions to bypass these strong impossibility results. We show how we can predict O(m+n)values to obtain a deterministic strategyproof algorithm whose makespan is within a constant factor of the optimal makespan when the predictions are correct, and O(n) times the optimum no matter how poor the predictions are.