Optimal randomized scheduling bounds minimize job delays on selfish machines
Sharp Bounds for Truthful-in-Expectation Scheduling
Computer Science and Game Theory
Summary
Scheduling jobs fairly on machines controlled by people who might lie about their speeds is tough. The authors studied ways to assign jobs and pay these people so that no one gains by cheating, even on average. They found the best possible method to keep the maximum time a job takes pretty low when random choices are allowed. Their method works well for any number of machines, with exact results for small numbers and a simple formula for bigger groups.
What this means in practice
- •For cloud infrastructure teams: Schedule computing tasks fairly across independent servers whose speeds vary and are privately known, ensuring truthful reporting without increasing job completion time unpredictably.
- •For logistics coordinators: Assign delivery tasks to agents who may misreport their capabilities while minimizing maximum delivery time using guaranteed randomized scheduling.
A theory result. No direct application yet.
Authors
Yunpeng Li
Abstract
We study randomized mechanisms for scheduling indivisible jobs on $n$ unrelated machines. Each machine is controlled by a selfish agent who privately knows its processing time for each job. A mechanism assigns every job to a machine and makes payments. We require truthfulness in expectation: no agent can increase its expected payment minus its expected processing cost by misreporting, regardless of the other agents' reports. The makespan is the maximum total processing time assigned to a machine; the objective is to minimize its expectation. We prove that the optimal approximation ratio is $(n+1)/2$ for every $n\ge7$, relative to the minimum makespan of an integral assignment. The lower bound holds for every $n$ and allows unrestricted computation and arbitrary correlations among assignments, assuming finite expected payments and a guarantee uniform over all finite job counts. The matching mechanism uses correlated rounding and runs in expected polynomial bit time on rational inputs. These guarantees hold for all finite nonnegative processing times. For two machines, we characterize the optimal approximation ratio exactly as an analytic constant, approximately $1.505995705434$, and give a mechanism attaining it. For three machines the optimal ratio is $2$. For four, five, and six machines we obtain upper bounds of $3$, $105/32$, and $29/8$, respectively, compared with the general lower bound $(n+1)/2$. The proofs for $n\ge7$ do not rely on computer-assisted certificates; the two- and three-machine results use exact rational computer-assisted certificates.