Strategyproof scheduling balances prediction accuracy and worst case performance
Consistency-Robustness Tradeoffs for Strategyproof Scheduling with Predictions
Computer Science and Game Theory
Summary
Scheduling jobs on machines can be tricky, especially when machines have private information about processing times. This paper studies how to design systems that make good use of predictions about those times while preventing machines from cheating. The authors propose a method called EdgeSkip that assigns jobs based on prediction-informed rules, improving on past techniques. They also show mathematical limits on how well any such method can do, balancing good results when predictions are right and safety when they aren't.
What this means in practice
- •For cloud infrastructure teams: Use EdgeSkip scheduling to assign tasks to servers when runtime information is uncertain but predictions are available, ensuring good performance even if predictions are inaccurate.
- •For manufacturing operations planners: Implement prediction-informed, strategyproof job assignments to machines to minimize total production time while handling private machine speed data and uncertain estimates.
Authors
Hau Chan, Jianan Lin, Chenhao Wang
Abstract
We study strategyproof scheduling on \(n\) unrelated machines with predictions. Each machine is controlled by an agent with privately known processing times, while the mechanism receives a public prediction of the processing-time matrix before the agents report. The objective is to minimize the makespan subject to strategyproofness. We measure performance by consistency, the approximation guarantee for correct predictions, and robustness, the worst-case guarantee for arbitrary predictions. We introduce \textsc{EdgeSkip}, a deterministic strategyproof member of the class of job-wise weighted mechanisms. Such mechanisms allocate each job independently using prediction-dependent weights. Using a polynomial-time \(2\)-approximate reference schedule computed from the prediction and a standard tradeoff parameter, \textsc{EdgeSkip} is \(4\)-consistent and \((2n-2)\)-robust, improving on the \((6,2n)\) guarantee of Balkanski, Gkatzelis, and Tan. Without computational restrictions, \textsc{EdgeSkip} with an optimal reference schedule is \(C\)-consistent and \(\max\{n,(n-1)C/(C-1)\}\)-robust for every \(C>1\). We prove a matching information-theoretic lower bound for all job-wise weighted mechanisms, thereby determining the exact consistency--robustness tradeoff for this class. For arbitrary deterministic strategyproof mechanisms, we establish the robustness lower bound \(\max\{n,C/(C-1)\}\) for every \(C>1\). We also study an error-tolerant variant and improve upon prior guarantees. Experiments demonstrate that our mechanisms achieve good empirical performance.