Richard Cole

Parsimonious Predictions for Strategyproof Scheduling

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 determi…