Limits found on fair job scheduling methods for unrelated machines
Universally truthful mechanisms for scheduling
Computer Science and Game Theory
Summary
Scheduling many jobs on different machines that work in unrelated ways is a tricky problem. The authors studied a special kind of scheduling method that is always truthful in a randomized way, meaning machines have no incentive to lie about their speed. They found a mathematical limit showing these methods can’t schedule jobs too efficiently compared to the best possible solution. They also gave a method that nearly matches this limit, showing the bound is close to the best we can do.
What this means in practice
- •For system engineers: Determine feasibility limits when using universally truthful randomized scheduling for unrelated machines to set realistic performance targets.
- •For cloud infrastructure teams: Avoid seeking universally truthful randomized scheduling algorithms with discrete distributions that outperform the proven approximation boundaries.
A theory result. No direct application yet.
Authors
Georgios Anastasiadis, George Christodoulou, Elias Koutsoupias, Annamaria Kovacs, Conrad Schecker
Abstract
We consider universally truthful randomized mechanisms for the problem of scheduling $m$ jobs on $n$ unrelated machines. We prove a lower bound on the expected approximation ratio of every such mechanism whose probability distribution has discrete support. We show that no universally truthful randomized mechanism in this class can achieve approximation ratio smaller than $n/12 - o(n)$ with respect to the optimal makespan. We match this, up to a constant factor, by a mechanism with approximation ratio $n/2 + o(n)$.