Randomization limits truthful scheduling accuracy on unrelated machines

Tight bounds for fractional and randomized truthful scheduling

Computer Science and Game Theory

Summary

The paper looks at how well we can schedule tasks fairly and truthfully among different machines that all work differently. It shows that even if we allow random methods and only ask for truthfulness on average, we cannot do much better than a certain approximation ratio. Specifically, the best possible truthful scheduling that splits tasks fractionally has a known lower bound, and the authors prove it cannot be improved. They also provide a method that nearly matches this limit, showing random methods only improve the approximation by about twice compared to deterministic methods.

What this means in practice

  • For distributed systems engineers: Design scheduling strategies for diverse machines knowing randomization only halves the deterministic accuracy barrier with truthfulness constraints.
  • For cloud infrastructure managers: Set expectations on task allocation efficiency when enforcing truthful reporting from autonomous resource providers in cloud environments.

A theory result. No direct application yet.

Authors

Georgios Anastasiadis, George Christodoulou, Elias Koutsoupias, Annamaria Kovacs, Conrad Schecker

Abstract

We resolve one of the longest-standing open problems in algorithmic mechanism design by showing that randomization cannot yield a sublinear approximation for truthful scheduling on unrelated machines, even when truthfulness is required only in expectation. Our main technical result concerns fractional scheduling, where tasks may be split among machines. We prove that every deterministic truthful fractional mechanism on $n$ unrelated machines has worst-case approximation ratio at least $(n+1)/2$, even against the optimal integral makespan. This matches the known upper bound exactly and settles the optimal approximation ratio of truthful fractional scheduling. Since the expected allocations and payments of a truthful-in-expectation mechanism define a truthful fractional mechanism, the same lower bound applies to all truthful-in-expectation mechanisms and, in particular, to all universally truthful mechanisms. On the positive side, we give a universally truthful mechanism with approximation ratio $n/2+o(n)$. Together, these results establish the optimal leading constant $1/2$ for randomized truthful scheduling. Thus, randomization improves on the optimal deterministic approximation ratio by an asymptotic factor of two, and no more.