Parsimonious Predictions for Strategyproof Scheduling
Richard Cole, Anupam Gupta, Pranav Jangir
We consider the problem of scheduling $m$ jobs on $n$ unrelated  strategic machines to minimize the maximum load of any machine, but  the machines are strategic and 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.