Bayesian Truthful Mechanisms for Job Scheduling from Bi-criterion Approximation Algorithms

Constantinos Daskalakis, S. Matthew Weinberg

We provide polynomial-time approximately optimal Bayesian mechanisms for makespan minimization on unrelated machines as well as for max-min fair allocations of indivisible goods, w…